Алгоритм минимакс на прикладі гри «Збери 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))));}
, генератор ходів виконав найпростішим і неоптимальним способом, але, найменш мозголомность — простим перебором рівнянь вертикалей, горизонталей і діагоналей, вийшло досить об'ємно, але, нічого складного
 <habracut/>
 
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 дня разом з налагодженням і настроюванням. Спасибі за увагу.
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.