Реализация алгоритма минимакс на примере игры «Собери 4» очень увлекательное занятия и, в связи с этим, появилось желание рассказать об этом увлечении еще кому-нибудь, что и сделал. Игра доступна по данному адресу.
Поле игры можно варьровать, устанавливая константы, я принял 7 на 6 как в примере по ссылке. Смысл игры заключается в том, чтобы, совершая ходы, выстроить 4 своих фигуры (крестики или нолики) в один ряд: по горизонтали, вертикали, диагонали. Для создания игры (видимо любой) необходимы две вещи: генератор ходов и анализатор ходов (позиций).
Правила игры таковы, что установить фигуру можно не в любое место доски, а лишь в низ, причем низом считается также и поле, находящееся сверху поля, занятого фигурой (любой). Доску представил в виде одномерного массива
Конечно наиболее важная и сложная процедура в программе — это сам алгоритм минимакс. Суть алгоритма заключается в поиске оптимального хода, причем, оценка вырабатывается, как совокупность оценок ходов своего и против��ика. Процедура рекурсивная. На каждом шаге мы ищем оценку своего хода и оценку наилучшего хода противника. Например: наш ход оценим в 2 балла, ответ противника в 10 баллов, итого = 2 — 10 = -8 — это и есть оценка нашего хода, рекурсивно пробираясь вниз по дереву вариантов, оцениваем позицию на глубину N. Данная игра, хотя и достаточно простая, но перебор всех вариантов, а их — факториал 42 для пустого поля, задача невыполнимая на персональном компьютере (видимо только на супер ЭВМ). Невозможность просчитать до упора вынуждает применять эвристику — расчет позиции. Приведу процедуру минимакс:
Для правильной оценки необходимо ввести коэффициенты (теория чисто моя :). Связано с тем, что выйгрыш на разной глубине — это неравносильные понятия (да и вобщем оценка), потому как ценность выше, чем меньше глубина поиска. Пояснение: например при ходе А вы получаете проигрыш на глубине 5, а при ходе Б — на глубине 2. Ясно, что 2 случится раньше чем 5:), и поэтому в данной ситуации более предпочтительным для вас является ход 5, это же касается не только победы/поражения, но и просто оценки позиции. В связи с этим нужно формировать коэффициенты по принципу, чем глубже, тем меньше значимости придаем ходу. Но, тут вот как раз и начинаются сложности:) Необходимо чтобы алгоритм правильно взвесил позиции, несмотря на противоречие — думать глубже, но оценку занижать тем больше, чем больше глубина. Здесь возможна, видимо, строгая математика, но, специальной подготовки я не имею. Но можно и так очевидно: в цикле провести партии между программами с постепенным изменением коэффициентов и записью в лог. Затем по логу можно найти наилучшие варианты и списать коэффициенты. Для глубины перебора 6 — у меня получилось 0,2. Вот примерно на данном этапе я и завершаю, вижу, хотя, по-ходу, еще одно улучшение — варьировать глубину в зависимости от числа вариантов, ясно, что число вариантов в данной игре уменьшается пропорционально занятым полям… Сейчас алгоритм легко выигрывает у среднестатистического игрока:) С программой по ссылке выше проигрывает, если ходит вторым, первым — сводит вничью на максимальной сложности. Программка писалась 2 дня вместе с отладкой и настройкой. Спасибо за внимание.
Поле игры можно варьровать, устанавливая константы, я принял 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=%d\n", 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=%d\n", 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);
, то смысла искать глубже — нет, рекурсия прекращается, если ходов не осталось(ничья) — возвращаем 0 (возможно неоптимально), иначеif(rait >= WIN){
оцениваем реакцию противника на наш ход и рассчитываем рейтинг, далее выбираем максимальный рейтинг и возвращаем позицию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 дня вместе с отладкой и настройкой. Спасибо за внимание.
