Knight moves exhaustion
octobre 4th, 2024 Posted in Non classé(Annonce de nouveau livre, et réponse longue à mon éditeur, qui me demandait si j’étais un passionné du jeu d’échecs)
Je n’ai jamais été un bon joueur aux échecs.
Trop pressé, pas très attentif, incapable de prévoir beaucoup plus qu’un coup en avance, j’ai toujours confusément espéré que les progrès me viendraient naturellement, sans lire un livre, sans étudier les ouvertures, sans apprendre de mes erreurs. J’ai donc rapidement eu du mal à trouver des adversaires humains assez médiocres ou indulgents pour prendre du plaisir à jouer contre moi.
Alors je me suis rabattu sur les machines, bien sûr. Leur patience est à toute épreuve et c’est tout ce que je demandais.
Le premier jeu d’échecs sur ordinateur auquel j’aie joué tournait sur ma première machine, un Sinclair ZX81. C’est un jeu que l’Histoire retient comme la plus concise implémentation du jeu d’échecs, puisque l’ensemble du code du programme ne dépassait pas un kilo-octet, et a ainsi pu être publiée sur deux pages par un magazine informatique. À l’époque, les ordinateurs ne servaient quasiment qu’à programmer, et bien souvent, les programmes que nous utilisions étaient issus de journaux tels que Science & Vie, Le Haut-Parleur, ou de la presse informatique anglo-saxonne.
Ce premier jeu d’échecs m’a battu. Je peux accuser son imperfection : il ne gère pas le coup « en passant », mais l’honnêteté me force à admettre que je ne connaissais pas ce coup ; son interface était un peu confuse, aussi. Dans les années qui ont suivi, tous les logiciels de ce genre m’ont battu, ou presque. Sur un coup de chance ou stimulé par la mini-série Le jeu de la dame, j’ai remporté une partie il y a quelques années. L’exploit n’a pas été reproduit par la suite.
Je reste envieux de ceux qui savent jouer, car j’aime ce jeu, non pour y jouer moi-même mais pour tout le reste. J’aime ses pièces, qui me racontent toute une histoire. J’aime son Histoire, qui se perd dans un Orient lointain — Inde ? Perse ? J’aime l’universalité de ce jeu, la manière il a circulé entre des mondes qui s’ignoraient ou se toisaient. Je suis fasciné par la culture des échecs, par ses grand-maîtres, par les passionnés qui savent regarder une partie d’échecs comme un match sportif, par ceux qui passent leur vie à écrire des traités et par ceux qui les lisent, par les philosophes (Leibniz), par les artistes (pensons à Marcel Duchamp, qui fut un temps joueur professionnel) ou écrivains qui ont fait de ce jeu un outil de travail, une métaphore de l’existence ou encore le sujet de leurs travaux : Cervantes, Goethe, Zweig, Perec…
Et je suis intéressé par tous les enjeux mathématiques qui entourent ce jeu, à commencer par l’inconcevable nombre de parties possibles, dont Chaude Shannon a calculé une estimation : dix puissance cent-vingt1. Et il ne s’agit là que de parties ayant un sens et d’un nombre de coups limité. Dix puissance cent-vingt, c’est un 1 avec 120 zéros derrière. C’est un nombre qui est des milliards de milliards de milliards de fois supérieur au nombre d’atomes présents dans l’Univers2. Même en vivant mille vies et en jouant du matin au soir, on ne saurait jouer qu’une fraction imperceptible de l’ensemble des parties potentielles, alors même que cet ensemble est, et c’est ce qui est le plus fascinant, nécessairement un nombre fini : le jeu d’échecs n’est pas un jeu de hasard, et pourtant il n’est pas envisageable d’en explorer toutes les combinaisons. L’immensité de ce nombre fait qu’aucun ordinateur ne pourra jamais calculer la totalité des parties possibles et c’est bien ce qui fait des échecs un enjeu pour les chercheurs en mathématiques, en informatique et en intelligence artificielle : si l’on ne peut anticiper l’ensemble des coups possibles, il faut trouver des règles, des méthodes, des raccourcis pour espérer reproduire ce qui se passe dans la tête d’un grand-maître.
Claude Shannon, ingénieur électricien et mathématicien, est une personnalité majeure de l’Histoire de l’informatique, avec ses travaux sur l’Information et le rapport signal/bruit, mais il est aussi une figure de l’Histoire de l’Intelligence artificielle, puisqu’il fait partie des organisateurs des conférence de Dartmouth (1956), à l’occasion desquelles est né le nom « Intelligence artificielle ». La réflexion sur la formalisation des fonctions cognitives (calcul, logique, automatisation…) n’est pas née en 1956, elle date de l’Antiquité, mais l’année 1956 marque bien la naissance de l’Intelligence artificielle en tant que discipline scientifique. Une autre figure proéminente de l’Histoire de l’informatique3 comme de celle de ce qu’on allait nommer Intelligence artificielle s’est penché sur les échecs : Alan Turing. En 1948, Turing, avec son ami David Champernowne, a écrit le programme d’un jeu d’échecs qui est vraisemblablement non seulement le premier du genre, mais aussi le premier jeu sur ordinateur. Ou plutôt le premier jeu pour ordinateur, car ayant rompu l’année précédente avec le centre de recherche avec lequel il avait conçu le Automatic Computing Engine, Turing n’avait pas d’ordinateur sous la main pour tester son programme. Il l’a pourtant fait, en prenant la place de l’ordinateur : un joueur humain proposait des coups auxquels Turing répondait en suivant scrupuleusement son programme (et, pour la petite histoire, perdant la partie). C’est un peu l’exact contraire du « turc mécanique » de Von Kempelen : en apparence, c’est un automate qui affrontait les têtes couronnées d’Europe4, mais en réalité, c’est l’assistant de Von Kempelen, dissimulé dans la table, qui poussait les pions. Dans le cas de Turing, c’est une personne de chair et d’os qui énonce les mouvements, mais elle le fait en suivant les instructions d’un programme automatique.
Cette histoire de jeu informatique écrit et testé sans ordinateur ma ramène une fois de plus à ma biographie numérique. En 1983, en camping avec mes parents, privé de mon ordinateur, j’avais écrit une aventure de type Donjons et Dragons, inspirée d’une émission de radio de l’époque. J’avais couvert des pages et des pages de code, mais une fois rentré chez moi, je n’ai pas eu le courage ni l’envie de le saisir : je savais ce qu’il était censé faire, j’étais sûr qu’il fonctionnerait, alors il est resté à l’état virtuel5.
Une pièce que j’aime tout particulièrement aux échecs est le cavalier. Son déplacement en L, sa capacité à passer au dessus d’autres pièces lui ont toujours conféré une aura un peu magique pour moi. Selon Wikipédia, c’est une pièce mineure dont l’intérêt faiblit au fur et à mesure que la partie progresse. Cela n’a pas empêché de nombreux amateurs de jeux cérébraux d’étudier ses mouvements, et ce, au moins depuis le 9e siècle, avec le poète Rudrata en Inde et le joueur Al-Ádlí ar-Rúmí en Anatolie6. Un problème souvent posé est celui nommé « Problème du Cavalier », qui consiste à parcourir chaque case de l’échiquier sans jamais revenir sur une cas déjà visitée. Au milieu du XVIIIe siècle, Léonhard Euler a proposé plusieurs variantes de ce problème (symétrie, nombre de cases différent, carrés magiques, etc.) que l’on nomme souvent, en son honneur, le « cavalier d’Euler » car s’il n’a été ni le premier ni le dernier à l’avoir fait, Euler est le plus célèbre mathématicien à s’être intéressé à cette question. C’est une variante à dix fois dix cases que Georges Perec a utilisé pour structurer La Vie Mode d’emploi :
Le programme que j’ai mis au point pour produire mon petit livre n’est pas très intelligent, il est même particulièrement laborieux. Il commence avec le cavalier blanc de gauche (B1)7, qui a trois déplacements possibles (A3, C3, D2). Il choisit une de ces destinations au hasard. Une fois sur la seconde case, il vérifie le nombre de possibilités qui lui sont offertes et choisit, toujours aléatoirement, une de celles-ci, en excluant de la liste les éventuelles cases sur lesquelles il est déjà passé. Et ainsi de suite jusqu’au moment où il n’est plus possible de trouver une case qui n’a pas été visitée. Là, je stocke le trajet et je recommence en partant de la cases B1. Quand j’ai obtenu 64×64 (4096) trajets différents, je les classe par nombre de sauts puis les calculs s’arrêtent et je passe à la mise-en-page du livre.
Le programme commence par créer un fichier pdf, passe une page, écrit le titre, puis dessine les soixante-quatre premiers circuits sur une page, les soixante-quatre suivants sur une la page suivante, et ainsi de suite jusqu’à obtenir soixante-quatre pages qui, donc, contiennent chacune soixante-quatre circuits réalisés sur un échiquier (que l’on doit deviner, car je ne le dessine pas, lui) de soixante-quatre cases. Mais ce n’est pas tout à fait terminé : une fois l’ensemble des dessins réalisés, le programme se lit lui-même et s’ajoute au livre. Ainsi, on revient à l’antiquité de la micro-informatique, quand les programmes ne se stockaient pas sur des supports magnétiques mais sur du papier : la personne patiente qui recopiera mon code (un code assez foutraque et hésitant) pourra produire mon livre, ou plutôt, une version de mon livre, puisque celui-ci, partiellement construit par le hasard, ne contient jamais que 4096 trajets du cavalier parmi les 13 267 364 410 532 possibles.
Mon programme ajoute enfin le colophon au cahier intérieur, puis crée la couverture du livre en y dessinant le dernier des trajets réalisés par mon cavalier — le plus complexe —, et en dessinant sur la quatrième le premier et le plus sommaire de ces circuits. Entre le moment où j’ai lancé le programme et le moment où le livre était fait et prêt à être imprimé, il s’est écoulé deux minutes, mais évidemment, le programme n’a pas été écrit en deux minutes, lui8.
Je n’ai nullement l’ambition de résoudre une quelconque énigme mathématique, mes lignes de code se contentent, poussivement, erratiquement, de dessiner 4096 circuits de complexité graduelle, et échoue à parcourir (il eut fallu un beau hasard pour que cela arrive) l’ensemble des soixante-quatre cases de l’échiquier. Échouer aux Échecs, ça semble être dans l’ordre des choses. Mon cavalier fait de son mieux, errant au gré du hasard et des contingences, accumulant les expériences sans toutefois pouvoir épuiser toutes les possibilités, loin de là. Confusément, je me dis qu’on peut en tirer une métaphore de l’existence, mais ne philosophons pas trop, nous n’en avons pas les moyens et cela risquerait de se voir.
Knight Moves Exhaustion
RRose éditions, tirage de 200 exemplaires.
format : 19 x 19 cm, 80 pages
ISBN : 978-2-9586199-5-4
13 euros
- Claude Shannon, Programming a Computer for Playing Chess, dans le numéro de février 1950 de Scientific American, issu d’une conférence donnée l’année précédente. [↩]
- Des calculs récents estiment désormais le nombre de parties possibles à 10 puissance 123, soit mille fois plus que ce que proposait Shannon. [↩]
- On peut citer aussi Charles Babbage — l’inventeur de l’ordinateur dans les années 1830, qui a joué une partie contre le joueur automate de Von Kempelen — Konrad Zuse, Norbert Wiener, John Von Neumann, Allen Newell, Herbert Simon, Marvin Minsky… Et ne parlons pas des recherches d’IBM sur Deep Blue, l’ordinateur qui a défait le grand maître Garri Kasparov en 1997, créant un véritable choc dans l’opinion publique. [↩]
- Le joueur d’échecs de Von Kempelen a joué contre Marie-Thérèse d’Autrice, Napoléon premier, Benjamin Franklin, mais aussi, des années plus tard, contre Edgar Allan Poe, qui en a tiré un essai, Mælzel’s chess player, qui avait l’ambition de démystifier l’automate, et plus largement de méditer sur la possibilité d’une intelligence mécanique, ce qui en fait, par anticipation, un des premiers textes consacrés à l’Intelligence Artificielle. Mælzel est le nom d’un des propriétaires de cet automate, qui a fait voyager la machine aux Amériques. [↩]
- J’ai déjà raconté cette histoire ici. [↩]
- On ne connaît ni la date ni le lieu d’origine du jeu d’échecs, mais on pense qu’il est âgé de près d’un millénaire et demi, quoique avec des règles légèrement différentes. [↩]
- Dans mon livre, j’écris B2 ! Pas très sérieux. [↩]
- Je pense alors à la légende de ce peintre qui avait courroucé l’empereur de Chine en lui réclamant une somme considérable pour le dessin d’un canard, exécuté devant lui en une fraction de seconde. Le peintre avait répondu que ce canard, parfaitement dessiné, était le fruit d’une vie entière de travail. [↩]
4 Responses to “Knight moves exhaustion”
By claude on Oct 14, 2024
bonjour. Je laisse ce message sans lien avec le contenu de l’article. J’ai déserté ce blog depuis plusieurs années, par manque de temps, mais aussi surement parce que le contenu des articles était presque trop dense, trop approfondi, jusqu’au-boutiste presque dans l’exploration des sujets. J’avais le souvenir d’un blog « encyclopédique » d’un grand sérieux. Aujourd’hui, ces temps-ci, devant le constat d’une nullité croissante d’internet, ou plutôt pour être plus précis, devant la difficulté d’accéder à de « nouveaux contenus » intéressants, à des découvertes, des univers nouveaux, ce qui était le propre d’internet, j’ai ressenti le besoin de revenir ici, pour retrouver justement « du contenu », de la matière tangible. Je vois que le rythme a un peu baissé (j’imagine bien sûr mille raisons à cela), mais je vois que ce « dernier des blogs » est toujours là, et je dois l’avouer : je trouve cela très salvateur et réconfortant. Merci Jean-Noël.
By J.-N. on Oct 16, 2024
@Claude : j’admets que ça m’arrive de vouloir dire trop de choses et de produire des articles inutilement longs, je ne l’ai pas vérifié méthodiquement mais je crois bien qu’il y a une vraie inflation dans la longueur des billets. Pour le reste, j’essaie de me tenir au programme contenu dans le nom de ce blog et de continuer jusqu’à être le dernier :-)
Les blogs me manquent, car si les réseaux sociaux permettent de s’exprimer, on oublie, on ne retrouve rien,…
By Jaime R. Gutiérrez Salazar on Oct 28, 2024
Ayant découvert le Problème du Tour du Cavalier quand j’étais encore au Lycée, je suis tout le temps en train de chercher des articles à ce sujet là. C’est ainsi que le titre de votre article m’a fait me rappeler d’un autre article (« All closed 8×8 knight’s tours on SSD » par G. Stertenbrink) que j’ai vu l’année dernière dans Chess Problem Net (un Forum d’échecs Anglais). Les fichiers (3 TB) seraint peut être disponibles cette année.
https://www.chessproblem.net/viewforum.php?f=49