Как реализовать минимакс в Tictactoe

Question

Я прочитал этот ответ, и он просто смутил меня: TicTacToe AI принимает неправильные решения

Может ли кто-нибудь помочь мне понять, как я могу применить это к Tictactoe?

1. Как бы я "пробирался сквозь дерево?"
2. Как мне даже создать дерево ходов?

Примечание. В настоящее время у меня есть класс доски, в котором хранится информация об игре (например, завершена ли игра с текущими ходами? Есть ли победитель? И т. Д.). Каждый ход на текущей доске сохраняется как 1 - 9. (сверху вниз слева направо в строках). Я могу с легкостью делать копии текущего состояния доски. Я могу вернуть список текущих ходов для «X» и «O», а также доступных ходов с доски.

Answer 1

Крестики-нолики: основы игрового дерева
Категория: Теория игр
Опубликовано: 30 июля 2008 г., 11:38, Марком К. Чу-Кэрроллом

Изображение в значительной степени говорит само за себя, но вот ссылка на сообщение в блоге: http://scienceblogs.com/goodmath/2008/07/30/solving-tictactoe-game-tree-ba/

Answer 2

Я могу ответить на ваш вопрос «2», и, надеюсь, это поможет вам разобраться с вопросом «1»:

Каждый узел в дереве представляет текущее состояние игры после некоторого количества ходов. Таким образом, корень дерева представляет игру в начале (то есть, пока не сыграно ни одной фигуры). У него девять детей (по одному на каждый возможный первый ход). У каждого ребенка по очереди 8 детей (по одному на каждый второй возможный ход). И так до тех пор, пока вы не достигнете точки, где игра была выиграна или сыграна вничью. Это листовые узлы.