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

Question

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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