Алгоритм минимакс на примере игры «Собери 4 (connect4)»

    Реализация алгоритма минимакс на примере игры «Собери 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=%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);
    
    , если мы выйграли
    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 дня вместе с отладкой и настройкой. Спасибо за внимание.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 22

      +1
      Спрячьте пожалуйста статью под кат. Спасибо за внимание.
        –2
        Почему? И что такое кат?
          +4
          Прочитали бы всё-таки правила публикации — не задавали бы таких вопросов.
            +5
            Большие посты обчно помещаются под habracut (есть такой специальный тег, который вы можете использовать в своей статье что бы спрятать бОльшую часть статьи под кнопкой «Читать дальше»). В результате в списке постов будет видно только начало вашего поста, а кто заинтересуется — тот нажмет кнопку «Читать дальше» и прочитает весь пост.
            +2
            А что неверно — поправьте, буду умнее в следующий раз (на ум приходят только пару :)
              +6
              А еще есть такая кнопка «Ответить» под каждым комментарием — пожалуйста пользуйтесь ею что бы ответить кому-то конкретно. Читать комментарии «в один столбик» — глаза вылазят.
                +3
                Поставил тег после примерно 300-50 символов, нормально сейчас?
                  0
                  Норм.
                    –1
                    Спасибо за совет
                    +3
                    Вроде бы да, так лучше, спасибо.
                      0
                      Спасибо за совет
                        +4
                        Ок, продолжаем ликбез.

                        Для простого «спасибо» достаточно плюсануть комментарий, нажав на «стрелочку вверх» в его правой части.
                        Если вам такой способ кажется недостаточно выразительным, можно изложить всю свою признательность хабраюзеру, отправив ему личное сообщение.
                        Суть в том, что комментарии типа «спасибо» не несут полезного содержания для остальных читателей Хабра.

                        Чтобы отправить личное сообщение хабраюзеру, нужно открыть страницу профиля адресата (нажав на его имя или юзерпик, которые являются ссылками), и найти на этой странице иконку с конвертом (располагается справа от чисел рейтинга).
                          0
                          :) — выложил материал чисто чтобы кому-то было полезно, а всякуя по-ь выслушивать, ну блин вообще неинтересно
                            0
                            Простите, конечно, но это называется неуважением. Вам не пое-ь говорят, а излагают правила сайта, которые вы, очевидно, не удосужились прочитать. Будете и дальше вести себя столь вызывающе, ваш пост заминусуют и больше вы на Хабр ничего не напишете.
                              0
                              спасибо на самом деле за советы, но блин — написал я спасибо вам и еще… реально благодарен… а тут еще минусуют за то что поблагодарил — во до чего докатились:)
                              +1
                              Просто на хабре свои правила — они изложены в письменном виде, доступны всем и касаются оформления статей, комментирования, стиля изложения, даже грамотности :) Соблюдение этих правил, вместе с системой кармы и плюсов за посты, некоторым образом гарантирует что хабр не скатится в хаос «каждый постит хрень и вообще творит что хочет», как многие другие сайты в рунете у которых вроде бы все начиналось хорошо. Если вы пишете сюда — просто соблюдайте их, как и все остальные, только и всего :)
                                0
                                ОК. Я стараюсь соблюдать — с катом вот промашка вышла, исправил сразу же. И не грубил никому и все такое — говорил спасибо.
                  0
                  По сути комментарии будут?
                  Суть Минимакса не раскрыта, на мой взгляд.

                  «Максимум выгоды при минимуме удачи», «Минимум ущерба при максимально худшем стечении обстоятельств».

                  Про оптимизацию весов / функции оценки сумбурно.

                  По оформлению… Не ставьте знаки препинания сразу после тэгов кода и переносите последующий текст на следующую строку явно. То, что представлено в статье сейчас, выглядит как сломавшаяся разметка.

                  Код не анализировал… за качество оного не скажу ничего.
                    0
                    Это результаты без теории можно сказать — плод моих собственных измышлений в минимакс. Но, определенный положительный результат есть! Если у вас есть соображения по поводу увеличения силы игры программы напишите пожалуйста, испробую, изложу результаты.
                      0
                      Я исследую вот прям также методом научного тыка генетические алгоритмы, что не есть хорошо. Без теоретической базы трудно нормальные тесты написать.

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

                      Кстати, МиниМакс как раз хорошо вписавыется в задачу оптимизации на ГА. Как говорится, «веселее вместе».
                        0
                        Добился абсолютной победы над программой! Благодаря, в том числе, вашим замечаниям: повышение значимости ответа соперника (понял примерно так), т.е. на практике достигается путем умножения результата соперника на константу более единицы, я выбрал (от фонаря) = 10 и алгоритм обыграл программу при ходе первым и при ходе вторым. Теперь функция минимакс выглядит вот так:
                        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 = 100.*koeff;
                        				s.step = i;
                        				return s;
                        			} else if(!isstep(field)){
                        				rait = 0.;				
                         			} else {
                        				r = game(field, deep+1, it, (t==Tic)?Tac:Tic);
                        				rait-=(CorrectK[it]*r.rait);
                        			}
                        			if(rait > s.rait){
                        				s.rait = rait;
                        				s.step = i;
                        			}
                        			field[i] = EMPTY;
                        		}
                        	}
                        	s.rait = s.rait*koeff;
                        	return s;
                        }
                        

                        Задачу можно считать решенной и переходить к более сложной игре)))
                          0
                          А таперича прогоните через профайлер, найдите нагруженные места и попробуйте улучшить производительность :)

                  Only users with full accounts can post comments. Log in, please.