Стратегическое сокращение TicTacToe

Question

Я решил написать небольшую программу, которая решает TicTacToe, чтобы опробовать влияние некоторых методов обрезки на тривиальную игру. Полное дерево игр, использующее минимакс, чтобы решить его, заканчивается 549 946 возможными играми. С обрезкой альфа-бета количество состояний, необходимых для оценки, было сокращено до 18 297. Затем я применил таблицу транспонирования, которая снизила число до 2592. Теперь я хочу посмотреть, как низко это число может пойти.

Следующее улучшение, которое я хочу применить, - это стратегическое сокращение. Основная идея состоит в том, чтобы объединить государства, которые имеют эквивалентную стратегическую ценность. Например, на первом ходу, если Х играет первым, нет ничего стратегически отличного (если ваш оппонент играет оптимально) в выборе одного угла вместо другого. В той же ситуации то же самое верно и для центра стен доски, и центр также имеет значение. Сводя только к значимым состояниям, вы получите только 3 состояния для оценки на первом ходу вместо 9. Этот метод должен быть очень полезным, так как он сокращает состояния в верхней части дерева игры. Эта идея возникла из метода GameShrink, созданного группой в CMU, только я пытаюсь избежать написания общей формы и просто делаю то, что необходимо для применения этой техники к TicTacToe.

Чтобы добиться этого, я изменил свою хеш-функцию (для таблицы транспонирования), чтобы перечислять все стратегически эквивалентные позиции (используя функции поворота и переворачивания) и возвращать только самые низкие значения для каждой доски. К сожалению, теперь моя программа думает, что Х может заставить выиграть в 5 ходов с пустой доски, когда идет первым. После долгого сеанса отладки мне стало очевидно, что программа всегда возвращала ход за наименьшее стратегически значимое движение (я сохраняю последний ход в таблице транспонирования как часть моего состояния). Есть ли лучший способ, как я могу добавить эту функцию, или простой метод определения правильного хода, применимого к текущей ситуации с тем, что я уже сделал?

Answer 1

У меня такое чувство, что вы используете слишком большой молот, чтобы решить эту проблему. Каждое из 9 мест может иметь только одну из двух меток: X или O или пусто. Тогда у вас не более 3 ^ 9 = 19 683 уникальных досок. Поскольку для каждой доски есть 3 эквивалентных отражения, у вас действительно есть только 3 ^ 9/4 ~ 5k досок. Вы можете уменьшить это, выбрасывая недействительные доски (если у них есть строка X и строка O одновременно).

Таким образом, при компактном представлении вам потребуется менее 10 КБ памяти для перечисления всего. Я бы оценил и сохранил весь игровой граф в памяти.

Мы можем маркировать каждую отдельную доску ее истинным минимаксным значением, вычисляя минимаксные значения снизу вверх, а не сверху вниз (как в вашем методе поиска по дереву). Вот общий план: мы вычисляем минимаксные значения для всех уникальных досок и сначала помечаем их все, прежде чем игра начнется. Чтобы сделать минимаксное движение, вы просто смотрите на доски, следующие за вашим текущим состоянием, и выбираете движение с лучшим минимаксным значением.

Вот как выполнить начальную маркировку. Генерируйте все действительные уникальные доски, выбрасывая отражения. Теперь мы начинаем маркировать доски с наибольшим количеством ходов (9) и переходим к доскам с наименьшим количеством ходов (0). Маркируйте любые доски эндшпиля победами, проигрышами и ничьями. Для любых неигровых досок, на которых настанет ход Х: 1) если существует доска-преемник, которая является победой для Х, обозначьте эту доску победой; 2) если на досках-преемниках нет выигрышей, но есть ничья, то обозначьте эту доску как ничью; 3) если на досках-преемниках нет побед и ничьих, тогда эта доска считается проигрышной. Логика схожа при маркировке для поворота О.

Что касается реализации, из-за небольшого размера пространства состояний я бы закодировал логику «если есть» просто как цикл по всем 5k-состояниям. Но если вы действительно хотите настроить это для асимптотического времени выполнения, вы должны построить ориентированный граф, из которых состояния платы приводят к тому, какие другие состояния платы, и выполнять минимаксную маркировку, перемещаясь в обратном направлении краев. .

Answer 2

Вы на правильном пути, когда думаете о отражениях и поворотах.Однако вы применяете это не в том месте.Не добавляйте его в таблицу транспонирования или код таблицы транспонирования - поместите его в функцию генерации перемещения, чтобы исключить логически эквивалентные состояния с самого начала.

Сохраняйте таблицу переноса и связанный с ней код маленькими максимально эффективно.

Answer 3

Вам необходимо вернуть (обратное) транспонирование вместе с наименьшим значением позиции. Таким образом, вы можете применить обратную транспозицию к предполагаемым ходам, чтобы получить следующую позицию.

Answer 4

Вы можете попытаться решить крестики-нолики, используя симуляцию Монте-Карло. Если один (или оба) из игроков является машинным игроком, он может просто использовать следующие шаги (эта идея взята из одного из мини-проектов в coursera course Принципы вычислений 1 , который является частью Основ специализации вычислительной техники, преподаваемой в университете RICE.):

Каждый игрок машины должен использовать симуляцию Монте-Карло, чтобы выбрать следующий ход из заданной позиции на доске TicTacToe. Основная идея состоит в том, чтобы сыграть в набор игр со случайными ходами, начиная с позиции, а затем использовать результаты этих игр, чтобы вычислить хороший ход.

Когда игрок с точным автоматом выигрывает одну из этих случайных игр, он хочет отдать предпочтение клеткам, в которых он играл (в надежде выбрать выигрышный ход), и избегать площадок, на которых играл противник. И наоборот, когда он проигрывает одну из этих случайных игр, он хочет отдать предпочтение клеткам, в которых играл противник (чтобы заблокировать своего противника), и избегать площадок, в которых он играл.

Короче говоря, квадраты, в которых выигравший игрок играл в этих случайных играх, должны иметь преимущество перед клетками, в которых играл проигравший игрок. Оба игрока в этом случае будут игроками машины.

Следующая анимация показывает игру между двумя игроками машины (которая завершилась ничьей ) с использованием 10 испытаний MC в каждом состоянии доски для определения следующего хода.

Он показывает, как каждый из игроков машины учится играть в игру, просто используя симуляцию Монте-Карло с 10 испытаниями (небольшое количество испытаний) в каждом состоянии доски, оценки показаны в правом нижнем углу каждого квадрата сетки используются каждым из игроков на их соответствующих ходах, чтобы выбрать свой следующий ход (более яркие ячейки представляют лучшие ходы для текущего игрока, согласно результатам моделирования).

Вот мой блог об этом для более подробной информации.

Answer 5

Об этом можно сказать много, но здесь я приведу лишь один совет, который уменьшит размер вашего дерева: Мэтт Гинсберг разработал метод под названием Поиск разделов , который уменьшает эквивалентность на доске,Это хорошо сработало в Bridge, и он использует крестики-нолики в качестве примера.

Answer 6

Зачем вам нужно сделать таблицу транспонирования изменчивой? Лучший ход не зависит от истории.