Как разработать алгоритм для больших игровых досок Tic Tac Toe?

Question

Я создал игру про тактику в Android, и это здорово. Но эта игра имеет 3 * 3 игрового процесса. В игре 3 * 3 мы можем реализовать наш ручной ИИ (сначала заполнение угловой позиции) или использовать алгоритм минимакса, чтобы получить лучший ход. Это отлично подходит для 3 * 3 доски. Но когда я попробовал один и тот же алгоритм для 4 * 4 и 5 * 5, алгоритм занял огромное время, чтобы определить лучший ход. Следовательно, я не могу использовать минимаксный алгоритм.

Так что же мне теперь делать? Я хочу реализовать другой уровень с другой целью, как показано ниже

Здесь это доска 6 * 6, и цель (последовательный символ победы) равна 5. Поэтому я хочу разработать ай для этой динамической доски с динамической целью. Цель может быть 3,4,5 и т. Д. Как я могу сделай это? Заранее спасибо.

Answer 1

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

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

• 1 шаг, если его линия закрыта на другом конце, 2 шага, если его линия открыта на обоих концах.

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

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