Немного предыстории: в качестве способа изучения многоузловых деревьев в C ++ я решил сгенерировать все возможные платы TicTacToe и сохранить их в дереве таким образом, чтобы ветви, начинающиеся в узле, были всеми досками, которые могут следовать из этого узла, и потомками узел - это доски, которые следуют за один ход. После этого я подумал, что было бы интересно написать ИИ для игры в TicTacToe, используя это дерево в качестве дерева решений.

ТТТ - это решаемая проблема, когда идеальный игрок никогда не проиграет, поэтому мне казалось, что ИИ легко запрограммировать, когда я впервые пробовал ИИ.

Теперь, когда я впервые реализовал ИИ, я вернулся и добавил два поля к каждому узлу при генерации: количество раз Х выиграет & количество раз O победит во всех дочерних элементах ниже этого узла. Я подумал, что лучшим решением было бы просто выбрать свой ИИ на каждом ходу и пойти вниз по поддереву, где он побеждает чаще всего. Затем я обнаружил, что, хотя в большинстве случаев это звучит идеально, я нашел способы, с помощью которых я мог бы победить. Это не было«проблема с моим кодом, просто проблема с тем, как я его выбрал»с пути.

Затем я решил выбрать дерево с максимальными выигрышами для компьютера или максимальными потерями для человека, в зависимости от того, что больше. Это заставило его выступить ЛУЧШЕ, но все же не идеально. Я все еще мог победить это.

Итак, у меня есть две идеи, и ям в надежде на вклад, по которому лучше:

1) Вместо того, чтобы максимизировать выигрыши или потери, я мог бы назначить значения 1 для победы, 0 для ничьи и -1 для проигрыша. Тогда выбор дерева с наибольшим значением будет лучшим ходом, потому что следующий узел можетэто будет движение, которое приведет к потере. Это'Легко изменить поколение плат, но оно сохраняет то же пространство поиска и использование памяти. Или же...

2) Во время генерации доски, если есть доска, в которой Х или О выиграют в следующем ходу, будет сгенерирован только тот ребенок, который предотвращает эту победу. Другие дочерние узлы не будут рассматриваться, и после этого генерация продолжится как обычно. Это сокращает размер дерева, но тогда мне нужно реализовать алгоритм, чтобы определить, есть ли выигрыш за один ход, и я думаю, что это можно сделать только за линейное время (я думаю, что создание доски намного медленнее?)

Что лучше, или есть еще лучшее решение?