Jeux et recherche adversariale

Une recherche dans un jeu commence par un état : suffisamment d'informations pour déterminer ce qui peut se produire ensuite. Au morpion, il s'agit de la grille et du joueur au trait. La grille seule est incomplète, car la prochaine marque dépend du joueur dont c'est le tour.

Définir les six composantes

Un modèle de jeu fournit :

• Un état initial, $S_0$.
• Une fonction, $\text{Joueur}(s)$, qui indique le joueur agissant dans l'état $s$.
• Les coups autorisés, $\text{Actions}(s)$.
• Un modèle de transition, $\text{R}\acute{\text{e}}\text{sultat}(s,a)$, qui donne l'état après l'action $a$.
• Un test de fin de partie, $\text{Est-Terminal}(s)$, qui détecte la fin de la partie.
• Une fonction d'utilité, $\text{Utilit}\acute{\text{e}}(s,p)$, qui donne le gain numérique du joueur $p$ dans un état terminal.

Au morpion, on part d'une grille vide de 3×3 cases et X joue en premier. Une action choisit une case vide. La transition place la marque du joueur au trait et passe le tour à l'autre joueur. La partie se termine dès qu'un joueur aligne trois marques sur une ligne, une colonne ou une diagonale, ou lorsque la grille pleine donne une partie nulle. Du point de vue de X, attribue +1 à une victoire, 0 à une partie nulle et −1 à une défaite. Le test de fin de partie doit être exécuté avant de placer une autre marque : la partie ne continue pas après une victoire.

Classer le jeu selon des axes distincts

Ces axes sont indépendants. Les dés rendent le backgammon stochastique même si son plateau est visible. Les cartes cachées concernent l'information, et non le caractère aléatoire d'une action elle-même. Dans un jeu à information cachée, un joueur raisonne sur les états possibles compatibles avec ses observations, qui forment un état de croyance.

Garder un point de vue fixe sur les gains

Dans un jeu à deux joueurs à somme nulle, le gain d'un joueur est la perte de l'autre. Les scores à somme constante se comportent de la même façon : 1 pour une victoire, 0 pour une défaite et ½ pour chaque joueur en cas de partie nulle donnent toujours un total de 1. Un seul nombre suffit pour exprimer cette opposition. Appelons MAX le joueur qui souhaite l'augmenter et MIN celui qui souhaite le réduire. Ce sont des rôles : MAX n'est pas nécessairement toujours les Blancs ou X.

Une recherche ordinaire peut choisir chaque action le long d'un chemin. Un agent qui joue doit répondre à des coups qu'il ne contrôle pas. Sa solution est une stratégie, qui précise quoi faire dans chaque situation qu'il pourrait rencontrer. Un plan qui ne fonctionne que si l'adversaire donne une réponse favorable ne suffit pas.

Un arbre de jeu part de l'état courant. Chaque arête sortante représente un coup autorisé et son enfant est l'état obtenu. Indique à chaque nœud non terminal le joueur qui y agit. Dans un jeu à deux joueurs qui jouent chacun leur tour, les niveaux de MAX et de MIN alternent.

Compter les tours individuels

Un demi-coup est un coup joué par un joueur. Aux échecs, un coup complet comprend généralement un tour des Blancs et un tour des Noirs, soit deux demi-coups. Une recherche à la profondeur 4 depuis le tour des Blancs atteint les positions obtenues après que les Blancs, les Noirs, les Blancs puis les Noirs ont joué. Compte les arêtes à partir de la racine, dont la profondeur est zéro.

Soit $b$ le facteur de branchement et $m$ la profondeur maximale. Un arbre uniforme a $b^d$ nœuds à la profondeur $d$ et $b^m$ feuilles. Son nombre total de nœuds est :

Pour $b>1$, les niveaux les plus profonds dominent, ce qui donne une croissance exponentielle. Avec quatre coups par position, la profondeur 3 compte 64 feuilles et la profondeur 4 en compte 256. Un demi-coup supplémentaire multiplie le nombre de feuilles par quatre et non par un.

Distinguer les parties des positions

Le morpion compte au plus $9!=362880$ ordres pour remplir la grille. Beaucoup continueraient après une victoire et ne sont pas des parties complètes autorisées. En s'arrêtant immédiatement à chaque victoire, on obtient 255 168 parties complètes : 131 184 victoires de X, 77 904 victoires de O et 46 080 parties nulles. Dans les parties autorisées, il n'existe que 5 478 positions distinctes sur la grille, grille vide comprise.

L'écart vient en partie des transpositions : des ordres de coups différents qui atteignent le même état. X peut jouer dans un coin, O au centre, puis X dans le coin opposé, ou X peut jouer ces deux coins dans l'ordre inverse. Les deux chemins aboutissent à la même grille et au même joueur au trait. Un arbre conserve les deux chemins ; un graphe de jeu peut stocker une seule fois leur état commun. Pour réutiliser le travail, il faut identifier les états complets, et non seulement les grilles visuellement semblables.

Comprendre pourquoi la recherche complète devient impossible

On modélise souvent les échecs avec environ 35 coups autorisés par position et une partie de 100 demi-coups, soit 50 coups par joueur. On obtient cet ordre de grandeur :

Les branches réelles se terminent à des profondeurs différentes et présentent des nombres de coups différents, mais cette estimation suffit à expliquer pourquoi il est irréaliste d'énumérer un arbre de jeu d'échecs entier. Sur un plateau de go vide de 19×19 cases, la première pierre dispose à elle seule de 361 points possibles.

L'arbre de recherche est ce qu'un algorithme génère effectivement. Pour un jeu fini qu'il explore jusqu'au bout, minimax simple génère l'arbre de jeu complet sous l'état considéré. L'élagage, les limites de profondeur et la simulation sélective en génèrent moins. Une feuille de coupure peut donc être une position non terminale, même si une feuille de l'arbre de jeu complet est terminale.

Visualiser une stratégie dans l'arbre

Un sous-arbre de stratégie pour MAX conserve une arête choisie à chaque nœud de MAX et toutes les arêtes autorisées à chaque nœud de MIN. MAX choisit sa propre action mais doit conserver une réponse à tout coup de l'adversaire. Un seul chemin de la racine à une feuille ne décrit qu'une partie possible. Il ne peut pas montrer que le plan choisi résiste aux autres réponses.

Minimax choisit le meilleur résultat que MAX peut garantir face à un adversaire optimal. L'utilité de chaque feuille est mesurée pour MAX. Un grand nombre favorise MAX, même lorsque le nœud évalué appartient à MIN.

Remonter des feuilles vers la racine

À un nœud terminal, renvoie son utilité. À un nœud de MAX, renvoie la plus grande valeur des enfants. À un nœud de MIN, renvoie la plus petite. Continue jusqu'à ce que la racine reçoive une valeur :

La valeur d'un enfant résume déjà la suite optimale à partir de cet enfant. C'est pourquoi un parent compare les valeurs renvoyées au lieu de rouvrir chaque feuille située en dessous. La récursion fonctionne quel que soit le nombre de niveaux alternés.

Suivre une décision sur deux demi-coups

MAX dispose de trois coups qui mènent chacun à un nœud de MIN :

Prends d'abord le minimum de chaque ligne. MIN peut ramener la valeur de A à 4, celle de B à 2 et celle de C à 5. MAX prend ensuite le maximum de ces trois résultats :

La valeur minimax est 5. La décision minimax est le coup vers C. La première est un nombre qui décrit la position ; la seconde est une action que le programme peut jouer.

La plus grande feuille, 15, se trouve sous B, mais MAX ne contrôle pas la réponse qui y mène. MIN choisirait 2. La moyenne des feuilles de B vaut 10, ce qui paraît également attrayant, mais une moyenne modélise un choix aléatoire avec des probabilités adaptées. Face à un adversaire optimal, il faut prendre un minimum.

Lire la variante principale

La variante principale est la suite suivie lorsque les joueurs choisissent des coups optimaux. Ici, MAX joue C et MIN choisit sa feuille de valeur 5. Dans un arbre plus profond, suis le maximum ou le minimum choisi à chaque niveau. L'utilité terminale de cette suite correspond à la valeur de la racine. Si plusieurs coups sont ex æquo, plusieurs suites optimales peuvent exister.

Comprendre la garantie

Dans un jeu fini, déterministe, à deux joueurs, à somme nulle et à information parfaite, suivre la stratégie minimax garantit au moins la valeur de la racine. Un adversaire optimal limite MAX à cette valeur. Une erreur de l'adversaire peut permettre un meilleur résultat : 5 est donc un minimum garanti, et non une prédiction selon laquelle chaque partie se termine exactement à 5.

Un programme peut exploiter une faiblesse tout en conservant ce minimum garanti. Si deux coups ont tous deux une valeur minimax de 5, il peut préférer celui qui donne davantage d'occasions à l'adversaire de se tromper. Choisir un coup de valeur minimax 2 parce qu'il contient un 15 tentant revient à abandonner la garantie de 5. La différence tient au fait que le coup conserve ou non la meilleure valeur dans le pire cas.

La définition de minimax est déjà un programme récursif. Une fonction de valeur prend un état et renvoie un nombre. Une fonction de recherche compare les premiers coups possibles et renvoie l'action à jouer.

Séparer le choix du coup du calcul de la valeur

Le pseudocode suivant suppose que MAX joue à la racine et que les tours alternent :

MINIMAX-SEARCH(s):
    if Is-Terminal(s): return no action
    bestMove = no action
    bestValue = -infinity
    for a in Actions(s):
        value = MIN-VALUE(Result(s, a))
        if value > bestValue:
            bestValue = value
            bestMove = a
    return bestMove

MAX-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a)))
    return v

MIN-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a)))
    return v

Initialise MAX à l'infini négatif pour que n'importe quel enfant améliore sa valeur ; initialise MIN à l'infini positif. Teste la fin de partie avant de générer les successeurs. Une grille de morpion pleine sans alignement gagnant est une partie nulle, et non une position non terminale dont il faut choisir le meilleur coup dans une liste vide.

Suivre ce que découvre la récursion

Considère cette grille de morpion, où X est au trait et un point représente une case vide :

X O X
. O .
. . .

O menace de compléter la colonne du milieu. Si X joue ailleurs qu'en bas au milieu, O peut gagner au tour suivant. Ces coups ont une valeur de −1 pour X. Jouer en bas au milieu bloque la victoire immédiate et permet une partie nulle si les deux joueurs jouent au mieux, ce qui donne la valeur 0. La racine renvoie la case du bas au milieu. L'algorithme n'a pas besoin d'une instruction distincte indiquant cette menace : les issues terminales déterminent les valeurs.

Évaluer le coût en temps et en mémoire

Minimax en profondeur d'abord examine $O(b^m)$ nœuds pour un facteur de branchement $b$ et une profondeur maximale $m$. Stocker tous les nœuds frères générés à chaque niveau actif nécessite une mémoire $O(bm)$. Générer les successeurs un par un réduit le stockage de la recherche active à $O(m)$, indépendamment de la représentation de l'état. Le temps exponentiel, et non la pile de récursion, constitue généralement le principal obstacle.

Respecter la convention de calcul des scores

Dans le code MAX/MIN, chaque appel renvoie l'utilité de MAX. N'inverse pas son signe simplement parce que MIN joue ensuite. Negamax utilise une autre convention : chaque valeur est donnée du point de vue du joueur au trait ; la valeur d'un enfant est donc changée de signe avant que le parent ne la maximise :

Pour un jeu qui se termine en moins de 100 demi-coups, on peut tenir compte du moment de l'issue en attribuant à une victoire de MAX à la profondeur $d$ le score $100-d$, à une défaite le score $-100+d$ et à une partie nulle le score 0. Les victoires plus rapides obtiennent alors un meilleur score et les défaites retardées sont moins négatives. La limite stricte de profondeur garantit que chaque victoire reste positive et chaque défaite négative.

Par exemple, les victoires aux demi-coups 3 et 7 valent 97 et 93 : la victoire la plus rapide est donc préférée. Les défaites à ces profondeurs valent −97 et −93, ce qui rend la défaite plus tardive préférable, même si les deux restent moins bonnes qu'une partie nulle.

Une seule utilité pour MAX suffit lorsque les intérêts de deux joueurs sont strictement opposés. Avec plusieurs joueurs ou des intérêts qui se rejoignent, conserve un vecteur d'utilités. Pour les joueurs A, B et C, le vecteur (1, 2, 6) donne leurs gains dans cet ordre.

Choisir selon la composante du joueur actif

À un nœud où C joue, compare les troisièmes composantes des vecteurs des enfants. Renvoie le vecteur entier de l'enfant préféré par C. À un nœud de B, compare les deuxièmes composantes des vecteurs renvoyés ; à un nœud de A, compare les premières.

Ne maximise pas chaque composante indépendamment. Si les issues possibles sont (1, 2, 6) et (4, 2, 3), C choisit (1, 2, 6). La combinaison (4, 2, 6) n'est pas une issue possible et ne peut pas être remontée.

Remonter les choix de trois joueurs

A joue en premier, puis B et enfin C. Après le coup de gauche de A, B choisit entre deux nœuds de C :

• Le premier a pour feuilles (1, 2, 6) et (4, 2, 3). C choisit (1, 2, 6).
• Le second a pour feuilles (6, 1, 2) et (7, 4, 1). C choisit (6, 1, 2).

B compare les deuxièmes composantes, 2 et 1 : la branche de gauche renvoie donc (1, 2, 6).

Après le coup de droite de A :

• C choisit (5, 4, 5) plutôt que (2, 5, 4), car 5 dépasse 4 dans la troisième composante.
• C choisit (5, 2, 4) plutôt que (7, 7, 1), car 4 dépasse 1 dans la troisième composante.

B compare les deuxièmes composantes, 4 et 2 : la branche de droite renvoie donc (5, 4, 5). Enfin, A compare les premières composantes, 1 et 5, et choisit la droite. La racine reçoit le vecteur entier (5, 4, 5).

Préciser comment les ex æquo sont départagés

Si C peut choisir (2, 3, 4) ou (6, 1, 4), les deux donnent 4 à C. Le gain final de A pourrait être 2 ou 6. Une prédiction nécessite une règle de départage ou un modèle du choix de C. L'indifférence d'un autre joueur n'est pas nécessairement sans conséquence pour le joueur à la racine.

Si deux poursuivants veulent tous deux capturer MAX, un tour comprend un niveau MAX et un niveau MIN pour chaque poursuivant. Avec deux poursuivants, un tour représente trois demi-coups. Ce modèle diffère de celui de trois joueurs indépendants qui poursuivent leurs propres récompenses.

Admettre que les intérêts peuvent se rejoindre

Dans un jeu à somme générale, les deux joueurs peuvent préférer (100, 100) à des gains conjoints plus faibles. Les joueurs peuvent aussi tirer temporairement avantage d'une attaque contre un meneur commun. Un tel comportement, semblable à une alliance, peut découler de leurs propres préférences et changer lorsque la position change.

Les coupures alpha-bêta ordinaires reposent sur des intérêts opposés et ne s'appliquent pas directement aux vecteurs d'utilités. Le modèle paranoïaque rétablit une opposition entre deux joueurs, ce qui permet la recherche alpha-bêta, mais il peut prédire une hostilité coordonnée que les autres joueurs ne choisiraient pas réellement.

L'élagage alpha-bêta donne la même valeur à la racine que minimax sur le même arbre avec les mêmes valeurs aux feuilles. Il économise du travail en démontrant que certaines branches ne peuvent pas améliorer le choix. Des coups optimaux ex æquo peuvent être renvoyés dans un ordre différent.

Transmettre une fenêtre de recherche le long du chemin

Deux bornes décrivent les choix disponibles au-dessus du nœud courant :

• $\alpha$ est la meilleure valeur disponible pour MAX le long du chemin : MAX peut déjà obtenir au moins cette valeur.
• $\beta$ est la meilleure valeur disponible pour MIN le long du chemin : MIN peut déjà limiter MAX à cette valeur au plus.

Initialise la racine avec l'infini négatif et l'infini positif. Chaque enfant récursif reçoit les bornes courantes. Ce sont des arguments locaux, et non des nombres globaux partagés entre des recherches de nœuds frères sans lien.

À un nœud de MAX, conserve la plus grande valeur d'enfant rencontrée. Arrête-toi lorsqu'elle atteint ou dépasse bêta : MIN, plus haut, dispose déjà d'une autre possibilité qui ne dépasse pas bêta. Sinon, augmente alpha lorsque MAX trouve une amélioration. À un nœud de MIN, conserve la plus petite valeur d'enfant rencontrée. Arrête-toi lorsqu'elle atteint alpha ou lui devient inférieure : MAX, plus haut, dispose déjà d'une autre possibilité au moins aussi bonne. Sinon, diminue bêta.

MAX-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a), alpha, beta))
        if v >= beta: return v
        alpha = max(alpha, v)
    return v

MIN-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a), alpha, beta))
        if v <= alpha: return v
        beta = min(beta, v)
    return v

La racine compare les actions et conserve alpha entre elles :

ALPHA-BETA-SEARCH(s):
    if Is-Terminal(s): return no action
    alpha = -infinity
    beta = +infinity
    bestMove = no action
    for a in Actions(s):
        v = MIN-VALUE(Result(s, a), alpha, beta)
        if v > alpha:
            alpha = v
            bestMove = a
    return bestMove

Suivre une coupure à un nœud de MIN

Explore de gauche à droite les branches de MIN A = (4, 9, 6), B = (2, 15, 13) et C = (5, 8, 10). A doit examiner ses trois feuilles et renvoie 4. La racine a maintenant un alpha de 4. La première feuille de B vaut 2. Son minimum final ne peut que rester à 2 ou diminuer : B ne peut donc pas surpasser A. Ignore les deux feuilles restantes de B. C examine ses trois feuilles et renvoie 5. La racine choisit C après avoir examiné sept feuilles sur neuf.

Suivre une coupure à un nœud de MAX

Supposons qu'un parent de MIN possède déjà un enfant de valeur 3, ce qui fixe bêta à 3. Son enfant de MAX suivant trouve une feuille de valeur 6. La valeur de cet enfant est d'au moins 6 : MIN préférera donc la valeur 3 dont il dispose déjà. Ignore les enfants restants de ce nœud de MAX. Le raisonnement justifiant la coupure utilise l'autre possibilité de MIN, même si le nœud courant est celui de MAX.

Un nœud de MIN élagué peut renvoyer une borne supérieure ; un nœud de MAX élagué peut renvoyer une borne inférieure. Leurs valeurs exactes restent inconnues. La valeur obtenue à la racine est exacte pour l'arbre exploré. L'égalité permet aussi une coupure, car une branche qui peut au mieux égaler la meilleure valeur courante ne peut pas l'améliorer.

Alpha-bêta économise le plus de travail lorsque les coups forts sont explorés tôt. Les valeurs ne changent pas avec l'ordre des coups, mais le moment où la recherche peut justifier une coupure change.

Comparer deux ordres

Pour les trois branches de MIN A = (4, 9, 6), B = (2, 15, 13) et C = (5, 8, 10), commencer par A conduit à examiner sept feuilles. Commence plutôt par C. Ses trois feuilles fixent alpha à 5. A trouve ensuite immédiatement 4 et effectue une coupure ; B trouve immédiatement 2 et effectue une coupure. Seules cinq feuilles sont évaluées et la réponse reste C, de valeur 5.

Pour un arbre uniforme avec un ordonnancement parfait, le nombre de feuilles est :

Cela représente environ $O(b^{m\mathrm{/}2})$ au lieu de $O(b^m)$ pour minimax. Le facteur de branchement effectif descend à environ $\sqrt{b}$, ce qui permet d'atteindre environ deux fois la profondeur pour un budget comparable. Avec $b=35$, la recherche à la profondeur 8 avec un ordonnancement parfait évalue 3 001 249 feuilles ; minimax ordinaire à la profondeur 4 en compte 1 500 625. La comparaison porte sur l'ordre de grandeur et non sur un temps d'exécution identique.

Dans le pire ordre, alpha-bêta peut examiner chaque feuille de minimax. Ses vérifications supplémentaires des bornes ajoutent un surcoût même lorsqu'elles n'économisent aucune feuille.

Utiliser des indices d'ordonnancement peu coûteux

Le meilleur coup exact est inconnu avant la recherche. Les programmes utilisent des estimations rapides. Aux échecs, ils peuvent essayer les prises, puis les menaces, puis les coups calmes. Un coup tueur a provoqué une coupure ailleurs à la même profondeur de recherche et est essayé tôt dans une autre position. Ces indices influencent l'efficacité ; ils ne justifient pas d'écarter les autres coups autorisés.

L'approfondissement itératif recherche jusqu'à la profondeur 1, puis 2, puis 3 et ainsi de suite. Un coup fort de l'itération précédente devient un candidat examiné tôt dans la suivante. Le résultat de l'itération achevée la plus profonde est aussi prêt si le temps est écoulé.

Le coût du travail répété varie selon l'élagage. Pour une recherche uniforme sans élagage avec un facteur de branchement de 35, toutes les itérations moins profondes ajoutent environ $1\mathrm{/}(35-1)\approx \mathrm{2,9}\mathrm{\%}$ à la recherche finale. Pour alpha-bêta avec un ordonnancement parfait, les profondeurs 1 à 7 réunies évaluent 1 677 159 feuilles, soit environ 56 % du nombre de feuilles à la profondeur 8. Un meilleur ordonnancement peut malgré tout rendre l'ensemble du processus avantageux.

Mettre les positions en mémoire avec leur signification

Une table de transposition stocke des résultats indexés par état de jeu complet. Si un autre ordre de coups atteint cet état, le programme peut réutiliser une entrée adaptée. Stocke la profondeur explorée et indique si le résultat est exact, une borne inférieure ou une borne supérieure. Une entrée peu profonde ne remplace pas les informations nécessaires à une recherche plus profonde. Une borne peut resserrer une fenêtre ou justifier une coupure, mais ne doit pas être traitée comme une valeur exacte.

Une fonction d'évaluation estime à quel point une position non terminale est favorable à MAX. Elle rend possible la recherche à profondeur limitée : la frontière reçoit des valeurs estimées que minimax ou alpha-bêta peut faire remonter.

Rendre les scores utiles à la recherche

Une bonne fonction d'évaluation est rapide, respecte l'ordre des issues terminales réelles et donne des valeurs corrélées au succès à partir des positions non terminales. Les états terminaux eux-mêmes doivent recevoir leur utilité exacte. Une victoire de MAX doit obtenir un score supérieur à toute estimation non terminale, afin que gagner des pièces ne puisse pas devenir plus attrayant que gagner la partie.

Une façon de voir l'évaluation consiste à regrouper les positions selon leurs caractéristiques communes. Si un tel groupe produit 72 % de victoires, 8 % de parties nulles et 20 % de défaites, avec les utilités 1, ½ et 0, son utilité moyenne est :

Cette interprétation dépend de la façon dont les positions et leurs suites ont été échantillonnées. C'est une estimation de la qualité de l'issue, et non une preuve de victoire forcée.

Ajouter des caractéristiques pondérées

Une conception courante utilise une somme pondérée :

Chaque caractéristique $f_i(s)$ mesure une propriété de la position ; chaque poids $w_i$ indique sa contribution. Les différences entre les camps rendent le point de vue explicite. Une différence matérielle positive signifie que MAX a plus de matériel.

Les valeurs traditionnelles aux échecs sont : pion 1, cavalier 3, fou 3, tour 5 et dame 9. Aucune valeur matérielle de pièce capturable n'est attribuée au roi. Supposons que MAX joue les Blancs. Les Blancs ont une dame, deux tours, un fou et six pions :

Les Noirs ont deux tours, deux cavaliers, un fou et sept pions :

La caractéristique matérielle vaut donc $28-26=2$. Si les Blancs ont 30 coups autorisés et les Noirs 24, la différence de mobilité est de 6. Avec un poids de 1 pour le matériel et de 0,1 pour la mobilité :

Ce 2,6 est un score de caractéristiques, et non une probabilité de victoire de 260 %. Les poids définissent son échelle.

Tenir compte des interactions entre caractéristiques

Une somme linéaire simple donne à chaque caractéristique une contribution fixe indépendante des autres. La valeur réelle dans le jeu peut dépendre de combinaisons : une paire de fous peut valoir plus que la somme de leurs effets séparés et l'importance d'un pion peut changer en finale. Des caractéristiques combinées, des poids dépendant de la phase de jeu ou des fonctions d'évaluation non linéaires peuvent rendre compte de ces effets. Les poids peuvent être choisis par jugement ou ajustés aux résultats de parties enregistrées.

Davantage de caractéristiques prennent aussi plus de temps. Une fonction d'évaluation élaborée qui empêche d'explorer un demi-coup supplémentaire utile peut nuire à la décision, même si ses estimations individuelles s'améliorent.

Adapter l'échelle à la règle de remontée

Dans minimax déterministe, des transformations strictement croissantes appliquées de manière cohérente préservent l'ordre à travers les maxima et les minima. Élever au carré uniquement des scores positifs, par exemple, conserve leur ordre. Élever au carré des scores de signes quelconques ne le conserve pas. Aux nœuds de hasard, les écarts réels entre les utilités comptent, car les valeurs sont moyennées. Un score conçu uniquement pour classer les positions doit être calibré avant de pouvoir représenter une espérance d'utilité.

Minimax heuristique s'arrête avant la fin de la partie. Sa réponse est optimale pour l'arbre exploré avec les scores attribués à sa frontière. Il peut tout de même choisir un coup perdant dans le jeu réel lorsque ces estimations ne rendent pas compte de ce qui se produit ensuite.

Distinguer les états terminaux des coupures

Un état terminal a une issue connue. Une coupure en profondeur laisse la partie inachevée et nécessite une estimation. Effectue les tests dans cet ordre :

H-MINIMAX(s, d):
    if Is-Terminal(s): return Utility(s, MAX)
    if Is-Cutoff(s, d): return Eval(s)
    if To-Move(s) == MAX:
        return max over a of H-MINIMAX(Result(s, a), d + 1)
    return min over a of H-MINIMAX(Result(s, a), d + 1)

Le test de coupure vérifie généralement si la profondeur a atteint une limite. Alpha-bêta peut élaguer ce même arbre heuristique. Son élagage reste exact relativement à ces valeurs de frontière ; il ne transforme pas les estimations en véritables issues du jeu.

Lorsque le temps est limité, l'approfondissement itératif conserve l'action de l'itération achevée la plus profonde. Une recherche plus profonde mais inachevée à la racine peut favoriser la première branche simplement parce que les autres n'ont pas encore été évaluées.

Terminer un échange tactique

Une position quiescente est suffisamment calme pour qu'une courte suite forcée ait peu de chances de modifier fortement son évaluation. La recherche de quiescence se poursuit au-delà de la profondeur normale dans les positions instables, généralement en suivant les prises jusqu'à ce que l'échange se stabilise.

Supposons que la dame blanche prenne un pion exactement à la limite de profondeur. Le score matériel s'améliore de 1. Mais les Noirs peuvent reprendre cette dame au demi-coup suivant. Le changement net de matériel est :

S'arrêter après la première prise indique +1 ; une courte extension des prises révèle −8. Le problème vient de l'évaluation au milieu d'un échange, et non d'une défaillance de la règle de remontée de minimax.

Reconnaître les pertes retardées

L'effet d'horizon se produit lorsqu'un programme retarde une perte inévitable jusqu'à ce qu'elle se trouve au-delà de la profondeur de recherche. Un fou piégé peut tout de même être perdu après plusieurs échecs donnés avec des pions. Si la recherche voit les échecs mais s'arrête avant la prise du fou, elle peut sacrifier des pions pour masquer cette perte future.

Une extension singulière explore plus profondément un coup qui se distingue nettement des autres possibilités. Les programmes prolongent aussi les échecs contraignants ou les reprises. Les extensions consacrent une profondeur supplémentaire à certaines suites ; elles nécessitent un budget pour que la recherche puisse tout de même se terminer.

L'élagage anticipé, qui consiste par exemple à ne conserver que quelques-uns des meilleurs coups, peut écarter le coup gagnant. Les économies réalisées ne bénéficient pas de la garantie d'alpha-bêta.

Remplacer la recherche par des connaissances exactes stockées

Une bibliothèque d'ouvertures fournit des coups de début de partie étudiés. Les tables de finales remontent depuis des issues connues par analyse rétrograde. Les tables de finales d'échecs à sept pièces comprennent les deux rois et fournissent des résultats exacts pour les finales qu'elles couvrent. Les règles et les informations sur l'état utilisées pour consulter une table doivent correspondre au jeu en cours.

Un nœud de hasard représente un événement aléatoire. Ses branches indiquent les issues possibles et leurs probabilités, dont la somme vaut 1. Aucun joueur ne choisit la branche qui lui est la plus favorable.

Utiliser la règle propre à chaque nœud

Pour des issues $r$, un nœud de hasard a pour valeur :

Expectiminimax combine les quatre règles. Expectimax utilise MAX et le hasard lorsqu'il n'y a pas de joueur qui minimise. Un modèle probabiliste d'un adversaire aléatoire peut fournir des branches de hasard même dans un jeu dont les règles de déplacement sont déterministes.

Remonter à travers le hasard et l'opposition

MAX choisit L ou R. Chaque coup mène à un événement aléatoire, suivi d'un choix de MIN.

Après L, une pièce équilibrée donne deux nœuds de MIN. Leurs feuilles sont (3, 7) et (8, 4). MIN renvoie 3 et 4. Le nœud de hasard donne alors :

Après R, les probabilités 0,25 et 0,75 mènent à des nœuds de MIN dont les feuilles sont (10, 1) et (6, 5). Leurs valeurs sont 1 et 5, donc :

MAX choisit R car 4 dépasse 3,5. Calculer d'abord la moyenne des feuilles terminales brutes laisserait le hasard remplacer la décision de MIN. Traite chaque nœud après avoir résolu ses enfants.

Attribuer les bonnes probabilités

Deux dés équilibrés ont 36 issues ordonnées équiprobables. Le backgammon regroupe les ordres inversés, comme 3-5 et 5-3, en un même lancer. On obtient ainsi 21 lancers distincts : six doubles de probabilité 1/36 chacun et 15 lancers sans double de probabilité 1/18 chacun. La vérification donne :

Attribuer la probabilité 1/21 à chacun des 21 lancers compterait trop les doubles et pas assez les autres lancers. Des branches qui semblent équivalentes n'ont pas nécessairement des probabilités égales.

Si chaque étape de décision comporte $b$ coups autorisés et un événement aléatoire à $n$ issues, explorer $m$ étapes de ce type coûte environ $O(b^m{n}^m)$. La convention de profondeur doit tenir compte de la fréquence des événements aléatoires. Avec environ 20 coups autorisés et 21 lancers, les branches de hasard supplémentaires du backgammon limitent rapidement l'anticipation exhaustive.

Par exemple, deux étapes comportant chacune 21 issues aléatoires et 20 actions produisent $(21\times 20{)}^2=176400$ chemins. Compte les événements aléatoires séparément des demi-coups des joueurs pour estimer ce coût.

N'élaguer que lorsque les issues non examinées sont bornées

Une moyenne partielle n'est pas une borne minimax. Si les utilités sont comprises entre 0 et 10 et que la première de deux issues équiprobables vaut 2, la valeur du nœud entier est comprise entre 1 et 6. En particulier :

Si MAX dispose déjà d'un autre coup de valeur 7, ce nœud de hasard ne peut pas le surpasser et l'issue restante peut être ignorée. Sans borne adaptée sur les valeurs non examinées, une issue extrême pourrait encore modifier suffisamment la moyenne pour inverser le choix.

Minimax cherche le résultat qu'un adversaire peut imposer. Expectimax cherche l'utilité moyenne qui découle d'un modèle probabiliste. Leurs décisions peuvent différer même sur un même arbre, car elles représentent des comportements différents.

Comparer une opposition optimale et une opposition aléatoire

Pour les branches de MIN A = (4, 9, 6), B = (2, 15, 13) et C = (5, 8, 10), minimax choisit C avec une garantie de 5. Si l'adversaire choisit plutôt chaque réponse uniformément, les espérances sont d'environ 6,33, 10 et 7,67. Expectimax choisit B.

Ce choix est raisonnable selon le modèle uniforme, mais un adversaire expérimenté peut répondre à B par 2. Expectimax ne suppose pas que l'adversaire minimise une moyenne. Il utilise les probabilités indiquées. Avec un modèle correct, il maximise l'espérance d'utilité ; la protection dans le pire cas est plus faible que celle de minimax. Sa performance moyenne peut égaler celle de minimax lorsque les deux recommandent le même coup.

Un arbre peut mélanger les modèles. Le nœud d'un agent hostile prend un minimum, tandis que celui d'un agent aléatoire prend une moyenne pondérée. Utilise la règle de l'agent qui agit au nœud considéré, et non une même règle pour chaque niveau autre que MAX.

Comprendre pourquoi l'ordre seul ne suffit pas

Supposons que le coup A donne 2 avec une probabilité de 0,6 et 3 avec une probabilité de 0,4. Le coup B donne 1 avec une probabilité de 0,6 et 4 avec une probabilité de 0,4 :

A a la plus grande espérance. Élève maintenant chaque valeur terminale au cube. Leur classement reste le même, mais les espérances deviennent :

B l'emporte maintenant dans la comparaison. Calculer la moyenne des issues transformées diffère de transformer leur moyenne. La mise au cube amplifie suffisamment l'avantage de l'issue élevée de B pour modifier la décision.

Préserver les décisions avec les bonnes transformations

Une transformation affine strictement croissante multiplie chaque espérance par le même nombre positif et ajoute la même constante. Appliquer $10x+5$ donne à A une valeur de 29 et à B une valeur de 27 : A reste préféré.

Si A et B étaient des nœuds de MIN, leurs valeurs seraient 2 et 1 avant la mise au cube, puis 8 et 1 après. Leur ordre resterait inchangé. Les maxima et les minima sélectionnent la valeur d'un enfant ; les moyennes combinent les grandeurs de plusieurs valeurs.

Une fonction d'évaluation utilisée en présence de hasard devrait donc estimer l'espérance d'utilité visée sur une échelle cohérente, comme la probabilité de victoire ou une transformation affine strictement croissante de celle-ci. Un score de classement non linéaire peut convenir à minimax déterministe tout en conduisant à de mauvais compromis face au risque en présence de hasard.

La recherche arborescente de Monte-Carlo estime les coups à partir de parties simulées tout en construisant un arbre qui guide les simulations futures. Une suite simulée jusqu'à la fin est une simulation de partie ou partie simulée. Sa politique peut choisir des coups autorisés au hasard ou utiliser des connaissances peu coûteuses pour produire un jeu plus raisonnable.

Stocker les éléments observés à chaque nœud

Conserve un nombre de visites $N(n)$ et une récompense cumulée $U(n)$. Dans un jeu à deux joueurs avec victoire ou défaite, compte les victoires du joueur qui a joué le coup menant au nœud $n$. Une partie nulle ajoute généralement une demi-victoire. Alors, $U(n)\mathrm{/}N(n)$ estime le taux de réussite de ce joueur.

La racine n'a pas de coup entrant. Ses visites comptent tout de même chaque itération ; ses victoires peuvent être suivies du point de vue du joueur à la racine si nécessaire. Les scores des enfants, qui guident la sélection, doivent toujours utiliser le point de vue du joueur ayant joué le coup entrant.

Répéter les quatre phases

1. Sélection : depuis la racine, suivre une politique de sélection parmi les enfants existants jusqu'à atteindre un nœud terminal ou un nœud possédant un coup non essayé.
2. Développement : si le nœud n'est pas terminal, ajouter un enfant pour un coup autorisé non essayé.
3. Simulation : simuler une partie depuis cet enfant jusqu'à une issue terminale.
4. Rétropropagation : mettre à jour les visites et les récompenses des nœuds sur le chemin sélectionné.

Si la sélection atteint un nœud terminal, ignore le développement et la simulation. Son issue connue peut être remontée immédiatement. La suite temporaire d'une simulation n'a pas besoin d'être stockée sous forme de nouveaux nœuds de l'arbre : le développement ordinaire ajoute un enfant par itération.

Suivre une mise à jour des récompenses

Les Blancs jouent à la racine. La sélection et le développement suivent :

• n1, atteint par un coup des Blancs ;
• n2, atteint par un coup des Noirs ;
• n3, atteint par un coup des Blancs.

La partie simulée se termine par une victoire des Noirs. Augmente les visites de un à la racine ainsi qu'à n1, n2 et n3. Parmi ces trois nœuds enfants, augmente les victoires uniquement à n2, car le joueur ayant joué le coup entrant de n2 était les Noirs. Les nœuds enfants des Blancs ne reçoivent aucune victoire supplémentaire. Si la convention utilise le point de vue du joueur à la racine, le total des victoires de la racine reste lui aussi inchangé.

Une partie nulle ajouterait 0,5 à la récompense de chaque enfant. Compter la victoire des Noirs comme un succès à chaque nœud conduirait les Blancs à choisir des coups qui aident les Noirs.

Laisser l'arbre se développer de manière inégale

Les itérations répétées concentrent les simulations sur les branches prometteuses ou incertaines. Les coups qui semblent forts tendent à acquérir des sous-arbres plus grands, tandis que les mauvais coups reçoivent moins de travail. La recherche n'impose pas une profondeur fixe à chaque suite. Dès qu'un coup autorisé est disponible, elle peut s'arrêter à la limite de temps et utiliser les statistiques accumulées.

L'action finale est généralement celle qui mène à l'enfant de la racine le plus visité. Un coup ayant deux victoires en deux simulations a un taux observé parfait, mais peu d'éléments à l'appui. Un coup très visité a été examiné bien plus souvent pendant la recherche.

La recherche de Monte-Carlo pure attribue aux coups à la racine des simulations indépendantes sans développer d'arbre de décision. Elle peut manquer à plusieurs reprises une réponse forte de l'adversaire, car la suite du jeu reste régie par la politique de simulation. La recherche arborescente de Monte-Carlo apprend où développer l'arbre plus profondément à mesure qu'elle accumule des résultats, même si une réfutation tactique rare peut encore prendre du temps à être découverte.

La recherche arborescente de Monte-Carlo doit décider où une simulation supplémentaire sera la plus utile. L'exploitation revisite les coups qui semblent déjà forts. L'exploration examine les coups pour lesquels on dispose de moins d'éléments et qui pourraient se révéler meilleurs. Chercher toujours le plus grand taux de victoire observé peut enfermer la recherche dans un résultat initial dû à la chance.

Calculer un score UCB1

Le score de borne supérieure de confiance pour l'enfant $n$ est :

Le premier terme est le taux de victoire observé. Le second est un bonus d'exploration. Il augmente lorsque le parent accumule des visites et diminue lorsque l'enfant en reçoit davantage. Le logarithme est népérien. Pendant la sélection, choisis l'enfant dont le score total est le plus élevé.

Considère qu'un enfant non visité a une priorité infinie au lieu de diviser par zéro. Chaque coup autorisé à un nœud est essayé avant que la sélection ne favorise à plusieurs reprises les possibilités déjà visitées. La recherche arborescente de Monte-Carlo utilisant cette règle de sélection est appelée UCT, pour bornes supérieures de confiance appliquées aux arbres.

Comparer trois enfants

Un parent compte 50 visites. Ses enfants ont pour nombres de victoires et de visites 21/30, 7/12 et 3/8. Avec $C=\sqrt{2}$ et $\ln 50\approx \mathrm{3,912}$ :

Le deuxième enfant est sélectionné. Son taux de victoire actuel est inférieur à celui du premier, mais son bonus d'incertitude est plus élevé. Le troisième est encore moins visité, mais son taux de victoire plus faible laisse son total légèrement en dessous de celui du deuxième.

Avec $C=\mathrm{0,5}$, les mêmes totaux deviennent environ 0,881, 0,869 et 0,725. La sélection favorise alors le premier enfant. Aucune issue n'a changé ; le programme a modifié le poids qu'il accorde à l'incertitude.

Interpréter la constante d'exploration

Une valeur positive de $C$ plus grande donne plus de poids à l'exploration. La fixer à zéro supprime le bonus et conduit à choisir uniquement selon la moyenne observée. La formulation du problème du bandit avec des récompenses comprises entre 0 et 1 motive le choix de $C=\sqrt{2}$ dans cette forme de l'équation ; les programmes de jeu utilisés en pratique ajustent la constante. Modifier l'échelle des récompenses modifie aussi l'équilibre avec le terme d'exploration.

À chaque parent, ses enfants enregistrent les victoires du joueur qui y choisit. Maximiser UCB1 a donc un sens au tour de chacun des deux joueurs. Stocker uniquement les victoires des Blancs dans tout l'arbre tout en maximisant chaque score conduirait les Noirs à favoriser les succès des Blancs.

Distinguer la priorité de recherche de la qualité d'un coup

UCB1 choisit où consacrer la prochaine simulation. Un grand bonus d'incertitude peut rendre intéressant l'examen d'un coup peu échantillonné. À la fin de la recherche, choisis l'enfant de la racine le plus visité, et non celui qui a le score UCB1 actuel le plus élevé. Dans les conditions d'UCT pour un jeu fini et avec une exploration continue, une recherche illimitée converge vers le comportement minimax ; un budget fini laisse toutefois une incertitude d'échantillonnage.

Une méthode de recherche s'adapte à la taille de l'espace des coups, à la qualité de l'évaluation disponible et au type d'incertitude présent dans le jeu. Un même budget de temps peut produire des décisions très différentes selon ce que la méthode examine.

Comparer la couverture tactique et la simulation

Alpha-bêta peut trouver une réfutation tactique unique dans les limites de sa profondeur de recherche. La recherche arborescente de Monte-Carlo peut d'abord préférer un coup qui gagne la plupart des simulations aléatoires mais perd face à une réponse précise. À mesure que son arbre se développe, elle peut découvrir cette réponse, mais un petit budget de simulations peut la manquer. Un taux de victoire élevé dans les simulations ne garantit donc pas le résultat dans le pire cas.

Relier les méthodes à des programmes marquants

En 1997, Deep Blue d'IBM a utilisé la recherche alpha-bêta, du matériel spécialisé et une évaluation des positions d'échecs pour battre le champion du monde Garry Kasparov 3½ à 2½ en six parties. Son succès a montré ce qu'une recherche performante et une évaluation propre au jeu pouvaient accomplir ensemble.

Le go rendait cette association plus difficile. Un plateau vide de 19×19 offre 361 placements de pierre, et il est difficile d'évaluer une position à partir de caractéristiques simples. La recherche arborescente de Monte-Carlo est devenue une approche performante parce qu'elle pouvait estimer les issues en jouant et développer un arbre sélectif sans nécessiter de fonction d'évaluation statique écrite à la main.

AlphaGo associait la recherche arborescente de Monte-Carlo à des réseaux de neurones qui suggéraient des coups et évaluaient les positions. Sa description dans Nature en 2016 a précédé sa victoire 4 à 1 sur Lee Sedol en mars 2016. AlphaZero a ensuite utilisé une évaluation par réseau de neurones à la place des simulations aléatoires et a atteint un niveau surhumain aux échecs, au shogi et au go. Ces programmes montrent qu'un cadre de recherche peut utiliser différentes sources de valeurs pour les positions.

Distinguer un jeu performant de la résolution d'un jeu

Un programme peut battre un champion sans démontrer la valeur de la position initiale. En 2007, l'équipe de Jonathan Schaeffer a utilisé la recherche et de grandes bases de données de finales pour établir que le jeu de dames est nul si les deux camps jouent parfaitement. Résoudre le jeu établit une issue face à toute stratégie adverse possible, et pas seulement face aux adversaires rencontrés en match.

Adapter la méthode au modèle

Dans un jeu stochastique, échantillonne les issues aléatoires selon leurs probabilités réelles pendant le parcours de l'arbre et les simulations. Un événement de probabilité 0,8 devrait se produire environ quatre fois plus souvent qu'un événement de probabilité 0,2 sur un grand nombre de tirages. On estime ainsi la même espérance pondérée que celle calculée par la remontée explicite des valeurs aux nœuds de hasard.

Toute approche dépend encore de règles et de transitions d'état correctes. Alpha-bêta à profondeur limitée dépend de sa fonction d'évaluation ; la recherche arborescente de Monte-Carlo dépend de sa politique de simulation ou d'évaluation et de son budget fini d'échantillons. Modéliser un adversaire hostile comme aléatoire peut coûter cher, quel que soit le mécanisme de recherche utilisé pour calculer la réponse de ce modèle.