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.
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:
