Intelligence artificielle

AI Sidewalk # 5: Tout sur Minimax!

AI Sidewalk # 5: Tout sur Minimax!


Configurations possibles du tableau de tic-tac-toe et de leurs scores associés

Le concept central derrière Minimax pour ce scénario avec deux agents est qu'un agent agira en tant que maximiseur (dans notre cas, le lecteur 'X' ou le processeur), tandis que l'autre agira en tant que minimiseur (dans notre cas, le lecteur 'O', ou l'utilisateur).

Passons en exemple sur la façon dont Minimax aide à décider quel mouvement le processeur doit effectuer:

L'algorithme global consiste essentiellement en deux étapes distinctes. Au cours de la première étape, l’algorithme descend dans l’arbre et attribue des «scores» pertinents à chacun des conseils à chaque niveau. Ensuite, la deuxième étape se propage vers le haut et choisit un mouvement en fonction du chemin global le plus élevé.

Phases de l'algorithme Minimax

Classe de Tic-Tac-Toe Board

Premièrement, nous pouvons simplement créer une classe simple pour initialiser des objets représentant les objets TicTacToeBoard que nous allons montrer dans notre interface utilisateur frontale. Il existe de nombreuses méthodes dans cette classe, dont certaines ne sont pas réellement utilisées dans le produit final. Ci-dessous l'extrait de code complet:

Passons en revue certaines des fonctions essentielles qui sont réellement utilisées dans notre produit final:

  • __init__: Initialise un tableau vide par 3 (de tous les zéros)
  • execute_turn: Prend un symbole, un numéro de ligne et un numéro de colonne et exécute le déplacement approprié sur l'objet de tableau en cours.
  • game_is_won: Résultats vrai si l’un des deux camps a gagné le match sur le tableau actuel. Sinon, renvoie false.
  • faire bouger: Pas le meilleur nom! Simule un déplacement sur une copie du tableau actuel et renvoie un nouveau tableau avec l'état résultant approprié.
  • get_possible_moves: Retourne un tableau de tuples sous la forme (row, col), chacun représentant un déplacement possible pouvant être effectué sur le tableau actuel.
  • Calculate_board_score: Calcule le score du tableau actuel. Ce score sera +10 si ‘X’ est en position gagnante sur le tableau actuel, ‘-10’ si ‘O’ est en position gagnante et ‘0’ si personne ne l’est.

Fichier App Tic-Tac-Toe Flask

En plus de la classe de conseil ci-dessus, nous avons un fichier d'application Flask avec certains de ses propres points de terminaison et fonctions pour permettre à notre interface (que nous créerons) d'appeler notre système. Le code correspondant est fourni ci-dessous:

Concentrons-nous sur les trois fonctions implémentant l’algorithme Minimax, car elles constituent la fonctionnalité principale de notre agent TicTacToe de niveau «dur»:

Fonction Minimax

C’est notre principale fonction minimax, et elle renvoie simplement le coup maximisant le score si le joueur IA est «X» et le coup minimisant le score si le joueur AI est «O». Mais dans le calcul des scores pour les coups individuels, il prend en compte tous les coups futurs que le joueur adverse ferait. Enfin, il renvoie le coup en produisant le meilleur score pour le joueur donné:

Fonction d'agent minimiseur

La première fonction d’aide utilisée par notre algorithme simule simplement l’agent de minimisation (dans notre cas, «O»). Notez que cette fonction appelle de manière récursive la fonction de maximiseur (qui représente «X»). Vous pouvez penser à cela comme tirer le meilleur parti de ce qui nous est donné. Par conséquent, dans cette fonction, nous essayons de trouver la moyenne des scores qui nous sont renvoyés par la fonction de maximisation, qui dans notre cas calcule en fait le plus élevé des scores du minimiseur précédemment renvoyés:

Fonction d'agent Maximizer

Il s’agit de la deuxième fonction d’aide principale utilisée par notre algorithme. Elle simule simplement l’agent maximiseur (dans notre cas, «X»). Notez que cette fonction appelle de manière récursive la fonction de minimiseur (qui représente «O»). Vous pouvez à nouveau penser à cela comme à tirer le meilleur parti de ce qui nous est donné. Par conséquent, dans cette fonction, nous essayons de trouver le score le plus élevé des scores qui nous sont renvoyés par la fonction minimiseur, qui dans notre cas calcule en fait la moyenne des scores calculés du minimiseur:

Essayons de produire notre modèle de base afin qu’il soit plus accessible aux utilisateurs! Nous pouvons utiliser certains codes HTML et CSS de base pour cela, tout en respectant la structure de répertoires de projets standard de Flask.

Structure de répertoire de haut niveau

Dans notre cas, la structure des répertoires est assez simple, constituée de deux dossiers différents, en plus de nos deux fichiers précédents:

  • dossier statique: Ce dossier contient les fichiers CSS que nous allons utiliser
  • dossier de modèles: Cela comprend tous les fichiers HTML que nous allons utiliser

Démo

Voici une simple démonstration pour montrer à quoi peut ressembler un produit final. Il a exactement le même backend que dans le dépôt Github associé, et a été hébergé sur Heroku @ calm-brook-53734.herokuapp.com

Notez que pour la démo, il existe deux difficultés différentes auxquelles les utilisateurs peuvent jouer, Easy et Hard. Il s’agit principalement de montrer la différence qualitative de performance entre une approche de déplacement aléatoire et une approche minimax!

Code

Tout le code associé (y compris les bits frontaux!) Peut être trouvé @ https://github.com/ShantanuPhadke/AI-Sidewalk/tree/master/5_Minimax

Nous remercions https://www.pexels.com/@jeshoots-com-147458.

Nous avons bien couvert de bonnes choses dans cet article! Mais comme on dit, ce n’est que la pointe de l’iceberg. Nous avons implémenté un agent Minimax légèrement modifié sur le jeu de plateau relativement simple de Tic-Tac-Toe (qui est simple en ce sens que la taille de son espace d'état est relativement petite). Maintenant que vous connaissez les bases, imaginez tous les autres jeux pour lesquels vous pouvez créer des agents! Au début, cela peut sembler complexe, mais le processus de base se décompose en 2 à 4 étapes, en fonction de ce que vous souhaitez accomplir:

(1) Trouvez un moyen de représenter les états du jeu en question.

(2) Créez un arbre (ou un graphique) de tous les différents états possibles du jeu en question et effectuez une recherche intelligente dans cet espace d’états pour déterminer le meilleur coup à suivre pour votre IA.

(3) En tant qu’add-on (2), accélérez votre intelligence artificielle en «supprimant» les parties de l’espace d’état qui n’ont pas besoin d’être explorées. Un exemple de technique de taille s'appelle Taille alpha-bêta.

(4) Produisez votre IA de manière à ce que le public visé puisse facilement jouer contre elle!

Afficher plus

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Articles similaires

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Bouton retour en haut de la page
Fermer