MinMax et Alpha-Beta

Dans un jeu à deux joueurs à tour de rôle (tic-tac-toe, échecs, puissance 4), MinMax choisit le meilleur coup en supposant que l'adversaire joue lui aussi parfaitement. Alpha-Beta obtient exactement le même résultat en explorant beaucoup moins de positions.

L'arbre de jeu

Chaque noeud est une position, chaque arête un coup. Les niveaux alternent entre les deux joueurs :

• ▲ MAX (nous) cherche la valeur la plus grande ;
• ▼ MIN (l'adversaire) cherche la valeur la plus petite.

Les feuilles ont une valeur donnée par une fonction d'évaluation : +1 / 0 / −1 pour une partie terminée, ou une estimation (avantage matériel, par exemple) quand on arrête la recherche à une profondeur fixe.

MinMax

On calcule les valeurs de bas en haut : un noeud MAX prend le maximum de ses enfants, un noeud MIN le minimum. On explore en profondeur, de gauche à droite.

minmax(noeud):
    si noeud est une feuille: retourner évaluation(noeud)
    si noeud est MAX: retourner max(minmax(e) pour chaque enfant e)
    sinon:            retourner min(minmax(e) pour chaque enfant e)

Exemple : la racine A (MAX) a trois enfants MIN.

                A (MAX)
       /           |           \
    B (MIN)     C (MIN)     D (MIN)
   /  |  \     /  |  \     /  |  \
  4   9   6   3   7   5   8   2   10

• B = min(4, 9, 6) = 4
• C = min(3, 7, 5) = 3
• D = min(8, 2, 10) = 2
• A = max(4, 3, 2) = 4 : le meilleur coup est d'aller vers B.

MinMax visite toutes les feuilles : O(b^d) pour un facteur de branchement b et une profondeur d.

Élagage Alpha-Beta

On transmet deux bornes en descendant dans l'arbre :

• α : la meilleure valeur que MAX est déjà sûr d'obtenir sur le chemin (départ −∞) ;
• β : la meilleure valeur que MIN est déjà sûr d'obtenir sur le chemin (départ +∞).

Un noeud MAX met à jour α, un noeud MIN met à jour β. Dès que α ≥ β, les enfants restants ne peuvent plus changer la décision : on les élague.

Le même exemple avec Alpha-Beta

1. B (α = −∞, β = +∞) : on voit 4, 9, 6 → B = 4. De retour à A, α = 4.
2. C (α = 4, β = +∞) : première feuille 3, donc β = 3. Comme α = 4 ≥ β = 3, on coupe : C vaudra au plus 3, et A a déjà une option à 4. Les feuilles 7 et 5 sont élaguées.
3. D (α = 4, β = +∞) : feuille 8 → β = 8, pas de coupure. Feuille 2 → β = 2 ≤ α, on coupe : la feuille 10 est élaguée.
4. A = 4, comme avec MinMax, mais avec 3 feuilles de moins à évaluer.

L'ordre des coups compte

Alpha-Beta élague davantage quand les meilleurs coups sont explorés en premier. Avec un ordre parfait, la complexité tombe à environ O(b^d/2), ce qui permet de chercher deux fois plus profondément dans le même temps. Avec un ordre défavorable, on ne coupe rien et on retombe sur O(b^d).

Pièges fréquents