En 1950, Claude Shannon (le fondateur de la théorie de l'information) publiait un article intitulé "Programming a Computer for Playing Chess". Il n'avait pas encore écrit les programmes. Il calculait si c'était seulement possible.

Sa conclusion : le nombre de positions légales d'échecs est d'environ 10^43. Le nombre de parties distinctes possibles est encore plus grand. Une recherche exhaustive de l'arbre de jeu complet dépasserait les capacités de n'importe quel ordinateur physiquement réalisable : pas par manque de vitesse, mais parce que le temps nécessaire dépasserait l'âge de l'univers.

Il fallait donc trouver autre chose.

Qu'est-ce que la complexité algorithmique ?

La complexité algorithmique est une branche de l'informatique théorique qui étudie les ressources (temps, mémoire) nécessaires pour résoudre des problèmes. Elle classe les problèmes selon leur "difficulté fondamentale" : non pas en pratique sur un ordinateur donné, mais en théorie, asymptotiquement, à mesure que la taille du problème croît.

Les classes les plus connues :

  • P : problèmes solubles en temps polynomial (rapides)
  • NP : problèmes dont les solutions peuvent être vérifiées en temps polynomial (potentiellement lents à résoudre, rapides à vérifier)
  • PSPACE : problèmes solubles avec de la mémoire polynomiale (même si le temps est exponentiel)
  • EXPTIME : problèmes qui nécessitent un temps exponentiel dans le pire cas
  • EXPSPACE : la classe la plus redoutable, nécessitant à la fois temps et mémoire exponentiels

Les échecs généralisés (sur un échiquier n×n au lieu de 8×8) appartiennent à la classe EXPTIME-complets selon les résultats de Fraser et al. (1981). Cela signifie que la résolution exacte des échecs sur un échiquier arbitraire est, au sens formel, aussi difficile que les problèmes les plus durs de sa classe, et qu'aucun algorithme polynomial ne peut espérer les résoudre.

Pour les échecs sur échiquier 8×8 standard, la question est légèrement différente : la partie se termine toujours (règle des 50 coups, répétition), donc le problème est fini. Mais l'espace de recherche reste astronomique.

L'arbre de jeu et la malédiction de l'explosion combinatoire

Imaginez l'arbre de jeu d'une partie d'échecs. À la racine, la position de départ. Après le premier coup des Blancs (20 possibles), 20 nœuds. Après le premier coup des Noirs (20 possibles), 400 nœuds. Après deux coups de chaque côté : environ 8 902 positions. Après cinq coups de chaque côté : environ 69 milliards.

Le facteur de branchement moyen d'une partie d'échecs est d'environ 35 (le nombre de coups légaux dans une position typique). La longueur moyenne d'une partie est d'environ 40 coups par joueur. L'arbre complet a donc approximativement 35^80 ≈ 10^123 nœuds.

C'est le nombre de parties distinctes possibles. Il dépasse de loin le nombre d'atomes dans l'univers observable (10^80). Même si chaque atome de l'univers était un ordinateur analysant un milliard de positions par seconde depuis le Big Bang, on n'aurait exploré qu'une fraction infinitésimale de cet espace.

Cette explosion combinatoire explique pourquoi les premiers programmes d'échecs, dans les années 1950-1970, étaient si faibles malgré des ordinateurs de plus en plus puissants. La force brute seule ne pouvait pas fonctionner. Il fallait des heuristiques : des raccourcis intelligents qui sacrifient la garantie d'optimalité pour la praticabilité.

L'élagage alpha-bêta : le premier grand saut

L'algorithme alpha-bêta pruning, développé dans les années 1950-1960 par plusieurs chercheurs (dont John McCarthy et Donald Knuth), est l'heuristique fondamentale des moteurs d'échecs classiques.

L'idée : si on recherche l'arbre de jeu et qu'on trouve une branche qui ne peut pas être meilleure que ce qu'on a déjà trouvé, on arrête de l'explorer. Plus précisément : on maintient deux valeurs, alpha (le meilleur score que les Blancs peuvent garantir) et bêta (le meilleur score que les Noirs peuvent garantir). Dès qu'une branche produit un score en dehors de cette fenêtre [alpha, bêta], elle est abandonnée.

Dans le meilleur cas, l'élagage alpha-bêta réduit le nombre de nœuds à explorer de la racine carrée de l'arbre complet. À partir d'un espace de 10^123, on peut espérer chercher 10^61, toujours astronomique, mais beaucoup plus gérable avec de bonnes heuristiques d'ordonnancement des coups (chercher d'abord les coups probablement bons rend l'élagage plus efficace).

Combiné à une fonction d'évaluation: une formule qui estime la valeur d'une position sans aller jusqu'aux feuilles de l'arbre : l'alpha-bêta permet de chercher à une profondeur fixe et d'évaluer les positions résultantes. C'est exactement ce que faisait Deep Blue en 1997.

Deep Blue : la victoire de l'ingénierie

Deep Blue n'était pas un programme subtil. C'était un chef-d'œuvre d'ingénierie brute appliqué aux heuristiques d'échecs.

IBM avait construit des puces spécialisées (ASICs) conçues uniquement pour évaluer des positions d'échecs : des centaines en parallèle. Deep Blue évaluait entre 100 et 300 millions de positions par seconde. Avec un élagage alpha-bêta bien optimisé et des heuristiques d'ordonnancement sophistiquées, il cherchait typiquement à une profondeur de 12 à 16 coups, parfois plus dans les positions critiques ("recherche d'extension").

La fonction d'évaluation avait été développée avec l'aide de Grands Maîtres : elle codifiait explicitement des concepts comme la structure de pions, la sécurité du roi, l'activité des pièces, les cases faibles. Chaque concept était traduit en termes numériques, avec des poids ajustés par les ingénieurs.

Kasparov avait battu Deep Blue en 1996 (4-2). Il avait perdu en 1997 (3.5-2.5). Sa défaite n'était pas due à la "compréhension" du jeu par Deep Blue : il n'y en avait aucune au sens cognitif. C'était de la puissance de calcul + des heuristiques humaines codifiées + de l'ingénierie matérielle, poussés jusqu'à un seuil où la force de calcul brut compensait les limitations de l'approche.

AlphaZero : une révolution d'une nature différente

Vingt ans plus tard, DeepMind présentait AlphaZero. La différence n'était pas quantitative : c'était qualitative.

AlphaZero n'avait reçu que les règles du jeu : quelles pièces existent, comment elles bougent, quand une partie se termine. Aucune base de données de parties humaines. Aucune heuristique explicitée. Aucun concept codifié par des Grands Maîtres.

Il jouait contre lui-même : des millions de parties. À chaque partie, un réseau de neurones profond apprenait : quelles positions tendent à être gagnantes, quels coups tendent à être bons depuis quelles positions. Après 9 heures d'entraînement sur des TPUs (processeurs spécialisés de Google), AlphaZero avait atteint un niveau qui dépassait Stockfish, le meilleur moteur "classique" de l'époque.

Le style de jeu qu'AlphaZero avait développé fascinait les Grands Maîtres : dynamique, volontiers sacrificiel, avec des intuitions positionnelles que les théoriciens n'avaient jamais codifiées explicitement. AlphaZero cherchait nettement moins de positions que Stockfish (environ 80 000 par seconde contre 60 millions), mais chacune était évaluée par un réseau de neurones qui encodait une "intuition" apprise par l'expérience plutôt que par des règles explicites.

Ce n'était plus de la recherche exhaustive améliorée. C'était quelque chose de structurellement différent : une approximation de l'intuition par apprentissage profond.

Ce que l'IA révèle sur la cognition humaine aux échecs

La trajectoire Deep Blue → AlphaZero révèle quelque chose d'important sur la nature de la cognition humaine aux échecs.

Deep Blue battait les humains en faisant différemment : plus de calcul brut, plus vite, plus profond. AlphaZero bat les humains en faisant quelque chose de plus similaire à ce que les humains font : de la reconnaissance de patterns, de l'évaluation intuitive, une recherche très élaguée dans l'arbre de jeu.

Les études IRMf sur les joueurs d'échecs experts montrent que leur cerveau n'est pas un calculateur brut. Face à une position, un Grand Maître ne "calcule" pas d'abord toutes les variantes. Il reconnaît la position comme appartenant à une famille, identifie les thèmes clés, et n'explore en profondeur que 3 à 5 coups candidats maximum. La plupart des 35 coups légaux disponibles sont rejetés en quelques centièmes de secondes par un processus intuitif, avant même la réflexion consciente.

Ce traitement (rapide, pattern-based, économique) est ce qu'AlphaZero reproduit mieux que Deep Blue. Et c'est probablement pourquoi AlphaZero a développé des concepts de jeu que les humains reconnaissent comme "beaux" ou "audacieux" : contrairement au jeu solide mais mécanique de Stockfish.

La complexité algorithmique des échecs était si grande qu'il a fallu attendre non pas un ordinateur assez rapide pour la résoudre de force, mais un nouveau paradigme computationnel (l'apprentissage profond) pour approximer la cognition qui, depuis toujours, permettait aux humains de jouer malgré cette complexité.

Shannon avait vu juste en 1950. La recherche exhaustive était impossible. La solution n'était pas de chercher plus vite. C'était d'apprendre à ne pas chercher.

Claude Shannon jouait lui-même aux échecs, avec un niveau "raisonnable" selon ses contemporains. Il aurait probablement trouvé ironique que la meilleure solution à son problème soit d'imiter non pas l'ordinateur, mais l'humain.

Pour aller plus loin