Алгоритм для реализации игры tic tac toe?

Question

Можно создать дубликат:
What Algorithm for a Tic-Tac-Toe Game Can I Use To Determine the “Best Move” for the AI?

Я уже создал крестики нолики игра для 2 игроков т.е. играющих друг против друга. Теперь я планировал реализовать ту же игру, но для игры против компьютера. Так может ли кто-нибудь предложить какой-нибудь хороший алгоритм или идею реализовать это?

Answer 1

Поскольку игра настолько проста, вы можете создать дерево поиска. Это дерево, альтернативы между «вашим движением» и «вражеским движением». Враг всегда выбирает то, что лучше для них, и вы всегда выбираете то, что лучше для вас. Для каждой позиции доски оценивайте ее как «WINS»/«LOSE»/«TIE», если оптимальная игра приводит к выигрышу/проигрышу/привязке, соответственно. Выполните поиск по глубине (или любой поиск) и выберите ветку. Это в основном то, как работают сложные шахматные программы, которые избивают гроссмейстеров (хотя они сильно оптимизированы и работают на отличном оборудовании параллельно). Это называется minimax algorithm.

В качестве альтернативы вы можете запрограммировать все оптимальные ходы под рукой (с помощью процедуры, которая сравнивает ее с известными ходами, вращая и переворачивая плату). Есть только 500-ий возможности.

Однако, поскольку tic-tac-toe - решаемая игра, это было бы довольно скучно. Компьютер всегда будет связывать вас, если компьютер играет оптимально. Поскольку tic-tac-toe только бросает вызов 5-летним подросткам, вы можете рассмотреть аудиторию своей игры: может быть разумно, чтобы компьютер сделал случайный не проигрывающий ход. Тогда у человека, по крайней мере, есть шанс.

Answer 2

Поисковое дерево, как и ранее предлагаемое ninjagecko, было бы простым и оптимальным для кодирования.

Но так же, как создание дерева поиска более интересно, чем кодирование всех оптимальных ходов вручную, я думаю, было бы еще более интересно попробовать подход к компьютерному обучению.

Было бы здорово сделать программу, которая использовала, например, reinforcement learning.