Emanuel Lasker, longtemps champion du monde d’échecs, était mathématicien. Nul doute qu’il a fait des études mathématiques sur le jeu d’échecs, en tout cas il est également connu comme créateur de jeux mathématiques.

Alan Turing, mathématicien britannique pionnier de l’informatique, était échéphile. Au milieu du XXe siècle, il a inventé les concepts aujourd’hui à la mode d’IA et de chatbot (agents conversationnels, comme le célèbre chatGPT). Il a créé avec le mathématicien D. G. Champernowne la première IA jouant aux échecs, un algorithme nommé Turochamp.

Garry Kasparov est entré dans l’histoire comme premier champion du monde d’échecs à avoir été battu par une IA. Kasparov a lui-même programmé des algorithmes de jeu d’échecs, destinés à s’entraîner (on trouve de telles applications sur tous les smartphones aujourd’hui). Magnus Carlsen est quant à lui, le premier des champions du monde d’échecs à avoir été formé par des IA.

Lorsque Google se lance dans la production d’IA de jeux, c’est par le jeu de Go : AlphaGo bat le champion du monde de Go (jeu réputé bien plus difficile que les échecs) et la suite AlphaGo Zero est généralisée avec AlphaZero qui utilise des réseaux de neurones pour chercher, non pas des positions de pions, mais des motifs à évaluer : Alpha Zero recherche des concepts, et n’a pas besoin de challengers humains pour se perfectionner puisqu’elle pratique un apprentissage non supervisé. La suite MuZero est capable d’apprendre non seulement la stratégie gagnante, mais aussi les règles du jeu, inférées par l’observation de nombreuses parties.

Quant à ludii, on peut s’en servir pour jouer non seulement aux échecs mais aussi à des dizaines de variantes de ce jeu, dont la version malgache (sans parler de Go, Shogi etc : ludii peut aussi servir d’encyclopédie des jeux mathématiques).

L’IA de ludii permet même d’engendrer le manuel d’un jeu, ce qui aide considérablement à l’explication des règles du jeu. On va le tester avec le jeu alquerkonane :

Le jeu se joue sur un damier (ci-dessus, de 6 lignes et 4 colonnes). Les cases claires représentent une eau un peu boueuse où nagent des poissons (un poisson par case) et les cases foncées sont des îlots où nichent de gros oiseaux (un par case) incapables de voler. Au début du jeu, les deux rangées les plus proches des joueurs sont occupées par des pions du joueur (ci-dessus 4 pions parce qu’il y a 4 cases de chaque couleur dans les deux rangées).

Les oiseaux peuvent avancer (ils n’ont pas le droit de reculer) en effectuant un pas en diagonale, ce qui leur évite de se noyer :

Pour pouvoir aller sur une case, il faut bien entendu qu’elle soit libre. Le nombre maximum de cases accessibles à un oiseau au cours du jeu est 2 :

(ci-dessus les oiseaux du bas sont bloqués par la première ligne).

Les poissons, eux, peuvent se faire minces et glisser entre deux plans d’eau (à condition que le plan d’eau d’arrivée soit vide et plus en avant, c’est-à-dire plus bas sur l’écran) que le plan d’eau du départ) :

Les poissons aussi ont accès à deux cases maximum à chaque tour de jeu :

En bref, au jeu de dames réunionnais, comme au jeu de dames traditionnel, un pion avance d’une case en diagonale. Sauf que, comme les poissons sont dans des cases claires, on ne prend pas comme au jeu de dames classique :

• Un oiseau peut, si un poisson lui fait face, marcher sur le poisson sans se noyer pour aller à la case qui est symétrique de sa position par rapport à celle du poisson (à condition que la case d’arrivée soit vide) :

Dans ce cas, le poisson est tellement traumatisé de s’être fait piétiner, qu’il va à l’infirmerie jusqu’à la fin de la partie : il a été « mangé ». Dans un tour de jeu, on ne mange qu’une fois maximum, mais on peut manger en avant, en arrière ou sur les côtés.

• Un poisson aussi peut « manger » un oiseau : il attend que l’oiseau baisse la tête, mord le bec de l’oiseau et se fait projeter par le sursaut de l’oiseau, vers le plan d’eau symétrique de son plan d’eau actuel (à condition qu’il n’y ait pas déjà un poisson dedans) :

L’oiseau est alors tellement choqué par l’expérience, que lui aussi va à l’infirmerie jusqu’à la fin de la partie.

Une autre différence avec le jeu de dames traditionnel est qu’il n’y a pas de promotion à dame ! Une fois arrivé au bout, un pion est bloqué (puisqu’il n’a pas le droit de reculer). De fait, on peut gagner en mangeant tous les pions de l’adversaire :

ou en laissant bloqués au bout tous le(s) pion(s) de l’adversaire (ci-dessous, les blancs bougent, donc après cela c’est au tour des noirs, et l’oiseau qui reste, étant déjà arrivé en haut, ne peut plus bouger : les noirs ont perdu !) :

De fait, le premier qui ne peut plus effectuer de mouvement (soit parce qu’il n’a plus de pion, soit parce que tous ses pions sont bloqués au bout) a perdu le jeu.

Ce jeu, créé il y a quelques années par une réunionnaise de 6 ans qui souhaite maintenant garder son anonymat, a déjà eu pas mal de succès de la Moyenne Section jusqu’au CM2.

La première chose à faire pour tester des IA sur alquerkonane, c’est de télécharger le logiciel ludii, en suivant ce lien. Il s’agit d’un logiciel programmé en Java donc qui peut se lancer sur toute machine sur laquelle est déjà installé un logiciel en Java (CaRMetal, GeoGebra, Minecraft, etc).

La seconde chose à faire, est de télécharger le fichier alquerkonane programmé en ludii ci-dessous :

(à dézipper, en fait il s’agit d’un fichier texte et ces fichiers sont automatiquement zippés par spip qui gère ce site)

Ensuite, bien évidemment, on démarre le logiciel ludii préalablement téléchargé (ce qui permet au passage de découvrir un jeu javanais relativement peu connu, le surakarta (jeu)). Là, on clique sur file puis sur load game from file :

puis on sélectionne le fichier alquerkonane0.lud préalablement téléchargé. Au bout d’un certain temps, on voit apparaître le plateau du jeu alquerkonane, avec la position initiale des pions. Les dimensions par défaut du plateau sont celles (6 lignes et 4 colonnes) qui ont été le plus pratiquées en école primaire jusqu’ici. Dans un premier temps on se propose de simplifier un peu les choses, en réduisant le nombre de lignes à 4. Pour cela on clique sur options puis sur rows et enfin sur 4 :

Il y a trois moyens de se servir d’une IA pour jouer :

• utiliser le logiciel comme interface avec deux joueurs humains jouant à tour de rôle sur un même ordinateur (ou en réseau),
• faire jouer deux IA l’une contre l’autre et observer le résultat,
• ou imiter Magnus Carlsen en jouant (en tant que joueur humain) contre une IA.

Dans ce dernier cas, en ludii, on clique sur un icône représentant un des joueurs, en haut à droite, et on choisit que le joueur P1 (les blancs, en haut) soit humain, alors que P2 soit une IA (ci-dessous, on a choisi AlphaBeta, voir plus bas pour une description de cette IA) :

Ensuite il suffit de cliquer sur le bouton play (un triangle) en bas pour lancer la partie. Mais pour savoir comment jouer, il est bon (dans view) d’afficher les mouvements possibles :

Cela permet de voir (en bleu) que pour l’instant seuls deux poissons peuvent nager, les deux autres étant bloqués :

Pour jouer, il faut donc cliquer sur un des deux (celui qu’on souhaite bouger) :

Les points rouges montrent où ce poisson (qui est actuellement en B3) peut aller :

• en A2 (en glissant vers son nord-est),
• en C2 (en glissant vers son nord-ouest),
• ou en B1 (en mangeant l’oiseau qui est en B2).

En cliquant sur la case A2, le poisson glisse vers cette case, et la riposte de l’IA est presque immédiate (on ne lui a laissé qu’une seconde de réflexion) :

Dans l’ouvrage fondateur théorie des jeux et comportements économiques de Von Neumann et Morgenstern (1944) il est proposé un algorithme permettant de gagner à coup sûr à un jeu combinatoire : l’algorithme minimax consistant à minimiser les pertes (en supposant l’adversaire rationnel, on minimise le maximum de gain de celui-ci d’où le nom de l’algorithme). Cela revient à explorer l’arbre de toutes les positions de jeu, et calculer à partir des feuilles (1 pour chaque feuille gagnante, -1 pour chaque feuille perdante) une valeur résumant le sous-arbre partant de chaque nœud : on donne à un nœud de l’aversaire la valeur maximale parmi celles de ses enfants, et à chaque nœud de soi-même la valeur minimale parmi celles de ses enfants. Quand on arrive à la racine de l’arbre, on sait qu’on doit choisir la branche allant vers un nœud de valeur 1 pour gagner à coup sûr. C’est le parcours de cet arbre que fait le Capitaine Haddock en estimant pour chaque branche de l’arbre (afin de les minimiser), les dégâts que peut lui infliger Tintin :

L’algorithme du minimax est présent dans le sujet d’informatique du concours CCINP PC de 2024.

Le problème est de nature combinatoire : si on veut explorer tout l’arbre du jeu jusqu’aux feuilles, on est vite confronté (même avec un ordinateur puissant) à l’immensité du nombre de Shannon. On n’explore donc que jusqu’à une profondeur donnée (ci-dessus 10) et si on n’a rien trouvé à cette profondeur, on joue au hasard.

Pour améliorer le minimax, on enlève (c’est-à-dire qu’on n’explore pas) les branches qui ne mènent manifestement pas à une stratégie gagnante (par exemple celles permettant à l’adversaire de gagner), d’où le nom d’élagage alpha-bêta donné à cet algorithme.

L’inscription alpha-beta completed search of depth 10 signifie que la recherche par l’IA s’est arrêtée à la profondeur 10 de l’arbre. Mais en continuant à jouer on constate qu’au coup suivant l’IA a trouvé l’existence d’une stratégie gagnante pour elle :

D’ailleurs on constate qu’on est rapidement piégé :

En effet il ne reste plus qu’un poisson en C4, et

• s’il va en B3 il est mangé latéralement par l’oiseau en A3,
• s’il va en D3 il est mangé vers le bas par l’oiseau en D4 (qui, du coup, récupère sa mobilité).

Mais qu’est-ce qui prouve que le joueur humain a joué au mieux ? Pour savoir s’il y a une stratégie gagnante à ce jeu, on peut laisser une IA Alpha-Beta jouer contre une autre IA Alpha-Beta aussi :

L’IA a prouvé que sur un damier à 4 lignes et 4 colonnes, il y a une stratégie gagnante pour celui qui joue en premier. Ou plutôt, les IA :

• l’IA du premier joueur a prouvé (en explorant l’arbre jusqu’à la profondeur 11) l’existence d’une stratégie gagnante pour elle (et effectivement il y a 6 coups du joueur 1 et 5 coups du joueur 2 dans la partie),
• puis l’IA du joueur 2 a prouvé que si le joueur 1 joue au mieux de ses intérêts, elle perd (mais là c’est à la profondeur 10 ; en fait cette analyse du joueur 2 à la profondeur 10 avait déjà servi au joueur 1 à l’étape précédente),
• ensuite l’IA du joueur 1 reprouve l’existence d’une stratégie gagnante, à la profondeur 9,
• puis deux coups plus tard, à la profondeur 7,
• puis deux coups plus tard, à la profondeur 5,
• puis deux coups plus tard, à la profondeur 0 (et pas 3 : l’élagage a fait son œuvre et il ne s’est pas avéré nécessaire d’aller plus loin).

Il est tentant à ce stade de regarder si l’IA Alpha-Beta est capable de prouver l’existence d’une stratégie gagnante pour d’autres dimensions du damier, en particulier le damier à 6 lignes qui a été pratiqué par beaucoup d’enfants jusqu’à présent :

On pourrait

• recenser toutes les ouvertures possibles (2 coups par joueur) et lancer des IA Alpha-Beta pour voir si, dans chaque cas, le joueur 2 a une stratégie gagnante,
• ou augmenter le temps de réflexion des IA (cela peut éventuellement faire gagner une unité sur la profondeur de l’arbre analysé).

Mais autant automatiser cela, avec la recherche arborescente Monte-Carlo, consistant à explorer au hasard différents parcours de l’arbre, en modifiant les poids des branches selon l’identité du gagnant : si on constate qu’un jeu au hasard fait gagner plus souvent en optant pour une branche donnée, on a a priori intérêt à choisir cette branche en priorité. Le nom de Monte-Carlo est une allusion aux casinos que Stanislaw Ulam connaissait à Monaco (dans le cadre du projet Manhattan d’ailleurs mené par Von Neumann). L’acronyme anglais pour la recherche au hasard dans l’arbre du jeu est MCTS (pour Monte Carlo Tree Search).

L’algorithme MCTS est un exemple

• de démarche bayésienne (il s’agit d’estimer des probabilités conditionnelles, en passant de la probabilité d’avoir suivi cette branche sachant que j’ai gagné, à la probabilité de gagner si j’ai suivi cette branche),
• de machine learning puisque les poids des branches à suivre sont estimés après de nombreuses parties du jeu au hasard,
• d’apprentissage non supervisé (MCTS n’a pas besoin de jouer contre des joueurs humains, en faisant jouer MCTS contre MCTS chacune des deux IA apprend à jouer au mieux contre l’autre),
• de construction d’une expertise : comme au jeu d’échecs c’est en jouant un grand nombre de fois et en mémorisant l’ouverture ayant mené à la victoire ou à la défaite qu’on s’améliore.

L’algorithme MCTS est présent dans le sujet MPI de Centrale-Supélec 2024, à propos du jeu de Go.

Plusieurs variantes de MCTS sont présentes dans ludii mais la préférée de Cameron Browne est celle qui fixe une borne supérieure sur la confiance (UCB pour Upper Confidence Bound) dans le cas d’un arbre : UCB on Trees s’abrège en UCT.

On peut donc essayer de remplacer pour le joueur 1 l’algorithme Alpha-Beta par UCT :

Cela n’empêche pas forcément le joueur 2 de gagner :

La sortie de UCT donne une estimation de la probabilité de gain. Un nombre proche de 1 signifie que l’IA va gagner presque à coup sûr, et un nombre proche de -1 signifie que son adversaire va gagner presque à coup sûr (c’est le cas ici, lorsque AlphaBeta a prouvé à la profondeur 13 qu’elle va gagner, l’IA UCT en est à -0,977 qui signifie qu’elle est bien déprimée).

Là encore, cela ne prouve pas l’existence d’une stratégie gagnante pour le joueur 2. D’ailleurs si le joueur 1 joue aussi avec l’IA UCT (qui est l’IA par défaut de ludii, elle s’appelle donc aussi ludii AI), il peut arriver que cela le fasse gagner :

Il est possible (en cliquant sur view puis show AI distribution) d’afficher les poids des différentes branches de l’arbre de jeu :

Le réseau de neurones de Alpha Zero est organisé en couches, la première couche stockant la position des pièces et chaque couche pouvant être considérée comme conceptualisant le plateau de jeu à un niveau plus abstrait que la couche précédente. Ce qui permet de découvrir, par examen de ces couches abstraites, des motifs (features en ludii). Le dessin ci-dessus en montre deux, ce sont ceux d’où partent (ou arrivent) les flèches les plus grosses.

• Le premier de ces motifs est celui où un poisson est pris au piège, parce qu’il est à distance de cavalier entre deux oiseaux qui le menacent :

Ce motif a la forme d’un triangle rectangle isocèle et le joueur 1 cherche à éviter ce motif car il diminue fortement sa liberté de mouvement.

• Le second motif est celui auquel aboutit la plus grosse flèche, c’est un alignement en diagonale de 3 pièces [1] :

D’où l’idée de créer une IA ad hoc pour alquerkonane, en modifiant UCT pour favoriser l’apparition de motifs forts et défavoriser l’apparition de motifs faibles. Mais pour cela, il faut commencer par regarder quelle IA on va améliorer, et pourquoi pas poser la question à ludii ? En cliquant sur analysis puis predict best agent on obtient une suggestion sous la forme de scores obtenus par les diverses AI disponibles contre chacune des autres AI :

Sans grande surprise, on constate que AlphaBeta est encore meilleure que UCT puisqu’elle bat les autres IA dans trois quarts des cas. C’est donc celle-là qu’on va essayer d’améliorer, en lui ajoutant des heuristiques. Dans la liste des heuristiques disponibles pour AlphaBeta, on ne trouve pas l’alignement de 3 pions, mais il y a

• La mobilité influenceAdvanced (quotient du nombre de cases que le joueur peut atteindre en un coup par le nombre total de cases atteignables par les deux joueurs - a priori c’est un bon atout tactique parce que par exemple il amène à éviter de se faire manger ses pions et augmente le nombre de choix possibles, et donc la possibilité que le choix gagnant soit présent),
• le nombre material de pions sur le plateau (évite de se faire manger ses pions, cherche à manger ceux de l’adversaire)
• le nombre ownRegionsCount de pions dans les deux premières lignes du damier (un pion qui n’a jamais bougé a plus de chances d’être bloqué au bout après ceux de l’adversaire).

Comme les pions qui n’ont jamais bougé ne servent à rien s’ils se font manger, il a été décidé de donner un poids plus petit (20% du poids total soit 0,2) à cette heuristique. Comme le fait d’avoir beaucoup de choix ne garantit pas la victoire, on lui a donné un poids plus petit (30% du poids total soit 0,3) qu’au nombre total de pions. Programmée en ludii, cette IA est :

Pour utiliser ludii comme coach d’alquerkonane, il suffit d’ouvrir avec ludii le fichier suivant :

Le joueur 1 reste-t-il gagnant avec cette IA ? Contre l’IA Random (jeu complètement au hasard), oui :

Mais on constate qu’au bout de 5 coups l’IA découvre que son adversaire dispose d’une stratégie gagnante. Coup de chance pour elle, le joueur 2 joue totalement au hasard et rate son coup, ce qui fait qu’au sixième coup l’IA trouve, au contraire, une stratégie gagnante pour elle !

Après tout il semble que c’est bien au second joueur que vient l’avantage dans ce jeu. D’ailleurs en faisant jouer l’IA contre elle-même c’est rapidement le cas :

Et l’analyse obtenue en cliquant sur analysis puis sur evaluation dialog aboutit à ce que le second joueur a gagné toutes les parties jouées :

On remarque qu’en moyenne chaque joueur a joué 11 fois (et comme 22 est pair, c’est bien le second joueur qui a gagné dans chaque cas).

Les coefficients de l’IA alquerkonane ont été obtenus empiriquement en les modifiant, puis en jouant pour voir l’effet de la modification, ceci en boucle jusqu’à obtenir un résultat satisfaisant (c’est-à-dire une IA qui gagne pratiquement toujours), la solution trouvée ci-dessus étant

• 30% pour l’influence sur le damier (mobilité)
• 50% pour le matériel (nombre de pièces sur le damier)
• 20% pour le nombre de pièces en réserve

Mais calculer (ou estimer) ces coefficients, est une tâche typique de l’IA et plus particulièrement des réseaux de neurones. Les coefficients sont stockés dans un tenseur et le réseau de neurones modifie le(s) tenseur(s) à partir des données d’apprentissage.

La structure de couches d’un réseau de neurones se voit bien avec un autre jeu, appelé Y. Ce jeu, qui fut le plus populaire parmi les expérimentateurs humains de la thèse de Cameron Browne, et qui a été créé par non moins que John Milnor, a déjà été testé en Grande Section, les élèves arrivant bien à jouer, mais n’arrivant pas toujours à savoir qui a gagné (ils ne voient pas bien le chemin gagnant).

Le jeu Y se joue sur un plateau triangulaire à structure en nid d’abeilles, chaque joueur à son tour coloriant dans sa couleur (blanc ou noir, en posant une yunzi de sa couleur sur l’hexagone et en ne la bougeant plus pendant toute la partie) un des hexagones non encore coloriés. Le premier qui a réussi à établir un chemin de sa couleur joignant les 3 côtés du triangle a gagné (respectivement perdu dans la version qui perd gagne qui semble encore plus amusante à jouer) le jeu. Par exemple, ci-dessous, les noirs ont gagné en fabriquant un chemin noir (en forme de Y, d’où le nom du jeu) qui joint les trois côtés du triangle :

Seulement, s’ils n’ont pas vu ce chemin, ils vont continuer à jouer jusqu’au bout :

Et à ce moment, il existe un algorithme permettant de savoir qui a gagné : on décompose le plateau en triangles de 3 hexagones (ci-dessous, un triangle vert en bas à gauche, et un triangle mauve juste à sa droite ; le rond blanc en bas est à la fois vert et mauve) :

Les trois neurones (hexagones) d’une couche sont reliés à un même neurone de la couche suivante :

Et la couleur d’un neurone est la couleur majoritaire parmi ses trois entrées de la couche précédente (la couleur du sommet d’un tétraèdre est la couleur la plus répandue parmi les trois sommets de la base du tétraèdre). Par exemple, dans la couche coloriée plus haut, on constate que le triangle vert a plus de pions noirs que de pions blancs, donc l’hexagone qui le résume dans la couche suivante est noir. Idem pour le triangle mauve.

Or, un théorème dit que chaque couche est un jeu de Y différent (déjà, parce qu’il est plus petit que celui d’en dessous) mais ayant le même gagnant.

Pour le jeu ci-dessus, on a le bilan suivant :

Couche 1 (le jeu initial) :

Couche 2 :

Couche 3 :

Couche 4 :

Couche 5 :

Couche 6 :

Comme la couche 6 est noire, on en déduit l’existence d’un chemin gagnant pour les noirs dans toutes les autres couches, en particulier dans la première couche.

En cherchant des moyens d’évaluer la qualité de certains jeux mathématiques par l’IA, Cameron Browne a obtenu comme sous-produits des jeux conçus par IA !

Le premier d’entre eux s’appelle Yavalath. Il se joue sur un plateau hexagonal à structure en nid d’abeilles, et les joueurs posent alternativement des pièces de leur couleur sur le plateau. Ensuite

• le premier qui a réussi à former un alignement de 4 pièces de sa couleur a gagné le jeu, mais
• le premier qui a réussi à former un alignement de 3 pièces de sa couleur, a perdu le jeu !

Voici la règle du jeu en français et la page que Cameron Browne lui consacre.

Ci-dessous par exemple le jeu n’est pas encore fini, mais presque :

En effet, si les noirs jouent ici :

ils perdent immédiatement en réalisant un alignement de 3, et s’ils jouent ailleurs ils laissent les blancs gagner en complétant leur alignement vertical de longueur 4.

La règle du jeu permet de jouer à 3 voire 4 joueurs.

L’idée de l’alignement de 3 perdant n’était jamais venue à un créateur humain de jeux mathématiques. L’IA a donc commencé à servir le monde des jeux mathématiques, en créant de tels jeux. N’est-ce pas là le plus grand service qu’elle puisse rendre aux ludologues ?

Plutôt le passé : on lit dans ce rapport de Cédric Villani à la page 2, que

d’ici 2040, les besoins en espace de stockage au niveau mondial, fondamentalement corrélés au développement du numérique et de l’IA, risquent d’excéder la production disponible globale de silicium.

mais surtout, à la page 124, que

d’ici 2040, l’énergie requise pour les besoins en calcul devrait également dépasser la production énergétique mondiale.

Le nombre de réseaux de neurones en silicium augmentant exponentiellement, c’est peut-être bien avant 2040 que l’IA étouffera, faute de silicium pour la construire, et d’électricité pour l’alimenter. On entrera alors dans une ère post-IA qu’aucun auteur de science-fiction n’a encore réussi à imaginer. On jouera à des jeux mathématiques papier-crayon et de nouveaux Anatoly Karpov apparaîtront avec leurs coachs humains. On jouera à alquerkonane à la plage, en dessinant un damier sur le sable et en y posant des cailloux noirs et des morceaux de corail (enfin, s’il existe encore du corail sur la planète d’ici-là), comme le faisaient les hawaiiens avec le jeu konane il y a plusieurs siècles...

Finalement, Horace, auteur de ira furor brevis est (la colère est une courte folie) :

La colère est une courte folie (Horace)

aurait peut-être plutôt dû dire IA furor brevis est !