Come rendere imbattibile il tuo gioco Tic Tac Toe utilizzando l'algoritmo minimax

Ho lottato per ore scorrendo tutorial, guardando video e sbattendo la testa sulla scrivania cercando di costruire un gioco imbattibile Tic Tac Toe con un'intelligenza artificiale affidabile. Quindi, se stai attraversando un viaggio simile, vorrei presentarti l'algoritmo Minimax.

Come un giocatore di scacchi professionista, questo algoritmo vede qualche passo avanti e si mette nei panni del suo avversario. Continua a giocare fino a quando non raggiunge una disposizione terminale del tabellone ( stato terminale ) con conseguente pareggio, vittoria o sconfitta. Una volta in uno stato terminale, l'IA assegnerà un punteggio positivo arbitrario (+10) per una vittoria, un punteggio negativo (-10) per una sconfitta o un punteggio neutro (0) per un pareggio.

Allo stesso tempo, l'algoritmo valuta le mosse che portano a uno stato terminale in base al turno dei giocatori. Sceglierà la mossa con il punteggio massimo quando è il turno dell'IA e sceglierà la mossa con il punteggio minimo quando è il turno del giocatore umano. Usando questa strategia, Minimax evita di perdere contro il giocatore umano.

Provalo tu stesso nel seguente gioco, preferibilmente utilizzando un browser Chrom.

Un algoritmo Minimax può essere meglio definito come una funzione ricorsiva che fa le seguenti cose:

  1. restituisce un valore se viene trovato uno stato terminale (+10, 0, -10)
  2. passare attraverso i posti disponibili sul tabellone
  3. chiama la funzione minimax su ogni punto disponibile (ricorsione)
  4. valutare i valori restituiti dalle chiamate di funzione
  5. e restituire il miglior valore

Se non conosci il concetto di ricorsione, ti consiglio di guardare questo video dal CS50 di Harvard.

Per comprendere appieno il processo di pensiero di Minimax, implementiamolo nel codice e guardiamolo in azione nelle due sezioni seguenti.

Minimax in Code

Per questo tutorial lavorerai su uno stato quasi finale del gioco mostrato nella figura 2 di seguito. Poiché minimax valuta ogni stato del gioco (centinaia di migliaia), uno stato near end ti permette di seguire più facilmente le chiamate ricorsive di minimax (9).

Per la figura seguente, supponiamo che l'IA sia X e il giocatore umano sia O.

Per lavorare più facilmente con la tavola Ti Tac Toe, dovresti definirla come un array con 9 elementi. Ogni elemento avrà il suo indice come valore. Questo tornerà utile in seguito. Poiché il tabellone sopra è già popolato con alcune mosse X e Y, definiamo il tabellone con le mosse X e Y già al suo interno ( origBoard ).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

Quindi dichiara le variabili aiPlayer e huPlayer e impostale rispettivamente su "X" e "O" .

Inoltre, è necessaria una funzione che cerchi combinazioni vincenti e restituisca true se ne trova una, e una funzione che elenchi gli indici dei posti disponibili nel tabellone.

/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }

Ora tuffiamoci nelle parti buone definendo la funzione Minimax con due argomenti newBoard e player . Quindi, è necessario trovare gli indici degli spot disponibili nel tabellone e impostarli su una variabile chiamata availSpots .

// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);

Inoltre, è necessario verificare gli stati del terminale e restituire un valore di conseguenza. Se O vince dovresti restituire -10, se X vince dovresti restituire +10. Inoltre, se la lunghezza dell'array availableSpots è zero, significa che non c'è più spazio per giocare, il gioco è risultato in pareggio e dovresti restituire zero.

 // checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

Successivamente, è necessario raccogliere i punteggi da ciascuno dei punti vuoti per valutarli in seguito. Pertanto, crea un array chiamato mosse e passa in rassegna i punti vuoti mentre raccogli l'indice e il punteggio di ogni mossa in un oggetto chiamato mossa .

Quindi, impostare il numero di indice dello spazio vuoto memorizzato come numero nell'origBoard sulla proprietà index dell'oggetto di spostamento . Successivamente, imposta lo spazio vuoto sul newboard sul giocatore corrente e chiama la funzione minimax con l'altro giocatore e il newboard appena modificato . Successivamente, si deve memorizzare l'oggetto derivato dalla minimax chiamata di funzione che include un punteggio struttura al punteggio di proprietà del movimento dell'oggetto.

Se la funzione minimax non trova uno stato terminale, continua ad andare in modo ricorsivo livello per livello più in profondità nel gioco. Questa ricorsione avviene fino a quando non raggiunge uno stato terminale e restituisce un punteggio superiore di un livello.

Infine, Minimax resetta newBoard di quanto era prima e spinge il movimento dell'oggetto al mosse matrice.

// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }

Quindi, l'algoritmo minimax deve valutare la migliore mossa in mosse matrice. Dovrebbe scegliere la mossa con il punteggio più alto quando sta giocando l'IA e la mossa con il punteggio più basso quando sta giocando l'umano. Pertanto, se il giocatore è aiPlayer , imposta una variabile chiamata bestScore su un numero molto basso e scorre l' array di mosse , se una mossa ha un punteggio più alto di bestScore , l'algoritmo memorizza quella mossa . In caso di mosse con punteggio simile, verrà memorizzata solo la prima.

Lo stesso processo di valutazione si verifica quando il giocatore è huPlayer , ma questa volta bestScore sarebbe impostato su un numero alto e Minimax cerca una mossa con il punteggio più basso da memorizzare.

Alla fine, Minimax restituisce l'oggetto memorizzato in bestMove .

// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i  bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }
Questo è tutto per la funzione minimax. :) puoi trovare l'algoritmo di cui sopra su github e codepen. Gioca con diverse schede e controlla i risultati nella console.

Nella prossima sezione, andiamo sul codice riga per riga per capire meglio come si comporta la funzione minimax data la scheda mostrata in figura 2.

Minimax in azione

Usando la figura seguente, seguiamo una per una le chiamate di funzione ( FC ) dell'algoritmo .

Nota: nella figura 3, i numeri grandi rappresentano ciascuna chiamata di funzione ei livelli si riferiscono a quanti passi avanti rispetto al gioco sta giocando l'algoritmo.

1. origBoard e aiPlayer vengono inviati all'algoritmo. L'algoritmo crea un elenco dei tre punti vuoti che trova, controlla gli stati dei terminali e scorre ogni punto vuoto a partire dal primo. Quindi, cambia il newBoard posizionando aiPlayer nel primo punto vuoto.Dopo di che,chiama se stesso con newBoard e huPlayer e attende che l'FC restituisca un valore.

2. While the first FC is still running, the second one starts by making a list of the two empty spots it finds, checks for terminal states, and loops through the empty spot starting from the first one. Then, it changes the newBoard by placing the huPlayer in the first empty spot.After thatit calls itself with newBoard and the aiPlayer and waits for the FC to return a value.

3. Finally the algorithm makes a list of the empty spots, and finds a win for the human player after checking for terminal states. Therefore, it returns an object with a score property and value of -10.

Poiché il secondo FC elencava due posti vuoti, Minimax cambia il nuovo tabellone posizionando huPlayer nel secondo posto vuoto. Quindi, si chiama da solo con la nuova scheda e aiPlayer .

4. L'algoritmo crea un elenco degli spazi vuoti e trova una vittoria per il giocatore umano dopo aver controllato gli stati terminali. Pertanto, restituisce un oggetto con una proprietà score e un valore di -10.

Sulla seconda FC l'algoritmo raccoglie i valori provenienti dai livelli inferiori (3 ° e 4 ° FC). Poiché il turno di huPlayer ha prodotto i due valori, l'algoritmo sceglie il più basso dei due valori. Poiché entrambi i valori sono simili, sceglie il primo e lo restituisce al primo FC. A questo punto il primo FC ha valutato il punteggio dello spostamento di aiPlayer nel primo spot vuoto. Successivamente, cambia il newBoard posizionando aiPlayer nel secondo posto vuoto. Quindi, chiama se stesso con newBoard e huPlayer .

5. Sul quinto FC, l'algoritmo fa un elenco degli spazi vuoti e trova una vittoria per il giocatore umano dopo aver controllato gli stati del terminale. Pertanto, restituisce un oggetto con una proprietà score e un valore di +10.

Dopodiché, il primo FC si sposta cambiando il newBoard e posizionando aiPlayer nel terzo spazio vuoto. Quindi, chiama se stesso con la nuova scheda e huPlayer .

6. Il 6 ° FC inizia facendo un elenco di due punti vuoti che trova, controlla gli stati dei terminali e scorre i due punti vuoti a partire dal primo. Quindi, cambia il newBoard posizionando huPlayer nel primo punto vuoto.Dopo di che,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

8. On the 8th FC,l'algoritmo crea un elenco vuoto di punti vuoti e trova una vittoria per aiPlayer dopo aver controllato gli stati del terminale. Pertanto, restituisce un oggetto con proprietà score e valore +10 di un livello superiore (7 ° FC).

Il 7 ° FC ha ricevuto solo un valore positivo dai livelli inferiori (8 ° FC). Poiché il turno di aiPlayer ha portato a quel valore, l'algoritmo deve restituire il valore più alto che ha ricevuto dai livelli inferiori. Pertanto, restituisce il suo unico valore positivo (+10) di un livello superiore (6 ° FC). Poiché il 6 ° FC elencava due posti vuoti, Minimax cambia newBoard posizionando huPlayer nel secondo posto vuoto. Quindi, si chiama con la nuova scheda e aiPlayer .

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

A questo punto, il 6 FC deve scegliere tra il punteggio (+10) che è stato inviato dal 7 ° FC (restituito originariamente dall'8 FC) e il punteggio (-10) restituito dal 9 ° FC. Poiché il turno di huPlayer ha prodotto quei due valori restituiti, l'algoritmo trova il punteggio minimo (-10) e lo restituisce verso l'alto come un oggetto contenente proprietà di punteggio e indice. Infine sono stati valutati tutti e tre i rami della prima FC (-10, +10, -10). Ma poiché il turno di aiPlayer ha prodotto quei valori, l'algoritmo restituisce un oggetto contenente il punteggio più alto (+10) e il suo indice (4).

Nello scenario precedente, Minimax conclude che spostare la X al centro del tabellone produce il miglior risultato. :)

Fine!

By now you should be able to understand the logic behind the Minimax algorithm. Using this logic try to implement a Minimax algorithm yourself or find the above sample ongithub or codepen and optimize it.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tuba Yilmaz, Rick McGavin, and Javid Askerovfor reviewing this article.