Minimax en Python : comprendre l’algorithme avec un exemple de jeu

L’algorithme minimax sert à choisir le meilleur coup dans un jeu à deux joueurs où les intérêts sont opposés. Un joueur essaie de maximiser son score, l’autre essaie de le minimiser. C’est une idée très utilisée dans les jeux de stratégie simples comme le morpion, les jeux d’allumettes, certains jeux de plateau et les premiers moteurs de jeu.

En Python, minimax se programme naturellement avec une fonction récursive : on simule les coups possibles, on regarde les réponses de l’adversaire, puis on remonte le meilleur score jusqu’au coup initial.

def minimax(etat, joueur_maximise):
    if position_terminale(etat):
        return evaluer(etat)

    if joueur_maximise:
        meilleur_score = float("-inf")
        for coup in coups_possibles(etat):
            nouvel_etat = jouer(etat, coup)
            score = minimax(nouvel_etat, False)
            meilleur_score = max(meilleur_score, score)
        return meilleur_score

    meilleur_score = float("inf")
    for coup in coups_possibles(etat):
        nouvel_etat = jouer(etat, coup)
        score = minimax(nouvel_etat, True)
        meilleur_score = min(meilleur_score, score)
    return meilleur_score

Ce squelette résume toute la logique : le joueur max choisit le score le plus élevé, tandis que le joueur min choisit le score le plus bas.

La réponse courte

Minimax explore les coups possibles comme un arbre de décision. À chaque niveau, les joueurs alternent :

• le joueur maximisant cherche le meilleur score ;
• le joueur minimisant cherche le pire score pour son adversaire ;
• quand une partie est terminée, on attribue un score : victoire, défaite ou match nul ;
• le score remonte dans l’arbre jusqu’au premier coup.

Dans une version simple, on peut noter :

victoire = 1
match_nul = 0
defaite = -1

L’algorithme ne “devine” pas le bon coup. Il l’obtient en supposant que chaque joueur joue au mieux.

Comprendre minimax avec un jeu d’allumettes

Pour éviter de se perdre dans les règles du morpion dès le départ, prenons un jeu plus simple.

Règles :

• il y a un tas de jetons ;
• à chaque tour, un joueur peut prendre 1 ou 2 jetons ;
• celui qui prend le dernier jeton gagne.

Si le joueur Python commence avec 5 jetons, le meilleur coup consiste à prendre 2 jetons. Il laisse alors 3 jetons à l’adversaire, ce qui est une position perdante si les deux joueurs jouent parfaitement.

Voici une implémentation complète.

def coups_possibles(jetons):
    return [prise for prise in (1, 2) if prise <= jetons]


def minimax(jetons, tour_max):
    if jetons == 0:
        return -1 if tour_max else 1

    if tour_max:
        meilleur_score = float("-inf")

        for prise in coups_possibles(jetons):
            score = minimax(jetons - prise, False)
            meilleur_score = max(meilleur_score, score)

        return meilleur_score

    meilleur_score = float("inf")

    for prise in coups_possibles(jetons):
        score = minimax(jetons - prise, True)
        meilleur_score = min(meilleur_score, score)

    return meilleur_score


def meilleur_coup(jetons):
    meilleur_score = float("-inf")
    meilleur_choix = None

    for prise in coups_possibles(jetons):
        score = minimax(jetons - prise, False)

        if score > meilleur_score:
            meilleur_score = score
            meilleur_choix = prise

    return meilleur_choix


print(meilleur_coup(5))  # 2

Ce code est court, mais il contient déjà les ingrédients essentiels de minimax : état du jeu, coups possibles, simulation, récursion, évaluation et choix du meilleur coup.

Pourquoi le score terminal dépend du tour

La ligne la plus importante est celle-ci :

if jetons == 0:
    return -1 if tour_max else 1

Si jetons == 0, cela signifie que le joueur précédent a pris le dernier jeton. La partie est terminée.

Deux cas sont possibles :

• si c’est maintenant au tour du joueur maximisant, cela veut dire que son adversaire vient de gagner, donc le score est -1 ;
• si c’est maintenant au tour du joueur minimisant, cela veut dire que le joueur maximisant vient de gagner, donc le score est 1.

Cette convention permet d’évaluer toutes les branches depuis le point de vue du joueur maximisant.

Afficher les scores de chaque coup

Pour mieux voir ce que fait l’algorithme, affichons le score associé à chaque choix.

def analyser_position(jetons):
    for prise in coups_possibles(jetons):
        score = minimax(jetons - prise, False)
        print(f"Prendre {prise} -> score {score}")


analyser_position(5)

Résultat :

Prendre 1 -> score -1
Prendre 2 -> score 1

Avec 5 jetons, prendre 1 laisse 4 jetons à l’adversaire. S’il joue bien, il peut ensuite forcer une victoire. Prendre 2 laisse 3 jetons, une position défavorable pour lui.

Minimax n’a donc pas seulement choisi un coup “qui marche”. Il a comparé les conséquences futures de chaque option.

Adapter minimax au morpion

Le morpion est souvent l’exemple classique, mais le principe reste le même. Il faut définir quatre fonctions :

def position_terminale(grille):
    ...


def evaluer(grille):
    ...


def coups_possibles(grille):
    ...


def jouer(grille, coup, symbole):
    ...

Ensuite, minimax peut parcourir les coups disponibles.

def minimax_morpion(grille, joueur_maximise):
    if position_terminale(grille):
        return evaluer(grille)

    if joueur_maximise:
        meilleur_score = float("-inf")

        for coup in coups_possibles(grille):
            nouvelle_grille = jouer(grille, coup, "X")
            score = minimax_morpion(nouvelle_grille, False)
            meilleur_score = max(meilleur_score, score)

        return meilleur_score

    meilleur_score = float("inf")

    for coup in coups_possibles(grille):
        nouvelle_grille = jouer(grille, coup, "O")
        score = minimax_morpion(nouvelle_grille, True)
        meilleur_score = min(meilleur_score, score)

    return meilleur_score

La difficulté du morpion n’est pas minimax lui-même. Elle se trouve surtout dans la représentation de la grille et dans la fonction d’évaluation : détecter une victoire, une défaite ou un match nul.

Éviter les recalculs avec la mémoïsation

Minimax peut recalculer plusieurs fois les mêmes positions. Dans le jeu des jetons, ce n’est pas grave. Dans un vrai jeu, cela devient vite coûteux.

Python fournit lru_cache, un décorateur qui mémorise le résultat d’une fonction pour les mêmes arguments.

from functools import lru_cache


def coups_possibles(jetons):
    return [prise for prise in (1, 2) if prise <= jetons]


@lru_cache(maxsize=None)
def minimax(jetons, tour_max):
    if jetons == 0:
        return -1 if tour_max else 1

    if tour_max:
        meilleur_score = float("-inf")

        for prise in coups_possibles(jetons):
            score = minimax(jetons - prise, False)
            meilleur_score = max(meilleur_score, score)

        return meilleur_score

    meilleur_score = float("inf")

    for prise in coups_possibles(jetons):
        score = minimax(jetons - prise, True)
        meilleur_score = min(meilleur_score, score)

    return meilleur_score

Attention : pour utiliser lru_cache, les arguments doivent être hashables. Un entier comme jetons fonctionne très bien. Pour une grille de morpion, il vaut mieux utiliser un tuple plutôt qu’une liste.

grille = (
    "X", "O", "X",
    " ", "O", " ",
    " ", "X", " ",
)

Un tuple est immuable, donc il peut être utilisé comme clé de cache.

L’élagage alpha-bêta

L’élagage alpha-bêta est une optimisation de minimax. Il ne change pas le résultat final, mais il évite d’explorer certaines branches inutiles.

L’idée :

• alpha représente le meilleur score déjà garanti pour le joueur maximisant ;
• beta représente le meilleur score déjà garanti pour le joueur minimisant ;
• si une branche ne peut plus améliorer la décision finale, on l’arrête.

Voici une version alpha-bêta du jeu des jetons.

def minimax_alpha_beta(jetons, tour_max, alpha=float("-inf"), beta=float("inf")):
    if jetons == 0:
        return -1 if tour_max else 1

    if tour_max:
        meilleur_score = float("-inf")

        for prise in coups_possibles(jetons):
            score = minimax_alpha_beta(jetons - prise, False, alpha, beta)
            meilleur_score = max(meilleur_score, score)
            alpha = max(alpha, meilleur_score)

            if beta <= alpha:
                break

        return meilleur_score

    meilleur_score = float("inf")

    for prise in coups_possibles(jetons):
        score = minimax_alpha_beta(jetons - prise, True, alpha, beta)
        meilleur_score = min(meilleur_score, score)
        beta = min(beta, meilleur_score)

        if beta <= alpha:
            break

    return meilleur_score

Sur un petit jeu, la différence est peu visible. Sur un jeu avec beaucoup de coups possibles, alpha-bêta peut réduire fortement le nombre de positions explorées.

Complexité de minimax

La complexité de minimax dépend de deux valeurs :

• b, le nombre moyen de coups possibles à chaque position ;
• d, la profondeur de recherche.

Sans optimisation, l’ordre de grandeur est :

O(b^d)

Cela signifie que le coût augmente très vite. Si un jeu propose en moyenne 8 coups possibles et que vous explorez 6 tours, cela fait déjà des milliers de positions.

C’est pour cette raison que les programmes de jeu utilisent souvent :

• une profondeur limitée ;
• une fonction d’évaluation approximative ;
• l’élagage alpha-bêta ;
• la mémoïsation ;
• un ordre intelligent des coups.

Minimax complet fonctionne bien sur des jeux petits ou fortement limités. Pour des jeux plus grands, il faut l’adapter.

Minimax, minmax et negamax : quelle différence ?

Vous verrez parfois les termes minimax, minmax et negamax.

Minimax est le nom classique de l’algorithme : un joueur maximise, l’autre minimise.

Minmax est souvent une variante d’écriture utilisée dans certains articles ou requêtes de recherche. Dans la pratique, les deux termes désignent généralement la même idée.

Negamax est une reformulation plus compacte de minimax. Elle repose sur l’idée que le score d’un joueur est l’opposé du score de l’autre. Le code est souvent plus court, mais la logique est un peu moins intuitive pour débuter.

Si vous apprenez l’algorithme, commencez par minimax. Une fois la récursion et les scores bien compris, negamax devient plus facile à lire.

Erreurs fréquentes

Oublier d’alterner les joueurs

À chaque appel récursif, le tour doit changer.

score = minimax(nouvel_etat, False)

Puis au niveau suivant :

score = minimax(nouvel_etat, True)

Si vous oubliez cette alternance, le même joueur joue plusieurs fois de suite dans l’arbre simulé.

Évaluer une position trop tôt

Dans une version complète, evaluer() doit être appelée seulement quand la position est terminale, ou quand une profondeur limite est atteinte.

if position_terminale(etat) or profondeur == 0:
    return evaluer(etat)

Si vous évaluez trop tôt sans raison, minimax ne regarde pas assez loin.

Modifier l’état au lieu d’en créer un nouveau

Dans les jeux, une erreur courante consiste à modifier directement la grille pendant la simulation, puis à oublier de l’annuler.

Préférez une fonction jouer() qui renvoie un nouvel état.

nouvelle_grille = jouer(grille, coup, "X")

Cela rend le code plus sûr et plus facile à déboguer.

Utiliser une liste avec lru_cache

Les listes ne sont pas hashables.

@lru_cache(maxsize=None)
def minimax(grille):
    ...

Si grille est une liste, Python lèvera une erreur. Utilisez plutôt un tuple.

Mini-exercices

Essayez de répondre avant d’exécuter le code.

Exercice 1

Dans le jeu des jetons, quel est le meilleur coup avec 4 jetons ?

print(meilleur_coup(4))

Réponse : 1. Le joueur laisse 3 jetons à l’adversaire, une position perdante.

Exercice 2

Que renvoie meilleur_coup(6) ?

print(meilleur_coup(6))

Avec 6 jetons, la position est perdante si l’adversaire joue parfaitement. Le programme choisira l’un des coups disponibles, mais aucun ne garantit une victoire.

Exercice 3

Modifiez les règles pour autoriser 1, 2 ou 3 jetons par tour.

def coups_possibles(jetons):
    return [prise for prise in (1, 2, 3) if prise <= jetons]

Observez ensuite les positions gagnantes et perdantes. Vous verrez apparaître un nouveau cycle.

Quand utiliser minimax en Python

Minimax est un bon choix si :

• le jeu a deux joueurs ;
• les joueurs ont des objectifs opposés ;
• les règles sont connues ;
• les coups possibles peuvent être simulés ;
• l’espace de recherche reste raisonnable, ou peut être limité.

Il est moins adapté si :

• le jeu contient beaucoup d’aléatoire ;
• le nombre de coups possibles est trop grand ;
• l’information est cachée ;
• les joueurs ne sont pas strictement opposés ;
• l’évaluation d’une position est très difficile.

Dans ces cas, on peut regarder d’autres approches : Monte Carlo Tree Search, apprentissage par renforcement ou heuristiques spécifiques.

Pour aller plus loin

Le minimax s’inscrit dans une famille d’algorithmes utiles pour comprendre les décisions et l’optimisation en Python. Vous pouvez continuer avec :

• l’algorithme negamax en Python, une version plus compacte de minimax ;
• l’algorithme du simplexe en Python, pour une autre approche de l’optimisation ;
• la méthode de Monte Carlo en Python, utile quand l’exploration exhaustive devient trop coûteuse.

Si vous retenez une seule idée, gardez celle-ci : minimax suppose que l’adversaire joue parfaitement. Le meilleur coup n’est donc pas seulement celui qui semble bon maintenant, mais celui qui reste bon après la meilleure réponse possible de l’autre joueur.

Références

• Documentation Python – functools.lru_cache
• Documentation Python – types tuple
• Documentation Python – fonctions max() et min()