Le minimax : comment pense un adversaire qui vous veut le pire

Théorie des jeux, partie 3 sur 9

Manchester, 1952. Alan Turing joue aux échecs contre Alick Glennie, mais ce n’est pas lui qui choisit ses coups. Il exécute un programme écrit quelques années plus tôt avec David Champernowne.

Aucun ordinateur capable de le faire tourner n’existe encore : le processeur, c’est Turing lui-même. Un crayon, du papier et des dizaines de minutes par coup.

Le programme, qu’on appellera plus tard Turochamp, a perdu la partie en 29 coups. Mais la règle que suivait Turing lui a survécu, à lui comme à son époque. Aujourd’hui, la plupart des logiciels d’échecs classiques choisissent leurs coups avec elle, tout comme le bot de dames de MindLounge. Cette règle s’appelle le minimax.

Juger un coup sur son pire scénario

L’idée du minimax tient en une phrase : jugez votre coup sur la meilleure réponse de l’adversaire, et non sur celle que vous espérez.

Le plus simple est de partir d’un piège que presque tout le monde rencontre en apprenant les échecs, le coup du berger :

1.e4 e5 2.Fc4 Cc6 3.Dh5

Les Blancs menacent 4.Dxf7, mat. Si les Noirs ne voient pas la menace et jouent par exemple 3...Cf6 ??, la partie est finie en un coup. Certains tendent ce piège en se disant : « et si ça marchait ? »

Le minimax pose une autre question : que se passe-t-il si les Noirs trouvent la meilleure réponse ? Voici, approximativement, comment Stockfish 16 évalue les deux options (profondeur 28–30, en pions ; un signe plus indique un avantage blanc) :

Après 3...g6, la dame doit reculer et les Noirs gagnent du temps pour se développer. Le petit avantage que les Blancs tenaient du trait passe chez l’adversaire. Il est modeste, mais c’est un prix — et il ne vaut pas la peine d’être payé pour l’espoir d’une erreur d’autrui. Vous pouvez analyser vous-même la position après 3.Dh5.

D’où vient le nom ? Dans chaque position, l’adversaire choisit le coup qui minimise votre résultat. Parmi vos coups, vous choisissez celui dont ce minimum est le plus élevé. Le maximum des minimums : le minimax.

Pourquoi le pessimisme n’est pas ici une faiblesse

Dans la vie, on qualifie rarement de sage quelqu’un qui s’attend toujours au pire. Pourquoi est-ce alors la bonne stratégie devant l’échiquier ?

La réponse vient du mathématicien d’origine hongroise John von Neumann. En 1928, la revue Mathematische Annalen publie son article « Zur Theorie der Gesellschaftsspiele » — « Sur la théorie des jeux de société ». Son idée clé est le jeu à somme nulle : ce que gagne un joueur, l’autre le perd. Les échecs, les dames, le go ou le poker à deux sont des jeux à somme nulle.

Dans un tel jeu, l’adversaire qui vous veut le pire n’est pas malveillant. Il joue simplement pour lui. Le pire pour vous est exactement le meilleur pour lui. Supposer qu’il trouvera la réponse la plus forte n’est donc pas du pessimisme : c’est prendre ses intérêts au sérieux.

Von Neumann a démontré davantage. Tout jeu fini à deux joueurs et à somme nulle possède un nombre : la valeur du jeu.

Le premier joueur peut s’assurer au moins ce résultat, quoi que fasse l’adversaire. Le second peut garantir que le premier n’obtiendra pas plus. La garantie « par le bas » et la garantie « par le haut » coïncident.

Une réserve importante s’impose. Dans les jeux à information cachée, comme pierre-feuille-ciseaux, cette égalité n’est atteinte que si les joueurs choisissent leurs coups au hasard, selon certaines probabilités. Ces stratégies mixtes auront leur propre volet dans la série.

Aux échecs et aux dames, où tout est visible, la valeur est atteinte par une suite de coups ordinaire. C’est ce que nous avons appelé « la réponse des échecs » dans le deuxième volet.

En 1944, von Neumann et l’économiste Oskar Morgenstern publient Theory of Games and Economic Behavior (« Théorie des jeux et comportement économique »). Avec ce livre, la théorie des jeux sort de l’échiquier.

Comment calculent les machines

Le théorème dit que la valeur du jeu existe, pas comment la trouver. Nous l’avons vu dans le volet précédent : on ne peut pas calculer les échecs jusqu’au bout. Que fait donc un programme ?

En 1950, Claude Shannon décrit une recette toujours en usage. Le programme déploie un arbre de variantes sur quelques demi-coups, puis s’arrête. Il évalue les positions finales de manière approchée, à l’aide d’une fonction d’évaluation : matériel, activité des pièces, sécurité du roi.

Ces notes remontent ensuite l’arbre selon la règle du minimax. Là où le programme a le trait, on prend le maximum ; là où c’est l’adversaire, le minimum.

Le programme de Turing faisait exactement cela, mais sur papier. Il regardait environ trois demi-coups en avant et suivait les prises jusqu’à ce qu’il n’y en ait plus.

La deuxième grande découverte est l’élagage alpha-bêta. Plusieurs chercheurs l’ont trouvé indépendamment dans les années 1950 et 1960 ; Donald Knuth et Ronald Moore en ont publié une analyse complète en 1975. L’idée parlera à tous ceux qui ont mis trop longtemps à choisir un restaurant.

Supposons que vous ayez déjà trouvé un coup qui vous garantit une position égale. Vous examinez un autre coup et voyez que l’adversaire a une réponse qui vous coûte une pièce. Inutile de regarder les autres réponses à ce coup : il est déjà moins bon que celui que vous avez. Avec un ordre des coups idéal, cet élagage permet de calculer jusqu’à environ deux fois plus profond dans le même temps.

Le Stockfish d’aujourd’hui fonctionne de la même manière : recherche alpha-bêta et fonction d’évaluation. Seule l’évaluation a changé. Depuis 2020, elle s’appuie sur un réseau de neurones, NNUE, et plus seulement sur des règles écrites par des humains.

Le minimax sur MindLounge

Le bot d’échecs de MindLounge, c’est Stockfish, volontairement affaibli par son réglage de niveau. Pour les dames, il n’existe pas de moteur de cette envergure prêt à l’emploi ; le bot de dames a donc été écrit pour le site à partir de zéro. C’est du minimax avec élagage alpha-bêta à l’état pur.

Voici ce que montre son code :

• les niveaux ne diffèrent que par la profondeur : le facile calcule 2 demi-coups, le moyen 4, le difficile 6 ;
• un pion vaut 1 point et une dame 1,6, avec 0,05 de plus pour chaque rangée parcourue par un pion ;
• entre deux chemins également gagnants, le bot choisit le plus court.

Attention, lecteurs habitués aux dames internationales sur 100 cases : MindLounge joue sur un damier de 64 cases, selon les règles anglo-américaines. Les dames ne se déplacent que d’une case, la prise est obligatoire et une rafle commencée doit être menée jusqu’au bout.

Que signifie concrètement une profondeur de 2 ? Nous avons pris une position construite pour cet article et y avons lancé le code du bot. Le bot joue les Noirs (« n ») ; trait aux Noirs :

8 · · · · 7 · · n n 6 · · · · 5 · · b n 4 · · · · 3 · · · b 2 · b · · 1 · · · · a b c d e f g h

Le niveau facile a joué e7-f6. Le coup a l’air actif : les Noirs attaquent le pion e5. À profondeur 2, le bot voit son coup et une réponse des Blancs. Quatre coups ont reçu la même note, et, comme le prévoit son code, il a pris le premier.

Mais les Blancs répondent g3-h4 ! Les Noirs sont obligés de prendre : f6xd4. Cette prise libère f6, et les Blancs raflent deux pions d’un coup, h4xf6xh8, en allant à dame au passage. Le dernier pion noir, en d4, tombe au coup suivant.

Les niveaux moyen et difficile ont joué g5-f4. La profondeur 4 a vu que e7-f6 perd un pion. La profondeur 6 en a vu davantage : après e7-f6, la partie est perdue.

Même règle, même code ; la seule différence, c’est jusqu’où il voit. Les programmeurs appellent cela l’effet d’horizon : ce qui se passe au-delà de la profondeur de recherche n’existe pas pour le minimax.

Là où le minimax ne suffit pas

Il est utile de connaître aussi les limites de cette façon de penser.

L’horizon. Le minimax vaut exactement ce que vaut sa profondeur. Devant l’échiquier, un humain a lui aussi un horizon. Se demander avant chaque coup « et si l’adversaire trouvait la réponse la plus forte ? », c’est le repousser d’au moins un demi-coup.

Un adversaire en chair et en os. Le minimax suppose que l’adversaire joue parfaitement. Les gens se trompent, et les joueurs expérimentés choisissent parfois le coup qui pose le plus de problèmes pratiques. Mais un calcul honnête vérifie d’abord si ce coup détériore la position face à un jeu précis. Si c’est le cas, ce n’est plus une stratégie, c’est un pari sur l’erreur.

La somme non nulle. C’est la limite principale. Le minimax se justifie quand votre gain est la perte de l’adversaire. Dans une négociation, au travail ou en amitié, ce n’est généralement pas le cas. Agir comme si l’autre vous voulait le pire, c’est risquer que tous deux repartent les mains vides. C’est le sujet du prochain volet.

Exercice

1. Une autre position sur laquelle nous avons testé le bot. Le niveau facile (Noirs) a joué a7-b6. Trouvez le coup blanc qui gagne du matériel.

8 · · · · 7 n n · · 6 · · · · 5 · n b · 4 n · · · 3 b · b · 2 b · · · 1 · · · · a b c d e f g h

1. Vous hésitez entre les coups A et B. Contre A, l’adversaire a deux réponses : l’une vous laisse à +3, l’autre à −1. Contre B, les deux réponses vous laissent à +1 et +2. Quel coup choisit le minimax ? Et celui qui compte sur une erreur ?
2. Jouez contre le bot de dames de MindLounge au niveau facile et essayez de lui tendre un coup « j’en donne un, j’en prends deux ». Puis tentez la même chose au niveau moyen.

Les réponses sont à la fin.

Questions pour la discussion

• Vous est-il arrivé de tendre un piège en comptant sur une erreur de l’adversaire ? Comment cela s’est-il terminé ?
• Dans quelles situations de votre vie est-il utile de supposer le pire coup de « l’adversaire », et dans lesquelles cette hypothèse fait-elle du tort ?
• Au niveau facile, le bot ne calcule pas mal : il ne voit simplement pas loin. Vos propres erreurs sur l’échiquier ressemblent-elles à cela ?

Prochainement dans la série : « Le dilemme du prisonnier », un jeu où chacun agit raisonnablement pour lui-même… et où tous deux perdent.

Réponses. 1) e3-d4 ! Les Noirs doivent prendre par c5xe3, et les Blancs répondent par la rafle double a3xc5xa7. Dans cette position, les niveaux moyen et difficile jouent c7-b6 et n’autorisent pas le coup. 2) Le minimax choisit B : son pire cas est +1, contre −1 pour A. Celui qui compte sur une erreur choisit A pour le +3. 3) Pas de réponse toute faite ici : l’expérience est la vôtre.