Генетический алгоритм для Tic-Tac-Toe

Поэтому мне была назначена проблема написания 5x5x5 tic-tac-toe-плеера с использованием генетического алгоритма. Мой подход состоял в том, чтобы начать с 3x3, получить эту работу, а затем расширить до 5x5, а затем до 5x5x5.

Как это работает:

  • Имитировать целую кучу игр, и в каждом повороте каждой игры искать в соответствующей таблице (таблица X или таблица O, реализованная в виде С++ stdlib-карт) для ответа. Если платы там не было, добавьте плату к столу. В противном случае сделайте произвольный ответ.

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

  • Используя свои выигрыши/потери для оценки работоспособности, я сохраняю определенный процент от лучших, и они продвигаются дальше. Прополощите и повторите для X поколений, и появится оптимальный игрок.

Для 3х3, дисконтирующих плат, которые были отражениями/вращениями других плат, и доски, на которых перемещение либо "выигрывает", либо "блокирует победу", общее количество плат, с которыми я столкнулся, было либо 53, либо 38, в зависимости от того, будете ли вы идти первым или вторым. Фантастика! Оптимальный игрок был создан менее чем через час. Очень круто!

Используя ту же стратегию для 5x5, я знал, что размер таблицы будет увеличиваться, но не понял, что это будет так резко увеличиваться. Даже при дисконтировании поворотов/отражений и обязательных ходов моя таблица составляет ~ 3,6 млн. Записей, без конца.

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

Каков реалистичный способ этого? Я собираюсь застрять с использованием функций платы? Цель состоит в том, чтобы жестко закодировать как можно меньше функциональности игры.

Я занимаюсь исследованиями, но все, что я читаю, приводит к минимуму/максимальному сокращению A-B как единственного жизнеспособного варианта. Я, конечно, могу так поступить, но GA действительно классный, мой нынешний метод немного превосходит реальность здесь.

Проблема EDIT была решена в значительной степени:

Используя функцию подобия, которая сочетает в себе отдачу от открытых пространств, возможные условия выигрыша и несколько других мер привели таблицу к вполне управляемым 2500 возможностям, которые std::map обрабатывает за долю секунды.

Ответы

Ответ 1

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

Изменить: Я не думал о том, чтобы начать с конкретной доски, начиная с пустой доски. Очевидно, что на плате 3x3, которые перемещают последовательности, начиная с (1,1), лучше всего подходят для X. Важно не то, чтобы на финальной доске X был посередине, а X сначала был помещен в середину. Если есть один или несколько лучших первых шагов для X, возможно, также есть лучший второй, третий или четвертый ход для X? После нескольких раундов тестирования на пригодность и рекомбинации мы обнаружим, что X-секундное перемещение обычно одно и то же или представляет собой один из небольших значений? А как насчет третьего хода?

Это не минимакс, потому что вы не ищете лучших ходов по одному на основе предыдущего состояния доски, вы ищете все лучшие ходы одновременно, надеясь сблизиться на стратегии выигрыша.

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