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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

Об этом можно многое сказать, но я просто дам здесь один совет, который уменьшит ваш размер дерева: Мэтт Гинзберг разработал метод под названием Partition Search, который делает сокращения эквивалентности на плате. Это хорошо работало в Бридже, и он использует tic-tac-toe в качестве примера.

Ответ 6

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

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

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

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

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

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

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