Algorithme minimax

2. L'arbre de jeu

Pour raisonner sur toutes les suites possibles, on déplie la partie en un arbre.

3. La valeur minimax d'une position

Le cœur de l'algorithme tient en une seule définition récursive.

Le coup optimal à la racine (à MAX) est celui qui mène à la fille dont la valeur est maximale : c'est la fille qui « réalise » le max. On obtient donc à la fois la valeur de la position et le coup à jouer.

4. Le code récursif

On représente ici un arbre de jeu par des listes imbriquées : une feuille est un entier (son score), un nœud interne est la liste de ses filles. Le booléen est_max indique si c'est à MAX de jouer dans la position courante.

def minimax(position, est_max):
    if isinstance(position, int):       # position terminale : c'est un score
        return position
    if est_max:                         # c'est a MAX de jouer
        return max(minimax(f, False) for f in position)
    else:                               # c'est a MIN de jouer
        return min(minimax(f, True) for f in position)

Table de trace sur un petit arbre

Prenons l'arbre binaire de profondeur 3 ci-dessous, racine à MAX. Les feuilles portent les scores. On note les nœuds par leur chemin (L = fille gauche, R = fille droite) :

# feuille = int, noeud interne = liste des filles
arbre = [
    [ [3, 5], [6, 9] ],    # L (MIN)  : filles LL et LR, toutes deux MAX
    [ [1, 2], [0, -1] ],   # R (MIN)  : filles RL et RR, toutes deux MAX
]
print(minimax(arbre, True))   # racine a MAX

On évalue de bas en haut. Les nœuds MAX de profondeur 2 prennent le max de leurs deux feuilles ; les nœuds MIN de profondeur 1 prennent le min de leurs deux enfants ; la racine MAX prend le max des deux nœuds MIN.

La valeur de la position est donc $5$. Le coup optimal de MAX à la racine est d'aller vers L (valeur $5$), pas vers R (valeur $0$). Remarque parlante : la feuille $9$ est la plus grosse de l'arbre, mais MAX ne l'obtiendra jamais, car MIN, au nœud L, choisira l'enfant de valeur $5$ plutôt que celui de valeur $9$.

5. Élagage alpha-bêta et complexité

Complexité : exponentielle en la profondeur

Minimax visite chaque nœud de l'arbre. Si le facteur de branchement est $b$ (nombre de coups par position) et la profondeur explorée est $p$, l'arbre possède environ $b^p$ feuilles, et le nombre total de nœuds est du même ordre. La complexité en temps est donc :

$\mathcal{O}(b^p)$

C'est une croissance exponentielle en la profondeur. Aux échecs, $b\approx 35$ : explorer ne serait-ce que 5 demi-coups représente déjà $35^5\approx 5\times 10^7$ feuilles. Explorer une partie entière est hors de portée — d'où deux réponses en pratique : limiter la profondeur (avec une heuristique d'évaluation des positions non terminales) et… élaguer.

L'élagage alpha-bêta (à connaître d'existence)

L'élagage alpha-bêta est une optimisation de minimax qui donne exactement la même valeur, mais en évitant d'explorer des branches inutiles. L'idée : pendant le parcours, on retient deux bornes, $\alpha$ (le meilleur score déjà garanti à MAX) et $\beta$ (le meilleur déjà garanti à MIN). Dès qu'on découvre qu'une branche ne pourra pas améliorer le choix d'un joueur — parce qu'elle est déjà « battue » par une valeur connue plus haut — on l'abandonne sans finir de l'explorer (une coupure).

Dans le meilleur cas (bon ordre d'exploration des coups), alpha-bêta fait passer la complexité de $\mathcal{O}(b^p)$ à environ $\mathcal{O}(b^{p/2})$ : on peut explorer deux fois plus profond à coût égal. Le programme n'est pas exigible en détail ; retiens son existence, son rôle (accélérer sans changer le résultat) et son principe (couper les branches condamnées).

6. Exercices corrigés

def meilleur_coup(position):
    # position est a MAX et non terminale : liste de filles
    valeurs = [minimax(f, False) for f in position]
    meilleure = max(valeurs)
    return valeurs.index(meilleure)   # indice de la 1re fille optimale