Minimax et élagage alpha-bêta

Dans un jeu à deux joueurs, à somme nulle et à information parfaite, les deux joueurs savent tout et le gain de l’un est la perte de l’autre. MAX veut une utilité finale grande ; MIN la veut petite. Le jeu optimal contre un adversaire parfait a une définition exacte, et il se calcule de bas en haut.

La valeur minimax

$$\text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal},\\ \max_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MAX moves at } s,\\ \min_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MIN moves at } s. \end{cases}$$

Lisez-la comme une hypothèse sur l’adversaire : MAX suppose que MIN répondra toujours par le pire coup pour MAX. La valeur est ce que MAX peut garantir même face à un jeu parfait - une borne inférieure indiscutable, non une prédiction de ce que fera un adversaire faible.

Exemple résolu

L’arbre standard à deux demi-coups. Une racine MAX a trois enfants MIN, dont les feuilles sont

$$B: (3, 12, 8) , \qquad C: (2, 4, 6) , \qquad D: (14, 5, 2) .$$

Remontez les nœuds MIN. Chacun prend le minimum de ses feuilles :

$$B = \min(3,12,8) = 3 , \quad C = \min(2,4,6) = 2 , \quad D = \min(14,5,2) = 2 .$$

Remontez la racine MAX. Elle prend le maximum de ses enfants :

$$\text{root} = \max(3, 2, 2) = 3 .$$

La valeur minimax est $\mathbf{3}$, et le coup optimal est celui qui mène à $B$.

Notez le piège du nœud $D$ : il contient la plus grande feuille de tout l’arbre, $14$. Il vaut $2$, parce que MAX ne choisit pas quelle feuille de $D$ est atteinte - c’est MIN qui choisit, et MIN prendra le $2$. Une branche vaut ce que votre adversaire autorisera, non ce qu’elle contient.

L’élagage alpha-bêta

Le minimax examine chaque nœud, ce qui est en $O(b^m)$ et sans espoir pour de vrais jeux. Mais vous n’avez pas besoin de voir chaque nœud pour connaître la valeur de la racine.

Supposons que MAX ait déjà établi que $B$ garantit $3$. Examinez maintenant $C$ et trouvez que sa première feuille vaut $2$. Le nœud $C$ est un nœud MIN, donc sa valeur finale est au plus $2$ - MIN peut toujours prendre ce $2$, et les feuilles suivantes ne peuvent que l’abaisser. Comme $2 < 3$, MAX ne choisira jamais $C$. Les feuilles restantes de $C$ ne peuvent pas changer la valeur de la racine : elles n’ont donc pas à être examinées du tout.

C’est toute l’idée, suivie au moyen de deux bornes : $\alpha$, la meilleure valeur que MAX peut déjà garantir, et $\beta$, la meilleure que MIN peut déjà garantir.

Ce que l’élagage change. Appliqué à un arbre minimax standard, l’alpha-bêta renvoie le même coup que le minimax, tout en élaguant des branches qui ne peuvent en rien influencer la décision finale. Il est exact, non approché : la valeur est identique, seul le travail diffère. Quiconque le décrit comme une approximation plus rapide l’a mal compris.

L’ordre des coups

L’élagage dépend entièrement de l’examen précoce des bons coups. Si le meilleur coup est cherché en premier, $\alpha$ monte immédiatement et les branches ultérieures sont coupées rapidement. Avec un ordre parfait, le facteur de branchement effectif tombe de $b$ à environ $\sqrt{b}$, ce qui permet à une recherche d’aller à peu près deux fois plus profond dans le même temps. Avec l’ordre du pire cas, rien n’est élagué et vous avez payé le coût complet du minimax.

C’est pourquoi les vrais moteurs investissent lourdement dans des heuristiques d’ordonnancement avant d’approfondir la recherche.

Avant le quiz

Sachez remonter les valeurs dans un petit arbre, énoncer que l’alpha-bêta renvoie la valeur identique en examinant moins de nœuds, et expliquer pourquoi $D$ vaut $2$ bien qu’il contienne $14$. Voyez La recherche adversariale et le minimax.