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

в 8:31, , рубрики: Алгоритмы, игры, минимакс, метки: ,

Реализация алгоритма минимакс на примере игры «Собери 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

Источник

Поделиться

* - обязательные к заполнению поля