Comment rendre votre jeu Tic Tac Toe imbattable en utilisant l'algorithme Minimax

J'ai eu du mal pendant des heures à faire défiler des didacticiels, à regarder des vidéos et à me cogner la tête sur le bureau en essayant de créer un jeu Tic Tac Toe imbattable avec une intelligence artificielle fiable. Donc, si vous traversez un parcours similaire, je voudrais vous présenter l'algorithme Minimax.

Comme un joueur d'échecs professionnel, cet algorithme voit quelques pas en avant et se met dans la peau de son adversaire. Il continue à jouer jusqu'à ce qu'il atteigne une disposition terminale du tableau ( état terminal ) entraînant une égalité, une victoire ou une perte. Une fois dans un état terminal, l'IA attribuera un score arbitraire positif (+10) pour une victoire, un score négatif (-10) pour une perte, ou un score neutre (0) pour une égalité.

En même temps, l'algorithme évalue les mouvements qui mènent à un état terminal basé sur le tour des joueurs. Il choisira le coup avec le score maximum quand c'est le tour de l'IA et choisira le coup avec le score minimum quand c'est le tour du joueur humain. En utilisant cette stratégie, Minimax évite de perdre face au joueur humain.

Essayez-le par vous-même dans le jeu suivant en utilisant de préférence un navigateur Chrom.

Un algorithme Minimax peut être défini au mieux comme une fonction récursive qui effectue les opérations suivantes:

  1. renvoie une valeur si un état terminal est trouvé (+10, 0, -10)
  2. parcourir les places disponibles sur le plateau
  3. appeler la fonction minimax sur chaque spot disponible (récursivité)
  4. évaluer les valeurs renvoyées par les appels de fonction
  5. et renvoyer la meilleure valeur

Si vous êtes nouveau dans le concept de récursivité, je vous recommande de regarder cette vidéo du CS50 de Harvard.

Pour saisir complètement le processus de réflexion du Minimax, implémentons-le dans le code et voyons-le en action dans les deux sections suivantes.

Minimax dans le code

Pour ce didacticiel, vous travaillerez sur un état proche de la fin du jeu, illustré dans la figure 2 ci-dessous. Puisque minimax évalue chaque état du jeu (des centaines de milliers), un état proche de la fin vous permet de suivre plus facilement les appels récursifs de minimax (9).

Pour la figure suivante, supposons que l'IA est X et que le joueur humain est O.

Pour travailler plus facilement avec la planche Ti Tac Toe, vous devez la définir comme un tableau avec 9 éléments. Chaque élément aura son index comme valeur. Cela vous sera utile plus tard. Parce que le tableau ci-dessus est déjà peuplé de quelques mouvements X et Y, définissons le tableau avec les mouvements X et Y déjà dedans ( origBoard ).

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

Ensuite, déclarez les variables aiPlayer et huPlayer et définissez-les respectivement sur «X» et «O» .

De plus, vous avez besoin d'une fonction qui recherche les combinaisons gagnantes et renvoie true si elle en trouve une, et d'une fonction qui répertorie les index des emplacements disponibles dans le tableau.

/* 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; } }

Passons maintenant aux bonnes parties en définissant la fonction Minimax avec deux arguments newBoard et player . Ensuite, vous devez trouver les index des places disponibles dans le tableau et les définir sur une variable appelée availableSpots .

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

En outre, vous devez vérifier les états terminaux et renvoyer une valeur en conséquence. Si O gagne, vous devez renvoyer -10, si X gagne, vous devez renvoyer +10. De plus, si la longueur du availableSpots tableau est zéro, cela signifie qu'il n'y a plus de place pour jouer, le jeu a entraîné une cravate, et vous devez revenir à zéro.

 // 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}; }

Ensuite, vous devez collecter les scores de chacun des emplacements vides pour les évaluer plus tard. Par conséquent, créez un tableau appelé moves et parcourez les espaces vides tout en collectant l'index et le score de chaque mouvement dans un objet appelé move .

Ensuite, définissez le numéro d'index de l'emplacement vide qui a été stocké sous forme de nombre dans l' origBoard sur la propriété index de l' objet de déplacement . Plus tard, définissez l'emplacement vide sur le newboard sur le joueur actuel et appelez la fonction minimax avec un autre joueur et le newboard nouvellement changé . Ensuite, vous devez stocker l'objet résultant de l' appel de fonction minimax qui inclut une propriété score dans la propriété score de l' objet move .

Si la fonction minimax ne trouve pas d'état terminal, elle continue de progresser de manière récursive niveau par niveau plus profondément dans le jeu. Cette récursivité se produit jusqu'à ce qu'elle atteigne un état terminal et renvoie un score d'un niveau supérieur.

Enfin, Minimax réinitialise newBoard à ce qu'il était avant et pousse l' objet move dans le tableau moves .

// 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); }

Ensuite, l'algorithme minimax doit évaluer le meilleur mouvement dans le tableau des mouvements . Il doit choisir le coup avec le score le plus élevé lorsque l'IA joue et le coup avec le score le plus bas lorsque l'humain joue. Par conséquent, si le joueur est aiPlayer , il définit une variable appelée bestScore sur un nombre très faible et parcourt le tableau des mouvements , si un mouvement a un score plus élevé que bestScore , l'algorithme stocke ce mouvement . Dans le cas où il y a des coups avec un score similaire, seul le premier sera enregistré.

Le même processus d'évaluation se produit lorsque le joueur est huPlayer , mais cette fois bestScore sera réglé sur un nombre élevé et Minimax recherche un coup avec le score le plus bas à stocker.

À la fin, Minimax renvoie l'objet stocké dans 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]; }
C'est tout pour la fonction minimax. :) vous pouvez trouver l'algorithme ci-dessus sur github et codepen. Jouez avec différents tableaux et vérifiez les résultats dans la console.

Dans la section suivante, passons en revue le code ligne par ligne pour mieux comprendre comment la fonction minimax se comporte avec le tableau illustré à la figure 2.

Minimax en action

En utilisant la figure suivante, suivons les appels de fonction de l'algorithme ( FC ) un par un.

Remarque: dans la figure 3, les grands nombres représentent chaque appel de fonction et les niveaux se réfèrent au nombre de pas avant le jeu auxquels l'algorithme est en train de jouer.

1. origBoard et aiPlayer sont fournis à l'algorithme. L'algorithme dresse une liste des trois emplacements vides qu'il trouve, vérifie les états terminaux et parcourt chaque emplacement vide en commençant par le premier. Ensuite, il change le newBoard en plaçant le aiPlayer dans le premier emplacement vide.Après ça,il s'appelle avec newBoard et huPlayer et attend que le FC renvoie une valeur.

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.

Puisque le deuxième FC a répertorié deux emplacements vides, Minimax change le newBoard en plaçant huPlayer dans le deuxième emplacement vide. Ensuite, il s'appelle avec la nouvelle carte et le aiPlayer .

4. L'algorithme fait une liste des emplacements vides et trouve une victoire pour le joueur humain après avoir vérifié les états terminaux. Par conséquent, il renvoie un objet avec une propriété score et une valeur de -10.

Sur le deuxième FC, l'algorithme collecte les valeurs provenant des niveaux inférieurs (3ème et 4ème FC). Puisque le tour de huPlayer a abouti aux deux valeurs, l’algorithme choisit la plus basse des deux valeurs. Parce que les deux valeurs sont similaires, il choisit la première et la renvoie au premier FC. À ce stade, le premier FC a évalué le score du déplacement de aiPlayer dans le premier emplacement vide. Ensuite, il change le newBoard en plaçant aiPlayer dans le deuxième emplacement vide. Ensuite, il s'appelle avec le newBoard et le huPlayer .

5. Sur le cinquième FC, l'algorithme fait une liste des emplacements vides, et trouve une victoire pour le joueur humain après avoir vérifié les états terminaux. Par conséquent, il renvoie un objet avec une propriété score et une valeur de +10.

Après cela, le premier FC passe à autre chose en changeant le newBoard et en plaçant aiPlayer dans le troisième emplacement vide. Ensuite, il s'appelle avec la nouvelle carte et le huPlayer .

6. Le 6e FC commence par dresser une liste de deux emplacements vides qu'il trouve, vérifie les états terminaux, et parcourt les deux emplacements vides en commençant par le premier. Ensuite, il change le newBoard en plaçant le huPlayer dans le premier emplacement vide.Après ça,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'algorithme crée une liste vide de points vides et trouve une victoire pour aiPlayer après avoir vérifié les états du terminal. Par conséquent, il renvoie un objet avec une propriété de score et une valeur de +10 d'un niveau supérieur (7e FC).

Le 7e FC n'a reçu qu'une valeur positive des niveaux inférieurs (8e FC). Puisque le tour de aiPlayer a abouti à cette valeur, l'algorithme doit renvoyer la valeur la plus élevée qu'il a reçue des niveaux inférieurs. Par conséquent, il renvoie sa seule valeur positive (+10) d'un niveau supérieur (6e FC). Depuis que le 6e FC a répertorié deux places vides, Minimax change newBoard en plaçant huPlayer dans la deuxième place vide. Ensuite, il s'appelle avec la nouvelle carte et le 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.

À ce stade, le 6 FC doit choisir entre le score (+10) qui a été envoyé depuis le 7e FC (retourné à l'origine du 8 FC) et le score (-10) renvoyé par le 9e FC. Puisque le tour de huPlayer a abouti à ces deux valeurs renvoyées, l'algorithme trouve le score minimum (-10) et le renvoie vers le haut sous la forme d'un objet contenant les propriétés de score et d'index. Enfin, les trois branches du premier FC ont été évaluées (-10, +10, -10). Mais comme le tour de aiPlayer a abouti à ces valeurs, l'algorithme renvoie un objet contenant le score le plus élevé (+10) et son index (4).

Dans le scénario ci-dessus, Minimax conclut que déplacer le X au milieu de la planche donne le meilleur résultat. :)

La fin!

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.