La recherche adversariale et le minimax

Chercher un itinéraire diffère de jouer à un jeu sur un point décisif : dans un jeu, quelqu’un d’autre joue ensuite, et il cherche à vous faire perdre. Vous ne pouvez pas planifier une suite fixe d’actions, car les réponses de votre adversaire ne vous appartiennent pas. La recherche adversariale traite cela en supposant que l’adversaire joue aussi bien que possible, et en calculant la meilleure réponse à cela.

A. L’arbre de jeu

Deux joueurs, conventionnellement MAX (qui joue en premier et maximise) et MIN (qui minimise la même quantité). Un arbre de jeu a la position initiale à la racine, une branche par coup légal, des couches alternées de nœuds MAX et MIN, et des positions terminales aux feuilles portant une utilité - le gain pour MAX.

Comme l’utilité de MIN est l’opposée de celle de MAX, c’est un jeu à somme nulle : ce que l’un gagne, l’autre le perd exactement. C’est ce qui permet à un seul nombre par feuille de décrire l’issue pour les deux.

B. La valeur minimax

La valeur d’un nœud se définit récursivement :

$$\textsc{Minimax}(s) = \begin{cases} \textsc{Utility}(s) & \text{if } s \text{ is terminal},\\[4pt] \max_{a} \textsc{Minimax}(\textsc{Result}(s, a)) & \text{if } s \text{ is a MAX node},\\[4pt] \min_{a} \textsc{Minimax}(\textsc{Result}(s, a)) & \text{if } s \text{ is a MIN node}. \end{cases}$$

MAX choisit la plus grande valeur parmi les enfants ; MIN choisit la plus petite. Les valeurs se propagent des feuilles jusqu’à la racine, et le meilleur coup de MAX à la racine est celui qui mène à l’enfant dont la valeur égale celle de la racine.

Ce que l’hypothèse achète, et ce qu’elle coûte. Le minimax suppose un adversaire qui joue optimalement. Contre un adversaire optimal, la valeur est exactement ce que MAX peut garantir : c’est donc une vraie garantie du pire cas, non une prédiction. Contre un adversaire faible elle est conservatrice : elle peut renoncer à un piège dans lequel un adversaire faillible serait tombé.

C. Dérouler un arbre à la main

Un arbre à trois demi-coups : la racine est MAX, ses trois enfants sont des nœuds MIN, chacun avec trois enfants terminaux.

La couche MIN. Chaque nœud MIN prend le minimum de ses enfants :

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

La racine. MAX prend le maximum :

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

MAX devrait aller en $B$, garantissant au moins 3.

Remarquez le peu d’importance des grandes valeurs de feuilles. Le $12$ sous $B$ et le $14$ sous $D$ ne sont jamais obtenus, car MIN ne les autoriserait jamais - MIN va respectivement au $3$ et au $2$. Seuls les minima de chaque branche survivent.

D. L’élagage alpha-bêta

Le minimax examine chaque feuille, ce qui est sans espoir pour de vrais jeux - l’arbre croît exponentiellement avec la profondeur. L’élagage alpha-bêta calcule la valeur identique en sautant les branches dont on peut prouver qu’elles ne peuvent pas l’affecter.

Deux valeurs sont transportées dans la recherche, définies par Russell et Norvig ainsi :

• $\alpha$ - la valeur du meilleur choix (le plus élevé) trouvé jusqu’ici en tout point de choix le long du chemin, pour MAX ;
• $\beta$ - la valeur du meilleur choix (le plus bas) trouvé jusqu’ici le long du chemin, pour MIN.

La recherche élague les branches restantes d’un nœud dès qu’on sait que la valeur du nœud est pire que l’$\alpha$ courant (pour MAX) ou le $\beta$ courant (pour MIN).

E. Élaguer l’arbre, pas à pas

En parcourant le même arbre de gauche à droite :

Nœud $B$. On examine $3$, $12$, $8$. Rien ne peut être élagué - c’est la première branche et MAX n’a pas encore d’$\alpha$. $B = 3$, la racine pose donc $\alpha = 3$ : MAX peut déjà garantir 3.

Nœud $C$. On examine la première feuille, $2$. $C$ est un nœud MIN, donc sa valeur finale est au plus $2$ - MIN ne peut que descendre à partir d’ici.

Or MAX dispose déjà d’un 3 garanti ailleurs. Une branche valant au plus 2 ne sera jamais préférée à une branche valant 3, quel que soit le contenu des feuilles restantes. Les feuilles $4$ et $6$ ne sont donc jamais examinées. C’est l’élagage.

Nœud $D$. On examine $14$ : valeur provisoire $14$, encore au-dessus de $\alpha = 3$, pas d’élagage. On examine $5$ : valeur provisoire $5$, encore au-dessus de $3$. On examine $2$ : valeur $2$. $D = 2$.

Racine. $\max(3, 2, 2) = 3$ - la même réponse que le minimax complet.

L’alpha-bêta a examiné 7 des 9 feuilles, en élaguant les deuxième et troisième enfants de $C$.

Son exécution affiche la valeur 3 par les deux méthodes, examined: [3, 12, 8, 2, 14, 5, 2] (sept feuilles), et les deux feuilles élaguées.

F. Pourquoi l’ordre des coups décide de tout

L’élagage dépend de la découverte précoce des bons coups. Si le meilleur coup de MAX est examiné en premier, $\alpha$ monte immédiatement et élague agressivement. S’il est examiné en dernier, il n’y a rien contre quoi élaguer avant la fin.

Avec un ordre parfait, l’alpha-bêta examine à peu près $O(b^{m/2})$ nœuds au lieu de $O(b^m)$ pour un facteur de branchement $b$ et une profondeur $m$. Cet exposant divisé par deux signifie chercher deux fois plus profond dans le même temps - la différence entre un programme amateur et un programme expert.

L’ordre parfait suppose de connaître la réponse d’avance : les vrais programmes l’approchent donc par des heuristiques - essayer d’abord les prises, essayer le coup qui était le meilleur à la profondeur inférieure précédente, et ainsi de suite.

G. Quand l’arbre est trop grand malgré tout

Même divisé par deux, l’exposant défait des jeux comme les échecs ou le go. Les programmes pratiques s’arrêtent tôt et appliquent une fonction d’évaluation aux positions non terminales, estimant l’utilité au lieu de la calculer.

Cela introduit deux nouveaux problèmes qui méritent d’être nommés. L’effet d’horizon est la tendance à repousser une perte inévitable juste au-delà de la profondeur de recherche, si bien qu’elle semble évitée alors qu’elle est simplement hors de vue. Et la fonction d’évaluation doit être appliquée à des positions quiescentes - s’arrêter au milieu d’un échange donne une estimation gravement fausse, la recherche est donc prolongée jusqu’à ce que les choses se stabilisent.

Historiquement, la recherche alpha-bêta fut conçue par John McCarthy en 1956 ; sa correction et sa complexité en temps furent établies par Knuth et Moore en 1975.

À retenir

• La recherche adversariale suppose un adversaire optimal, ce qui fait de la valeur minimax une garantie du pire cas.
• MAX maximise, MIN minimise, et les valeurs se propagent des feuilles à la racine.
• Notre arbre : nœuds MIN $3, 2, 2$ ; valeur racine $3$ ; MAX joue vers $B$.
• L’alpha-bêta renvoie la valeur identique en sautant des branches prouvablement hors sujet - 7 feuilles au lieu de 9 ici.
• $\alpha$ est la meilleure garantie de MAX jusqu’ici, $\beta$ celle de MIN ; une branche est coupée dès qu’elle ne peut plus les battre.
• L’ordre des coups détermine le bénéfice ; un ordre parfait divise à peu près par deux l’exposant de profondeur effective.

La suite

Le minimax suppose une opposition stricte. La plupart des situations stratégiques réelles ne sont pas à somme nulle - les joueurs peuvent gagner tous les deux ou perdre tous les deux, et « jeu optimal » demande à être redéfini. Cette généralisation est La théorie des jeux et l’équilibre de Nash.