Les échecs : un jeu fini, mais vertigineux
Les échecs sont le modèle même du jeu à information complète : deux joueurs, tout est visible, pas de hasard. En 1913, Ernst Zermelo démontre qu'un tel jeu a une valeur : soit les Blancs peuvent forcer le gain, soit les Noirs, soit chacun peut forcer au moins la nulle. Mais personne ne sait laquelle, car l'arbre des parties est inimaginablement grand. Cette page part des pièces et de leurs déplacements, compte les parties possibles, vous fait jouer contre une machine qui calcule, montre comment elle élague ses calculs, et finit là où Zermelo a raison en pratique : les finales simples, que l'on sait résoudre exactement.
Les mots des échecs
| Mot | Sens |
|---|---|
| Échec, mat, pat | Le roi est en échec s'il est attaqué. Échec et mat : il ne peut y échapper, la partie est perdue. Pat : le joueur au trait n'a aucun coup légal sans être en échec — la partie est nulle. |
| Roque | Coup double du roi et d'une tour, permis si ni l'un ni l'autre n'a bougé, si les cases entre eux sont vides et si le roi ne traverse pas de case attaquée. |
| Prise en passant | Un pion qui avance de deux cases à côté d'un pion adverse peut être pris comme s'il n'avait avancé que d'une case, au coup suivant seulement. |
| Promotion | Un pion qui atteint la dernière rangée devient dame, tour, fou ou cavalier, au choix. |
| Notation | Les pièces sont notées R (roi), D (dame), T (tour), F (fou), C (cavalier) ; les pions sans lettre. « Cf3 » : un cavalier va en f3 ; « x » marque une prise, « + » un échec, « # » le mat. |
| Demi-coup | Le coup d'un seul joueur (en anglais ply) ; un coup complet est un coup blanc suivi d'un coup noir. |
Les pièces et leur mobilité
Chaque pièce a sa façon de se déplacer. La tour va en ligne droite, le fou en diagonale, la dame fait les deux, le roi fait un pas dans toutes les directions, le cavalier saute en « L » par-dessus les autres pièces. Choisissez une pièce et touchez une case : ses déplacements possibles sur un échiquier vide s'affichent. La carte de droite colore chaque case selon le nombre de coups que la pièce y aurait : on voit pourquoi les pièces sont plus fortes au centre.
Combien de parties ? L'arbre qui explose
Au départ, les Blancs ont 20 coups possibles, les Noirs aussi : 400 positions après un coup de chaque. Après trois demi-coups, 8 902 ; après quatre, 197 281. La page les compte vraiment, avec son propre générateur de coups — il respecte toutes les règles (roque, prise en passant, promotion, interdiction de laisser son roi en échec). Ces nombres, appelés perft par les programmeurs, servent justement à vérifier un générateur : la moindre erreur de règle les fausse. En 1950, Claude Shannon estimait à 10120 le nombre de parties possibles : bien plus que d'atomes dans l'univers observable.
Jouer contre la machine
Vous avez les Blancs. Touchez une pièce, puis la case d'arrivée (les coups légaux s'allument). La machine joue les Noirs : elle explore l'arbre des coups jusqu'à une profondeur fixée, évalue les positions atteintes (matériel et placement des pièces), puis remonte le meilleur choix par le minimax : elle suppose que vous jouerez toujours le coup qui lui est le plus défavorable. Au bout de l'horizon, elle prolonge seulement les prises, pour ne pas s'arrêter au milieu d'un échange.
Minimax et élagage alpha-bêta
Voici un arbre de jeu en miniature : à la racine, c'est au joueur Max de choisir ; au niveau suivant à Min, et ainsi de suite. Les feuilles portent des évaluations. Le minimax remonte les valeurs : Max prend le maximum de ses enfants, Min le minimum. L'élagage alpha-bêta évite de regarder des branches inutiles : dès qu'on sait qu'une branche ne sera jamais choisie, parce que l'adversaire dispose déjà d'une meilleure réfutation, on l'abandonne. Le résultat est exactement le même, pour beaucoup moins de calcul — surtout si l'on examine les meilleurs coups en premier.
Zermelo a raison : les finales résolues exactement
Pour les échecs entiers, l'arbre est trop grand. Mais avec trois pièces seulement — le roi blanc, une tour (ou une dame) et le roi noir —, il n'y a que quelques centaines de milliers de positions. On peut alors appliquer le raisonnement de Zermelo à la lettre, en partant de la fin : on marque toutes les positions de mat, puis celles d'où les Blancs peuvent mater en un coup, puis celles où les Noirs, quoi qu'ils fassent, tombent dans une position déjà marquée, et ainsi de suite. C'est l'analyse rétrograde. La page la calcule entièrement dans votre navigateur et connaît ensuite, pour chaque position, le nombre exact de coups avant le mat.
Ce qu'il faut retenir
Un jeu à information complète
Rien n'est caché, rien n'est aléatoire. Le théorème de Zermelo garantit une valeur : gain blanc, gain noir ou nulle, avec un jeu parfait.
L'explosion combinatoire
Environ 30 coups par demi-coup : l'arbre dépasse 10100 parties. Les machines cherchent sur un horizon limité, avec une évaluation et l'élagage alpha-bêta.
La rétrograde
Quand il y a peu de pièces, on remonte depuis les mats et l'on connaît le jeu parfait. C'est Zermelo appliqué à la lettre.
Pour aller plus loin
Les vérifications de la page. Le générateur de coups retrouve les nombres de référence : 20, 400, 8 902 et 197 281 positions depuis le départ, et 48, 2 039, 97 862 pour la position « Kiwipete », conçue pour piéger les générateurs (roques, prises en passant, promotions, clouages). L'analyse rétrograde retrouve les longueurs maximales connues : 16 coups pour la tour, 10 pour la dame.
Repères. E. Zermelo, « Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels » (1913) ; J. von Neumann, théorème du minimax (1928) ; C. Shannon, « Programming a computer for playing chess » (1950) ; D. Knuth et R. Moore, « An analysis of alpha-beta pruning » (1975) ; K. Thompson, premières bases de finales par analyse rétrograde (années 1970-1980) ; Deep Blue contre Kasparov (1997) ; AlphaZero (2017).
Pages voisines. Le jeu de Nim (un jeu combinatoire entièrement résolu), le bridge (le même minimax, cartes ouvertes), les équilibres de Nash.