nlothik (nlothik) wrote,
nlothik
nlothik

Categories:

Доломал минимакс

Вот многие считают, на мой взгляд, необоснованно, что машина, созданная человеком, завсегда будет дурнее создателя. По моему опыту, верно обратное — созданный человеком искуственный интеллект (оговорюсь сразу, для данной конкретной определённой задачи — т.н. “слабый” ИИ) работает намного мощнее, чем способен человек, его написавший. Во всяком случае, мои крестики-нолики легко меня громят, если только я не наморщу ум — тогда получается ничья. Да и 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. Все игры так же были сведены к ничьей. Урррря!!

Надо будет написать программу, играющую в преферанс. А то комп меня легко дрючит, особенно на распасах (я вообще не очень играю ни в преферанс, ни в шахматы, ни в шашки, хотя почему-то неплохо — в поддавки).

Mirrored from Лабораторный Журнал №6.

Tags: программирование
Subscribe

  • Политический кофе

    Вот есть такое распространённое и распропагандированное (вполне известно кем) понимание капитализма как системы, построенной на жажде наживы и…

  • Почти всё

    Так как одиннадцатая винда фичами пока не радует, попробовал заменить на рабочем компе всё на Убунту 20.04 И оно, знаете, практически взлетело.…

  • Про одиннадцатую винду

    Что-то не хочется мне на неё обновляться. Главная проблема в новой системе виртуализированной безопасности (virtualization-based security, VBS).…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments