Recherche et IA de jeu : A* et minimax en Python

Le concept en termes simples

L'IA classique résout des problèmes en explorant les états possibles. A* trouve le chemin le moins coûteux en additionnant le coût déjà parcouru et une estimation du coût restant, et minimax choisit les coups dans les jeux à deux joueurs en supposant que l'adversaire joue bien.

Trouvez le plus court chemin sur une grille avec la recherche A* et choisissez le meilleur coup d'une partie avec minimax.

Idées clés

A* trouve le meilleur chemin quand l'estimation (heuristique) ne surestime jamais le coût réel.
Minimax explore l'arbre de jeu jusqu'à une profondeur fixe ou jusqu'à la fin de la partie.
L'élagage alpha-bêta ignore les branches qui ne peuvent pas changer la décision.
Les algorithmes génétiques cherchent autrement : ils font évoluer une population de solutions candidates.

Quand l’utiliser ?

Comprendre ce qui se passe à l'intérieur des réseaux de neurones et des bibliothèques d'IA.
Apprendre l'idée avant de l'implémenter dans les défis correspondants.
Se préparer aux cours d'apprentissage automatique, aux entretiens et aux projets.

À vous de jouer

Appuyez sur Lecture pour voir A* explorer la grille ; cliquez sur les cases pour ajouter ou retirer des murs. Dans l'arbre de jeu, cliquez sur une feuille pour changer son score.

Code d’exemple

Exécuter le code →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

Résultat attendu

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

Fonctionnement

La file de priorité développe toujours la case dont le coût + l'estimation est le plus petit, l'estimation étant la distance de Manhattan jusqu'au but ; A* atteint donc G en 5 pas en contournant les murs. minimax() prend le maximum à notre tour et le minimum au tour de l'adversaire ; le premier coup garantit 3, le meilleur des trois pires cas.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices pratiques

Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.

Modifiez les entrées ou les poids et prédisez la sortie avant d'exécuter.
Affichez les valeurs intermédiaires pour suivre chaque étape du calcul.
Résolvez les défis liés ci-dessous pour implémenter l'idée vous-même.

Exécuter dans l’IDE Python →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis