Алгоритм минимакс на примере игры «Собери 4 (connect4)»
Реализация алгоритма минимакс на примере игры «Собери 4» очень увлекательное занятия и, в связи с этим, появилось желание рассказать об этом увлечении еще кому-нибудь, что и сделал. Игра доступна по данному адресу.Поле игры можно варьровать, устанавливая константы, я принял 7 на 6 как в примере по ссылке. Смысл игры заключается в том, чтобы, совершая ходы, выстроить 4 своих фигуры (крестики или нолики) в один ряд: по горизонтали, вертикали, диагонали. Для создания игры (видимо любой) необходимы две вещи: генератор ходов и анализатор ходов (позиций).Правила игры таковы, что установить фигуру можно не в любое место доски, а лишь в низ, причем низом считается также и поле, находящееся сверху поля, занятого фигурой (любой). Доску представил в виде одномерного массива:
TicTac field[NSIZE_I*NSIZE_J]; Cами структуры могут быть таковы:
typedef enum {Tic, Tac, EMPTY} TicTac; Для игры понадобятся множество процедур (относительно конечно), процедуру валидации кода реализовал так:
int validstep (const TicTac *field, int step){ return ((field[step]==EMPTY)&&((step + NSIZE_J >= NSIZE_I*NSIZE_J)||((step + NSIZE_J < NSIZE_I*NSIZE_J)&&(field[step + NSIZE_J] != EMPTY))));} Генератор ходов выполнил простейшим и неоптимальным способом, но, наименее мозголомным — простым перебором уравнений вертикалей, горизонталей и диагоналей, получилось достаточно объемно, но, ничего сложного:
int c4getrait (const TicTac *field, TicTac Me){
int i, j, k, score=0, maxscore=-1;
/*
X
X
X
*/
for (i=0; i
Step game (TicTac *field, int deep, WHO it, TicTac t){
int i=0;
float rait, koeff = 1 — Koeff[it]*deep;
Step s, r;
s.step = -1;
s.rait = -1000.;
if (deep > DEEPMAX){
s.rait = 0.;
return s;
}
for (i=0; i
for (i=0; i
field[i] = t;
Ищем оценку:
rait = c4getrait (field, t);
Если мы выиграли:
if (rait >= WIN){
То смысла искать глубже — нет, рекурсия прекращается, если ходов не осталось (ничья) — возвращаем 0 (возможно неоптимально), иначе:
r = game (field, deep+1, it, (t==Tic)? Tac: Tic);
rait-=r.rait;
Оцениваем реакцию противника на наш ход и рассчитываем рейтинг, далее выбираем максимальный рейтинг и возвращаем позицию:
if (rait > s.rait){
s.rait = rait;
s.step = i;
}
field[i] = EMPTY;
Возвращаем результат:
s.rait = s.rait*koeff;
return s;
Для правильной оценки необходимо ввести коэффициенты (теория чисто моя). Связано с тем, что выигрыш на разной глубине — это неравносильные понятия (да и вобщем оценка), потому как ценность выше, чем меньше глубина поиска. Пояснение: например, при ходе А вы получаете проигрыш на глубине 5, а при ходе Б — на глубине 2. Ясно, что 2 случится раньше чем 5, и поэтому в данной ситуации более предпочтительным для вас является ход 5, это же касается не только победы/поражения, но и просто оценки позиции. В связи с этим нужно формировать коэффициенты по принципу, чем глубже, тем меньше значимости придаем ходу. Но, тут вот как раз и начинаются сложности. Необходимо чтобы алгоритм правильно взвесил позиции, несмотря на противоречие — думать глубже, но оценку занижать тем больше, чем больше глубина. Здесь возможна, видимо, строгая математика, но, специальной подготовки я не имею. Но можно и так очевидно: в цикле провести партии между программами с постепенным изменением коэффициентов и записью в лог. Затем по логу можно найти наилучшие варианты и списать коэффициенты. Для глубины перебора 6 — у меня получилось 0,2. Вот примерно на данном этапе я и завершаю, вижу, хотя, по-ходу, еще одно улучшение — варьировать глубину в зависимости от числа вариантов, ясно, что число вариантов в данной игре уменьшается пропорционально занятым полям… Сейчас алгоритм легко выигрывает у среднестатистического игрока. С программой по ссылке выше проигрывает, если ходит вторым, первым — сводит вничью на максимальной сложности. Программка писалась 2 дня вместе с отладкой и настройкой. Спасибо за внимание.
