Вот многие считают, на мой взгляд, необоснованно, что машина, созданная человеком, завсегда будет дурнее создателя. По моему опыту, верно обратное — созданный человеком искуственный интеллект (оговорюсь сразу, для данной конкретной определённой задачи — т.н. “слабый” ИИ) работает намного мощнее, чем способен человек, его написавший. Во всяком случае, мои крестики-нолики легко меня громят, если только я не наморщу ум — тогда получается ничья. Да и Deep Blue, который обыграл Каспарова, писали хоть и люди, заведомо знакомые с шахматами, но всё же не игроки выше уровня великого шахматиста.
Поэтому, так сказать, в дальней перспективе я вижу, что человек сможет создать сильный искуственный интеллект, который превозойдёт его самого. Вопрос, какая роль будет отведена человеку в данном мире — ОЧЕНЬ интересный, и по-моему, однозначного ответа нет ни у кого. Элон Маск, например, считает, что человечество будет порабощено сильным ИИ. Создатели сериала “Person of Interest” думают, что человек будет существовать с сильным ИИ симбиотически — т.е. всё управление и развитие человечества возьмёт на себя ИИ, люди будут абсолютно счастливы, а в обмен на это будут этот самый ИИ обслуживать, например, батарейки вовремя менять 🙂 Ну, а создатели сериала “Westworld” отводят ИИ роль рабов, прислужников человека. Какой из этих ответов верный — неизвестно, но не исключено, что ответ мы узнаем в течение нашей жизни.
Однако хватит философии.
Вся задача написания игры, способной обыграть создателя, в итоге таки свелась к написанию алгоритма минимакс. В этом была вся загвоздка. Попытаюсь объяснить попроще, как он работает.
Для каждого потенциального хода нужно рассчитать некий коэффициент. Отрицательный коэффициент будет означать, что выиграл противник, положительный — что выиграла программа. Я начал с того, что присвоил немедленному выигрышу значение 1.0, проигрышу -1.0, а ничьей 0. Далее, алгоритм помечает этот ход как корневой узел, и строит исходящее из него дерево потенциальных ходов противника, а потом снова своих, вызывая сам себя рекурсивно (а как же ещё, если речь идёт о деревьях произвольной высоты). Раньше или позже, алгоритм доберётся до листьев игрового дерева, и будет возвращать +1.0, -1.0 или 0. Остаётся только сложить все значения, полученные из листьев игрового дерева, вместе, и записать их в массив, из которого выбрать максимальное значение, присвоенное какому-либо ходу.
Но этого оказалось недостаточно. Написанная с таким алгоритмом программа таки играла, но на среднем уровне. У неё можно было выиграть. Шишечкой на этой ёлочке оказалось введение дополнительной поправки, на которую умножался коэффициент, полученный из листьев игрового дерева. По простой причине — немедленный выигрыш или проигрыш, прямо со следующего хода, должен учитываться значительно больше, чем выигрыш или проигрыш после нескольких ходов. Я начал с того, что коэффициенты, полученные из каждого более нижнего уровня игрового дерева, стал делить на 2. Но и этого оказалось мало, хотя и заметно улучшило работу алгоритма. Магическим числом оказалось 4. Т.е. немедленный выигрыш на первом ходе учитывается как +1.0, выигрыш на втором — как +0.25, на третьем — +0.0625 и так далее. Вот тут уже выиграть против программы не оказалось никаких шансов. В лучшем случае я могу сыграть вничью.
Смеха ради, запустил программу играть против гугловских крестиков-ноликов на уровне сложности impossible. Все игры так же были сведены к ничьей. Урррря!!
Надо будет написать программу, играющую в преферанс. А то комп меня легко дрючит, особенно на распасах (я вообще не очень играю ни в преферанс, ни в шахматы, ни в шашки, хотя почему-то неплохо — в поддавки).