Чтобы сделать традиционную игру Tic Tac Toe непобедимой, необходимо создать алгоритм, который может рассчитать все возможные движения, доступные для компьютера, и может использовать его для определения наилучшего возможного движения.
Введение
Чтобы решить игры с использованием ИИ, мы представим концепцию игрового дерева, за которым следует алгоритм Minimax. Этот алгоритм видит несколько шагов впереди и ставит себя на место своего противника. Он продолжает играть впереди, пока не достигнет терминальной договоренности Совета (терминального состояния), что приводит к связке, победе или проигрыше. Оказавшись в терминальном состоянии, ИИ назначит произвольную положительную оценку (+10) для победы, отрицательный результат (-10) для потери или нейтральный счет (0) для связи.
В то же время алгоритм оценивает ходы, которые приводят к терминалу, на основе очереди игроков. Он выберет шаг с максимальной оценкой, когда настало время AI, и выберет ход с минимальным результатом, когда настало время человека. Используя эту стратегию, Minimax избегает проигрыша человеческому игроку.
Что такое минимальный?
Минимакс (Иногда Minmax, MM или Saddle Point) – это правило принятия решений, используемое в искусственном интеллекте, теории решений, теории игр, статистике и философии для минимизации возможной потери для сценария наихудшего случая (максимальная потеря). При работе с прибылью это называется «Максимин» – чтобы максимизировать минимальное усиление Анкет Первоначально сформулирован для теории игр с нулевой и игровой игрой (один игрок выигрывает (+10), а другой игрок проигрывает (-10) или оба из всех, кто не выиграет (0)), охватывая оба случая, когда игроки принимают альтернативные ходы и те, которые Там, где они делают одновременные шаги, это также распространялось на более сложные игры и на общее принятие решений в присутствии неопределенности.
Как это работает?
Чтобы проверить, лучше ли текущий ход лучше, чем лучший шаг, мы принимаем помощь функции Minimax, которая будет рассмотреть все возможные способы, которыми игра может пойти, и возвращает наилучшее значение для этого хода, предполагая, что противник также играет оптимально, пока не найдет Терминальное состояние (выигрыш, рисует или проигрывает).
Игровое дерево
Изображение:
Объяснение:
Это изображение изображает все возможные пути, которые игра может пройти из штата корневой доски. Его часто называют деревом игры. 3 возможных сценария в приведенном выше примере:
- Левый ход: если X играет [2,0]. Затем o будет играть [2,1] и выиграть игру. Значение этого хода -10
- Средний ход: если X играет [2,1]. Затем o будет играть [2,2], что рисует игру. Значение этого хода равен 0
- Правильный ход: если X играет [2,2]. Тогда он выиграет игру. Значение этого хода составляет +10;
Помните, что, несмотря на то, что X имеет возможность выиграть, если он играет в среднем ходе, O никогда не позволит этому случиться, и вместо этого решит рисовать. Поэтому лучший выбор для X – играть [2,2], что гарантирует для него победу.
Ссылка GitHub для исходного кода:
dhruv/tic-tac-toe
🎃 Непревзойденная игра Tic Tac Toe с использованием алгоритма Minimax.
Использованная литература:
Оригинал: “https://dev.to/dhhruv/tic-tac-toe-you-can-t-beat-56oo”