Алгоритм минимакс на примере игры «Собери 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 дня вместе с отладкой и настройкой. Спасибо за внимание.