Intelligence artificielle des jeux de société : l'algorithme Minimax : 8 étapes

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

Vous êtes-vous déjà demandé comment sont fabriqués les ordinateurs contre lesquels vous jouez aux échecs ou aux dames ? Eh bien, ne cherchez pas plus loin que ce Instructable car il vous montrera comment créer une intelligence artificielle (IA) simple mais efficace à l'aide de l'algorithme Minimax ! En utilisant l'algorithme Minimax, l'IA effectue des mouvements bien planifiés et réfléchis (ou du moins imite un processus de réflexion). Maintenant, je pourrais juste vous donner le code de l'IA que j'ai créée, mais ce ne serait pas amusant. Je vais expliquer la logique derrière les choix de l'ordinateur.

Dans ce Instructable, je vais vous guider à travers les étapes sur la façon de faire une IA pour Othello (AKA Reversi) en python. Vous devez avoir une compréhension intermédiaire de la façon de coder en python avant de vous attaquer à ce projet. Voici quelques bons sites Web à consulter pour vous préparer à cet Instructable: w3schools ou learnpython. À la fin de ce Instructable, vous devriez avoir une IA qui effectuera des mouvements calculés et devrait être capable de vaincre la plupart des humains.

Étant donné que ce Instructable traitera principalement de la façon de créer une IA, je n'expliquerai pas comment concevoir un jeu en python. Au lieu de cela, je vais donner le code du jeu où un humain peut jouer contre un autre humain et le modifier pour que vous puissiez jouer à un jeu où un humain joue contre l'IA.

J'ai appris à créer cette IA grâce à un programme d'été à Columbia SHAPE. J'ai passé un bon moment là-bas, alors jetez un œil à leur site Web pour voir si vous seriez intéressé.

Maintenant que nous avons réglé la logistique, commençons à coder !

(J'ai mis quelques notes dans les images alors assurez-vous de les regarder)

Fournitures

C'est facile:

1) Ordinateur avec un environnement python tel que Spyder ou IDLE

2) Téléchargez les fichiers du jeu Othello depuis mon GitHub

3) Votre cerveau avec patience installé

Étape 1: Téléchargez les fichiers nécessaires

Lorsque vous accédez à mon GitHub, vous devriez voir 5 fichiers. Téléchargez les 5 et placez-les tous dans le même dossier. Avant de lancer le jeu, ouvrez tous les fichiers dans l'environnement Spyder.

Voici à quoi servent les fichiers:

1) othello_gui.py ce fichier crée le plateau de jeu sur lequel les joueurs peuvent jouer (humains ou informatiques)

2) othello_game.py ce fichier joue à deux ordinateurs l'un contre l'autre sans le plateau de jeu et n'affiche que le score et les positions de déplacement

3) ai_template.py c'est là que vous allez mettre tout votre code pour faire votre IA

4) randy_ai.py c'est une IA prédéfinie qui choisit ses mouvements au hasard

5) othello_shared.py un ensemble de fonctions prédéfinies que vous pouvez utiliser pour créer votre IA, par exemple pour vérifier les mouvements disponibles, le score ou l'état du tableau

6) Les trois autres fichiers: Puma.py, erika_5.py et nathan.py, réalisés par moi, Erika et Nathan respectivement à partir du programme SHAPE, ce sont trois IA différentes avec des codes uniques

Étape 2: Comment ouvrir et jouer à Python Othello

Une fois tous les fichiers ouverts, dans le coin inférieur droit de l'écran, tapez "run othello_gui.py" et appuyez sur Entrée dans la console IPython. Ou dans le terminal Mac, tapez "python othello_gui.py" (après vous êtes bien sûr dans le bon dossier). Ensuite, un tableau devrait apparaître sur votre écran. Ce mode est le mode humain contre humain. La lumière passe en second et l'obscurité en premier. Regardez ma vidéo si vous êtes confus. iEn haut, il y a le score de chaque tuile de couleur. Pour jouer, cliquez sur une case de déplacement valide pour y placer une tuile, puis donnez l'ordinateur à votre adversaire qui fera de même et recommencera.

Si vous ne savez pas jouer à Othello, lisez ces règles sur le site des ultra boards:

Noir se déplace toujours en premier. Un coup est effectué en plaçant un disque de la couleur du joueur sur le plateau dans une position qui "dépasse" un ou plusieurs disques de l'adversaire. Un disque ou une rangée de disques est débordé lorsqu'il est entouré aux extrémités de disques de couleur opposée. Un disque peut déborder n'importe quel nombre de disques sur une ou plusieurs rangées dans n'importe quelle direction (horizontale, verticale, diagonale)…. (finir la lecture sur leur site web)

La différence entre le jeu original et ce jeu python est que lorsqu'il n'y a plus de mouvements valides pour un joueur, le jeu se termine

Maintenant que vous pouvez jouer au jeu avec un ami, créons une IA avec laquelle vous pouvez jouer.

Étape 3: Algorithme Minimax: Génération de scénarios

Avant de parler de la façon d'écrire cela dans le code, passons en revue la logique qui la sous-tend. L'algorithme minimax est un algorithme de prise de décision et de retour en arrière et est généralement utilisé dans les jeux au tour par tour à deux joueurs. Le but de cette IA est de trouver le prochain meilleur coup et les meilleurs coups suivants jusqu'à ce qu'il gagne la partie.

Maintenant, comment l'algorithme déterminerait-il quel mouvement est le meilleur ? Arrêtez-vous et réfléchissez à la façon dont vous choisiriez le prochain mouvement. La plupart des gens choisiraient le coup qui leur donnerait le plus de points, n'est-ce pas ? Ou s'ils réfléchissaient à l'avenir, ils choisiraient le coup qui créerait une situation où ils pourraient gagner encore plus de points. Cette dernière façon de penser est la façon dont l'algorithme Minimax pense. Il anticipe toutes les futures configurations de tableau et effectue le mouvement qui conduirait au plus grand nombre de points.

J'ai appelé cela un algorithme de retour en arrière, car il commence par créer et évaluer tous les futurs états du tableau avec leurs valeurs associées. Cela signifie que l'algorithme jouera le jeu autant qu'il le souhaite (en effectuant les mouvements pour lui-même et pour l'adversaire) jusqu'à ce que chaque scénario du jeu ait été joué. Pour garder une trace de tous les états du tableau (scénarios), nous pouvons dessiner un arbre (regardez dans les images). L'arbre dans l'image ci-dessus est un exemple simple d'un jeu de Connect 4. Chaque configuration de plateau s'appelle un état de plateau et sa place sur l'arbre s'appelle un nœud. Tous les nœuds au bas de l'arbre sont les états finaux du plateau après avoir effectué tous les mouvements. De toute évidence, certains états du plateau sont meilleurs pour un joueur que pour l'autre. Donc, maintenant, nous devons faire en sorte que l'IA choisisse l'état de la carte auquel elle veut accéder.

Étape 4: Minimax: évaluation des configurations de carte

Pour donner des valeurs aux états du plateau, nous devons apprendre les stratégies du jeu auquel nous jouons: dans ce cas, les stratégies d'Othello. Parce que ce jeu est une bataille consistant à retourner les disques de l'adversaire et vos disques, les meilleures positions de disque sont celles qui sont stables et ne peuvent pas être retournées. Le coin, par exemple, est l'endroit où lorsqu'un disque est placé, il ne peut pas être changé pour l'autre couleur. Ainsi, cet endroit serait extrêmement précieux. D'autres bonnes positions incluent les côtés de la planche, ce qui vous permettrait de prendre beaucoup de pierres. Il y a plus de stratégies sur ce site.

Maintenant, nous pouvons attribuer des valeurs aux positions pour chaque conseil d'état du conseil. Lorsqu'une position est occupée par la pièce de l'IA, alors vous donnez un certain nombre de points en fonction de la position. Par exemple, un état de plateau où la pièce de l'IA est dans le coin, vous pouvez donner un bonus de 50 points, mais si c'était dans un endroit défavorable, la pièce peut avoir une valeur de 0. Après avoir pris en compte toutes les valeurs de les positions, vous attribuez une valeur à l'état du conseil. Par exemple, si l'IA a une pièce dans le coin, l'état du plateau peut avoir un score de 50 alors qu'un autre état du plateau avec la pièce de l'IA au milieu a un score de 10.

Il y a plusieurs façons de le faire, et j'ai trois heuristiques différentes pour évaluer les pièces du plateau. Je vous encourage à créer votre propre type d'heuristique. J'ai téléchargé trois IA différentes sur mon github par trois fabricants différents, avec trois heuristiques différentes: Puma.py, erika5.py, nathanh.py.

Étape 5: Algorithme Minimax: Choisir le meilleur coup

Maintenant, ce serait bien si l'IA pouvait simplement choisir tous les mouvements pour atteindre l'état du plateau avec le score le plus élevé. Mais rappelez-vous que l'IA choisissait également les mouvements de l'adversaire lorsqu'elle générait tous les états du plateau et si l'adversaire est intelligent, cela ne permettra pas à l'IA d'atteindre le score le plus élevé du plateau. Au lieu de cela, un adversaire intelligent ferait le pas pour que l'IA passe à l'état le plus bas du plateau. Dans l'algorithme, nous appelons les deux joueurs un joueur maximisant et un joueur minimisant. L'IA serait le joueur maximisant car elle veut obtenir le plus de points pour elle-même. L'adversaire serait le joueur minimisant puisque l'adversaire essaie de faire le coup où l'IA obtient le moins de points.

Une fois que tous les états des cartes sont générés et que des valeurs ont été attribuées aux cartes, l'algorithme commence à comparer les états des cartes. Dans les images, j'ai créé un arbre pour représenter comment l'algorithme choisirait ses mouvements. Chaque division dans les branches est un mouvement différent que l'IA ou l'adversaire peut jouer. À gauche des rangées de nœuds, j'ai écrit si le joueur maximisant ou minimisant allait. La rangée du bas contient tous les états du tableau avec leurs valeurs. À l'intérieur de chacun de ces nœuds se trouve un numéro et ce sont les scores que nous attribuons à chacun des tableaux: plus ils sont élevés, mieux c'est pour l'IA.

Définitions: nœud parent - un nœud qui résulte ou crée des nœuds en dessous; l'origine des nœuds enfants - les nœuds qui proviennent du même nœud parent

Les nœuds vides représentent le mouvement que l'IA effectuera pour atteindre le meilleur état de la carte. Cela commence par comparer les enfants du nœud le plus à gauche: 10, -3, 5. Puisque le joueur maximisant ferait le coup, il choisirait le coup qui lui donnerait le plus de points: 10. Donc, nous sélectionnons et stockons ensuite cela déplacez-vous avec le score du tableau et écrivez-le dans le nœud parent. Maintenant que 10 est dans le nœud parent, c'est maintenant au tour des joueurs qui minimisent. Cependant, le nœud auquel nous comparerions 10 est vide, nous devons donc d'abord évaluer ce nœud avant que le joueur minimisant puisse choisir. Nous revenons donc au tour du joueur maximisant et comparons les enfants du nœud adjacent: 8, -2. Maximiser choisira 8 et nous l'écrirons dans le nœud parent vide. Maintenant que l'algorithme a fini de remplir les espaces vides pour les enfants d'un nœud au-dessus, le joueur minimisant peut comparer ces enfants - 10 et 8 et choisir 8. L'algorithme répète ensuite ce processus jusqu'à ce que l'arbre entier soit rempli. À la fin de cet exemple, nous avons le score 8. C'est l'état du plateau le plus élevé auquel l'IA peut jouer en supposant que l'adversaire joue de manière optimale. L'IA choisira donc le premier coup qui mène à l'état 8 du plateau, et si l'adversaire joue de manière optimale, l'IA devrait jouer tous les coups pour arriver à l'état 8 du plateau. (Suivez les notes sur mes photos)

Je sais que c'était beaucoup. Si vous faites partie de ceux qui ont besoin que quelqu'un vous parle pour comprendre quelque chose, voici quelques vidéos que j'ai visionnées pour m'aider à comprendre l'idée derrière cela: 1, 2, 3.

Étape 6: Algorithme Minimax: Pseudocode

Après avoir compris la logique derrière l'algorithme minimax, jetez un œil à ce pseudocode (les fonctions qui sont universelles à tous les codes) de wikipedia:

la fonction minimax(node, profondeur, maximizingPlayer) est

si profondeur = 0 ou nœud est un nœud terminal alors

renvoie la valeur heuristique du nœud

si maximisantPlayer alors

valeur:= −∞

pour chaque enfant de nœud faire

valeur:= max(valeur, minimax(enfant, profondeur − 1, FAUX))

valeur de retour

else (* joueur minimisant *)

valeur:= +∞

pour chaque enfant de nœud faire

valeur:= min(valeur, minimax(enfant, profondeur − 1, VRAI))

valeur de retour

Il s'agit d'une fonction récursive, c'est-à-dire qu'elle s'appelle encore et encore jusqu'à ce qu'elle atteigne un point d'arrêt. Premièrement, la fonction prend trois valeurs, le nœud, la profondeur et à qui revient le tour. La valeur du nœud est l'endroit où vous voulez que le programme commence la recherche. La profondeur est la distance à laquelle vous voulez que le programme recherche. Par exemple, dans mon exemple d'arbre, il a une profondeur de 3, car il a recherché tous les états du plateau après 3 mouvements. Bien sûr, nous aimerions que l'IA vérifie chaque état de la carte et choisisse une victoire gagnante, mais dans la plupart des jeux où il existe des milliers, voire des millions de configurations de cartes, votre ordinateur portable à la maison ne pourra pas traiter toutes ces configurations. Ainsi, nous limitons la profondeur de recherche de l'IA et la faisons passer au meilleur état de la carte.

Ce pseudocode reproduit le processus que j'ai expliqué dans les deux étapes précédentes. Maintenant, allons plus loin et corrigeons cela dans le code python.

Étape 7: Créer votre IA avec Ai_template.py

Avant de jeter un œil à mon code Minimax AI, essayez de créer votre propre IA avec le fichier ai_template.py et le pseudo-code dont nous avons parlé à la dernière étape. Il y a deux fonctions dans le modèle ai appelées: def minimax_min_node(board, color) et def minimax_max_node(board, color). Au lieu d'appeler la fonction minimax elle-même de manière récursive, nous avons deux fonctions différentes, qui s'appellent l'une l'autre. Pour créer l'heuristique permettant d'évaluer les états de la carte, vous devrez créer votre propre fonction. Il y a des fonctions prédéfinies dans le fichier othello_shared.py que vous pouvez utiliser pour construire votre IA.

Une fois que vous avez votre IA, essayez de l'exécuter sur randy_ai.py. Pour exécuter deux ais l'un contre l'autre, tapez "python othello_gui.py (insert ai file name).py (insert file name).py" dans le terminal mac ou tapez "run othello_gui.py (insert ai file name).py (insérer le nom du fichier).py" et assurez-vous que vous êtes dans le bon répertoire. Aussi, regardez ma vidéo pour les étapes exactes.

Étape 8: Il est temps de faire combattre l'IA

Maintenant, obtenez un groupe de vos amis informaticiens et faites-leur concevoir leur propre IA ! Ensuite, vous pouvez organiser une compétition et faire en sorte que votre IA s'en sorte. Espérons que même si vous ne pouviez pas créer votre propre IA, vous pouviez comprendre le fonctionnement de l'algorithme minimax. Si vous avez des questions, n'hésitez pas à poster des questions dans les commentaires ci-dessous.