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: