In questo articolo vedremo come realizzare una versione Flutter del classico gioco Tic-Tac-Toe (in italiano Tris) implementando l'algoritmo del Minimax, un algoritmo ricorsivo che minimizza la massima perdita possibile dei due giocatori. Nella prima parte descriveremo l'algoritmo, nella seconda vedremo l'applicazione Flutter.
L'algoritmo Minimax
L'algoritmo Minimax è un algoritmo ricorsivo per la ricerca della mossa migliore in un gioco a somma zero, ovvero quelli in cui i giocatori hanno obiettivi opposti e utilizzato nella teoria delle decisioni quando i giocatori si trovano in interazione strategica. È finalizzato a minimizzare la massima perdita possibile di ciascun giocatore. L'algoritmo Minimax consente di individuare le scelte migliori dei due giocatori nel corso del gioco, analizzando a ritroso l'albero di gioco a partire dai nodi terminali, ossia dalle possibili situazioni in cui può terminare il gioco ( fine gioco ), e risalendo progressivamente fino alla posizione corrente dei giocatori.
Una versione semplice adatta al gioco del tris, dove è possibile vincere, perdere o pareggiare, può essere riassunta in queste due regole:
- Se il giocatore X può vincere con una sola mossa, la mossa migliore è quella vincente.
- Se il giocatore O sa che una data mossa porterà X a poter vincere con la sua prossima mossa, mentre un'altra lo porterà a pareggiare, la migliore mossa del giocatore O è quella che lo porterà alla patta.
Verso la fine del gioco è facile capire quali sono le mosse migliori; l'algoritmo Minimax trova la mossa migliore in un dato momento cercandola a partire dalla fine del gioco e risalendo verso la situazione corrente. Ad ogni passo l'algoritmo assume che il giocatore A cerchi di massimizzare le sue probabilità di vincere, mentre O cerchi di minimizzare le probabilità di vittoria di X, per esempio massimizzando le proprie chance di vittoria.
L'applicazione al gioco Tic-tac-toe
Vediamo l'applicazione dell'algoritmo al gioco. Immaginiamo di trovarci nella condizione rappresentata dalla griglia e che la prossima mossa sia del giocatore X. Delle 3 possibili mosse, quella che massimizza il risultato per il giocatore X è l'unica vincente.
Se la scelta del giocatore X ricade su una delle altre due mosse disponibili, il giocatore O potrebbe massimizzare il proprio risultato nella mossa successiva:
Il punto chiave dell'algoritmo Minimax è testare i due giocatori a turno e per ognuno scegliere la mossa con il punteggio massimo. A sua volta, i punteggi per ciascuna delle mosse disponibili sono determinati dal giocatore avversario che decide quale delle sue mosse disponibili ha il punteggio minimo. E i punteggi per le mosse dei giocatori avversari sono nuovamente determinati dal giocatore di turno che cerca di massimizzare il suo punteggio e così via lungo l'albero delle mosse fino allo stato finale.
Dal punto di vista del giocatore X, l'algoritmo applica queste regole:
- se il gioco è finito, restituisci il punteggio dal punto di vista di X.
- altrimenti valuta i nuovi stati di gioco per ogni possibile mossa
- per ognuno di questi stati valuta il punteggio
- se è il turno di X, restituisci la mossa con il punteggio massimo
- se è il turno di O, restituisci la mossa con il punteggio minimo
Esaminiamo l'esecuzione dell'algoritmo con l'albero delle mosse completo e mostriamo perché, verrà scelta la mossa vincente. Ipotizziamo di associare un punteggio 10 alle vincita di X, un punteggio -10 alla vincita di O e 0 alla condizione di pareggio:
- È il turno di X nello stato 1. X genera gli stati 2, 3 e 4 e verifica il punteggio su quegli stati.
- Lo stato 2 determina il punteggio di +10 associato allo stato 1, perché il gioco è in uno stato finale.
- Gli stati 3 e 4 non sono negli stati finali, quindi 3 genera gli stati 5 e 6 e verifica il punteggio su di essi, mentre lo stato 4 genera gli stati 7 e 8 e verifica il punteggio su di essi.
- Lo stato 5 genera un punteggio di -10 associato alo stato 3, mentre lo stesso accade per lo stato 7 che genera un punteggio di -10 per lo stato 4.
- Gli stati 6 e 8 generano le uniche mosse disponibili, che sono gli stati finali, quindi entrambi generano un punteggio di +10 per gli stati 3 e 4.
- Poiché è il turno di O in entrambi gli stati 3 e 4, O cercherà di trovare il punteggio minimo e, data la scelta tra -10 e +10, entrambi gli stati 3 e 4 produrranno -10.
- Infine, per gli stati stati 2, 3 e 4 avremo i punteggi rispettivamente di +10, -10 e -10, e lo stato 1 che cerca di massimizzare il punteggio sceglierà la mossa vincente con punteggio +10, stato 2.
Casi particolari
Ci sono alcune condizioni particolari in cui l'algoritmo potrebbe dare delle risposte diverse da quelle "più logiche" che ci si aspetta. Ad esempio con una configurazione di questo tipo
La risposta "strana" è dovuta al fatto che, con questa configurazione, qualsiasi sia la scelta del giocatore O, la vittoria finale sarà sempre del giocatore X
- Dato lo stato 1 in cui entrambi i giocatori stanno giocando perfettamente, e O è il giocatore del computer. O sceglie la mossa nello stato 5 e poi perde immediatamente quando X vince nello stato 9.
- Ma se O blocca la vincita di X come nello stato 3, X ovviamente bloccherà la potenziale vincita di O come mostrato nello stato 7.
- Questo pone due vittorie certe per X come mostrato negli stati 10 e 11, quindi non importa quale mossa O scelga nello stato 7, X alla fine vincerà.
Come risultato di questi scenari e del fatto che stiamo iterando attraverso ogni spazio vuoto ella griglia, da sinistra a destra, dall'alto verso il basso, essendo tutte le mosse uguali, cioè risultando sempre una perdita per O, potrebbe capitare che la mossa scelta dipenda dall'ordine di scansione delle celle a parità di altri fattori, come mostrata nello stato 5, poiché è l'ultima delle mosse disponibili.
Per evitare che l'ordine di scansione influenzi il risultato dell'algoritmo, è tenere conto della "profondità" o del numero di turni fino alla fine del gioco. Fondamentalmente il giocatore perfetto dovrebbe giocare perfettamente, ma prolungare il gioco il più possibile.
Per ottenere ciò sottrarremo la profondità, cioè il numero di giri, o iterazioni, dal punteggio di fine partita, più giri più basso è il punteggio, meno giri più alto è il punteggio.
Questa volta la profondità (mostrata in nero a sinistra) fa sì che il punteggio differisca per ogni stato finale e poiché si parte dal livello 0, l'algoritmo cercherà di massimizzare i punteggi disponibili (poiché O è il giocatore di turno), il -6 il punteggio sarà scelto in quanto maggiore degli altri stati con un punteggio di -8. E così anche di fronte a una morte certa, l'algoritmo restituirà la scelta corretta.
L'implementazione in Dart
Rappresentiamo la nostra griglia di gioco usando una lista di 9 interi, ponendo a 0 (cella inizialmente vuota) il valore di ogni cella (in seguito indicheremo con 1 la cella occupata dal giocatore X e con -1 la cella occupata del giocatore O) :List<int> board = List.generate(9, (index) => 0);
Con questa rappresentazione, tutte le possibili configurazioni di vincita posso essere descritte in questo modo:
const WIN_POSITIONS = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[2, 4, 6],
];
e quindi sarà possibile determinare l'esito di ogni nuova mossa con queste funzioni:
bool isEmpty(List<int> board, int idx) {
return (board[idx] == 0);
}
bool isBoardFull(List<int> board) {
for (var value in board) {
if (value == 0) return false;
}
return true;
}
int checkWinner(List<int> board) {
for (var tris in WIN_POSITIONS) {
if (board[tris[0]] != 0 &&
board[tris[0]] == board[tris[1]] &&
board[tris[0]] == board[tris[2]]) {
return board[tris[0]];
}
}
if (isBoardFull(board)) {
return 2;
}
return 0;
}
La funzione isBoardFull ritorna TRUE se tutte le caselle sono occupate; la funzione checkWinner verifica ogni possibile condizione di vincita e ritorna 1 o -1 in caso di vincita, in base al giocatore, 2 in caso di pareggio (tutte le celle occupate e nessun vincitore) o 0 se è ancora possibile giocare; la funzione isEmpty verifica se la singola cella è vuota.
Con queste funzioni di supporto (inserite in una classe ad-hoc), l'algoritmo Minimax può essere scritto in questo modo:
import 'game.dart';
class Minimax {
static const MAX_SCORE = 10;
static const MIN_SCORE = -10;
static const DRAW_SCORE = 0;
// ritorna la mossa per il giocatore corrente
// level deve essere 0 per la prima mossa
int play(List<int> board, int currentPlayer, int level) {
return nextMove(board, currentPlayer, level).position;
}
// valuta la miglire mossa successiva
Move nextMove(List<int> board, int currentPlayer, int level) {
List<int> newBoard;
Move bestMove = Move(score: -10000, position: -1);
// per ogni casella della griglia
for (int currentMove = 0; currentMove < board.length; currentMove++) {
// verifica che la casella sia libera
if (!Game.isValidMove(board, currentMove)) continue;
// crea una nuova board a aprtire da quella corrente
// su cui valutare le mosse successive
newBoard = List.from(board);
newBoard[currentMove] = currentPlayer;
// cambia il segno per perchè la mossa successiva
// è dell'altro giocatore
int newScore = -getScore(
newBoard,
- currentPlayer, // test altro giocatore
level);
// se la nuova mossa è migliore di quella precedente
// memorizza la nuova mossa
if (newScore > bestMove.score) {
bestMove.score = newScore;
bestMove.position = currentMove;
}
}
return bestMove;
}
// calcolo del punteggio della mossa
// verificando se la mossa è o no vincente
int getScore(List<int> board, int currentPlayer, int level) {
final winner = Game.checkIfWinnerFound(board);
if (winner == currentPlayer) {
return MAX_SCORE - level;
} else if (winner == - currentPlayer) {
return MIN_SCORE + level;
} else if (winner == Game.DRAW) {
return DRAW_SCORE;
}
return nextMove(board, currentPlayer, level + 1).score;
}
}
class Move {
int score;
int position;
Move({
required this.score,
required this.position,
});
}
La funzione nextMove testa ogni posizione libera della griglia in modo ricorsivo (alternando i giocatori), fino a raggiungere una condizione di vittoria per uno dei due o una condizione di pareggio, memorizzando la mossa che massimizza il punteggio del giocatore corrente (ovvero minimizza il punteggio dell'altro giocatore).
Fine prima parte
La prima parte dell'articolo è terminato: abbiamo visto l'algoritmo e una sua veloce implementazione in linguaggio DART. Nella seconda parte useremo queste informazioni per realizzare un'app in Flutter.
Stay tuned !
Stay tuned !
Commenti
Posta un commento