Il y a quelque chose d'étrange dans le fait que la stratégie aux échecs, ce jeu millénaire d'intuition et d'art, puisse être réduite à un algorithme de quelques lignes. L'algorithme minimax fait exactement cela : il formalise le coeur du raisonnement stratégique dans un jeu à somme nulle en une récurrence mathématique élégante. Et ce n'est pas seulement l'âme des moteurs d'échecs modernes : c’est aussi une analogie utile pour organiser ton calcul, sans constituer une description démontrée de ton cerveau. (Pour le cadre théorique général dont minimax est l'algorithme central, voir théorie des jeux aux échecs ; pour le théorème qui garantit l'existence d'une valeur à toute position, le paradoxe de Zermelo.)

L'intuition derrière minimax

Imagine que tu joues les Blancs et que tu veux choisir le meilleur coup possible. Comment le définir ? Le meilleur coup est celui qui, en supposant que ton adversaire joue aussi parfaitement, te donne le meilleur résultat final.

Cette définition récursive est l'essence de minimax. Blanc veut maximiser le résultat (du point de vue des Blancs). Noir veut minimiser le résultat (du point de vue des Blancs, ou symétriquement maximiser du sien). Les deux joueurs alternent, et à chaque niveau de l'arbre, c'est l'un ou l'autre qui joue.

La formalisation mathématique est directe :

Où est la position courante, est la profondeur de recherche restante, est l'ensemble des coups légaux en , et est la position résultant du coup en .

La fonction d'évaluation : le coeur du moteur

Minimax pur résoudrait les échecs parfaitement si tu pouvais explorer l'arbre complet jusqu'aux positions terminales. Avec les moyens actuels, une telle exploration complète n'est pas réalisable en raison de la complexité combinatoire (l’ordre de grandeur de Shannon illustre l’explosion des suites de coups, pas un dénombrement exact des feuilles). Il faut arrêter la recherche à une profondeur finie et évaluer les positions non-terminales avec une fonction d'évaluation heuristique.

Une évaluation classique combine des caractéristiques telles que le matériel, la mobilité, la sécurité des rois et la structure de pions. Ces repères aident à lire une position ; ils ne constituent pas des valeurs absolues indépendantes du contexte.

Stockfish a intégré l’évaluation neuronale NNUE en 2020. Il faut distinguer cette architecture des anciennes sommes de critères écrits à la main. Dans la récurrence présentée, « évaluation » doit retourner l’utilité exacte d’une issue terminale et une estimation pour une position simplement coupée à profondeur zéro.

L'élagage alpha-bêta : l'intelligence de l'abandon

L'algorithme minimax brut est d'une inefficacité spectaculaire. Pour une profondeur de recherche de demi-coups et un facteur de branchement de (nombre moyen de coups légaux), le nombre de feuilles est de l’ordre de dans le modèle uniforme. À et , c'est positions. Impossible en pratique.

L'élagage alpha-bêta, présenté dans le chapitre de Russell et Norvig, réduit le coût en élaguant les branches qui ne peuvent pas influencer la décision finale.

Le principe est le suivant : si tu as déjà trouvé une option pour Blanc qui garantit un résultat de valeur , et que tu explores une branche où Noir peut forcer un résultat inférieur à pour Blanc, cette branche peut être abandonnée. Blanc ne la choisira jamais, car il a déjà mieux.

Formellement, tu maintiens deux bornes (dans le pseudo-code ou sur le tableau) :

  • : la meilleure valeur déjà garantie pour le joueur maximisant (Blanc)
  • : la meilleure valeur déjà garantie pour le joueur minimisant (Noir)

Quand , la branche courante est élagée : elle ne peut pas produire un résultat meilleur que ce qui est déjà connu.

Dans le cas optimal (si les meilleurs coups pour le camp au trait sont examinés en premier), alpha-bêta ramène l’ordre de grandeur vers . Il ne s’agit pas d’une égalité donnant le nombre exact de nœuds d’une position réelle.

Arbre minimax à trois niveaux avec élagage alpha-bêta : les branches grisées sont abandonnées car alpha vaut déjà 3, rendant inutile l'exploration de toute branche où MIN peut forcer moins de 3.

Negamax : la simplification qui change le code

Negamax exploite l’identité en évaluant la position du point de vue du joueur au trait. Le signe change lors d’un changement de camp. C’est une reformulation possible de minimax, pas une description de tous les moteurs ni une garantie de code plus court d’un nombre précis de lignes.

Null-move pruning : faire passer son tour pour gagner du temps

Une heuristique puissante : et si tu passes ton tour ? Si la position reste bonne pour toi malgré ce coup gratuit donné à l'adversaire, alors elle est probablement très bonne pour toi, et tu peux élaguer profondément le reste de l'analyse. C'est le null-move pruning, technique standard depuis les années 1990. Aux échecs, l'astuce a une limite connue (le zugzwang : situation où tout coup empire la position, typique des finales de pions), donc les implémentations ajoutent des conditions et des vérifications pour limiter ce risque. Un gain de vitesse universel de deux à quatre n’est pas établi ici.

Null-move pruning : si la position reste positive après un coup nul (passer son tour), le moteur élague profondément l'arbre ; avec la limite du zugzwang, que les implémentations cherchent à traiter par des conditions et vérifications.

Les techniques avancées des moteurs modernes

Les moteurs d'échecs modernes comme Stockfish ajoutent de nombreuses techniques au-dessus d'alpha-bêta de base :

Tables de transposition : un cache de positions déjà analysées. Si la même position est atteinte par des ordres de coups différents (transposition), le moteur réutilise l'analyse précédente au lieu de la recalculer. Les tables de transposition peuvent économiser des ordres de grandeur en temps de calcul.

Deux chemins peuvent rejoindre une même position

Approfondissement itératif : au lieu d'effectuer directement une recherche à profondeur , le moteur enchaîne des recherches successives à profondeur 1, 2, 3, ..., . Chaque itération fournit un meilleur ordonnancement des coups pour l'itération suivante, améliorant l'efficacité de l'élagage.

Recherche de quiescence : à la profondeur maximale, au lieu d'évaluer statiquement, la recherche se prolonge sur certains coups tactiques selon l’implémentation ; une position où le roi est en échec demande notamment des réponses légales, pas seulement des captures. Cela évite d'évaluer des positions où un échange de pièces non résolu fausserait l'évaluation.

Extensions de recherche : dans certaines positions (mat en vue, pion passé avancé, position critique), la profondeur de recherche est automatiquement étendue au-delà de la limite nominale pour éviter l'effet d'horizon.

Réductions de recherche (LMR) : inversement, pour les coups peu prometteurs (late move reduction), la profondeur est réduite pour économiser du temps. Si ces coups s'avèrent meilleurs que prévu, la profondeur est restaurée.

Une recherche qui évolue

Le code publié de Stockfish combine recherche, tables de transposition, approfondissement itératif et plusieurs mécanismes sélectifs. Ils ne doivent pas être confondus avec l’alpha-bêta exact sur un arbre fixé.

L’annonce NNUE de 2020 illustre une autre évolution : changer l’évaluation sans abandonner la famille de recherche alpha-bêta. Le moteur moderne ne se réduit donc pas à une formule matérielle suivie d’une exploration aveugle.

AlphaZero : une autre architecture de recherche

En 2017, DeepMind a publié les résultats d'AlphaZero, un programme qui a appris à jouer aux échecs par auto-jeu en quelques heures et battu Stockfish de façon convaincante.

AlphaZero emploie une recherche arborescente Monte-Carlo (MCTS), guidée par un réseau qui propose des probabilités de coups et une estimation de la valeur. La sélection des branches répartit les visites selon ces estimations et l'exploration, sans se confondre avec un parcours minimax exhaustif.

On peut analyser des sacrifices et l'activité des pièces dans les parties publiées, mais ces descriptions stylistiques n'établissent pas une intuition humaine dans le programme. La force du résultat doit se lire avec les conditions du match, le matériel et les versions comparées.

AlphaZero associe apprentissage par renforcement et recherche MCTS, une autre architecture que la recherche alpha-bêta classique. Son score dans un match ne mesure pas une « compréhension plus profonde » ni une distance à la stratégie optimale. Les protocoles sont présentés dans AlphaZero et Stockfish, les coûts de recherche dans les limites du calcul et les limites de l’analogie du chaos dans la théorie du chaos aux échecs.

Minimax comme outil pour ton calcul

Quand tu penses « si je joue là, quelle est sa meilleure réponse ? », tu peux utiliser minimax comme grille de lecture. Cela ne démontre pas que ton cerveau exécute cette procédure et ne permet pas d’attribuer 3–8 ou 7–10 niveaux à une catégorie de joueurs.

Sur une position d’entraînement, choisis deux coups candidats et examine une réponse adverse à chacun. Puis cherche une défense que tu n’avais pas envisagée. L’objectif est d’améliorer la vérification, pas de reproduire une mesure de profondeur humaine.

Même problème, deux démarches : un algorithme défini sur un arbre et un raisonnement humain dont les limites varient.

Un calcul alpha-bêta entièrement vérifiable

Construisons un arbre fictif où les Blancs choisissent A, B ou C, puis les Noirs répondent. Les valeurs sont des unités d'évaluation choisies pour l'exercice, pas des résultats d'une partie historique.

Coup blanc Valeurs possibles après les réponses noires Valeur retenue par MIN
A 5 ; 2 ; 4 2
B 1 ; 8 ; 9 1
C 3 ; 6 ; 4 3

Minimax choisit C, car . Il ne choisit pas B malgré la feuille à 9 : les Noirs peuvent imposer 1. Ces calculs ne demandent aucune intuition sur le style d'un moteur.

Examine les branches dans l'ordre A, B, C. Après A, les Blancs disposent d'une option de valeur 2. Dans B, la première réponse noire vaut 1. Comme les Noirs peuvent déjà limiter cette branche à 1 ou moins, les feuilles 8 et 9 n'ont plus besoin d'être lues pour choisir à la racine : B ne dépassera pas A. La branche C doit encore être examinée, car sa première valeur 3 laisse ouverte une option meilleure.

Inverse maintenant l'ordre des réponses noires dans B et lis 9, puis 8, puis 1. Tu devras aller jusqu'à la troisième feuille pour trouver la borne utile. La valeur finale reste identique, mais le coût change. L'ordre des coups améliore donc l'efficacité d'alpha-bêta sans modifier la question mathématique.

Une transposition demande un état correctement défini

Un même placement de pièces peut apparaître après des ordres différents. Par exemple, 1.Cf3 d5 2.d4 et 1.d4 d5 2.Cf3 conduisent au même placement et au même camp au trait. Cet exemple simple explique l'intérêt de réutiliser une analyse plutôt que de refaire tout le sous-arbre.

Mais un cache naïf fondé uniquement sur les cases occupées serait insuffisant. Les droits de roque, la possibilité d'une prise en passant et les informations nécessaires aux règles de nulle peuvent changer la suite légale ou son résultat. Il faut aussi connaître la profondeur de la recherche et le type de valeur enregistré : exacte pour la recherche effectuée, borne inférieure ou borne supérieure.

Pourquoi une borne ? Après une coupure, on peut savoir qu'une branche vaut au plus 1 sans avoir calculé sa valeur exacte. Remplacer « au plus 1 » par « exactement 1 » dans toutes les recherches ultérieures serait une erreur de programmation. Les tables réelles doivent préserver le sens de l'information qu'elles réemploient.

L'effet d'horizon ne disparaît pas avec une belle évaluation

Imagine un cas pédagogique fictif : une capture gagne une tour à la profondeur où la recherche s'arrête, mais la reprise adverse, juste au-delà, perd la dame. Si la feuille tronquée est évaluée avant cette reprise, elle donne une image trompeuse du gain matériel. Prolonger certaines suites tactiques permet de réduire ce problème.

Cela explique le rôle d'une recherche de quiescence, sans lui donner un pouvoir universel. Il faut choisir quels coups poursuivre, traiter les échecs et éviter une explosion nouvelle de l'arbre. Toutes les erreurs d'évaluation ne sont pas des échanges inachevés. Une faiblesse positionnelle ou un plan à longue portée peut aussi rester hors de l'horizon utile.

Le code officiel de Stockfish distingue plusieurs mécanismes de recherche. Lire un fichier de moteur permet de voir une architecture concrète ; cela ne transforme pas toutes ses heuristiques en théorèmes d'exactitude. Les paramètres et les implémentations évoluent avec les versions.

Trois niveaux de garantie à ne pas mélanger

Le premier niveau est le jeu résolu jusqu'aux issues terminales : la valeur correspond aux règles et aux résultats exacts de cet arbre complet. Le deuxième est l'arbre tronqué avec une évaluation définie : alpha-bêta exact retrouve la même valeur que minimax pour cet arbre, même si l'évaluation n'est pas la vérité échiquéenne. Le troisième est la recherche sélective pratique, qui gagne du temps en concentrant ou réduisant l'effort selon des heuristiques.

Cette distinction explique comment un moteur peut être extraordinairement fort sans prouver chaque évaluation affichée. Elle explique aussi pourquoi deux profondeurs, deux versions ou deux ressources de calcul peuvent modifier le choix. Une valeur affichée constitue une information d'analyse à interpréter avec son contexte de recherche.

Pour t'entraîner, compare deux candidats dans une de tes parties et précise le statut de ta conclusion : mat démontré, gain matériel après une ligne vérifiée, ou préférence de position. Tu ne reproduis pas Stockfish ; tu apprends à dire exactement ce que ton calcul établit.

Sources

  • Russell, S., & Norvig, P. (s. d., chapitre en ligne). Adversarial Search. Artificial Intelligence: A Modern Approach. Chapitre.
  • Équipe Stockfish (s. d.). search.cpp. Dépôt officiel Stockfish. Code.
  • Équipe Stockfish (2020). Introducing NNUE Evaluation. Annonce.
  • Silver, D., et al. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv. Article.