TicTacToe стратегическое сокращение
Я решил записать небольшую программу, которая решает TicTacToe для испытания эффекта некоторых методов сокращения на тривиальной игре. Полное игровое дерево использование минимакса для решения его только заканчивается с 549 946 возможными играми. С сокращением альфы - беты количество состояний, требуемых оценить, было сокращено к 18 297. Затем я применил таблицу перемещения, которая понижает число до 2 592. Теперь я хочу видеть, как низко, что число может пойти.
Следующее улучшение, которое я хочу применить, является стратегическим сокращением. Основная идея состоит в том, чтобы объединить состояния, которые имеют эквивалентное стратегическое значение. Например, на первом шаге, если X игр сначала, нет ничего стратегически различного (принятие Вашего противника играет оптимально) о выборе одного угла вместо другого. В той же ситуации то же верно для центра стен платы, и центр является также значительным. Путем сокращения до значительных состояний только, Вы заканчиваете только с 3 состояниями для оценки на первом шаге вместо 9. Эта техника должна быть очень полезной, так как она сокращает состояния около вершины игрового дерева. Эта идея прибыла из метода GameShrink, созданного группой в CMU, только я стараюсь не писать общую форму и просто делать то, что необходимо для применения техники к TicTacToe.
Для достижения этого я изменил свою хеш-функцию (для таблицы перемещения), чтобы перечислить все стратегически эквивалентные положения (использующий вращение и зеркально отражающий функции), и только возвратить самое низкое из значений для каждой платы. К сожалению, теперь моя программа думает X, может вызвать победу в 5 перемещениях от пустой платы при движении сначала. После длинного сеанса отладки это стало очевидным для меня, программа всегда возвращала перемещение для самого низкого стратегически значительного перемещения (я храню последнее перемещение в таблице перемещения как часть моего состояния). Существует ли лучший путь, которым я могу пойти о добавлении этой опции или простого метода для определения корректного перемещения, применимого к текущей ситуации с тем, что я уже сделал?
5 ответов
Вы на правильном пути, когда думаете об отражениях и поворотах. Однако вы применяете его не в том месте. Не добавляйте его в таблицу транспонирования или код таблицы транспонирования - поместите его в функцию генерации перемещения, чтобы с самого начала исключить логически эквивалентные состояния.
Делайте вашу таблицу транспонирования и связанный с ней код как можно меньше и эффективнее.
Вам нужно вернуть (обратную) транспозицию вместе с позицией наименьшего значения. Тогда вы сможете применить обратную транспозицию к последующим ходам, чтобы получить следующую позицию.
Почему вам нужно сделать таблицу транспонирования изменяемой? Лучший ход не зависит от истории.
Мне кажется, что вы используете слишком большой молоток, чтобы решить эту проблему. Каждое из 9 мест может иметь только одно из двух ярлыков: X или O или пустое. Тогда у вас будет не более 3 ^ 9 = 19 683 уникальных доски. Поскольку для каждой платы есть 3 эквивалентных отражения, у вас действительно есть только 3 ^ 9/4 ~ 5k досок. Вы можете уменьшить это, выбрасывая недействительные доски (если на них есть строка из X И строка из O одновременно).
Таким образом, при компактном представлении вам потребуется менее 10 КБ памяти для перечисления всего. Я бы оценил и сохранил весь график игры в памяти.
Мы можем пометить каждую доску ее истинным минимаксным значением, вычисляя минимаксные значения снизу вверх, а не сверху вниз (как в вашем методе поиска по дереву). Вот общий план: мы вычисляем минимаксные значения для всех уникальных досок и сначала помечаем их все до начала игры. Чтобы сделать минимаксный ход, вы просто смотрите на доски, следующие за вашим текущим состоянием, и выбираете ход с наилучшим минимаксным значением.
Вот как выполнить начальную маркировку. Сгенерируйте все действительные уникальные доски, отбрасывая отражения.Теперь мы начинаем маркировать доски с наибольшим количеством ходов (9) и переходить к доскам с наименьшим количеством ходов (0). Пометьте все доски эндшпиля победами, поражениями и ничьей. Для любых досок, не относящихся к финалу, на которых ход X теперь: 1) если существует следующая доска, которая является выигрышной для X, пометьте эту доску как выигрыш; 2) если на последующих досках нет выигрышей, но есть ничья, то пометьте эту доску как ничья; 3) если на последующих досках нет ни побед, ни ничьих, пометьте эту доску как проигрыш. Логика аналогична при разметке хода О.
Что касается реализации, из-за небольшого размера пространства состояний я бы закодировал логику «если существует» просто как простой цикл по всем 5К состояниям. Но если вы действительно хотите настроить это для асимптотического времени работы, вы должны построить ориентированный граф, показывающий, какие состояния платы приводят к каким другим состояниям платы, и выполнить минимаксную разметку, перемещаясь в обратном направлении краев. .
Об этом можно много говорить, но я просто дам один совет, который уменьшит размер вашего дерева: Мэтт Гинсберг разработал метод под названием Partition Search, который выполняет сокращение эквивалентности на доске. Он хорошо работает в бридже, а в качестве примера он использует крестики-нолики.