Introduzione all'algoritmo Minimax con un'implementazione Java

1. Panoramica

In questo articolo, discuteremo l'algoritmo Minimax e le sue applicazioni nell'IA. Poiché si tratta di un algoritmo di teoria dei giochi, implementeremo un gioco semplice utilizzandolo.

Discuteremo anche i vantaggi dell'utilizzo dell'algoritmo e vedremo come può essere migliorato.

2. Introduzione

Minimax è un algoritmo decisionale, tipicamente utilizzato in un gioco a turni a due giocatori . L'obiettivo dell'algoritmo è trovare la mossa successiva ottimale.

Nell'algoritmo, un giocatore è chiamato massimizzatore e l'altro giocatore è un minimizzatore. Se assegniamo un punteggio di valutazione al tabellone, un giocatore cerca di scegliere uno stato di gioco con il punteggio massimo, mentre l'altro sceglie uno stato con il punteggio minimo.

In altre parole, il massimizzatore lavora per ottenere il punteggio più alto, mentre il minimizzatore cerca di ottenere il punteggio più basso cercando di contrastare le mosse .

Si basa sul concetto di gioco a somma zero. In un gioco a somma zero, il punteggio di utilità totale viene diviso tra i giocatori. Un aumento del punteggio di un giocatore si traduce in una diminuzione del punteggio di un altro giocatore. Quindi, il punteggio totale è sempre zero. Perché un giocatore vinca, l'altro deve perdere. Esempi di tali giochi sono gli scacchi, il poker, la dama, il tris.

Un fatto interessante: nel 1997, il computer scacchista di IBM Deep Blue (costruito con Minimax) sconfisse Garry Kasparov (il campione del mondo di scacchi).

3. Algoritmo Minimax

Il nostro obiettivo è trovare la mossa migliore per il giocatore. Per fare ciò, possiamo semplicemente scegliere il nodo con il miglior punteggio di valutazione. Per rendere il processo più intelligente, possiamo anche guardare avanti e valutare le mosse del potenziale avversario.

Per ogni mossa, possiamo guardare avanti tutte le mosse consentite dalla nostra potenza di calcolo. L'algoritmo presume che l'avversario stia giocando in modo ottimale.

Tecnicamente, iniziamo con il nodo radice e scegliamo il miglior nodo possibile. Valutiamo i nodi in base ai loro punteggi di valutazione. Nel nostro caso, la funzione di valutazione può assegnare punteggi solo ai nodi di risultato (foglie). Pertanto, raggiungiamo in modo ricorsivo le foglie con i punteggi e indietro propaghiamo i punteggi.

Considera l'albero di gioco seguente:

Maximizer inizia con il nodo radice e sceglie la mossa con il punteggio massimo. Sfortunatamente, solo le foglie hanno punteggi di valutazione e quindi l'algoritmo deve raggiungere i nodi foglia in modo ricorsivo. Nell'albero di gioco dato, attualmente è il turno del minimizer di scegliere una mossa dai nodi foglia , quindi verranno selezionati i nodi con punteggi minimi (qui, nodo 3 e 4). Continua a scegliere i nodi migliori in modo simile, finché non raggiunge il nodo radice.

Ora definiamo formalmente i passaggi dell'algoritmo:

  1. Costruisci l'albero del gioco completo
  2. Valuta i punteggi per le foglie utilizzando la funzione di valutazione
  3. I punteggi di backup dalle foglie alla radice, considerando il tipo di giocatore:
    • Per il giocatore massimo, seleziona il bambino con il punteggio massimo
    • Per il giocatore minimo, seleziona il bambino con il punteggio minimo
  4. Al nodo radice, scegli il nodo con il valore massimo ed esegui lo spostamento corrispondente

4. Implementazione

Ora implementiamo un gioco.

Nel gioco, abbiamo un mucchio con n numero di ossa . Entrambi i giocatori devono raccogliere 1,2 o 3 ossa nel loro turno. Un giocatore che non può prendere le ossa perde la partita. Ogni giocatore gioca in modo ottimale. Dato il valore di n , scriviamo un AI.

Per definire le regole del gioco, implementeremo la classe GameOfBones :

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

Inoltre, abbiamo anche bisogno dell'implementazione per le classi Node e Tree :

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Ora implementeremo l'algoritmo. Richiede un albero di gioco per guardare avanti e trovare la mossa migliore. Implementiamolo:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Ora implementeremo il metodo checkWin che simulerà un play out, selezionando le mosse ottimali per entrambi i giocatori. Imposta il punteggio su:

  • +1, se il massimizzatore vince
  • -1, se il minimizer vince

Il checkWin restituirà true se il primo giocatore (nel nostro caso - il maximizer) vince:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Qui, il metodo findBestChild trova il nodo con il punteggio massimo se un giocatore è un massimizzatore. In caso contrario, restituisce il bambino con il punteggio minimo:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

Infine, implementiamo un test case con alcuni valori di n (il numero di bone in un heap):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Miglioramento

Per la maggior parte dei problemi, non è possibile costruire un intero albero di gioco. In pratica, possiamo sviluppare un albero parziale (costruire l'albero solo fino a un numero predefinito di livelli) .

Quindi, dovremo implementare una funzione di valutazione, che dovrebbe essere in grado di decidere quanto è buono lo stato attuale per il giocatore.

Anche se non costruiamo alberi di gioco completi, può richiedere molto tempo calcolare le mosse per giochi con un elevato fattore di ramificazione.

Fortunatamente, c'è un'opzione per trovare la mossa ottimale, senza esplorare ogni nodo dell'albero di gioco. Possiamo saltare alcuni rami seguendo alcune regole e non influirà sul risultato finale. Questo processo è chiamato potatura . La potatura alfa-beta è una variante prevalente dell'algoritmo minimax.

6. Conclusione

L'algoritmo Minimax è uno degli algoritmi più popolari per i giochi da tavolo per computer. È ampiamente applicato nei giochi a turni. Può essere una buona scelta quando i giocatori hanno informazioni complete sul gioco.

Potrebbe non essere la scelta migliore per i giochi con un fattore di ramificazione eccezionalmente alto (es. Gioco di GO). Tuttavia, data una corretta implementazione, può essere un'IA piuttosto intelligente.

Come sempre, il codice completo per l'algoritmo può essere trovato su GitHub.