Esempio: giocare a tris

Maxine e Minnie sono delle vere appassionate di giochi da tavolo. Semplicemente li adorano, soprattutto i giochi a due giocatori e a informazione perfetta come il tris o gli scacchi. Un giorno stavano giocando a tris. Maxine, o Max per gli amici, aveva come simbolo la X. Minnie, o Min per gli amici, aveva il cerchio. Min aveva appena fatto la sua mossa e la griglia appariva così:

Max stava guardando la griglia e studiando la sua prossima mossa, visto che era il suo turno, quando all'improvviso si è portata le mani al volto in un gesto di disperazione, un po' come Garry Kasparov durante la partita contro Deep Blue nel 1997.

Sì, Min stava per mettere tre cerchi nella riga in alto, ma Max avrebbe potuto facilmente mandare all'aria i suoi piani. E allora perché Max era così pessimista?

Alberi di gioco

Per risolvere i giochi usando l'IA, introdurremo il concetto di albero di gioco. I diversi stati del gioco sono rappresentati dai nodi nell'albero di gioco, in maniera molto simile ai precedenti problemi di pianificazione. Solo che l'idea è leggermente diversa. Nell'albero di gioco, i nodi sono disposti su livelli che corrispondono ai turni di ciascun giocatore in modo che il nodo "radice" dell'albero (solitamente rappresentato in cima al diagramma) sia la posizione iniziale del gioco. Nel tris, l'albero di gioco sarebbe la griglia vuota non ancora riempita con X o cerchi. Sotto la radice, al secondo livello, ci sono i possibili stati che possono risultare dalle mosse del primo giocatore, con qualunque simbolo giochi. Questi nodi sono detti "figli" del nodo radice.

Ciascun nodo sul secondo livello avrà successivamente come nodi figli gli stati che possono essere raggiunti partendo da esso in seguito alle mosse dell'avversario. Si continua così, livello dopo livello, fino a raggiungere gli stati in cui il gioco finisce. Nel tris ciò significa che uno dei giocatori riempie una linea con tre dei suoi simboli e vince, oppure che la griglia è piena e il gioco finisce in parità.

Minimizzare e massimizzare il valore

Per poter creare un'IA di gioco che cerchi di vincere il gioco, attribuiamo un valore numerico a ciascun risultato finale possibile. Alle posizioni sulla griglia in cui la X ha una linea di tre e quindi Max vince, attribuiamo il valore +1; analogamente, alle posizioni in cui Min vince con tre cerchi di fila attribuiamo il valore -1. Per le posizioni in cui la griglia è piena e nessun giocatore vince, utilizziamo il valore neutro 0 (non importa quali sono i valori purché siano in quest'ordine in modo che Max cerchi di massimizzare il valore e Min cerchi di minimizzarlo).

Un modello di albero di gioco

Consideriamo per esempio il seguente albero di gioco che non inizia alla radice ma nel mezzo della partita (perché altrimenti l'albero sarebbe troppo grande da rappresentare). Si noti che differisce dalla partita mostrata nell'illustrazione all'inizio di questa sezione. Abbiamo numerato i nodi con i numeri 1, 2, ..., 14.

L'albero è composto da strati alterni in cui tocca a Min mettere un cerchio o a Max mettere una X in una qualunque delle caselle vuote sulla griglia. La giocatrice a cui tocca la mossa successiva è mostrata a sinistra.

La partita continua dalla posizione sulla griglia mostrata nel nodo radice, numerato come (1) in alto, con Min che deve mettere un cerchio in una qualsiasi delle tre celle vuote. I nodi da 2 a 4 mostrano le posizioni sulla griglia risultanti rispettivamente da ognuna delle tre scelte. Nel passaggio successivo, ciascun nodo ha due possibili scelte a disposizione di Max per mettere la X, e così l'albero si dirama ulteriormente.

Quando si inizia dalla suddetta posizione di partenza, la partita termina sempre con un tris: nei nodi 7 e 9 la vincitrice è Max che gioca con la X e nei nodi da 11 a 14 la vincitrice è Min che gioca con il cerchio.

Si noti che, data l'alternanza di mosse dei giocatori, i livelli possono essere etichettati come livelli di Min e livelli di Max, a indicare di chi è il turno.

Essere strategici

Considerate i nodi da 5 a 10 sul secondo livello dal basso. Nei nodi 7 e 9 la partita finisce e Max vince con un tris di X. Il valore di queste posizioni è +1. Anche nei nodi restanti 5, 6, 8 e 10 la partita è praticamente finita, dato che per vincere Min deve solo mettere un cerchio nell'unica casella rimasta. In altre parole, sappiamo come finirà la partita in corrispondenza di ogni nodo sul secondo livello dal basso. Possiamo quindi decidere che i nodi 5, 6, 8 e 10 abbiano il valore -1.

E qui le cose si fanno interessanti. Consideriamo i valori dei nodi un livello più in alto verso la radice, ossia i nodi da 2 a 4. Avendo osservato che entrambi i figli di 2, cioè i nodi 5 e 6, portano alla vittoria di Min, possiamo attribuire senza esitazione il valore -1 anche al nodo 2. Tuttavia, per il nodo 3, il figlio a sinistra 7 fa vincere Max, +1, mentre il figlio a destra 8 fa vincere Min, -1. Qual è il valore del nodo 3? Pensateci un momento, tenendo presente chi fa la scelta in corrispondenza del nodo 3.

Essendo il turno di Max, naturalmente lei sceglierà il figlio di sinistra, il nodo 7. Pertanto, ogni volta che raggiungiamo la posizione della griglia nel nodo 3, Max si assicurerà la vittoria e possiamo dunque attribuire il valore +1 al nodo 3.

Lo stesso vale per il nodo 4: anche qui, poiché Max può scegliere dove mettere la X, si assicurerà sempre la vittoria e noi attribuiremo quindi il valore +1 al nodo 4.

Determinare chi vince

L'insegnamento più importante di questa sezione sta nell'applicare in modo ripetuto il suddetto tipo di ragionamento per determinare anticipatamente il risultato della partita a partire da qualsiasi posizione sulla griglia.

Finora abbiamo deciso che il valore del nodo 2 è -1, il che significa che finendo in questa posizione sulla griglia Min si assicurerà la vittoria, mentre l'opposto vale per i nodi 3 e 4: il loro valore è +1, il che vuol dire che Max potrà essere certa di vincere se sfrutterà bene il suo turno.

Infine, possiamo dedurre che, essendo Min una giocatrice esperta, anche lei può giungere alla stessa conclusione e avrà quindi una sola opzione realistica: mettere il cerchio al centro della griglia. Nel diagramma seguente abbiamo incluso il valore di ciascun nodo e le giocate ottimali a cominciare dal turno di Min nel nodo radice.

Il valore del nodo radice = chi vince

Il valore del nodo radice, che abbiamo detto essere il valore della partita, ci dice chi vince (e quanto, se il risultato non è solo vincere o perdere): Max vince se il valore della partita è +1, Min se il valore è -1, mentre se il valore è 0 la partita finisce in parità. In altri giochi, il valore potrebbe assumere anche altri valori (per esempio il valore monetario dei gettoni davanti a sé nel gioco del poker).

Tutto questo si basa sull'ipotesi che entrambi i giocatori scelgano ciò che è meglio per loro e che ciò che è meglio per uno sia peggio per l'altro (il cosiddetto "gioco a somma zero").

L'algoritmo minimax

Possiamo sfruttare il concetto descritto in precedenza del valore della partita per ottenere un algoritmo detto l'algoritmo minimax. Questo garantisce giocate ottimali, in teoria, in qualsiasi gioco deterministico a due giocatori, a informazione perfetta e a somma zero. Partendo da uno stato della partita, l'algoritmo calcola semplicemente i valori dei figli di tale stato e sceglie quello con il valore massimo se tocca a Max e quello con il valore minimo se tocca a Min.

L'algoritmo può essere implementato usando alcune righe di codice. Tuttavia, ci basterà capire l'idea generale. Se vi interessa dare un'occhiata all'algoritmo vero e proprio (attenzione: servono nozioni di programmazione), potete consultare per esempio Okpedia: Minimax.

OK, adesso posso andare a casa?

Come detto in precedenza, l'algoritmo minimax può essere usato per effettuare giocate ottimali in qualsiasi gioco deterministico a due giocatori, a informazione perfetta e a somma zero. Simili giochi includono il tris, forza 4, gli scacchi, il go ecc. Carta-sasso-forbice non rientra in questa classe di giochi perché implica informazioni nascoste all'altro giocatore; sono altresì esclusi il monopoli e il backgammon in quanto non deterministici. Per quanto riguarda quest'argomento, siamo giunti alla fine. Allora adesso possiamo andare a casa? La risposta in teoria è sì, ma in pratica è no.

Qualche trucchetto in più: gestire gli alberi di gioco troppo grandi

Per gestire gli alberi di gioco troppo grandi ci vuole qualche trucchetto in più. Molti di questi trucchi sono stati elementi cruciali nella vittoria del computer Deep Blue di IBM sul campione mondiale di scacchi Garry Kasparov nel 1997.

Se possiamo permetterci di esaminare solo una piccola parte dell'albero di gioco, abbiamo bisogno di un modo per fermare la ricorsività di minimax prima di raggiungere un nodo finale, ossia un nodo dove finisce la partita e il vincitore è noto. Ciò è possibile per mezzo di una cosiddetta funzione di valutazione euristica che prende come input una posizione sul tabellone del gioco, incluse le informazioni sul giocatore a cui tocca il turno successivo, e dà un punteggio che dovrebbe essere una stima del probabile risultato della partita a partire da tale posizione sulla griglia.

L'algoritmo minimax sopra presentato richiede modifiche minime per ottenere una versione limitata in profondità in cui l'euristica è applicata a tutti i nodi a un determinato limite di profondità: la profondità si riferisce semplicemente al numero di passaggi fino a cui si espande l'albero di gioco prima di applicare una funzione di valutazione euristica.