Реализация алгоритма минимакс на примере игры «Собери 4» очень увлекательное занятия и, в связи с этим, появилось желание рассказать об этом увлечении еще кому-нибудь, что и сделал. Игра доступна по данному адресу.
Поле игры можно варьровать, устанавливая константы, я принял 7 на 6 как в примере по ссылке. Смысл игры заключается в том, чтобы, совершая ходы, выстроить 4 своих фигуры (крестики или нолики) в один ряд: по горизонтали, вертикали, диагонали. Для создания игры (видимо любой) необходимы две вещи: генератор ходов и анализатор ходов (позиций).
Правила игры таковы, что установить фигуру можно не в любое место доски, а лишь в низ, причем низом считается также и поле, находящееся сверху поля, занятого фигурой (любой). Доску представил в виде одномерного массива
TicTac field[NSIZE_I*NSIZE_J];, сами структуры могут быть таковы
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<NSIZE_I; i++){
score=0;
for(j=0; j<NSIZE_J; j++){
//printf( "i=%d; j=%dn", i, j );
if(field[i*NSIZE_J + j] == Me)
score++;
else {
maxscore = (score > maxscore)?score:maxscore;
score = 0;
if(maxscore == WIN)
return maxscore;
}
}
maxscore = (score > maxscore)?score:maxscore;
}
/*
XXX
*/
for(j=0; j<NSIZE_J; j++){
score=0;
for(i=0; i<NSIZE_I; i++){
if(field[i*NSIZE_J + j] == Me)
score++;
else {
maxscore = (score > maxscore)?score:maxscore;
score = 0;
if(maxscore == WIN)
return maxscore;
}
}
maxscore = (score > maxscore)?score:maxscore;
}
/*main up diag
XXX
XX
X
*/
for(k=0; k<NSIZE_J; k++){
score=0;
for(i=0, j=NSIZE_J-k-1; i<NSIZE_I&&j>=0; i++, j--){
//printf( "i=%d; j=%dn", i, j );
if(field[i*NSIZE_J + j] == Me)
score++;
else {
maxscore = (score > maxscore)?score:maxscore;
score = 0;
if(maxscore == WIN)
return maxscore;
}
}
//printf( "n" );
maxscore = (score > maxscore)?score:maxscore;
}...
.
Конечно наиболее важная и сложная процедура в программе — это сам алгоритм минимакс. Суть алгоритма заключается в поиске оптимального хода, причем, оценка вырабатывается, как совокупность оценок ходов своего и противника. Процедура рекурсивная. На каждом шаге мы ищем оценку своего хода и оценку наилучшего хода противника. Например: наш ход оценим в 2 балла, ответ противника в 10 баллов, итого = 2 — 10 = -8 — это и есть оценка нашего хода, рекурсивно пробираясь вниз по дереву вариантов, оцениваем позицию на глубину N. Данная игра, хотя и достаточно простая, но перебор всех вариантов, а их — факториал 42 для пустого поля, задача невыполнимая на персональном компьютере (видимо только на супер ЭВМ). Невозможность просчитать до упора вынуждает применять эвристику — расчет позиции. Приведу процедуру минимакс:
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<NSIZE_I*NSIZE_J; i++){
if( validstep(field, i) ){
field[i] = t;
rait = c4getrait(field, t);
if(rait >= WIN){
field[i] = EMPTY;
s.rait = 10.*koeff;
s.step = i;
return s;
} else if(!isstep(field)){
rait = 0.;
} else {
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;
}В процедуре производится перебор всех позиций в цикле
for(i=0; i<NSIZE_I*NSIZE_J; 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 дня вместе с отладкой и настройкой. Спасибо за внимание.
Автор: vidoff
