Implémentation de l'algorithme Minimax pour l'IA en Python
Apprenez à coder une IA imbattable au morpion en utilisant l'algorithme Minimax en Python. Ce tutoriel couvre la théorie, la mise en œuvre et l'optimisation, idéal pour les passionnés de l'IA dans les jeux.
L'algorithme Mini-Max a une riche histoire dans le domaine de l'IA, qui remonte aux années 1920. Bien que le terme "IA" n'ait pas été utilisé pour désigner les algorithmes informatiques à l'époque, l'algorithme fondateur a certainement donné certaines des premières indications sur la manière dont les machines pouvaient prendre des décisions optimales dans des scénarios contradictoires. L'algorithme a été formalisé pour la première fois par John von Neumann dans son article de 1928 intitulé "Zur Theorie der Gesellschaftsspiele" (Sur la théorie des jeux de stratégie), qui a jeté les bases de la théorie moderne des jeux et des algorithmes de prise de décision.
En 1997, Deep Blue d'IBM a battu le champion du monde d'échecs Garry Kasparov en utilisant les variantes avancées de Mini-max. Depuis lors, l'algorithme a servi de base à des approches plus sophistiquées telles que la recherche arborescente de Monte Carlo (MCTS) et l l'apprentissage par renforcement d'apprentissage par renforcement.
Dans cet article, nous ne reconstruirons pas le célèbre Deep Blue pour les échecs mais une version bien plus simple pour le morpion en Python. En cours de route, vous acquerrez une forte intuition sur le fonctionnement de l'algorithme et sur la manière de l'appliquer à des jeux réels plus complexes.
Qu'est-ce que l'algorithme Minimax ?
Minimax est généralement un algorithme de prise de décision pour les jeux à deux joueurs (comme les échecs, le morpion ou les dames). Il permet aux ordinateurs de planifier plusieurs mouvements tout en supposant que votre adversaire fera toujours le meilleur mouvement possible. Dans cette section, nous allons donner un aperçu de l'algorithme à travers l'exemple du morpion.
Aperçu de l'algorithme Minimax
Dans un morpion du monde réel, à chaque fois que c'est votre tour, vous essayez de faire le meilleur mouvement possible tout en supposant que votre adversaire jouera également de son mieux. C'est exactement ce que fait l'algorithme Minimax : il aide l'ordinateur à effectuer le meilleur mouvement possible en réfléchissant à l'avance à tous les mouvements possibles.
L'algorithme Minimax tire son nom de son fonctionnement :
"Mini" représente l'adversaire qui tente de minimiser votre score.
"Max" représente le fait que vous essayez de maximiser votre score.
Lorsque c'est votre tour, vous voulez jouer les coups qui vous donnent les meilleures chances de gagner (maximisation). Lorsque c'est au tour de votre adversaire, vous supposez qu'il jouera les coups qui vous donneront le pire résultat (minimiser).
L'importance de Minimax dans l'IA
La méthode Minimax est très importante en intelligence artificielle pour plusieurs raisons :
Il aide les ordinateurs à prendre des décisions intelligentes dans les jeux à deux joueurs.
C'est le fondement de nombreux systèmes modernes d'intelligence artificielle pour le jeu.
Il apprend aux ordinateurs à penser à l'avance et à planifier les déplacements.
Le plus intéressant ? Cette même idée est utilisée dans de nombreuses applications du monde réel :
Adversaires de l'IA dans les jeux vidéo
Jeux de stratégie comme les échecs et les dames
Même certains outils d'aide à la décision pour les entreprises
Le Minimax peut sembler compliqué, mais il s'agit simplement d'apprendre à un ordinateur à penser comme un joueur prudent qui prend en compte à la fois ses coups et ceux de son adversaire avant de prendre une décision.
Comprendre l'algorithme Minimax
Décrivons le fonctionnement de Minimax à l'aide d'un exemple simple de morpion. Imaginez que vous jouez le rôle de X et que l'ordinateur est O.
Comment pense l'ordinateur
Lorsque c'est le tour de l'ordinateur, il suit les étapes suivantes :
Examinez tous les mouvements possibles qu'il peut effectuer
Pour chaque mouvement, il imagine ce que vous pourriez faire ensuite
Il continue à réfléchir jusqu'à ce qu'il atteigne un point final (comme une victoire ou une égalité).
Il choisit le mouvement qui lui donne le plus de chances de gagner
Le score du jeu
L'ordinateur peut utiliser un système de notation simple :
+10 points si l'ordinateur gagne
-10 points si vous gagnez
0 point en cas d'égalité
Pensez-y comme à un arbre de possibilités :
En haut se trouve le plateau de jeu actuel
Chaque branche est un mouvement possible
En bas, vous trouverez tous les résultats possibles
Le tour de rôle
L'ordinateur passe d'un mode de pensée à l'autre :
1. Mode de maximisation (tour de l'ordinateur) :
Recherche les mouvements qui obtiennent le score le plus élevé
Tentative de victoire ou de match nul
2. Mode minimisation (tour du joueur) :
Suppose que vous ferez les mouvements qui obtiendront le score le plus bas.
Préparez vos déplacements dans les meilleures conditions
Un exemple simple
Disons que c'est le tour de l'ordinateur (X) dans ce jeu :
L'ordinateur va :
Vous voyez qu'il y a 3 emplacements vides à choisir
Pour chaque emplacement vide, il imagine tous les mouvements futurs possibles
Choisit le mouvement qui mène à son meilleur résultat
Dans ce cas, il devrait sélectionner le coin inférieur médian pour bloquer votre victoire.
Cette façon de penser à l'avance permet à l'ordinateur de jouer une partie parfaite de morpion à chaque fois !
Pseudocode de l'algorithme Minimax
Voyons comment écrire l'algorithme Minimax étape par étape. Ne vous inquiétez pas si vous êtes novice en matière de pseudocode - considérez-le comme un moyen d'écrire les étapes en langage clair avant de les transformer en code réel !
Explication étape par étape
La fonction Minimax a besoin de trois éléments principaux pour fonctionner :
Le plateau de jeu actuel
La profondeur (le nombre de coups d'avance que nous recherchons)
Qu'il s'agisse du tour du joueur maximisateur (ordinateur) ou du tour du joueur minimisateur (humain)
Voici à quoi ressemble le pseudocode de base :
function minimax(board, depth, isMaximizingPlayer):# First, check if the game is overif game is won:return+10if computer wins,-10if human wins
if game is tied:return0# If it's the computer's turn (maximizing)if isMaximizingPlayer:
bestScore =-infinity
for each empty spot on board:
make the move
score = minimax(board, depth +1, false)
undo the move
bestScore =max(score, bestScore)return bestScore
# If it's the human's turn (minimizing)else:
bestScore =+infinity
for each empty spot on board:
make the move
score = minimax(board, depth +1, true)
undo the move
bestScore =min(score, bestScore)return bestScorePropulsé par
Alors que la plupart des exemples de pseudocode se lisent en anglais et sont parfaitement compréhensibles, l'exemple ci-dessus est différent car il utilise la récursivité. On parle de récursivité lorsqu'une fonction s'appelle elle-même à plusieurs reprises pour résoudre un problème plus important. Imaginez que vous vous regardez dans un miroir qui reflète un autre miroir : vous voyez la même image répétée plusieurs fois, de plus en plus petite à chaque fois.
Dans notre algorithme Minimax, nous avons besoin de la récursivité parce que nous essayons d'examiner tous les mouvements futurs possibles dans le jeu. Chaque fois que la fonction s'appelle elle-même, elle examine le prochain mouvement qui pourrait se produire.
Cela nous aide à déterminer le meilleur mouvement en vérifiant toutes les possibilités de déroulement du jeu, comme un joueur très intelligent qui se dit "Si je fais ceci, alors ils pourraient faire cela, alors je pourrais faire ceci..." et ainsi de suite jusqu'à la fin du jeu. Pour en savoir plus sur la récursion, vous pouvez consulter notre tutoriel sur la récursion.
Exemple illustratif
Voyons comment cela fonctionne dans une situation de jeu simple :
1. Position de départ :
2. L'ordinateur réfléchit :
"Si je place X dans n'importe quel endroit vide..."
"Que ferait l'humain ensuite ?"
"Et que pourrais-je faire après cela ?"
"Quel mouvement me permet d'obtenir le meilleur score final ?
3. Pour chaque emplacement vide, l'ordinateur :
Fait un geste
Vérifie si le jeu est terminé
Si ce n'est pas le cas, imaginez le meilleur mouvement de l'homme.
Continue jusqu'à ce qu'il trouve une fin
Choisit le mouvement avec le score le plus élevé
Pensez-y comme aux échecs : vous pensez toujours "Si je bouge ici, ils bougeront là, puis je pourrai bouger ici...", mais l'ordinateur peut penser à TOUS les mouvements possibles en même temps !
L'intérêt de cet algorithme est qu'il trouve toujours le meilleur coup possible, en supposant que les deux joueurs jouent parfaitement. C'est comme si vous aviez une boule de cristal qui vous montre tous les futurs possibles du jeu !
Implémentation de Minimax pour le Tic-tac-toe, étape par étape
Dans cette section, nous allons construire une IA de morpion imbattable alimentée par l'algorithme Mini-max en Python pur. Nous décomposerons la mise en œuvre en étapes simples et expliquerons l'intuition derrière chacune d'entre elles et comment elles s'intègrent dans l'image globale du jeu.
Étape 1 : Définition d'une classe TicTacToe
Tout d'abord, nous définissons une classe qui contient toute la logique et les méthodes dont nous avons besoin pour jouer au morpion avec nos ordinateurs :
classTicTacToe:def__init__(self):# Initialize empty board (using ' ' for empty squares)
self.board =[" "for _ inrange(9)]
self.human_player ="O"
self.ai_player ="X"defprint_board(self):"""Print the current state of the board"""for i inrange(0,9,3):print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")if i <6:print("---------")defavailable_moves(self):"""Returns list of available moves (indices of empty squares)"""return[i for i, spot inenumerate(self.board)if spot ==" "]Propulsé par
Ci-dessus, la méthode __init__ initialise un nouveau plateau de jeu sous la forme d'une liste de 9 cases vides (représentées par les espaces " "), les indices 0 à 8 représentant les positions du plateau de gauche à droite, de haut en bas. Il met également en place deux symboles de joueur - "O" pour le joueur humain et "X" pour l'IA.
La méthode print_board permet de visualiser l'état actuel de la carte. Il imprime la grille 3x3 avec des lignes de séparation entre les rangées, montrant les mouvements de chaque joueur dans leurs positions respectives.
La méthodeavailable_moves renvoie une liste de tous les mouvements valides qui peuvent encore être effectués. Pour ce faire, il vérifie quelles positions du tableau sont encore vides (contiennent un espace " ") et renvoie leurs indices. Cela sera crucial pour que l'algorithme minimax sache quels mouvements il peut prendre en compte.
Ces méthodes constituent la base sur laquelle nous nous appuierons pour créer notre joueur IA à l'aide de l'algorithme minimax.
Testons-les rapidement :
>>> game = TicTacToe()>>> game.print_board()||---------||---------||>>> game.available_moves()[0,1,2,3,4,5,6,7,8]Propulsé par
Comme prévu, l'échiquier est vide pour le moment et tous les coups sont disponibles.
Étape 2 : Mise en place de méthodes pour effectuer un mouvement et vérifier l'état du plateau.
Ajoutons maintenant une méthode pour effectuer un déplacement :
classTicTacToe:...defmake_move(self, position, player):"""Make a move on the board"""if self.board[position]==" ":
self.board[position]= player
returnTruereturnFalsePropulsé par
Nous avons ajouté la méthodemake_move qui :
Prend une position (0-8) et un symbole de joueur ("X" ou "O") en entrée.
Vérifie si la position sélectionnée est vide (" ")
Si vide, place le symbole du joueur et renvoie True
Si la position est déjà prise, renvoie Faux sans effectuer de changement.
Effectuons quelques mouvements et vérifions les mouvements restants :
>>> game = TicTacToe()>>> game.make_move(0,"X")>>> game.make_move(1,"O")>>> game.print_board()
X | O |-----------||-----------||>>> game.available_moves()[2,3,4,5,6,7,8]Propulsé par
Le travail est bien fait. L'étape suivante consiste à ajouter une méthode permettant de vérifier si le tableau est plein :
classTicTacToe:...defis_board_full(self):"""Check if the board is full"""return" "notin self.boardPropulsé par
is_board_full est une méthode booléenne qui vérifie s'il reste des espaces vides sur le plateau.
Ensuite, nous ajoutons une méthode pour vérifier si un état gagnant est atteint :
classTicTacToe:...defcheck_winner(self):"""Check if there's a winner. Returns winner symbol or None"""# Check rowsfor i inrange(0,9,3):if self.board[i]== self.board[i +1]== self.board[i +2]!=" ":return self.board[i]# Check columnsfor i inrange(3):if self.board[i]== self.board[i +3]== self.board[i +6]!=" ":return self.board[i]# Check diagonalsif self.board[0]== self.board[4]== self.board[8]!=" ":return self.board[0]if self.board[2]== self.board[4]== self.board[6]!=" ":return self.board[2]returnNonePropulsé par
La méthode check_winner évalue l'état actuel du plateau de Tic-tac-toe pour déterminer s'il y a un gagnant. Il vérifie toutes les combinaisons gagnantes possibles :
1. Rangs (3 possibilités) :
Première ligne (indices 0,1,2)
Ligne médiane (indices 3,4,5)
Rangée inférieure (indices 6,7,8)
2. Colonnes (3 possibilités) :
Colonne de gauche (indices 0,3,6)
Colonne centrale (indices 1,4,7)
Colonne de droite (indices 2,5,8)
3. Diagonales (2 possibilités) :
De haut en bas à gauche et de bas en haut à droite (indices 0,4,8)
Du haut à droite au bas à gauche (indices 2,4,6)
Pour chaque combinaison, il vérifie si les trois positions contiennent le même symbole de joueur (X ou O) et ne sont pas des espaces vides. Si une combinaison gagnante est trouvée, elle renvoie le symbole du joueur gagnant. Si aucun gagnant n'est trouvé après avoir vérifié toutes les possibilités, il renvoie None.
Testons la fonction dans les États gagnants et non gagnants :
game = TicTacToe()# Winning state
game.make_move(0,"X")
game.make_move(1,"X")
game.make_move(2,"X")>>> game.print_board()
X | X | X
-----------||-----------||>>> game.check_winner()'X'
game = TicTacToe()# Non-winning state
game.make_move(0,"X")
game.make_move(1,"O")
game.make_move(2,"O")
game.make_move(3,"X")>>> game.print_board()
X | O | O
-----------
X ||-----------||>>> game.check_winner()isNoneTruePropulsé par
Enfin, nous ajoutons une autre méthode booléenne pour spécifier si le jeu est terminé ou non :
classTicTacToe:...defgame_over(self):"""Check if the game is over"""return self.check_winner()isnotNoneor self.is_board_full()Propulsé par
La méthode renvoie True si le gagnant est trouvé ou si le tableau est plein.
À ce stade, nous avons construit tous les mécanismes de base du jeu :
Le tableau est représenté par une liste de 9 carrés initialisés vides
print_board() affiche visuellement l'état actuel du jeu
available_moves() renvoie les indices des carrés vides
make_move() place le symbole d'un joueur sur le plateau de jeu
check_winner() examine les lignes, les colonnes et les diagonales pour gagner à chaque coup
is_board_full() détermine s'il ne reste aucun mouvement
game_over() combine le contrôle du vainqueur et le contrôle du tableau complet
Ces méthodes fournissent les bases nécessaires à la création d'un jeu jouable, en gérant toutes les opérations de base telles que l'exécution des mouvements et la détermination de l'état du jeu.
Vient maintenant la partie critique : donner à l'ordinateur le "cerveau" nécessaire pour jouer au jeu avec Minimax.
Étape 3 : Implémentation de Minimax pour le morpion
Maintenant, implémentons l'algorithme du jeu dans une nouvelle méthode :
classTicTacToe:...defminimax(self, depth, is_maximizing):"""
Minimax algorithm implementation
Returns the best score possible for the current board state
"""# Base cases
winner = self.check_winner()if winner == self.ai_player:return1if winner == self.human_player:return-1if self.is_board_full():return0Propulsé par
La fonction prend deux paramètres :
depth - Curse le nombre de niveaux de la récursion. Cela peut être utilisé pour limiter la profondeur de recherche pour les jeux très complexes, bien que pour le morpion nous n'ayons pas besoin de la limiter.
is_maximizing - Indicateur booléen indiquant si nous recherchons actuellement le score maximum (tour de l'IA) ou le score minimum (tour de l'homme). Cette procédure alterne avec chaque appel récursif au fur et à mesure que les joueurs se succèdent.
Dans le corps de la fonction, nous commençons par définir les cas de base : Si la partie est gagnée par l'IA (winner == ai_player), nous retournons 1 car c'est le meilleur résultat possible pour l'IA. Si l'humain gagne (winner == human_player), nous renvoyons -1 car il s'agit du pire résultat pour l'IA. Si le tableau est plein et qu'il n'y a pas de gagnant, nous retournons 0 pour un tirage au sort.
defminimax(self, depth, is_maximizing):...# if it is the maximizing player's turn (AI), we want to maximize the scoreif is_maximizing:
best_score =float("-inf")for move in self.available_moves():# Make a calculating move
self.board[move]= self.ai_player
# Recursively call minimax with the next depth and the minimizing player
score = self.minimax(depth +1,False)# Reset the move
self.board[move]=" "# Update the best score
best_score =max(score, best_score)return best_scorePropulsé par
Lorsque is_maximizing est True, nous simulons le tour de l'IA et nous voulons trouver le mouvement qui mène au score le plus élevé possible. Nous commençons par fixer best_score à l'infini négatif afin que tout score réel soit meilleur. Ensuite, pour chaque mouvement disponible, nous :
Placez temporairement le symbole de l'IA sur le plateau de jeu.
Évaluer récursivement ce qui se passerait si nous faisions ce mouvement en appelant minimax avec is_maximizing=False (puisque ce serait le tour de l'humain ensuite).
Annulez le déplacement temporaire pour rétablir l'état de la carte.
Gardez la trace du score le plus élevé que nous ayons vu jusqu'à présent en utilisant max()
Cela nous permet de vérifier tous les mouvements possibles de l'IA. Pour chaque coup, nous examinons ce qui pourrait se produire ensuite, jusqu'à ce que quelqu'un gagne ou que le jeu soit à égalité. Nous travaillons ensuite à rebours pour déterminer quel premier coup donne à l'IA la meilleure chance de gagner.
Maintenant, faisons la partie minimisation pour l'homme :
defminimax(self, depth, is_maximizing):...# if it is the maximizing player's turn (AI), we want to maximize the scoreif is_maximizing:...else:# if it is the minimizing player's turn (human), we want to minimize the score
best_score =float("inf")for move in self.available_moves():# Make a calculating move
self.board[move]= self.human_player
# Recursively call minimax with the next depth and the maximizing player
score = self.minimax(depth +1,True)# Reset the move
self.board[move]=" "# Update the best score
best_score =min(score, best_score)return best_scorePropulsé par
Lorsque is_maximizing est False, nous simulons le tour du joueur humain et nous voulons trouver le mouvement qui mène au score le plus bas possible (puisqu'un score élevé signifie que l'IA gagne). Nous partons de best_score comme d'une infinité positive, de sorte que tout score réel sera inférieur. Pour chaque mouvement disponible, nous :
Placez temporairement le symbole de l'homme sur le tableau.
Évaluer récursivement ce qui se passerait en appelant minimax avec is_maximizing=True (puisque ce serait le tour de l'IA ensuite).
Annulez le déplacement temporaire pour rétablir l'état de la carte.
Le cursus du score le plus bas que nous ayons connu avec l'utilisation de min()
Cela simule le joueur humain essayant de faire les meilleurs mouvements pour empêcher l'IA de gagner. L'humain souhaite minimiser le score car les scores positifs représentent des victoires de l'IA. En alternant les tours de maximisation et de minimisation, l'algorithme peut déterminer la séquence de mouvements optimale pour les deux joueurs.
Étape 4 : Trouver le meilleur mouvement pour l'IA à l'aide de Minimax
Maintenant que l'algorithme est prêt, nous avons besoin d'une autre méthode qui utilise la méthodeminimax pour déterminer le meilleur coup pour l'IA après chaque coup humain :
classTicTacToe:...defget_best_move(self):"""Find the best move for AI using minimax"""
best_score =float("-inf")
best_move =Nonefor move in self.available_moves():# Make a calculating move
self.board[move]= self.ai_player
# Recursively call minimax with the next depth and the minimizing player
score = self.minimax(0,False)# Reset the move
self.board[move]=" "# Update the best scoreif score > best_score:
best_score = score
best_move = move
return best_movePropulsé par
La méthode get_best_move est chargée de déterminer le déplacement optimal du joueur IA à l'aide de l'algorithme minimax. Il fonctionne de la manière suivante :
1. En commençant par l'infini négatif comme meilleur score et en ne choisissant aucun mouvement
2. Pour chaque mouvement disponible sur le plateau :
Placer temporairement le symbole de l'IA dans cette position
L'utilisation de minimax pour évaluer la qualité de ce coup en simulant le reste du jeu
Annuler le déménagement temporaire
Si ce mouvement conduit à un meilleur score que ce que nous avons vu précédemment, nous mettons à jour à la fois le meilleur score et le meilleur mouvement.
3. Retourner enfin le mouvement qui a permis d'obtenir le score le plus élevé
Cette approche garantit que l'IA choisira le coup qui lui donne les meilleures chances de gagner, en supposant que le joueur humain joue lui aussi de manière optimale. La méthode prend en compte tous les états de jeu futurs possibles et choisit la voie qui maximise les chances de l'IA tout en minimisant les chances de victoire de l'humain.
Testons-le sur un exemple d'état de jeu :
game = TicTacToe()# Make a couple of moves
game.make_move(0,"X")
game.make_move(1,"O")# Print the board>>> game.print_board()
X | O |---------||---------||>>> game.get_best_move()3# AI moves>>> game.make_move(3,"X")# I move>>> game.make_move(4,"O")>>> game.print_board()
X | O |---------
X | O |---------||# Get the best move for AI>>> game.get_best_move()6Propulsé par
Comme vous pouvez le voir, l'IA a trouvé la combinaison gagnante en se basant sur mes déplacements (il s'agissait d'un état factice, mais cela prouve que notre algorithme fonctionne).
Étape 5 : Mise en œuvre d'une boucle de jeu
Maintenant que nous avons implémenté et testé notre algorithme minimax, créons une boucle de jeu qui nous permettra de jouer contre l'IA.
classTicTacToe:...defplay_game(self):"""Main game loop"""print("Welcome to Tic Tac Toe!")print("You are 'O' and the AI is 'X'")print("Enter positions (0-8) as shown below:")print("0 | 1 | 2")print("---------")print("3 | 4 | 5")print("---------")print("6 | 7 | 8")print("\n")Propulsé par
La méthode play_game commence par afficher un message de bienvenue et des instructions au joueur. Il montre que le joueur humain utilise "O" et que l'IA utilise "X". Il imprime ensuite une grille numérotée (0-8) pour indiquer au joueur quel numéro correspond à quelle position sur le plateau. Il est ainsi facile pour les joueurs de savoir exactement quel chiffre saisir pour le coup qu'ils souhaitent effectuer.
# ... the rest of the classdefplay_game(self):...# Randomly decide who goes firstimport random
ai_turn = random.choice([True,False])whilenot self.game_over():
self.print_board()if ai_turn:print("\nAI's turn...")
move = self.get_best_move()
self.make_move(move, self.ai_player)else:whileTrue:try:
move =int(input("\nYour turn (0-8): "))if0<= move <=8and self.make_move(move, self.human_player):breakelse:print("Invalid move! Try again.")except ValueError:print("Please enter a number between 0 and 8!")
ai_turn =not ai_turnPropulsé par
Après avoir affiché les instructions initiales, le jeu entre dans sa boucle principale. Le jeu décide de manière aléatoire qui commence - l'IA ou le joueur humain - en utilisant random.choice([True, False]). Cela crée un élément d'équité et d'imprévisibilité au début de chaque partie.
La boucle principale du jeu se poursuit jusqu'à ce que game_over() renvoie True (quelqu'un a gagné ou le plateau est plein). Pendant chaque tour, l'état actuel du plateau est affiché à l'aide de print_board().
Si c'est le tour de l'IA (ai_turn est True), le programme :
Imprime un message indiquant que l'IA est en train de réfléchir
Appelle get_best_move() pour déterminer le mouvement optimal à l'aide de l'algorithme minimax.
Effectue le déplacement en plaçant le symbole de l'IA ("X") à la position choisie.
Si c'est le tour de l'humain (ai_turn est Faux), le programme :
1. Entre dans une boucle pour obtenir des données valides de la part du joueur2. Demande un numéro de déplacement entre 0 et 83. Valide l'entrée est :
Un entier valide (en utilisant try/except)
Dans la plage de validité 0-8
Indique une position vide sur le tableau
4. Continue à demander jusqu'à ce qu'une entrée valide soit reçue. Effectue le déplacement en plaçant le symbole du joueur ("O") à la position choisie.
Après chaque tour, ai_turn est retourné à l'aide de not pour alterner entre les joueurs. Cela crée le flux de va-et-vient du jeu, chaque joueur jouant à tour de rôle jusqu'à ce que quelqu'un gagne ou que le jeu se termine par un match nul.
La validation des entrées garantit que le jeu ne peut pas se bloquer à cause d'une entrée invalide de l'utilisateur et fournit des messages d'erreur utiles pour guider le joueur afin qu'il entre les mouvements corrects. Cela permet de créer une expérience de jeu robuste et conviviale.
defplay_game(self):...# Game over
self.print_board()
winner = self.check_winner()if winner == self.ai_player:print("\nAI wins!")elif winner == self.human_player:print("\nCongratulations! You win!")else:print("\nIt's a tie!")Propulsé par
Lorsque le jeu se termine, l'état final du plateau est affiché à l'aide de print_board() et le gagnant est déterminé par check_winner(). Le jeu peut se terminer de trois façons :
L'IA gagne - Si check_winner() renvoie le symbole de l'IA ('X'), cela indique que l'IA a obtenu une ligne gagnante.
L'homme gagne - Si check_winner() renvoie le symbole de l'homme ('O'), cela indique que le joueur a obtenu une ligne gagnante.
Tirage au sort/égalité - Si aucun des deux joueurs n'a gagné mais que le plateau est plein, ce qui signifie qu'aucun autre coup n'est possible.
Le message approprié s'affiche pour annoncer le résultat du jeu. Cela permet au joueur de savoir clairement comment le jeu s'est terminé.
Étape 6 : Tout mettre en place
Il est maintenant temps de mettre tout le code que nous avons écrit jusqu'à présent dans un script Python avec ce qui suit if/main à la toute fin :
# Start the gameif __name__ =="__main__":
game = TicTacToe()
game.play_game()Propulsé par
Cela permet au jeu de démarrer dès que vous exécutez le script avec python script.py. Si vous vous êtes perdu parmi toutes les explications et les blocs de code, vous pouvez trouver le code complet du jeu dans ce GitHub gist.
Voici un exemple de jeu auquel j'ai participé :
❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O'and the AI is'X'
Enter positions (0-8)as shown below:0|1|2---------3|4|5---------6|7|8||---------||---------||
Your turn (0-8):4||---------| O |---------||
AI's turn...
X ||---------| O |---------||
Your turn (0-8):5
X ||----------| O | O
----------||
AI's turn...
X ||---------
X | O | O
---------||
Your turn (0-8):6
X ||---------
X | O | O
---------
O ||
AI's turn...
X || X
---------
X | O | O
---------
O ||
Your turn (0-8):1
X | O | X
---------
X | O | O
---------
O ||
AI's turn...
X | O | X
---------
X | O | O
---------
O | X |
Your turn (0-8):8
X | O | X
---------
X | O | O
---------
O | X | O
It's a tie!Propulsé par
N'oubliez pas que le morpion étant un jeu simple, vous n'avez aucune chance de battre l'IA. Soit vous êtes à égalité, soit vous perdez !
Formalisation de l'algorithme mini-maxi
Examinons maintenant la définition générale d'un algorithme au-delà de l'exemple simple du morpion.
L'algorithme Minimax peut être formellement défini comme une fonction récursive qui évalue les positions dans un jeu à somme nulle. Décortiquons ses composants formels et ses propriétés.
Définition mathématique
Pour un état de jeu s, la valeur minimax V(s) est définie comme suit :
V(s)=
utility(s)if s is terminal
max(V(s')) for all s'in S if player = MAX
min(V(s')) for all s'in S if player = MINPropulsé par
Où ?
s' représente les états successeurs de s
S est l'ensemble de tous les mouvements légaux à partir de l'état s
utility(s) est la fonction d'évaluation des états terminaux
Propriétés principales
1. Une information parfaite
Tous les joueurs ont une connaissance complète de l'état du jeu
Pas d'informations cachées ni d'éléments fortuits
Résultats déterministes
2. La nature à somme nulle
Le gain d'un joueur est exactement égal à la perte de l'autre joueur.
La somme des utilités de tous les joueurs est toujours égale à zéro
Pour les jeux à deux joueurs, les utilités sont généralement {-1, 0, 1}
3. Jeu optimal
On suppose que les deux joueurs prennent des décisions optimales
Garantit le meilleur résultat possible en cas de jeu parfait
Conduit à un équilibre de Nash en termes de théorie des jeux.
Analyse de la complexité
Complexité temporelle : O(b^m)
b = facteur de branchement (nombre de coups légaux à chaque état)
m = profondeur maximale de l'arbre de jeu
Complexité de l'espace : O(bm)
Nécessite le stockage de l'état du jeu à chaque niveau
Peut être optimisé par un approfondissement itératif
Fonction d'évaluation
Pour les états non terminaux, la fonction d'évaluation f(s) doit :
Corrélation avec la probabilité de gagner
Être efficace sur le plan informatique
Maintenir une échelle cohérente tout au long du jeu
La définition formelle :
f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ
Où ?
wᵢ sont les poids des différentes caractéristiques
xᵢ sont les valeurs des caractéristiques de l'état du jeu
n est le nombre de caractéristiques évaluées
Garantie d'optimalité
L'algorithme Minimax garantit un jeu optimal dans ces conditions :
Une information parfaite
Résultats déterministes
Recherche complète des états terminaux
Évaluation précise de l'état des terminaux
Il est donc particulièrement adapté aux jeux d'échecs, de morpion et de dames, pour lesquels ces conditions sont remplies.
Variantes avancées et limites
Si Minimax est parfait pour les jeux simples comme le morpion, il rencontre quelques problèmes avec les jeux plus importants. Voyons comment nous pouvons l'améliorer et quels sont ses points faibles.
Rendre Minimax plus rapide : Taille alpha-bêta
Imaginez que vous jouez aux échecs et que vous réfléchissez à vos mouvements. Si vous avez trouvé un coup gagnant, vous n'avez pas besoin de vérifier tous les autres coups possibles, n'est-ce pas ? L'élagage alpha-bêta fonctionne de la même manière - il aide l'ordinateur à ne pas vérifier les mouvements dont nous savons déjà qu'ils ne seront pas meilleurs que ceux que nous avons trouvés.
Pensez-y comme suit :
Vous cherchez la barre chocolatée la moins chère
Vous avez 1 $ à dépenser
Si vous trouvez une barre chocolatée à 50 cents, vous pouvez ne pas regarder les barres chocolatées qui coûtent plus d'un dollar.
Cela vous permet de gagner du temps !
Limites de profondeur : Ne pas regarder trop loin
Dans les grands jeux comme les échecs, il y a trop de mouvements possibles pour les vérifier tous. Nous ajoutons donc une limite de profondeur :
Ne regardez que 4 ou 5 coups à l'avance au lieu de regarder jusqu'à la fin.
Faites une bonne estimation de la qualité de la position à ce moment-là.
Choisissez le meilleur mouvement en fonction de ces suppositions
Vous ne pouvez pas planifier tous vos mouvements jusqu'à la fin de la partie, mais vous pouvez le faire quelques fois à l'avance !
Là où Minimax se bat
Minimax n'est pas parfait. Voici ses principaux problèmes :
1. Trop de choix
Les jeux comme le Go ont beaucoup trop de mouvements possibles
Même les ordinateurs rapides ne peuvent pas tous les vérifier
C'est pourquoi nous avons besoin d'autres méthodes pour les jeux vraiment complexes
2. Problèmes de temps
Plus vous regardez vers l'avant, plus cela prend du temps.
Aux échecs, les ordinateurs ne peuvent pas examiner tous les coups possibles
Ils doivent faire preuve d'intelligence dans le choix des mouvements à vérifier
3. Pas terrible pour les jeux incertains
Le Minimax fonctionne mieux lorsque vous pouvez tout voir
Il n'est pas adapté aux jeux de cartes où vous ne savez pas quelles sont les cartes des autres.
Il ne peut pas bien gérer les événements aléatoires (comme les jets de dés).
Des solutions modernes
L'IA des jeux d'aujourd'hui combine souvent le Minimax avec d'autres techniques intéressantes :
1. Apprentissage automatique
Les ordinateurs peuvent apprendre en regardant de nombreux jeux
Cela leur permet de mieux deviner les bons coups.
Des jeux comme AlphaGo utilisent cette méthode pour battre des champions humains.
2. Reconnaissance des formes
Au lieu de vérifier chaque mouvement, recherchez des modèles
Tout comme les joueurs humains reconnaissent les bons coups
L'ordinateur est ainsi beaucoup plus rapide
3. Banque de mémoire
Se souvenir de positions déjà vues
Ne perdez pas de temps à calculer deux fois la même chose
C'est comme si vous disposiez d'une antisèche de bons gestes !
Le plus intéressant ? Ces améliorations permettent aux ordinateurs de jouer à des jeux presque aussi bien que les humains, et parfois même mieux ! Mais n'oubliez pas que même avec tous ces ajouts fantaisistes, Minimax reste la base qui permet à tout de fonctionner.
Conclusion
Dans ce tutoriel, nous avons exploré l'algorithme Minimax depuis ses concepts de base jusqu'à sa mise en œuvre pratique. Voici ce que nous avons appris :
1. Concepts de base
Comment Minimax aide les ordinateurs à prendre des décisions dans les jeux
La différence entre les joueurs qui minimisent et ceux qui maximisent
Pourquoi on parle de "minimax" et comment cela fonctionne-t-il ?
2. Compétences en matière de mise en œuvre
Construire un jeu de morpion à partir de zéro
Écrire l'algorithme Minimax en Python
Test et débogage de la logique du jeu
3. Thèmes avancés
Rendre l'algorithme plus rapide grâce à l'élagage Alpha-Beta
Gestion des limitations dans les jeux complexes
Améliorations modernes grâce à l'apprentissage automatique
Quelle est la prochaine étape ?
L'algorithme Minimax n'est qu'une pièce du puzzle de l'IA. Si vous souhaitez en savoir plus sur l'IA et les algorithmes, voici quelques ressources intéressantes pour poursuivre votre voyage :
N'oubliez pas que, que vous construisiez un simple jeu ou un système d'intelligence artificielle complexe, la compréhension d'algorithmes tels que Minimax vous donne une base solide pour aborder des sujets plus avancés en matière d'intelligence artificielle. Continuez à vous entraîner, à apprendre et, surtout, à coder !
FAQ sur l'algorithme Minimax
Dans quelle mesure est-il difficile de comprendre et de mettre en œuvre l'algorithme Minimax ?⌄
L'algorithme Minimax est relativement simple à comprendre, en particulier lorsqu'il est mis en œuvre pour des jeux simples comme le morpion. Si le concept de récursivité peut être difficile à comprendre pour les débutants, le principe de base qui consiste à alterner les mouvements de maximisation et de minimisation est intuitif. Ce tutoriel décompose la mise en œuvre en étapes gérables, ce qui la rend accessible aux programmeurs ayant des connaissances de base en Python.
Puis-je utiliser cet algorithme pour d'autres jeux que le morpion ?⌄
Oui, l'algorithme Minimax peut être adapté à de nombreux jeux à deux joueurs, à somme nulle et à information parfaite, tels que les échecs, les dames ou Connect Four. Toutefois, pour les jeux plus complexes, vous devrez mettre en œuvre des optimisations supplémentaires telles que l'élagage Alpha-Beta et la limitation de la profondeur, car le nombre de mouvements possibles augmente de manière exponentielle.
Comment l'IA peut-elle ne jamais perdre au morpion ?⌄
L'algorithme Minimax fonctionne en simulant tous les états de jeu futurs possibles et en choisissant les mouvements qui conduisent au meilleur résultat possible. Dans un jeu simple comme le morpion, il y a relativement peu de mouvements possibles, ce qui permet à l'IA de calculer le mouvement optimal dans chaque situation. Le morpion étant un "jeu résolu", un jeu parfait des deux parties aboutit toujours à un match nul, ce qui explique pourquoi l'IA ne peut jamais perdre.
Quelles connaissances préalables dois-je avoir pour suivre ce tutoriel ?⌄
Vous devez avoir des connaissances de base en programmation Python, notamment :
Compréhension des fonctions et des classes
Familiarité avec les listes et les structures de données de base
Flux de contrôle de base (instructions if, boucles)
La compréhension de la récursivité est utile mais pas nécessaire, car le didacticiel explique le concept.
Pourquoi cet algorithme est-il important pour le développement de l'IA ?⌄
L'algorithme Minimax est fondamental pour comprendre la théorie des jeux et la prise de décision en IA. Il introduit des concepts importants tels que la recherche récursive dans les arbres, la pensée contradictoire et la prise de décision optimale en présence d'informations parfaites. Ces principes constituent la base d'algorithmes d'IA plus avancés utilisés dans des applications modernes, du jeu à la planification stratégique en passant par les systèmes d'aide à la décision.
Tutoriel complet d'introduction aux boucles Python. Apprenez et pratiquez les boucles while et for, les boucles imbriquées, les mots-clés break et continue, la fonction range et bien plus encore.
Découvrez les fondamentaux de l’IA, apprenez à l’utiliser efficacement dans votre travail et explorez les modèles d’IA pour vous repérer dans un domaine en constante évolution.
L'algorithme Mini-Max a une riche histoire dans le domaine de l'IA, qui remonte aux années 1920. Bien que le terme "IA" n'ait pas été utilisé pour désigner les algorithmes informatiques à l'époque, l'algorithme fondateur a certainement donné certaines des premières indications sur la manière dont les machines pouvaient prendre des décisions optimales dans des scénarios contradictoires. L'algorithme a été formalisé pour la première fois par John von Neumann dans son article de 1928 intitulé "Zur Theorie der Gesellschaftsspiele" (Sur la théorie des jeux de stratégie), qui a jeté les bases de la théorie moderne des jeux et des algorithmes de prise de décision.
En 1997, Deep Blue d'IBM a battu le champion du monde d'échecs Garry Kasparov en utilisant les variantes avancées de Mini-max. Depuis lors, l'algorithme a servi de base à des approches plus sophistiquées telles que la recherche arborescente de Monte Carlo (MCTS) et l l'apprentissage par renforcement d'apprentissage par renforcement.
Dans cet article, nous ne reconstruirons pas le célèbre Deep Blue pour les échecs mais une version bien plus simple pour le morpion en Python. En cours de route, vous acquerrez une forte intuition sur le fonctionnement de l'algorithme et sur la manière de l'appliquer à des jeux réels plus complexes.
Qu'est-ce que l'algorithme Minimax ?
Minimax est généralement un algorithme de prise de décision pour les jeux à deux joueurs (comme les échecs, le morpion ou les dames). Il permet aux ordinateurs de planifier plusieurs mouvements tout en supposant que votre adversaire fera toujours le meilleur mouvement possible. Dans cette section, nous allons donner un aperçu de l'algorithme à travers l'exemple du morpion.
Aperçu de l'algorithme Minimax
Dans un morpion du monde réel, à chaque fois que c'est votre tour, vous essayez de faire le meilleur mouvement possible tout en supposant que votre adversaire jouera également de son mieux. C'est exactement ce que fait l'algorithme Minimax : il aide l'ordinateur à effectuer le meilleur mouvement possible en réfléchissant à l'avance à tous les mouvements possibles.
L'algorithme Minimax tire son nom de son fonctionnement :
Lorsque c'est votre tour, vous voulez jouer les coups qui vous donnent les meilleures chances de gagner (maximisation). Lorsque c'est au tour de votre adversaire, vous supposez qu'il jouera les coups qui vous donneront le pire résultat (minimiser).
L'importance de Minimax dans l'IA
La méthode Minimax est très importante en intelligence artificielle pour plusieurs raisons :
Le plus intéressant ? Cette même idée est utilisée dans de nombreuses applications du monde réel :
Le Minimax peut sembler compliqué, mais il s'agit simplement d'apprendre à un ordinateur à penser comme un joueur prudent qui prend en compte à la fois ses coups et ceux de son adversaire avant de prendre une décision.
Comprendre l'algorithme Minimax
Décrivons le fonctionnement de Minimax à l'aide d'un exemple simple de morpion. Imaginez que vous jouez le rôle de X et que l'ordinateur est O.
Comment pense l'ordinateur
Lorsque c'est le tour de l'ordinateur, il suit les étapes suivantes :
Le score du jeu
L'ordinateur peut utiliser un système de notation simple :
Pensez-y comme à un arbre de possibilités :
Le tour de rôle
L'ordinateur passe d'un mode de pensée à l'autre :
1. Mode de maximisation (tour de l'ordinateur) :
2. Mode minimisation (tour du joueur) :
Un exemple simple
Disons que c'est le tour de l'ordinateur (X) dans ce jeu :
L'ordinateur va :
Cette façon de penser à l'avance permet à l'ordinateur de jouer une partie parfaite de morpion à chaque fois !
Pseudocode de l'algorithme Minimax
Voyons comment écrire l'algorithme Minimax étape par étape. Ne vous inquiétez pas si vous êtes novice en matière de pseudocode - considérez-le comme un moyen d'écrire les étapes en langage clair avant de les transformer en code réel !
Explication étape par étape
La fonction Minimax a besoin de trois éléments principaux pour fonctionner :
Voici à quoi ressemble le pseudocode de base :
Alors que la plupart des exemples de pseudocode se lisent en anglais et sont parfaitement compréhensibles, l'exemple ci-dessus est différent car il utilise la récursivité. On parle de récursivité lorsqu'une fonction s'appelle elle-même à plusieurs reprises pour résoudre un problème plus important. Imaginez que vous vous regardez dans un miroir qui reflète un autre miroir : vous voyez la même image répétée plusieurs fois, de plus en plus petite à chaque fois.
Dans notre algorithme Minimax, nous avons besoin de la récursivité parce que nous essayons d'examiner tous les mouvements futurs possibles dans le jeu. Chaque fois que la fonction s'appelle elle-même, elle examine le prochain mouvement qui pourrait se produire.
Cela nous aide à déterminer le meilleur mouvement en vérifiant toutes les possibilités de déroulement du jeu, comme un joueur très intelligent qui se dit "Si je fais ceci, alors ils pourraient faire cela, alors je pourrais faire ceci..." et ainsi de suite jusqu'à la fin du jeu. Pour en savoir plus sur la récursion, vous pouvez consulter notre tutoriel sur la récursion.
Exemple illustratif
Voyons comment cela fonctionne dans une situation de jeu simple :
1. Position de départ :
2. L'ordinateur réfléchit :
3. Pour chaque emplacement vide, l'ordinateur :
Pensez-y comme aux échecs : vous pensez toujours "Si je bouge ici, ils bougeront là, puis je pourrai bouger ici...", mais l'ordinateur peut penser à TOUS les mouvements possibles en même temps !
L'intérêt de cet algorithme est qu'il trouve toujours le meilleur coup possible, en supposant que les deux joueurs jouent parfaitement. C'est comme si vous aviez une boule de cristal qui vous montre tous les futurs possibles du jeu !
Implémentation de Minimax pour le Tic-tac-toe, étape par étape
Dans cette section, nous allons construire une IA de morpion imbattable alimentée par l'algorithme Mini-max en Python pur. Nous décomposerons la mise en œuvre en étapes simples et expliquerons l'intuition derrière chacune d'entre elles et comment elles s'intègrent dans l'image globale du jeu.
Étape 1 : Définition d'une classe TicTacToe
Tout d'abord, nous définissons une classe qui contient toute la logique et les méthodes dont nous avons besoin pour jouer au morpion avec nos ordinateurs :
Ci-dessus, la méthode
__init__initialise un nouveau plateau de jeu sous la forme d'une liste de 9 cases vides (représentées par les espaces " "), les indices 0 à 8 représentant les positions du plateau de gauche à droite, de haut en bas. Il met également en place deux symboles de joueur - "O" pour le joueur humain et "X" pour l'IA.La méthode
print_boardpermet de visualiser l'état actuel de la carte. Il imprime la grille 3x3 avec des lignes de séparation entre les rangées, montrant les mouvements de chaque joueur dans leurs positions respectives.La méthode
available_movesrenvoie une liste de tous les mouvements valides qui peuvent encore être effectués. Pour ce faire, il vérifie quelles positions du tableau sont encore vides (contiennent un espace " ") et renvoie leurs indices. Cela sera crucial pour que l'algorithme minimax sache quels mouvements il peut prendre en compte.Ces méthodes constituent la base sur laquelle nous nous appuierons pour créer notre joueur IA à l'aide de l'algorithme minimax.
Testons-les rapidement :
Comme prévu, l'échiquier est vide pour le moment et tous les coups sont disponibles.
Étape 2 : Mise en place de méthodes pour effectuer un mouvement et vérifier l'état du plateau.
Ajoutons maintenant une méthode pour effectuer un déplacement :
Nous avons ajouté la méthode
make_movequi :Effectuons quelques mouvements et vérifions les mouvements restants :
Le travail est bien fait. L'étape suivante consiste à ajouter une méthode permettant de vérifier si le tableau est plein :
is_board_fullest une méthode booléenne qui vérifie s'il reste des espaces vides sur le plateau.Ensuite, nous ajoutons une méthode pour vérifier si un état gagnant est atteint :
La méthode
check_winnerévalue l'état actuel du plateau de Tic-tac-toe pour déterminer s'il y a un gagnant. Il vérifie toutes les combinaisons gagnantes possibles :1. Rangs (3 possibilités) :
2. Colonnes (3 possibilités) :
3. Diagonales (2 possibilités) :
Pour chaque combinaison, il vérifie si les trois positions contiennent le même symbole de joueur (X ou O) et ne sont pas des espaces vides. Si une combinaison gagnante est trouvée, elle renvoie le symbole du joueur gagnant. Si aucun gagnant n'est trouvé après avoir vérifié toutes les possibilités, il renvoie None.
Testons la fonction dans les États gagnants et non gagnants :
Enfin, nous ajoutons une autre méthode booléenne pour spécifier si le jeu est terminé ou non :
La méthode renvoie True si le gagnant est trouvé ou si le tableau est plein.
À ce stade, nous avons construit tous les mécanismes de base du jeu :
print_board()affiche visuellement l'état actuel du jeuavailable_moves()renvoie les indices des carrés videsmake_move()place le symbole d'un joueur sur le plateau de jeucheck_winner()examine les lignes, les colonnes et les diagonales pour gagner à chaque coupis_board_full()détermine s'il ne reste aucun mouvementgame_over()combine le contrôle du vainqueur et le contrôle du tableau completCes méthodes fournissent les bases nécessaires à la création d'un jeu jouable, en gérant toutes les opérations de base telles que l'exécution des mouvements et la détermination de l'état du jeu.
Vient maintenant la partie critique : donner à l'ordinateur le "cerveau" nécessaire pour jouer au jeu avec Minimax.
Étape 3 : Implémentation de Minimax pour le morpion
Maintenant, implémentons l'algorithme du jeu dans une nouvelle méthode :
La fonction prend deux paramètres :
depth- Curse le nombre de niveaux de la récursion. Cela peut être utilisé pour limiter la profondeur de recherche pour les jeux très complexes, bien que pour le morpion nous n'ayons pas besoin de la limiter.is_maximizing- Indicateur booléen indiquant si nous recherchons actuellement le score maximum (tour de l'IA) ou le score minimum (tour de l'homme). Cette procédure alterne avec chaque appel récursif au fur et à mesure que les joueurs se succèdent.Dans le corps de la fonction, nous commençons par définir les cas de base : Si la partie est gagnée par l'IA (
winner == ai_player), nous retournons 1 car c'est le meilleur résultat possible pour l'IA. Si l'humain gagne (winner == human_player), nous renvoyons -1 car il s'agit du pire résultat pour l'IA. Si le tableau est plein et qu'il n'y a pas de gagnant, nous retournons 0 pour un tirage au sort.Lorsque
is_maximizingest True, nous simulons le tour de l'IA et nous voulons trouver le mouvement qui mène au score le plus élevé possible. Nous commençons par fixer best_score à l'infini négatif afin que tout score réel soit meilleur. Ensuite, pour chaque mouvement disponible, nous :is_maximizing=False(puisque ce serait le tour de l'humain ensuite).max()Cela nous permet de vérifier tous les mouvements possibles de l'IA. Pour chaque coup, nous examinons ce qui pourrait se produire ensuite, jusqu'à ce que quelqu'un gagne ou que le jeu soit à égalité. Nous travaillons ensuite à rebours pour déterminer quel premier coup donne à l'IA la meilleure chance de gagner.
Maintenant, faisons la partie minimisation pour l'homme :
Lorsque
is_maximizingest False, nous simulons le tour du joueur humain et nous voulons trouver le mouvement qui mène au score le plus bas possible (puisqu'un score élevé signifie que l'IA gagne). Nous partons debest_scorecomme d'une infinité positive, de sorte que tout score réel sera inférieur. Pour chaque mouvement disponible, nous :is_maximizing=True(puisque ce serait le tour de l'IA ensuite).min()Cela simule le joueur humain essayant de faire les meilleurs mouvements pour empêcher l'IA de gagner. L'humain souhaite minimiser le score car les scores positifs représentent des victoires de l'IA. En alternant les tours de maximisation et de minimisation, l'algorithme peut déterminer la séquence de mouvements optimale pour les deux joueurs.
Étape 4 : Trouver le meilleur mouvement pour l'IA à l'aide de Minimax
Maintenant que l'algorithme est prêt, nous avons besoin d'une autre méthode qui utilise la méthode
minimaxpour déterminer le meilleur coup pour l'IA après chaque coup humain :La méthode get_best_move est chargée de déterminer le déplacement optimal du joueur IA à l'aide de l'algorithme minimax. Il fonctionne de la manière suivante :
1. En commençant par l'infini négatif comme meilleur score et en ne choisissant aucun mouvement
2. Pour chaque mouvement disponible sur le plateau :
3. Retourner enfin le mouvement qui a permis d'obtenir le score le plus élevé
Cette approche garantit que l'IA choisira le coup qui lui donne les meilleures chances de gagner, en supposant que le joueur humain joue lui aussi de manière optimale. La méthode prend en compte tous les états de jeu futurs possibles et choisit la voie qui maximise les chances de l'IA tout en minimisant les chances de victoire de l'humain.
Testons-le sur un exemple d'état de jeu :
Comme vous pouvez le voir, l'IA a trouvé la combinaison gagnante en se basant sur mes déplacements (il s'agissait d'un état factice, mais cela prouve que notre algorithme fonctionne).
Étape 5 : Mise en œuvre d'une boucle de jeu
Maintenant que nous avons implémenté et testé notre algorithme minimax, créons une boucle de jeu qui nous permettra de jouer contre l'IA.
La méthode play_game commence par afficher un message de bienvenue et des instructions au joueur. Il montre que le joueur humain utilise "O" et que l'IA utilise "X". Il imprime ensuite une grille numérotée (0-8) pour indiquer au joueur quel numéro correspond à quelle position sur le plateau. Il est ainsi facile pour les joueurs de savoir exactement quel chiffre saisir pour le coup qu'ils souhaitent effectuer.
Après avoir affiché les instructions initiales, le jeu entre dans sa boucle principale. Le jeu décide de manière aléatoire qui commence - l'IA ou le joueur humain - en utilisant
random.choice([True, False]). Cela crée un élément d'équité et d'imprévisibilité au début de chaque partie.La boucle principale du jeu se poursuit jusqu'à ce que
game_over()renvoie True (quelqu'un a gagné ou le plateau est plein). Pendant chaque tour, l'état actuel du plateau est affiché à l'aide deprint_board().Si c'est le tour de l'IA (
ai_turnest True), le programme :get_best_move()pour déterminer le mouvement optimal à l'aide de l'algorithme minimax.Si c'est le tour de l'humain (
ai_turnest Faux), le programme :1. Entre dans une boucle pour obtenir des données valides de la part du joueur2. Demande un numéro de déplacement entre 0 et 83. Valide l'entrée est :
4. Continue à demander jusqu'à ce qu'une entrée valide soit reçue. Effectue le déplacement en plaçant le symbole du joueur ("O") à la position choisie.
Après chaque tour,
ai_turnest retourné à l'aide denotpour alterner entre les joueurs. Cela crée le flux de va-et-vient du jeu, chaque joueur jouant à tour de rôle jusqu'à ce que quelqu'un gagne ou que le jeu se termine par un match nul.La validation des entrées garantit que le jeu ne peut pas se bloquer à cause d'une entrée invalide de l'utilisateur et fournit des messages d'erreur utiles pour guider le joueur afin qu'il entre les mouvements corrects. Cela permet de créer une expérience de jeu robuste et conviviale.
Lorsque le jeu se termine, l'état final du plateau est affiché à l'aide de
print_board()et le gagnant est déterminé parcheck_winner(). Le jeu peut se terminer de trois façons :check_winner()renvoie le symbole de l'IA ('X'), cela indique que l'IA a obtenu une ligne gagnante.check_winner()renvoie le symbole de l'homme ('O'), cela indique que le joueur a obtenu une ligne gagnante.Le message approprié s'affiche pour annoncer le résultat du jeu. Cela permet au joueur de savoir clairement comment le jeu s'est terminé.
Étape 6 : Tout mettre en place
Il est maintenant temps de mettre tout le code que nous avons écrit jusqu'à présent dans un script Python avec ce qui suit if/main à la toute fin :
Cela permet au jeu de démarrer dès que vous exécutez le script avec python script.py. Si vous vous êtes perdu parmi toutes les explications et les blocs de code, vous pouvez trouver le code complet du jeu dans ce GitHub gist.
Voici un exemple de jeu auquel j'ai participé :
N'oubliez pas que le morpion étant un jeu simple, vous n'avez aucune chance de battre l'IA. Soit vous êtes à égalité, soit vous perdez !
Formalisation de l'algorithme mini-maxi
Examinons maintenant la définition générale d'un algorithme au-delà de l'exemple simple du morpion.
L'algorithme Minimax peut être formellement défini comme une fonction récursive qui évalue les positions dans un jeu à somme nulle. Décortiquons ses composants formels et ses propriétés.
Définition mathématique
Pour un état de jeu
s, la valeur minimaxV(s)est définie comme suit :Où ?
Propriétés principales
1. Une information parfaite
2. La nature à somme nulle
3. Jeu optimal
Analyse de la complexité
Complexité temporelle : O(b^m)
Complexité de l'espace : O(bm)
Fonction d'évaluation
Pour les états non terminaux, la fonction d'évaluation f(s) doit :
La définition formelle :
f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ
Où ?
Garantie d'optimalité
L'algorithme Minimax garantit un jeu optimal dans ces conditions :
Il est donc particulièrement adapté aux jeux d'échecs, de morpion et de dames, pour lesquels ces conditions sont remplies.
Variantes avancées et limites
Si Minimax est parfait pour les jeux simples comme le morpion, il rencontre quelques problèmes avec les jeux plus importants. Voyons comment nous pouvons l'améliorer et quels sont ses points faibles.
Rendre Minimax plus rapide : Taille alpha-bêta
Imaginez que vous jouez aux échecs et que vous réfléchissez à vos mouvements. Si vous avez trouvé un coup gagnant, vous n'avez pas besoin de vérifier tous les autres coups possibles, n'est-ce pas ? L'élagage alpha-bêta fonctionne de la même manière - il aide l'ordinateur à ne pas vérifier les mouvements dont nous savons déjà qu'ils ne seront pas meilleurs que ceux que nous avons trouvés.
Pensez-y comme suit :
Limites de profondeur : Ne pas regarder trop loin
Dans les grands jeux comme les échecs, il y a trop de mouvements possibles pour les vérifier tous. Nous ajoutons donc une limite de profondeur :
Vous ne pouvez pas planifier tous vos mouvements jusqu'à la fin de la partie, mais vous pouvez le faire quelques fois à l'avance !
Là où Minimax se bat
Minimax n'est pas parfait. Voici ses principaux problèmes :
1. Trop de choix
2. Problèmes de temps
3. Pas terrible pour les jeux incertains
Des solutions modernes
L'IA des jeux d'aujourd'hui combine souvent le Minimax avec d'autres techniques intéressantes :
1. Apprentissage automatique
AlphaGoutilisent cette méthode pour battre des champions humains.2. Reconnaissance des formes
3. Banque de mémoire
Le plus intéressant ? Ces améliorations permettent aux ordinateurs de jouer à des jeux presque aussi bien que les humains, et parfois même mieux ! Mais n'oubliez pas que même avec tous ces ajouts fantaisistes, Minimax reste la base qui permet à tout de fonctionner.
Conclusion
Dans ce tutoriel, nous avons exploré l'algorithme Minimax depuis ses concepts de base jusqu'à sa mise en œuvre pratique. Voici ce que nous avons appris :
1. Concepts de base
2. Compétences en matière de mise en œuvre
3. Thèmes avancés
Quelle est la prochaine étape ?
L'algorithme Minimax n'est qu'une pièce du puzzle de l'IA. Si vous souhaitez en savoir plus sur l'IA et les algorithmes, voici quelques ressources intéressantes pour poursuivre votre voyage :
1. Algorithmes associés
2. Applications de l'apprentissage automatique
3. Des cursus d'apprentissage complets
N'oubliez pas que, que vous construisiez un simple jeu ou un système d'intelligence artificielle complexe, la compréhension d'algorithmes tels que Minimax vous donne une base solide pour aborder des sujets plus avancés en matière d'intelligence artificielle. Continuez à vous entraîner, à apprendre et, surtout, à coder !