Генетический алгоритм для крестиков-ноликов
Итак, мне была поставлена задача написать игрока в крестики-нолики 5x5x5 с использованием генетического алгоритма. Мой подход заключался в том, чтобы начать с 3x3, заставить это работать, а затем расширить до 5x5, а затем до 5x5x5.
Это работает следующим образом:
Моделируйте целую группу игр, и на каждом этапе каждой игры ищите ответ в соответствующей таблице (таблица X или таблица O, реализованная как сопоставление stdlib c ++). Если доски не было, добавьте ее в стол. В противном случае сделайте случайный ответ.
После того, как у меня есть полные столы, я инициализирую группу игроков (каждый с копией таблицы доски, инициализированной случайными ответами) и позволяю им играть друг против друга.
- Использование их выигрышей / проигрышей для оценки пригодности , Я оставляю себе определенный процент лучших, и они уходят. Промойте и повторите в течение X поколений, и должен появиться оптимальный игрок.
Для 3x3, без учета досок, которые были отражениями / вращениями других досок, и досок, где ходом является либо «взять выигрыш», либо «заблокировать выигрыш», общее количество досок, с которыми я столкнулся бы, составляло 53 или 38, в зависимости от того, идете вы первым или вторым. Фантастический! Оптимальный игрок был создан менее чем за час. Очень круто!
Используя ту же стратегию для 5x5, я знал, что размер стола увеличится, но не понимал, что он вырастет так резко. Даже без учета поворотов / отражений и обязательных ходов моя таблица составляет ~ 3,6 миллиона записей, и конца этому не видно.
Ладно, это явно не сработает, мне нужен новый план. Что, если я перечисляю не все платы, а только несколько плат. Ну вроде и это не сработает, потому что, если у каждого игрока есть лишь небольшая часть возможных досок, которые они могут увидеть, то они будут делать много случайных ходов, явно движущихся в направлении, противоположном оптимальности.
Каков реальный способ сделать это? Могу ли я застрять в использовании функций платы? Цель состоит в том, чтобы жестко запрограммировать как можно меньше функциональных возможностей игры.
Я проводил исследования, но все, что я читаю, приводит к минимальному / максимальному значению с сокращением AB в качестве единственного жизнеспособного варианта. Я, конечно, могу сделать это таким образом, но GA действительно крутой, мой текущий метод здесь просто немного выходит за рамки реальности.
EDIT Проблема в значительной степени решена:
Использование функции подобия, которая объединяет хамминг расстояние до открытых пространств, возможные условия выигрыша и некоторые другие меры привели к тому, что таблица сократилась до очень удобных 2500 возможностей, который std :: map обрабатывает за доли секунды.