Pourquoi les échecs sont un problème mathématique (presque) impossible et comment l'IA s'en sort quand même

Tu as déjà vécu ce paradoxe : les applis et les médias te vendent le jeu d'échecs comme un objet d'une complexité cosmique, un jeu où chaque joueur trace une stratégie sur le long terme ; puis tu ouvres une appli, tu joues un coup raisonnable, et le moteur te corrige puis t'explique une ligne introuvable pour toi seul.

Alors quoi ? Peut-on vraiment tout ramener à des formules ? Ce jeu est-il un problème mathématique auquel les mathématiques et l'informatique apportent des réponses partielles ou est-ce une légende qu'on se répète pour se donner l'air profond ? La réponse tient en deux étapes : cette discipline est impossible à traiter par force brute sur tout l'espace des parties, mais elle devient jouable à un niveau surhumain dès que tu acceptes de mesurer le réel grâce à des programmes où se combinent exploration, évaluation, élagage et, aujourd'hui, apprentissage sur des machines très puissantes.

La vérité est plus intéressante que le mythe : aucune liste finie de coups ne "ferme" le jeu comme un énoncé formel clos et pourtant, des programmes battent régulièrement les meilleurs joueurs humains parce qu'ils ne cherchent pas la perfection absolue, seulement une décision assez bonne face à un adversaire réel.

L'échiquier vu de l'intérieur : un graphe d'états, pas un chaos

Pour un mathématicien ou un informaticien, le jeu d'échecs offre une qualité rare : les règles sont exactes, publiques, et le jeu est déterministe. Un Cavalier saute toujours en L, un Fou reste sur sa couleur : chaque coup légal de ce jeu d'échecs est reproductible, sans hasard ni surprise de règle, même si, devant un humain imprévisible, tu peux avoir l'impression d'incertitude.

• une position complète (pièces, trait, roque, prise en passant…) = un état du jeu ;
• un coup légal = une transition vers un autre état ;
• une partie = une trajectoire, donc une suite d'états dans un espace gigantesque.

Si tu veux être un peu formel, tu peux voir ça comme un graphe orienté : chaque nœud est un état, chaque arête est un coup légal ; depuis un état fixé, tu peux aussi imaginer un arbre d'exploration où les joueurs alternent des branches. Ce cadre est exactement celui exploré en détail dans théorie des jeux aux échecs, avec l'angle dual sur les équilibres dans les ouvertures.

L'arbre des coups : pourquoi "je calcule tout" est un mythe

À ton niveau de club, tu as peut-être déjà entendu un joueur dire : "J'ai tout calculé." C'est une phrase qui sonne bien, mais elle est presque toujours fausse à la rigueur : même les grands maîtres et les champions ne parcourent aucune fraction complète de l'arbre ; du joueur de club au grand maître, chacun n'effleure qu'une infime partie des branches. Ils calculent une petite partie, et ils le font bien.

Les ouvrages notent souvent (b) le nombre moyen de coups possibles (facteur de branchement), (d) la profondeur explorée en demi-coups (plies), et (N(b,d)) le nombre approximatif de nœuds à explorer ; une approximation naïve donne (N(b,d) \approx b^d). Dès que tu ajoutes de la profondeur, tu ne rajoutes pas "un peu" de travail : tu multiplies le travail, c'est une loi des mathématiques : l'exponentielle. Elle explique pourquoi même les machines les plus rapides restent contraintes par le temps disponible et la mémoire, même avec les meilleurs algorithmes connus.

En milieu de partie, (b) tourne souvent autour de 30-40. Si tu prends (b=35), alors à (d=6) c'est déjà énorme, à (d=10) c'est astronomique, à (d=16) c'est une autre planète. Le cerveau humain n'a pas été conçu pour parcourir des millions de branches : il a été conçu pour survivre, reconnaître des motifs, économiser de l'énergie, et c'est une excellente nouvelle, parce que c'est exactement ce que font aussi les moteurs modernes, en combinant algorithme et heuristique.

Pour endiguer cette explosion, il n'y a pas de magie : il faut couper, estimer, ordonner les coups ; autant de méthodes que cet article détaille ensuite.

Le nombre de Shannon : le "wow" qui n'est pas qu'un gimmick

Claude Shannon, professeur au MIT et père de la théorie de l'information, a posé au milieu du XXe siècle une question de mathématiques : combien de parties d'échecs sont possibles ? Son estimation, devenue célèbre, aboutit à (10^{120}), le nombre de Shannon. Attention : ce chiffre n'est pas une vérité gravée dans le marbre ; c'est une mesure pour saisir l'échelle, pas une liste exhaustive de configurations atteignables. Ce qui rend ça fascinant, c'est que cette impossibilité ne vient pas d'un détail technique mais d'une loi profonde : l'espace des possibles est si vaste que "tout explorer" est hors de portée, même pour les algorithmes les plus avancés.

Pourquoi ce jeu n'est pas "résolu" (et pourquoi ça n'empêche pas de gagner)

Un jeu est "résolu" au sens des mathématiques lorsque l'issue du jeu parfait (victoire, défaite, nul) est connue depuis la position initiale et/ou qu'une stratégie optimale est entièrement décrite. La théorie des jeux, héritée de John von Neumann, fournit un outil pour parler de joueurs rationnels et d'équilibre de Nash ; ici, la structure est surtout celle d'un duel à information quasi parfaite.

Le tableau suivant résume la différence entre quelques jeux célèbres et les échecs, le seul tableau de cet article.

Une confusion fréquente : "Si ce n'est pas résolu, un moteur ne peut pas être sûr." C'est exact au sens formel, mais ce n'est pas le but. En usage réel, un moteur n'a pas besoin de résoudre la position initiale pour te battre : il doit jouer suffisamment proche de l'optimal dans les situations réelles. Le théorème qui garantit qu'une réponse existe (sans qu'on puisse la trouver) est analysé en détail dans le paradoxe de Zermelo.

EXPTIME-complet : le résultat de complexité que personne ne contournera

Sur le plan strict de la complexité algorithmique, les échecs généralisés (sur un échiquier $n \times n$) appartiennent à la classe EXPTIME-complet : tout algorithme correct pour résoudre la position initiale demande un temps exponentiel en $n$. C'est le résultat de Fraenkel et Lichtenstein (1981). EXPTIME-complet signifie quelque chose de très fort : aucun progrès algorithmique n'amènera la résolution dans une classe polynomiale, sauf à briser une hiérarchie fondamentale de la théorie de la complexité (EXPTIME $\neq$ P, démontré). C'est l'un des rares résultats où l'on a une preuve d'impossibilité plutôt qu'une simple absence de solution.

Pour les échecs 8×8 spécifiquement (taille fixe, pas généralisée), le statut formel est plus subtil : c'est techniquement un problème fini, donc décidable. Mais la borne pratique reste $10^{120}$ : décidable au sens logique, indécidable au sens physique.

Résoudre un jeu et jouer très fort à ce jeu, ce n'est pas la même chose. Tu peux être imbattable pour l'immense majorité des joueurs sans disposer d'une preuve formelle totale sur l'issue du jeu parfait. Les machines impressionnent parce qu'elles excellent à chercher et à évaluer, pas à "fermer" le jeu par une preuve exhaustive.

Ce que fait un moteur "classique" : minimax, mais pas naïf

Tu peux résumer l'ossature des moteurs traditionnels (type Stockfish) en trois briques :

• exploration : parcours de l'arbre de coups ;
• évaluation : estimer qui est mieux sur le diagramme ;
• optimisations : pour ne pas se noyer dans les branches.

L'idée derrière minimax est presque philosophique : toi, tu cherches à maximiser ton avantage ; ton adversaire cherche à minimiser ton avantage ; tu choisis le coup qui maximise le minimum garanti face au meilleur jeu adverse. La version ultra simplifiée ressemble à une récurrence sur les nœuds du graphe :

Si tu veux une traduction club : minimax, c'est "je ne joue pas un coup qui marche seulement si l'autre dort." C'est une logique claire de prudence rationnelle, pas une garantie contre le tilt, mais un modèle du "pire cas".

Minimax brut, seul, te fait explorer un arbre beaucoup trop gros : sans optimisation, tu meurs avant d'avoir réfléchi ; la bonne nouvelle, c'est qu'une immense partie de l'arbre est inutile si tu sais la couper sans regret. (L'algorithme, ses raffinements modernes (negamax, null-move pruning, table de transposition) et leur version en réseau de neurones sont déroulés dans minimax aux échecs.)

Alpha-bêta : l'art de couper sans regret

L'élagage alpha-bêta est une optimisation du parcours minimax : son but n'est pas de trouver une autre vérité, mais de ne pas calculer ce qui ne peut plus changer la décision. Alpha est la meilleure valeur déjà garantie pour le joueur qui maximise ; bêta est la meilleure valeur déjà garantie pour le joueur qui minimise ; si une branche ne pourra jamais dépasser ce que tu as déjà trouvé ailleurs, tu la coupes.

C'est le même geste que toi quand tu calcules une tactique : tu explores une ligne, tu vois que même si tout marche, tu n'obtiens pas mieux qu'un autre plan, donc tu arrêtes de t'y attarder. La conséquence est énorme : avec un bon ordre des coups, alpha-bêta peut réduire drastiquement le nombre de nœuds explorés ; le moteur gagne des profondeurs "gratuites" pour la qualité affichée à l'écran.

L'évaluation : le vrai cœur, parce que tout est impossible à calculer

Même avec alpha-bêta, tu ne peux pas aller au bout de l'arbre : tu arrives sur des feuilles à profondeur limitée, et tu dois répondre à une question qui ressemble à de la magie : « cette configuration, elle vaut quoi ? ». Les moteurs "classiques" utilisent une fonction d'évaluation faite de critères comme :

• matériel ;
• structure de pions ;
• activité des pièces ;
• sécurité du roi ;
• contrôle de cases (et bien d'autres dans les moteurs de pointe).

Ce n'est pas qu'une addition naïve de points : les bons moteurs combinent des heuristiques, des ajustements et des paramètres optimisés pour obtenir une évaluation corrélée au résultat final sans atteindre ce résultat final. Dans la vraie vie, c'est comme juger une position "prometteuse" sans calculer le mat en vingt-huit coups : tu sais reconnaître un schéma où l'initiative et la paire de fous "sentent bon", même si nulle ligne ne tient lieu de preuve complète. Le moteur formalise ce savoir technique et le fait sans fatigue, pour des milliers de joueurs. (Là où l'évaluation devient instable même pour les moteurs, c'est le terrain analysé dans la théorie du chaos aux échecs : positions à fort exposant de Lyapunov où un demi-pas hors de la ligne juste fait basculer l'évaluation.)

L'IA : quand la machine apprend à évaluer et à choisir, au lieu que tout soit écrit à la main

Depuis quelques années, une idée a gagné une place énorme : au lieu de coder "à la main" une évaluation sophistiquée, il devient possible d'apprendre une évaluation à partir de données ou par auto-jeu. Les réseaux de neurones et l'apprentissage automatique sont au cœur de cette vague. Tu confonds peut-être souvent "IA" et "elle calcule plus" : en réalité, l'IA moderne brille surtout sur deux tâches :

• évaluer un diagramme de façon très riche (représentation compressée) ;
• proposer de bons coups candidats pour orienter l'exploration.

Résultat : le moteur n'a pas besoin d'explorer "tout" : il explore mieux. Tu peux le voir comme une version industrialisée de ce que font les joueurs forts : ils ne regardent pas trente-cinq coups au hasard ; ils en sélectionnent quelques-uns "sérieux", puis ils calculent. L'IA fait pareil avec une cohérence et une profondeur d'entraînement qui dépassent l'intuition.

Le point spectaculaire de certaines approches, c'est l'auto-jeu : une machine s'affronte à elle-même, apprend des positions qu'elle génère, améliore ses évaluations, et recommence. Ce n'est pas un miracle, c'est une boucle simple :

1. générer des expériences ;
2. apprendre à prédire ce qui mène à de bons résultats ;
3. renforcer les choix gagnants ;
4. itérer.

Ce qui est fascinant, c'est qu'en partant d'un jeu aux règles strictes, tu peux faire émerger des préférences stratégiques sans les écrire en français ligne par ligne.

IBM face à Kasparov : un jour historique pour le logiciel (sans "résoudre" le jeu)

En 1997, Deep Blue bat Garry Kasparov alors champion du monde d'échecs, contre une machine IBM conçue spécifiquement pour le jeu d'échecs. Ce succès marque le XXe siècle : le monde entier découvre la puissance du calcul spécialisé.

Pourtant, ce succès ne résout pas les échecs au sens théorique : une machine peut gagner des parties contre le meilleur joueur humain sans posséder une stratégie parfaite depuis la position initiale. Les programmeurs modernes, en France comme partout dans le monde, tirent bien plus du jeu qu'en 1997, sans abolir pour autant le socle de mathématiques sous-jacent.

Modèles stratégiques et mathématiques : ce qu'apporte la science des jeux

La théorie des jeux relie les échecs, via les mathématiques, à toute une famille de modèles où des joueurs choisissent des actions en réaction aux autres. Le formalisme y croise l'économie, l'aide à la décision et le calcul automatisé.

Pour un joueur de club, l'intuition à retenir est simple : tu navigues dans un jeu où le hasard pur est faible, mais l'incertitude sur les choix adverses est réelle, une structure proche des duels étudiés par la science des jeux, même si le jeu garde sa saveur propre.

Démonstrations. La communauté a publié une quantité de travaux sur des sous-problèmes (finales, ouvertures, tables de positions), mais aucune preuve ne fixe l'issue du jeu parfait depuis la position initiale : l'espace des parties résiste à l'exploration exhaustive.

Les notions de décidabilité et de complexité algorithmique expliquent pourquoi "tout tester" n'est pas réaliste. Cette limite n'appauvrit pas le jeu : elle y mêle rigueur et intuition.

"Impossible" ne veut pas dire "inutilisable" : la leçon au-delà du plateau

Les échecs sont un excellent modèle mental pour des problèmes modernes, par exemple :

• la sécurité informatique (attaque / défense) ;
• la stratégie (anticipation d'un adversaire) ;
• l'optimisation (où investir l'effort machine) ;
• la décision quand tu ne peux pas tout savoir d'un coup.

Le message le plus important n'est pas "l'IA est magique" : c'est que la puissance vient moins du fait de tout calculer que du fait de calculer ce qui compte.

À ton échelle de joueur, c'est la même leçon : tu ne peux pas tout voir ; tu peux apprendre à mieux choisir ce que tu regardes. L'échiquier amplifie ce que tu es : si tu cherches le contrôle partout, il te le renverra ; si tu acceptes de progresser sans te définir par un seul chiffre, tu pourras transformer chaque partie en terrain d'expérience.

Ce que ça change pour toi, joueur

À tester ici. Si tu veux voir ce que fait un moteur sur une configuration, ouvre l'espace d'analyse du site (Stockfish dans le navigateur) : profondeur, score et variantes en direct.

Sur le blog.

• Les échecs rendent-ils meilleur en maths ?
• Psychologie du joueur d'échecs
• Les échecs et le cerveau

Les échecs sont "impossibles" si tu imagines une solution brute : tout explorer, tout prouver, tout résoudre d'un seul tenant. Ils deviennent "possibles" dès que tu acceptes la réalité : tu gagnes en sélectionnant, en évaluant et en élaguant. Ce n'est pas la quantité de coups calculés qui fait la force, c'est la qualité du tri. Un joueur lucide le sait déjà.

Pour aller plus loin : chessprogramming.org, ICGA, arXiv.

Après lecture : ouvre l’espace d’analyse, repère le premier coup où ta variante et la ligne du moteur divergent de plus d’un demi-pion, puis rejoue cette position seule trois fois dans la journée (sans nouvelle partie).

À retenir

• L'arbre des parties est borné par le nombre de Shannon ($10^{120}$) : aucun algorithme par force brute n'arrivera à le parcourir
• Les échecs généralisés sont EXPTIME-complet : il existe une preuve d'impossibilité d'algorithme polynomial
• Les moteurs ne résolvent pas, ils approximent : minimax + alpha-bêta + évaluation heuristique + apprentissage
• Battre l'humain et résoudre le jeu sont deux problèmes différents ; Stockfish/AlphaZero font le premier, personne ne fait le second
• Progresser comme joueur, c'est améliorer ta fonction d'évaluation interne et ton élagage intuitif, exactement comme un moteur
• "Impossible" au sens formel ne veut pas dire "inutilisable" : la qualité du tri compte plus que la quantité de calcul

Sources et références

• Shannon, C. E. Programming a Computer for Playing Chess. Philosophical Magazine, Series 7, 41(314), 256-275, 1950. (Estimation originale du nombre de parties possibles, $\sim 10^{120}$.)
• Fraenkel, A. S., & Lichtenstein, D. Computing a Perfect Strategy for n×n Chess Requires Time Exponential in n. Journal of Combinatorial Theory, Series A, 31(2), 199-214, 1981. (Démonstration que les échecs généralisés sont EXPTIME-complets.)
• Knuth, D. E., & Moore, R. W. An Analysis of Alpha-Beta Pruning. Artificial Intelligence, 6(4), 293-326, 1975. (Analyse formelle de l'élagage alpha-bêta.)
• Silver, D., et al. Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv, 2017. (Publication originale d'AlphaZero, MCTS + réseau de neurones.)
• Campbell, M., Hoane, A. J., & Hsu, F. Deep Blue. Artificial Intelligence, 134(1-2), 57-83, 2002. (Description du système Deep Blue qui battit Kasparov en 1997.)
• Allis, L. V. Searching for Solutions in Games and Artificial Intelligence. PhD Thesis, University of Limburg, 1994. (Classification des jeux résolus et méthodes générales de résolution.)

Pour aller plus loin

• Les échecs rendent-ils meilleur en maths ? La vérité scientifique
• La psychologie du joueur d'échecs : ce qui se passe vraiment dans ta tête
• Les échecs et l'addiction : quand le jeu devient une drogue