Algoritmo Minimax con potatura alfa-beta

Fin dall’avvento dell’Intelligenza Artificiale (AI), il gioco è stato una delle applicazioni più interessanti dell’IA.

I primi programmi di scacchi furono scritti da Claude Shannon e da Alan Turing nel 1950, quasi non appena i computer divennero programmabili.

Giochi come scacchi, tic-tac-toe e Go sono interessanti perché offrono una pura astrazione della competizione tra i due eserciti.

È questa astrazione che rende il gioco un’area attraente per la ricerca AI.

In questo articolo, esamineremo le basi dell’algoritmo Minimax insieme al funzionamento dell’algoritmo.

Daremo anche un’occhiata all’ottimizzazione dell’algoritmo minimax, la potatura alfa-beta.

Che cos’è l’algoritmo Minimax?

Minimax è un algoritmo ricorsivo che viene utilizzato per scegliere una mossa ottimale per un giocatore supponendo che anche l’altro giocatore stia giocando in modo ottimale.

È usato in giochi come tic-tac-toe, go, scacchi, Isola, dama e molti altri giochi a due giocatori.

Tali giochi sono chiamati giochi di informazioni perfette perché è possibile vedere tutte le possibili mosse di un particolare gioco.

Ci possono essere giochi a due giocatori che non sono di informazioni perfette come Scrabble perché la mossa dell’avversario non può essere prevista.

È simile a come pensiamo quando giochiamo: “se faccio questa mossa, il mio avversario può fare solo queste mosse” e così via.

Minimax è chiamato così perché aiuta a ridurre al minimo la perdita quando l’altro giocatore sceglie la strategia che ha la perdita massima.

Terminologia

• Albero di gioco: Si tratta di una struttura sotto forma di un albero costituito da tutte le possibili mosse che consentono di passare da uno stato del gioco allo stato successivo.

Un gioco può essere definito come un problema di ricerca con i seguenti componenti:

• Stato iniziale: comprende la posizione del tabellone e mostra di chi è la mossa.
• Funzione successore: Definisce quali sono le mosse legali che un giocatore può fare.
• Stato terminale: è la posizione del tabellone quando il gioco finisce.
• Funzione di utilità: è una funzione che assegna un valore numerico per il risultato di una partita. Ad esempio, negli scacchi o nel tic-tac-toe, il risultato è una vittoria, una sconfitta o un pareggio, e questi possono essere rappresentati dai valori +1, -1 o 0, rispettivamente. Ci sono giochi che hanno una gamma molto più ampia di possibili risultati; ad esempio, le utilità in backgammon variano da +192 a -192. Una funzione di utilità può anche essere chiamata una funzione di payoff.

Come funziona l’algoritmo?

Ci sono due giocatori coinvolti in un gioco, chiamato MIN e MAX. Il giocatore MAX cerca di ottenere il punteggio più alto possibile e MIN cerca di ottenere il punteggio più basso possibile, cioè MIN e MAX cercano di agire l’uno di fronte all’altro.

Il processo generale dell’algoritmo Minimax è il seguente:

Passo 1: Per prima cosa, genera l’intero albero del gioco a partire dalla posizione corrente del gioco fino agli stati del terminale. Questo è come l’albero di gioco si presenta come per il gioco tic-tac-toe.

Cerchiamo di capire la terminologia definita in termini di diagramma sopra.

1. Lo stato iniziale è il primo livello che definisce che la scheda è vuota è il turno di MAX per giocare.
2. Funzione successore elenca tutte le possibili mosse successore. È definito per tutti i livelli nell’albero.
3. Stato terminale è l’ultimo livello dell’albero che mostra lo stato finale, cioè se il giocatore MAX vince, perde o si lega con l’avversario.
4. Le utilità in questo caso per gli stati del terminale sono 1, 0 e -1 come discusso in precedenza e possono essere utilizzate per determinare anche le utilità degli altri nodi.

Passo 2: Applicare la funzione di utilità per ottenere i valori di utilità per tutti gli stati del terminale.
Passaggio 3: Determinare le utilità dei nodi superiori con l’aiuto delle utilità dei nodi terminali. Ad esempio, nel diagramma seguente, abbiamo le utilità per gli stati terminali scritte nei quadrati.

Calcoliamo l’utilità per il nodo sinistro (rosso) del livello sopra il terminale. Dal momento che è la mossa del giocatore MIN, sceglieremo il minimo di tutte le utilità. Per questo caso, dobbiamo valutare MIN {3, 5, 10}, che sappiamo è certamente 3. Quindi l’utilità per il nodo rosso è 3.

Allo stesso modo, per il nodo verde nello stesso livello, dovremo valutare MIN{2,2} che è 2.

Passo 4: Calcola i valori di utilità con l’aiuto delle foglie considerando un livello alla volta fino alla radice dell’albero.
Passaggio 5: Alla fine, tutti i valori di backup raggiungono la radice dell’albero, ovvero il punto più in alto. A quel punto, MAX deve scegliere il valore più alto.

Nel nostro esempio, abbiamo solo 3 livelli, quindi abbiamo immediatamente raggiunto la radice, ma nei giochi reali, ci saranno molti più livelli e nodi. Quindi dobbiamo valutare MAX{3,2} che è 3.

Pertanto, la migliore mossa di apertura per MAX è il nodo sinistro (o quello rosso). Questa mossa è chiamata la decisione minimax in quanto massimizza l’utilità seguendo il presupposto che l’avversario sta giocando anche in modo ottimale per minimizzarlo.

Per riassumere,

Minimax Decision = MAX{MIN {3,5,10}, MIN {2,2}}
= MAX{3,2}
= 3

Codice sorgente:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

Ottimizzazione

Alberi di gioco sono, in generale, molto tempo per costruire, ed è solo per i giochi semplici che può essere generato in breve tempo.

Se ci sono\ (b\) mosse legali, cioè,\ (b\) nodi in ogni punto e la profondità massima dell’albero è \(m\), la complessità temporale dell’algoritmo minimax è dell’ordine \(b^m (O(b^m))\).

Per frenare questa situazione, ci sono alcune ottimizzazioni che possono essere aggiunte all’algoritmo.

Fortunatamente, è possibile trovare la decisione minimax effettiva senza nemmeno guardare ogni nodo dell’albero del gioco. Quindi, eliminiamo i nodi dall’albero senza analizzare, e questo processo è chiamato potatura.

Potatura alfa-beta

Il metodo che vedremo in questo articolo si chiama potatura alfa-beta.

Se applichiamo la potatura alfa-beta a un algoritmo minimax standard, restituisce la stessa mossa di quella standard, ma rimuove (pota) tutti i nodi che probabilmente non influenzano la decisione finale.

Cerchiamo di capire l’intuizione alla base di questo primo e poi formalizzeremo l’algoritmo. Supponiamo, abbiamo il seguente albero di gioco:

In questo caso,
Minimax Decisione = MAX{MIN{3,5,10}, MIN{2,a,b}, MIN{2,7,3}}
= MAX{3,c,2}
= 3

Si sarebbe sorpreso!

Come possiamo calcolare il massimo con un valore mancante? Ecco il trucco. MIN {2, a, b} sarebbe certamente minore o uguale a 2, cioè c < =2 e quindi MAX{3, c, 2} deve essere 3.

La domanda ora è abbiamo davvero bisogno di calcolare c? Certo che no.

Avremmo potuto raggiungere una conclusione senza guardare quei nodi. Ed è qui che entra in scena la potatura alfa-beta.

Alcune definizioni:

Alpha: È la scelta migliore finora per il giocatore MAX. Vogliamo ottenere il più alto valore possibile qui.
Beta: E ‘ la scelta migliore finora per MIN, e deve essere il valore più basso possibile.

Nota: Ogni nodo deve tenere traccia dei suoi valori alfa e beta. Alpha può essere aggiornato solo quando è il turno di MAX e, allo stesso modo, beta può essere aggiornato solo quando è la possibilità di MIN.

Come funziona la potatura alfa-beta?

1. Inizializza alpha = -infinity e beta = infinity come i peggiori casi possibili. La condizione per potare un nodo è quando alfa diventa maggiore o uguale a beta.
2. Inizia con l’assegnazione dei valori iniziali di alfa e beta alla radice e poiché alfa è inferiore a beta non lo potiamo.
3. Porta questi valori di alfa e beta al nodo figlio a sinistra. E ora dal valore di utilità dello stato del terminale, aggiorneremo i valori di alpha e be, quindi non dobbiamo aggiornare il valore di beta. Di nuovo, non potiamo perché la condizione rimane la stessa. Allo stesso modo, anche il terzo nodo figlio. E poi backtracking alla radice impostiamo alpha = 3 perché questo è il valore minimo che alpha può avere.
   
4. Ora, alfa = 3 e beta = infinito alla radice. Quindi non potiamo. Portando questo al nodo centrale e calcolando MIN {2, infinity}, otteniamo alpha = 3 e beta=2.
5. Potare il secondo e il terzo nodo figlio perché alpha è ora maggiore di beta.
6. Alfa alla radice rimane 3 perché è maggiore di 2. Portando questo al nodo figlio più a destra, valuta MIN {infinity, 2}=2. Aggiornamento beta a 2 e alfa rimane 3.
7. Potare il secondo e il terzo nodo figlio perché alpha è ora maggiore di beta.
8. Quindi, otteniamo 3, 2, 2 rispettivamente ai nodi MIN sinistro, centrale e destro. E calcolando MAX{3,2,2}, otteniamo 3. Pertanto, senza nemmeno guardare quattro foglie potremmo trovare correttamente la decisione minimax.

Pseudocodice (Fonte: Corso NPTEL):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

Conclusione

I giochi sono molto attraenti e scrivere programmi di gioco è forse ancora più eccitante. Che Gran Premio di corsa è per l’industria automobilistica, il gioco è quello di AI.

Proprio come non ci aspetteremmo che un’auto da corsa funzioni perfettamente su una strada sconnessa, non dovremmo aspettarci che gli algoritmi di gioco siano perfetti per ogni situazione.

Così è l’algoritmo minimax. Potrebbe non essere la soluzione migliore per tutti i tipi di giochi per computer che devono avere AI.

Ma data una buona implementazione, può creare un concorrente difficile.