Forza 4 in C

Forza4, il mitico gioco a turno dove occorre allineare 4 o più pedine in una scacchiera 6×7.

In questo articolo mostro come realizzare un IA abbastamza intelligente da poter giocare decentemente contro un avversario umano.

La grafica è completamente realizzata in ASCII, quindi niente di incredibile; quello che interessa è l’algorimo dell’IA e come esso è stato implementato: il minmax.

Minmax è una funzione di valutazione in grado di minimizzare (min) la massima perdita possibile e contemporaneamente massimizzare (max) il minimo guadagno. L’algorimo è applicabile a tutti i giochi a informazione completa come forza4, scacchi, dama, tris e in generale i giochi a turno.

L’algoritmo trova la mossa migliore esplorando tutto l’albero delle possibilità da quel punto del gioco in poi; in sostanza effettua una enorme quantità di simulazioni di gioco, provando tutte le prossime possibili mosse dell’avversario, tutte le possibili contromosse successive, tutte le possibili mosse successive dell’avversario e cosi’ via fino alla fine di ogni partita “simulata”. Ovviamente il numero dei possibili sviluppi di gioco aumenta esponenzialmente al numero delle mosse provate e quindi non è possibile esplorare completamente l’albero: occorre fermarsi prima.

500px-minimax.svg

Una realizzazione concreta proverà solo un ristretto numero di mosse in avanti terminate le quali verrà valutato in una scala opportuna il vantaggio del giocatore a quel preciso stato di gioco.

Codice sorgente: forza4

/* FORZA 4 - algoritmo DFS minimax */

#define SKILL 10
#define ROW 6
#define COLUMN 7

int board[ROW*COLUMN];
long int depth,skill;
unsigned long int nodes;

void display_board(void)
{
	long int i,j;
	printf("\n");
	for(j=0;j<ROW;j++)
	{
		for(i=0;i<COLUMN;i++)
		{
			if(board[i+j*COLUMN]==1) printf("X ");
			if(board[i+j*COLUMN]==-1) printf("O ");
			if(board[i+j*COLUMN]==0) printf(". ");
		}
		printf("\n");
	}
	for(i=0;i<(COLUMN*2)-1;i++) printf("-");
	printf("\n");
	for(i=0;i<COLUMN;i++) printf("%d ",i+1);
	printf("\n");
}

int checkwin(int player,int column,int lenght)
{
	long int j,r,l,i,height;
	lenght--;
	i = column;
	j = ROW-1;
	while(board[i+j*COLUMN]!=0) j--;
	j++;
	height = j;

	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	while(((--i)>=0)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	i = column;

	r = 0;
	while(((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
	if (r>=lenght) return 1;
	j = height;

	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	j = height;
	while(((--i)>=0)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	i = column;
	j = height;

	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	j = height;
	while(((--i)>=0)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;

	return 0;
}

int extimated_value(int player)
{
	long int i,j,value,l;

	value = 0;
	for(l=2;l<4;l++)
	{
		for(i=0;i<COLUMN;i++)
		{
			if(checkwin(player,i,l)) value = value + l;
		}
	}

	return value;
}

int goodness(int player,int depth,int column,int trigger)
{
	long int max,i,value,j;
	max = -200;
	if (checkwin(-player,column,4)) return -128;
	if (depth==0) return 0;
	for(i=0;i<COLUMN;i++)
	{
		if(board[i]==0)
		{
			j = ROW-1;
			while(board[i+j*COLUMN]!=0) j--;
			board[i+j*COLUMN] = player;
			nodes++;
			value = -goodness(-player,depth-1,i,-max)/2;
			board[i+j*COLUMN] = 0;
			if (value>max) max = value;
			if (value>trigger) return max;
		}
	}
	return max;
}

int best_move(int player)
{
	long int i,j,max,value,best,same,trigger,old,att;
	long int res[COLUMN];
	max = -100;
	best = -1;
	for(i=0;i<COLUMN;i++)
	{
		if(board[i]==0)
		{
			nodes = 0;
			j = ROW-1;
			while((board[i+j*COLUMN]!=0)&&(j>=0)) j--;
			board[i+j*COLUMN] = player;
			value = -goodness(-player,skill,i,200);
			printf("\nmove %d goodness: %d   tree size for this move: %d nodes",i+1,value,nodes);
			res[i] = value;
			board[i+j*COLUMN] = 0;
			if (value>max)
			{
				max = value;
				best = i;
			}
		}
	}
	if(best==-1)
	{
		for(i=0;i<COLUMN;i++) if(board[i]==0) return i;
	}

	return best;
}

int main(void)
{
	int move,j,i,coins;
	coins = ROW*COLUMN;
	skill = SKILL-3;

	for(i=0;i<(ROW*COLUMN);i++) board[i] = 0;
	display_board();

	while(coins!=0)
	{
		if (coins==40) skill=SKILL-2; /* quick start */
		if (coins==36) skill=SKILL-1; /* improve skill level... */
		if (coins==34) skill=SKILL;   /* ...to maximum */
		do
		{
			printf("\nchoose column [1-%d]...",COLUMN);
			scanf("%d",&move);
			if(board[move-1]!=0) printf("\ncolumn is full");
		}
		while(board[move-1]!=0);
		move--;
		j = ROW-1;
		while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
		board[move+j*COLUMN] = 1;
		coins--;
		display_board();
		if(checkwin(1,move,4))
		{
			printf("\nYou win\n");
			return 1;
		}
		move = best_move(-1);

		j = ROW-1;
		while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
		board[move+j*COLUMN] = -1;
		display_board();
		printf("\nCPU move in %d",move+1);
		coins--;
		if(checkwin(-1,move,4))
		{
			display_board();
			printf("\nCPU wins\n");
			return 1;
		}
		printf("\n");

	}
	printf("\n");
	return 1;
}

Ecco l’output del programma durante una partita:

forza4