Tic Tac Toe sur Arduino avec AI (algorithme Minimax): 3 étapes

2024 Auteur: John Day | [email protected]. Dernière modifié: 2024-01-30 09:09

Dans ce Instructable, je vais vous montrer comment créer un jeu de Tic Tac Toe avec une IA à l'aide d'un Arduino. Vous pouvez soit jouer contre l'Arduino, soit regarder l'Arduino jouer contre lui-même.

J'utilise un algorithme appelé "algorithme minimax", qui peut être utilisé non seulement pour créer une IA pour Tic Tac Toe, mais aussi pour une variété d'autres jeux comme Four in a Row, les dames ou même les échecs. Des jeux comme les échecs sont très complexes et nécessitent des versions beaucoup plus raffinées de l'algorithme. Pour notre jeu de Tic Tac Toe, nous pouvons utiliser la version la plus simple de l'algorithme, qui n'en est pas moins assez impressionnante. En fait, l'IA est si bonne qu'il est impossible de battre l'Arduino !

Le jeu est facile à construire. Vous n'avez besoin que de quelques composants et du croquis que j'ai écrit. J'ai également ajouté une explication plus détaillée de l'algorithme, si vous voulez comprendre son fonctionnement.

Étape 1: Construisez et jouez

Pour construire le jeu Tic Tac Toe, vous aurez besoin des composants suivants:

• Un Arduino Uno
• 9 LED RVB WS2812
• 9 boutons poussoirs
• quelques fils et câbles de démarrage

Câblez les composants comme indiqué dans le croquis Fritzing. Ensuite, téléchargez le code sur votre Arduino.

Par défaut, l'Arduino prend le premier tour. Pour rendre les choses un peu plus intéressantes, le premier mouvement est choisi au hasard. Après le premier mouvement, l'Arduino utilise l'algorithme minimax pour déterminer le meilleur mouvement possible. Vous démarrez une nouvelle partie en réinitialisant l'Arduino.

Vous pouvez regarder l'Arduino "penser" en ouvrant le moniteur série. Pour chaque coup possible, l'algorithme calcule une cote qui indique si ce coup entraînera un gain (valeur de 10) ou une perte (valeur de -10) pour l'Arduino ou un match nul (valeur de 0).

Vous pouvez également regarder l'Arduino jouer contre lui-même en décommentant la ligne "#define DEMO_MODE" au tout début du croquis. Si vous téléchargez le croquis modifié, l'Arduino effectue le premier mouvement de manière aléatoire, puis utilise l'algorithme minimax pour déterminer le meilleur mouvement pour chaque joueur à chaque tour.

Notez que vous ne pouvez pas gagner contre l'Arduino. Chaque match se terminera par un match nul ou vous perdrez si vous faites une erreur. C'est parce que l'algorithme choisit toujours le meilleur coup possible. Comme vous le savez peut-être, une partie de Tic Tac Toe se terminera toujours par un match nul si les deux joueurs ne se trompent pas. En mode démo, chaque partie se termine par un match nul car, comme nous le savons tous, les ordinateurs ne font jamais d'erreurs;-)

Étape 2: L'algorithme Minimax

L'algorithme se compose de deux composants: une fonction d'évaluation et une stratégie de recherche. La fonction d'évaluation est une fonction qui attribue une valeur numérique aux postes du conseil. Si la position est une position finale (c'est-à-dire une position où le joueur bleu ou le joueur rouge a gagné ou où aucun joueur n'a gagné), la fonction d'évaluation est très simple: disons que l'Arduino joue en bleu et le joueur humain joue en rouge. Si la position est une position gagnante pour le bleu, la fonction attribue une valeur de 10 à cette position; s'il s'agit d'une position gagnante pour le rouge, la fonction attribue une valeur de -10 à la position; et si la position est un match nul, la fonction attribue une valeur de 0.

Quand c'est au tour de l'Arduino, il veut choisir un coup qui maximise la valeur de la fonction d'évaluation, car maximiser la valeur signifie qu'il préférera une victoire à un match nul (10 est supérieur à 0) et préférera un match nul à une défaite (0 est supérieur à -10). Par un argument analogue, l'adversaire veut jouer de telle manière qu'elle minimise la valeur de la fonction d'évaluation.

Pour une position non finale, l'algorithme calcule la valeur de la fonction d'évaluation par une stratégie de recherche récursive. Partant de la position actuelle, il simule alternativement tous les mouvements que le joueur bleu et le joueur rouge peuvent effectuer. Cela peut être visualisé sous forme d'arbre, comme dans le diagramme. Lorsqu'il arrive à une position finale, il commence à reculer, portant la valeur de la fonction d'évaluation du niveau de récursivité inférieur au niveau de récursivité supérieur. Il attribue le maximum (si dans l'étape de récursivité correspondante c'est le tour du joueur bleu) ou le minimum (si dans l'étape de récursivité correspondante c'est le tour du joueur rouge) des valeurs de la fonction d'évaluation du niveau de récursivité inférieur à la position sur le niveau de récursivité plus élevé. Enfin, lorsque l'algorithme a fini de reculer et est de nouveau arrivé à la position actuelle, il prend ce mouvement (ou l'un des mouvements) qui a la valeur de fonction d'évaluation maximale.

Cela peut sembler un peu abstrait, mais ce n'est en fait pas si difficile. Considérez la position indiquée en haut du diagramme. Dans la première étape de récursivité, le bleu peut effectuer trois mouvements différents. Bleu essaie de maximiser la valeur de la fonction d'évaluation. Pour chacun des mouvements que le bleu peut effectuer, il y a deux mouvements que le rouge peut effectuer. Red essaie de minimiser la valeur de la fonction d'évaluation. Considérez le coup où le bleu joue dans le coin supérieur droit. Si rouge joue dans la case centrale, rouge a gagné (-10). Si, par contre, le rouge joue dans la case centrale du bas, le bleu gagnera au coup suivant (10). Ainsi, si le bleu joue dans le coin supérieur droit, le rouge jouera dans la case centrale, car cela minimise la valeur de la fonction d'évaluation. De même, si le bleu joue dans la case centrale du bas, le rouge jouera à nouveau dans la case centrale car cela minimise la fonction d'évaluation. Si, par contre, bleu joue dans la case centrale, peu importe le coup que prend rouge, bleu gagnera toujours (10). Puisque bleu veut maximiser la fonction d'évaluation, il jouera dans la case centrale, puisque cette position entraîne une valeur plus grande de la fonction d'évaluation (10) que les deux autres coups (-10).

Étape 3: Dépannage et étapes supplémentaires

Si vous appuyez sur un bouton et qu'une LED différente de celle correspondant au bouton s'allume, vous avez probablement soit mélangé les fils sur les broches A0-A2 ou 4-6, soit vous avez connecté les LED dans le mauvais ordre.

Notez également que l'algorithme ne choisit pas nécessairement toujours un mouvement qui permettra à l'Arduino de gagner le plus rapidement possible. En fait, j'ai passé du temps à déboguer l'algorithme car l'Arduino n'a pas choisi un mouvement qui aurait été un mouvement gagnant. Il m'a fallu un certain temps jusqu'à ce que je me rende compte qu'il avait plutôt choisi un coup qui garantissait qu'il gagnerait un coup plus tard. Si vous le souhaitez, vous pouvez essayer de modifier l'algorithme afin qu'il préfère toujours un coup gagnant à un gain ultérieur.

Une extension possible de ce projet serait d'utiliser l'algorithme pour construire une IA pour un 4x4 ou même un 5x5 Tic Tac Toe. Cependant, notez que le nombre de positions que l'algorithme doit examiner augmente très rapidement. Vous devrez trouver des moyens de rendre la fonction d'évaluation plus intelligente en attribuant des valeurs aux positions qui ne sont pas définitives, en fonction de la probabilité que la position soit bonne ou mauvaise pour le joueur en question. Vous pouvez également essayer de rendre la recherche plus intelligente en arrêtant la récursivité plus tôt si un mouvement s'avère moins digne d'une exploration plus approfondie que des mouvements alternatifs.

L'Arduino n'est probablement pas la meilleure plate-forme pour de telles extensions en raison de sa mémoire limitée. La récursivité permet à la pile de croître pendant l'exécution du programme, et si la pile croît trop, elle peut corrompre la mémoire du programme, entraînant des plantages ou un comportement erratique. J'ai choisi l'Arduino pour ce projet principalement parce que je voulais voir si cela pouvait être fait et à des fins éducatives, pas parce que c'est le meilleur choix pour ce genre de problème.