David Madore's WebLog: Jeux combinatoires et ordinaux

Profondeur de processus terminants

Considérons un jeu plus simple et beaucoup moins intéressant que le jeu de nim : j'ai, pour moi et seulement pour moi, un certain nombre (d'allumettes, disons, ou de points de vie), fini pour le moment ; et mon adversaire a un certain nombre pour lui et seulement pour lui. Chacun tour à tour, nous devons diminuer notre nombre (jeter des allumettes, si l'on veut, ou perdre des points de vie : au moins un, et éventuellement plus), et le premier qui ne peut plus jouer (faute d'allumettes restantes) a perdu. Il est complètement évident que si un joueur a strictement plus d'allumettes que son adversaire, ce joueur gagne ; tandis que si les deux joueurs en ont exactement autant au départ, c'est le second joueur à jouer qui gagne (parce que le premier joueur est forcé de jeter au moins une de ses précieuses allumettes, et le second peut alors se maintenir avec toujours au moins autant d'allumettes, et le premier joueur arrivera à court, justement, en premier).

Ce jeu est fabuleusement ininitéressant : chaque joueur jettera tour à tour une seule de ses allumettes, et c'est tout ce qui se produira. Essayons de le rendre un tout petit peu moins inintéressant en y mettant des ordinaux : chaque joueur dispose maintenant d'un ordinal d'allumettes ou de points de vie, et chacun à son tour doit décroître cet ordinal (c'est-à-dire retirer des allumettes par la droite, si on pense à l'ordinal comme une ligne de bâtonnets). Comme je l'ai souligné, on ne peut pas toujours décroître un ordinal seulement de 1 : l'ordinal ω, notamment, n'a pas de prédécesseur immédiat, donc le joueur qui a ω points de vie devra passer à un nombre fini au coup suivant — aussi grand qu'il le veut, mais fini. (D'autre part, si l'on veut voir ça comme une rangée d'allumettes dans lesquelles on en retire, il est essentiel que ce soit par la droite qu'on retire des allumettes, parce que par la gauche, vous pouvez retirer perpétuellement des bâtons à ω sans jamais terminer, vu que ça ne fait pas, justement, diminuer sa valeur.) Le jeu reste néanmoins très peu intéressant dans sa variante transfinie, et il est facile de se convaincre que, comme dans le cas fini, celui qui a un ordinal strictement plus grand que l'autre gagne, tandis que si les deux joueurs ont le même ordinal, le second à jouer gagne.

Donner à chacun des deux joueurs un ordinal à décroître n'est donc pas passionnant. Ça l'est un peu plus quand on compare un ordinal et autre chose : autrement dit, si un des joueurs dispose d'un ordinal qu'il doit décroître selon les règles précédentes, mais que l'autre est mis en face d'une autre forme de processus (qui implique des choix de sa part), processus qui termine à coup sûr, mais qu'il va essayer de faire durer aussi longtemps que possible. On peut appeler profondeur du processus en question l'ordinal qu'il faut donner à l'autre joueur (et dont on montre assez facilement qu'il est unique) de manière à rendre le jeu équilibré — équilibré signifiant que c'est le second joueur qui gagne.

Voici un exemple : on suppose qu'un joueur a deux ordinaux qu'il peut décroître, disons α et β : à chaque tour il peut diminuer l'un ou l'autre, comme il le veut (éventuellement les deux, ça ne change rien ici puisqu'il n'a jamais intérêt à ça), mais il doit en diminuer un : ce sera ça le processus à comparer ; l'autre adversaire n'a qu'un seul ordinal à sa disposition, γ, qui sera l'ordinal servant de comparaison. À quelle condition sur ces trois ordinaux le jeu est-il équilibré, au sens où aucun joueur n'a d'avantage sur l'autre (le second à jouer gagne) ? Si les ordinaux en question sont tous finis, il est évident que la condition est γ=α+β, mais pour des ordinaux en général ça ne peut pas être exactement ça vu que l'addition des ordinaux n'est pas commutative alors qu'ici α et β jouent des rôles complètement symétriques. En fait, la condition est γ=α⊞β où le symbole ⊞ désigne une nouvelle opération d'addition sur les ordinaux, qui s'appelle la somme naturelle ou somme de Hessenberg, et qui, à la différence de la somme usuelle, est commutative (elle est aussi associative, mais ça la somme usuelle l'est déjà) ; on peut la définir simplement en faisant la somme des coefficients dans la forme normale de Cantor (on a par exemple ω⊞1 = 1⊞ω = ω+1).

On peut aussi définir une multiplication naturelle (ou de Hessenberg), ⊠, sur les ordinaux (qui soit commutative et associative et distributive sur ⊞), de la façon suivante : pour définir α⊠β, on considère un jeu où un joueur mange une gaufre infinie de α lignes et β colonnes, qu'il cherche à faire durer aussi longtemps que possible, avec la condition qu'il doit manger au moins une cellule par tour et que si on mange une cellule on doit aussi manger toutes celles qui sont à droite et/ou en bas (à droite et en bas signifiant à des colonnes ou à des lignes indicées par un ordinal plus grand) ; si on n'aime pas les gaufres infinies, on peut aussi dire que ce joueur écrit des couples d'ordinaux (α′,β′) où α′<α et β′<β, et avec la condition qu'il n'a pas le droit d'écrire un couple (α′,β′) dont les composantes serait toutes deux supérieures ou égales à celles d'un autre couple précédemment écrit (la traduction entre ces deux formes se fait en décidant qu'écrire le couple (α′,β′) revient à manger la part de gaufre située en bas et à droite de ce coin). Bref, l'unique ordinal γ qui, donné à l'autre adversaire, équilibre le jeu, est le produit α⊠β recherché (et on peut également le définir en développant les formes normales de Cantor en ajoutant les exposants avec ⊞).

Bref, tout processus qui termine à coup sûr peut ainsi se voir affecter un ordinal, en considérant un jeu où un joueur suit ce processus tandis que l'autre diminue un ordinal, et en cherchant l'ordinal qui équilibre le jeu résultant. Voici un autre exemple, où le processus comparé ne fait pas intervenir d'ordinaux : il s'agit pour un joueur d'écrire des suites finies de nombres entre 1 et n (des mots sur n lettres, si on veut), avec la règle qu'une fois qu'il a écrit une suite, il ne peut jamais en écrire une autre comportant ces mêmes nombres dans le même ordre (même s'ils ne sont pas consécutifs consécutivement) — par exemple, une fois qu'il a écrit (1,3,3,2), il lui est interdit d'écrire (1,2,3,6,3,3,2) ou n'importe quoi qui contienne un 1 suivi d'un 3 suivi d'un autre 3 suivi d'un 2 pas forcément consécutivement (et s'il écrit un (1) tout seul, il ne peut plus jamais utiliser de 1 ; et s'il écrit la suite vide (), c'est son dernier coup). Autrement dit, il n'a pas le droit d'écrire une suite telle qu'en effaçant certains termes on obtienne une suite précédemment écrite. Il n'est déjà pas évident que ce processus consistant à écrire des mots dont aucun sous-mot n'ait été écrit termine toujours en temps fini ; et il est encore moins évident de déterminer quel est l'ordinal équivalent (c'est-à-dire, celui qu'il faut donner à décroître à l'autre joueur pour que ce soit toujours le deuxième qui gagne) : il se trouve que c'est ω^ωn−1.

Encore moins évident : un joueur dessine des arbres (enracinés, et dont les nœuds peuvent ou non être ordonnés, et peuvent ou non être étiquetés par des éléments d'un alphabet fini fixé ; si on est malicieux, on peut par exemple décider que ce joueur écrit des fichiers HTML) ; la règle est qu'une fois qu'il a dessiné un arbre T, il ne peut plus dessiner aucun arbre dont T s'obtiendrait par une succession d'opérations de type (1) effacer un nœud (et tous ses descendants) ou (2) remplacer un nœud x par un des descendants y (ce qui implique d'effacer tous les descendants de x qui ne sont pas descendants de y). Il est de nouveau non évident que ce processus termine forcément, et encore moins évident de trouver l'ordinal qu'il faut mettre en face pour équilibrer le jeu : si je lis bien la littérature, je crois que c'est le « petit » ordinal de Veblen, et je crois que ça n'a pas d'incidence sur l'ordinal que les nœuds soient ou non ordonnés ou qu'ils soient étiquetés dans un alphabet fini fixé, mais je ne suis pas totalement sûr (il y a plein de variantes à la fois sur l'énoncé du théorème et sur la façon dont on peut le comparer à un ordinal, ça n'aide pas trop) ; je pense en revanche que si on modifie (2) en (2′) remplacer un nœud x par plusieurs de ses descendants non emboîtés (en préservant l'ordre naturel entre eux si on a choisi la variante des arbres ordonnés), ce qui limite plus rapidement les possibilités du joueur arboricole, alors l'ordinal est considérablement diminué (peut-être jusqu'à ε₀).

On pourrait aussi jouer avec les différentes variantes du combat d'Hercule contre l'hydre : l'hydre est aussi un arbre enraciné, mais cette fois les règles sont différentes : Hercule choisit une tête de l'hydre à couper, c'est-à-dire une feuille de l'arbre, et l'hydre peut faire repousser autant de copies qu'elle veut de tout le sous-arbre dont la tête a été coupée (c'est-à-dire qu'elle peut répliquer en autant d'exemplaires qu'elle veut le père de la feuille décapitée et tous ses descendants après décapitation) ; si on fait choisir à un joueur à la fois les coups d'Hercule (quelle tête couper) et ceux de l'hydre (combien se reproduire), alors il faut donner à l'autre joueur l'ordinal ε₀ pour que ce soit équilibré. C'est d'ailleurs assez facile à voir, en regardant l'hydre comme l'arbre d'un ordinal écrit récursivement sous forme normale de Cantor.

Bref, on peut affecter un ordinal à tout processus qui termine à tous les coups.

Nombres à la Conway et jeux partiaux

Mais une idée originale de Conway (enfin, une des très nombreuses idées originales de Conway) est que ce genre de mesures peut servir beaucoup plus largement à étudier la théorie combinatoire des jeux (c'est-à-dire celle qui étudie les jeux à information complète et sans hasard) : qu'on peut toujours ramener les règles d'un jeu de ce type (qui termine toujours en temps fini et produit toujours un gagnant) à une situation de Zugzwang, c'est-à-dire que les joueurs sont en fait en train de retarder le plus possible le moment où ils ne pourront pas jouer, et que les ordinaux peuvent servir à mesurer, très grossièrement parlant, le nombre de « coups d'avance » que possède un joueur sur l'autre.

Je suis très vague en racontant ça. Voici une tentative rapide pour être plus précis sur le cadre dans lequel on s'inscrit. D'abord, ce que Conway appelle jeu [partial], c'est un jeu (déterministe, à information complète, produisant toujours un gagnant en temps fini) dans lequel s'affrontent un joueur gauche et un joueur droite, et chaque position du jeu admet certains coups possibles pour le joueur gauche et certains coups possibles pour le joueur droit, pas nécessairement égaux (comme dans mes exemples où un joueur décroît un ordinal pendant qu'un autre fait quelque chose de différent — mais en général, les coups d'un joueur peuvent bien sûr tout à fait influer sur ceux de l'autre, comme aux échecs). Bien sûr, comme les joueurs jouent tour à tour, cette distinction a quelque chose d'un peu artificiel (se demander quels sont les coups autorisés pour les blancs, aux échecs, dans une position où les blancs viennent de jouer, est une question assez bizarre, puisque justement ce sont les noirs qui vont faire un coup) ; mais cela fait une différence si on considère la somme de deux jeux, qui est le jeu dans lequel, à chaque coup, un joueur peut jouer dans une ou l'autre des composantes de la somme, mais une seule (et donc il se peut que si on regarde cette composante seule, un joueur ait fait plusieurs coups de suite).

Un jeu est qualifié de nul si le second joueur possède une stratégie gagnante (que ce soit gauche ou droite qui commence), de (strictement) positif si le joueur gauche en possède une (que ce soit lui qui commence ou non), de (strictement) négatif si c'est le joueur droite qui en possède une, et de flou si c'est le joueur qui commence qui possède une stratégie gagnante (quel qu'il soit). On peut définir la différence de deux jeux x et y comme la somme de l'un et de l'opposé de l'autre, l'opposé étant formé en inversant les rôles des joueux gauche et droite : on dit alors que x et y sont Conway-équivalents (Conway les dit carrément égaux) lorsque leur différence est gagnée par le second joueur, que x>y lorsque x−y est gagné par le joueur gauche, que x<y lorsque c'est le joueur droit qui y possède une stratégie gagnante, et que x∥y (les jeux sont incomparables) lorsque x−y admet une stratégie gagnante pour le premier joueur.

À l'intérieur des jeux [partiaux] en général, Conway distingue une classe particulière de nombres (nombres que Conway appelle Nombres avec une ‘N’ majuscule, je trouve que c'est une très mauvaise terminologie, et que Knuth a rebaptisés en nombres surréels, ce qui est nettement moins mauvais). Très grossièrement, ce sont les jeux qui se ramènent purement et simplement à l'avance en coups d'un joueur sur l'autre, ce nombre de coups étant quelque chose de plus général qu'un ordinal. Les jeux que j'ai présentés plus haut, pour comparer un processus terminant à un ordinal, sont des nombres en ce sens. Formellement, un nombre surréel est un jeu partial dont toutes les options sont elles-mêmes des nombres et dont toutes les options du joueur droit sont préférables pour le joueur gauche (c'est-à-dire, strictement supérieures) à toutes les options du joueur gauche — façon de dire qu'aucun joueur n'a envie de jouer. Les ordinaux sont un cas particulier des nombres surréels, en les voyant comme le jeu où le joueur gauche a le droit de décroître cet ordinal et le joueur droit n'a rien le droit de faire du tout (il a donc immédiatement perdu, ce qui ne rend pas le jeu très intéressant sauf s'il s'agit de le sommer ou de le comparer avec quelque chose d'autre).

Tous les jeux ne sont pas des nombres, il existe aussi à l'opposé des jeux que Conway qualifie de chauds, au sens où les deux joueurs ont envie de faire un coup (par exemple pour rafler quelque chose), et il y a toute une théorie de la température des jeux (avec des thermographes, des transitions de phase et tout un tas de choses en vérité assez incompréhensibles), et il y a aussi des jeux qui ne sont pas tout à fait chauds mais presque (comme le jeu de nim, dans les situations qui sont gagnantes pour le premier joueur, dont la température est 0 mais qui n'est pas un nombre ; de façon générale aucun jeu flou, c'est-à-dire gagné par le premier joueur, ne peut être un nombre dans la théorie de Conway). Les nombres (surréels) jouent cependant un rôle assez central dans la théorie de Conway, ne serait-ce que comme une échelle de comparaison (pour tout jeu G, on peut chercher les nombres t tels que G∥t, c'est-à-dire que G est incomparable à t, i.e., que le premier joueur possède une stratégie gagnante dans le jeu G−t qui donne t coups d'attente au joueur droite, ou −t au joueur gauche, ces nombres t forment un intervalle qui renseigne déjà beaucoup sur le jeu et constitue la base de son « thermographe »).

Dans le cadre de cette théorie des jeux, donc, Conway définit des nombres surréels, plus généraux que les ordinaux, pour lesquels l'addition et la multiplication coïncident avec les opérations naturelles ⊞ et ⊠ que j'ai définies plus haut : ce qui est sans doute surprenant, c'est que non seulement ce cadre lui permet de donner un sens à une soustraction tout à fait générale (par exemple, pour fabriquer le nombre surréel ω−1, qui n'a pas de sens dans les ordinaux, on considère le jeu où le joueur gauche décroît le nombre ω tandis que le joueur droite décroît le nombre 1 : évidemment le joueur gauche gagne facilement, mais le 1 n'est pas totalement inexistant, et par exemple si on compare ce jeu ω−1 avec ω, on se persuade qu'il lui est bien strictement inférieur), mais même une division (on peut définir des nombres surréels tels que ½ ou 1/ω) ou certaines racines d'équations algébriques (le corps des nombres surréels est réel-clos ; en fait, il s'agit du corps des séries de Hahn — voir ici — à coefficients réels, en l'indéterminée ω, dans le groupe des valeurs des nombres surréels eux-mêmes ; du coup, il y vivent toutes sortes de nombres assez fantasques comme ω^1/(ω+1) ou √(ε₀+1)=ω^(1/2)ε₀+(1/2)ω^{−(1/2)ε₀}−(1/8)ω^{−(3/2)ε₀}+⋯).

[Ajout : voir une entrée ultérieure où je fais une description beaucoup plus détaillée des nombres surréels.]

Je dois cependant dire que je trouve un peu décevante la théorie des jeux de Conway, parce qu'il définit une multiplication sur les nombres (surréels) et sur les nimbres (qui sont ce dont je vais parler dans la section suivante), avec des formules tout à fait analogues, mais il n'est pas possible d'en définir une sur les jeux en général (on peut définir la somme de deux jeux, mais pas le produit). Je pense que cela tient à ce qu'il identifie deux jeux lorsque leur différence est gagnée par le second joueur, et qu'une relation d'équivalence plus fine mériterait d'être étudiée, mais je digresse.

Fonction de Grundy et somme de nim

Les jeux de nim font partie des jeux (déterministes, à information complète, produisant toujours un gagnant en temps fini) qu'on appelle impartiaux, en ce qu'en n'importe quelle position, les deux joueurs ont les mêmes options à leur disposition (c'est-à-dire, les mêmes coups possibles). Pour de tels jeux, il n'y a que deux possibilités : soit le premier joueur dispose d'une stratégie gagnante, soit c'est le second. Les jeux où le second joueur possède une stratégie gagnante s'appellent nuls (ou P) : c'est le cas par exemple du jeu de nim dans une position où il n'y a que deux lignes ayant le même nombre d'allumettes (car le second joueur peut reproduire sur l'autre ligne tout ce que fait le premier joueur, pour se maintenir dans une telle situation), et c'est encore plus trivialement le cas du jeu vide (∅) où aucun joueur n'a de coup à faire (i.e., le premier joueur a immédiatement perdu puisqu'il ne peut pas jouer). À l'inverse, les jeux où le premier joueur possède une stratégie gagnante s'appellent parfois N, mais c'est en fait une catégorie fourre-tout comme on va le voir.

Remarquons qu'on peut toujours — et c'est une cause commune de confusion — considérer formellement un jeu quelconque comme un jeu impartial, quitte à décider que les coups jouables dépendent non pas du joueur qui les fait mais de la parité du tour (i.e., aux échecs, au lieu de dire que c'est le joueur L qui déplace les blancs et le R qui déplace les noirs, on peut dire qu'un tour sur deux la règle est de déplacer une pièce blanche et un tour sur deux c'est une pièce noire, auquel cas il s'agit d'un jeu impartial : cela ne fait aucune différence sur le jeu considéré isolément, mais si on doit en faire la somme avec un autre cela change tout et cette façon de voir est un peu artificielle).

Correction (2014-06-19T20:00+02:00) : En écrivant cette entrée, j'avais interchangé les conventions sur ‘N’ et ‘P’ (parce que je pensais que ‘N’ voulait dire nul ; en fait, le standard est que ‘N’ veut dire gagnable par le premier/prochain joueur, comme Next, et ‘P’ veut dire gagnable par le second/précédent joueur, comme Previous). Je corrige, mais il se peut que j'en oublie, et il se peut aussi que mes explications soient, du coup, un peu confuses.

Comment savoir si un jeu impartial est nul (P, gagnable par le second joueur) ou N (gagnable par le premier joueur) ? Si on suppose que ses options (c'est-à-dire les positions auxquelles on arrive en un seul coup depuis la situation initiale, positions elles-mêmes considérées comme des jeux partant de cette position) ont toutes été catégorisées en P ou N, c'est facile : si au moins une des options est P, le jeu est N (une stratégie gagnante pour le premier joueur consistant alors à aller vers cette option N, auquel cas le joueur qui suit, et qui devient alors premier, devra faire un coup perdant), tandis que si toutes les options sont N, le jeu est P. Autrement dit : un jeu (impartial) est nul si et seulement si il n'a aucune option nulle ; de façon quelque peu étonnante, ceci constitue une définition rigoureuse d'un jeu nul, à cause de l'hypothèse qu'on a faite que les jeux terminent toujours en temps fini : c'est le principe d'induction bien-fondée qui permet de supposer pour définir une propriété d'un jeu que cette propriété a déjà été définie pour toutes les options du jeu.

(On peut d'ailleurs définir un jeu impartial comme étant simplement un ensemble, l'idée étant que le premier joueur choisit un élément de cet ensemble, le second joueur choisit un élément de cet ensemble, etc., et le processus termine toujours en vertu de l'axiome de régularité=fondation. On peut donc faire cette définition amusante : un ensemble est nul en tant que jeu si et seulement si aucun de ses éléments n'est nul en tant que jeu.)

Pour le jeu de nim à une seule ligne, cette catégorisation n'est pas très intéressante : soit la ligne est vide, auquel cas le jeu est trivial (c'est ∅), et il est P, soit la ligne est non-vide, auquel cas le jeu est N parce que le premier joueur peut raffler toutes les alumettes et il a gagné. Pour y voir plus clair, il faut donc introduire une catégorisation plus fine dans les jeux N. Celle-ci est apportée par la fonction de Grundy :

La fonction de (Sprague-)Grundy d'un jeu impartial est définie comme le plus petit nombre qui n'est pas la fonction de Grundy d'une de ses options. Il s'agit de nouveau d'une définition récursive. La fonction de Grundy du jeu vide ∅ (où il n'y a aucun coup à jouer) vaut 0 car c'est le plus petit nombre qui n'appartient pas à l'ensemble vide. La fonction de Grundy du jeu {∅} qui correspond à une seule ligne formée d'une seule allumette (le seul coup possible est de retirer cette allumette et de se ramener au jeu vide) vaut 1 car c'est le plus petit nombre différent de 0. De façon générale, il est facile de se convaincre que la fonction de Grundy d'une unique ligne de n allumettes vaut n. La fonction de Grundy détermine quel joueur a une stratégie gagnante : si elle vaut 0, le jeu est P (le second joueur a une stratégie gagnante), sinon, le jeu est N. Mais en fait, la fonction de Grundy détermine complètement un jeu impartial : même si on doit en faire la somme (ou le produit, à définir plus loin) avec un autre jeu, on peut toujours remplacer un jeu par sa fonction de Grundy, donc par une ligne d'allumettes au jeu de nim. C'est la raison pour laquelle Conway qualifie ces jeux de nimbres (enfin, nimbers en anglais) : le nimbre n, c'est juste le jeu de nim avec une seule ligne formée de n allumettes, ou n'importe quel jeu qui lui est équivalent, et cela se généralise aux ordinaux, le nimbre α, pour α un ordinal, est le jeu impartial dans lequel on décroît l'ordinal α (les deux joueurs peuvent le décroître puisque c'est un jeu impartial). À la différence des nombres surréels (pour ceux qui ont lu la partie précédente), les nimbres sont exactement les ordinaux, il n'y en a pas de nouveaux, mais leurs opérations sont très différentes de l'addition et la multiplication usuelle, ce sont les opérations de nim.

La somme de deux jeux est le jeu dans lequel, à chaque coup, un joueur peut jouer dans une ou l'autre des composantes de la somme, mais une seule. Le jeu de nim avec plusieurs lignes d'allumettes est donc la somme, en ce sens, des différents jeux de nim réduits à une seule ligne (ou nimbres) le constituant. Il se trouve que la fonction de Grundy d'une somme est complètement déterminée par la somme des fonctions de Grundy, et l'opération qui intervient, qui est donc celle qui calcule la fonction de Grundy du jeu de nim à partir des nombres d'allumettes des différentes lignes, s'appelle la somme de nim, que je noterai ⊕.

Cette somme de nim doit vérifier x⊕x=0 pour tout x, car quel que soit le jeu impartial G, le second joueur a toujours une stratégie gagnante à la somme de deux copies de G : il suffit qu'il réplique à chaque coup du premier joueur en faisant le même coup dans l'autre composante de la somme. (Pour ceux qui ont lu la partie précédente, les jeux impartiaux vérifient G=−G puisque les deux joueurs ont les mêmes coups, et il n'est pas surprenant qu'en ajoutant G à −G on tombe sur 0.) On a donc affaire à une addition de caractéristique 2.

De fait, l'opération ⊕ d'addition de nim est une opération bien connue des informaticiens, c'est le ou exclusif (bit-à-bit, des nombres écrits en binaire) : pour la calculer, on écrit les nombres en binaire, et pour chaque chiffre séparément (les unités, les deuxaines, les quatraines, les huitaines, les seizaines, etc.), on applique les règles d'addition modulo 2 sans retenue, c'est-à-dire 0⊕0=0, 0⊕1=1⊕0=1 et 1⊕1=0. La stratégie gagnante au jeu de nim est donc : calculer le ou exclusif des nombres d'allumettes sur chaque ligne, et s'arranger pour qu'après qu'on a joué ce nombre vaille 0 (tandis que si elle est déjà 0 quand on doit jouer, on va devoir espérer que l'adversaire commette une erreur, vu qu'il a une stratégie gagnante). En pratique, sur un nombre d'allumettes aussi petit que 1+3+5+7=16 (remarquons au passage que 1⊕3⊕5⊕7=0, donc c'est le second joueur qui a une stratégie gagnante quand on part de la disposition usuelle), il est assez facile de mémoriser toutes les positions P, surtout quand on a retenu qu'on pouvait ignorer deux lignes ayant le même nombre d'allumettes.

Il est peut-être étonnant que tout ceci se transpose exactement à l'identique aux jeu de nim transfini (où chaque ligne porte un nombre ordinal d'allumettes et chaque joueur décroît à son tour un de ces ordinaux et un seul) : les ordinaux possèdent une unique écriture en base 2, c'est-à-dire comme somme (décroissante, finie) de puissances de 2 (même si cette somme n'est pas toujours très intéressante, par exemple ω=2^ω a pour écriture binaire un 1 à la ω-ième position et des 0 partout ailleurs), et la somme de nim se fait de façon complètement identique. On peut par exemple jouer au jeu de nim en partant de ω, ω3, ω5 et ω7 allumettes disposées respectivement sur quatre lignes, et le second joueur possède une stratégie gagnante (remarquez que ω=2^ω, ω3=2^ω+1+2^ω, ω5=2^ω+2+2^ω et ω7=2^ω+2+2^ω+1+2^ω).

Multiplication de nim

Pour définir une autre opération sur les nimbres, je dois d'abord reformuler le jeu de nim : je suppose que j'ai une rangée de pièces de monnaie, ou disons peut-être de pièces d'Othello/reversi (vous savez, ces jetons qui sont blancs d'un côté et noir de l'autre ; Conway, lui, propose de jouer en retournant des tortues), la situation initiale étant par exemple que toutes les pièces sont blanches sauf la 1^re, 3^e, 5^e et 7^e qui sont noires. Chaque joueur tour à tour peut retourner une ou deux pièces de son choix, avec la restriction que la pièce retournée la plus à droite (donc la seule s'il n'en retourne qu'une) doit passer de noir à blanc (l'autre pièce retournée, s'il y en a une, peut être indifféremment blanche ou noire).

Cette dernière condition garantit la terminaison, mais la condition vraiment importante est celle qui impose qu'on retourne au plus deux pièces. Si on imposait qu'on en retourne toujours exactement deux, le jeu se terminant lorsqu'il n'est plus possible de jouer, c'est-à-dire si toutes les pièces sont blanche sauf peut-être la plus à gauche qui peut être noire, on obtient encore un jeu équivalent, comme on s'en rend compte en numérotant 0 la pièce la plus à gauche du nouveau jeu et ignorant son état qui ne fait que compléter la parité des autres. En revanche, si on permet de tourner au plus k pièces pour différentes valeurs de k (à vrai dire, seuls les k impairs sont vraiment intéressants, les k pairs s'en déduisant), on obtient toutes sortes de jeux dont les fonctions de Grundy ont été diversement étudiées : k=3, k=4, k=5, k=6, k=7, etc.

Il est assez facile de se convaincre que le ce jeu de retourner au plus deux pièces (en faisant passer celle de droite de noir à blanc) est équivalent au jeu de nim : les rangs des pièces noires (en numérotant 1 la pièce la plus à gauche si on retourne au plus deux pièces, 0 si on en retourne exactement deux) indiquent les nombres d'allumettes des différentes lignes de nim — on peut supposer qu'ils sont tous différents vu que de toute façon deux lignes ayant le même nombre d'allumettes « s'annulent » (si un joueur en entame une, l'autre joueur réplique sur l'autre ligne). C'est d'ailleurs peut-être une forme plus intéressante du jeu de nim, et qui se prête en tout cas à plus de variations. La fonction de Grundy d'une position est donnée comme la somme de nim des positions des pièces noires.

Dans ces conditions, il est assez naturel de considérer le jeu suivant : au lieu d'une simple ligne de pièces d'Othello/reversi, j'en ai tout un tableau (cf. l'illustration ci-contre, si vous la voyez, qui est également jouable si votre navigateur est de bonne humeur). La règle m'autorise à tourner une, deux ou quatre pièces, sachant que si j'en tourne deux elles doivent être sur la même ligne ou sur la même colonne, et si j'en tourne quatre elles doivent être sur exactement deux lignes et deux colonnes (i.e., former les quatre coins d'un carré) ; et dans tous les cas, la pièce en bas et à droite doit passer de noir à blanc. Comment gagner à ce nouveau jeu ? Manifestement, la fonction de Grundy est la somme de nim de celles des positions où une seule pièce est noire (pour les différentes pièces noires du jeu), mais comment calculer cette valeur-là ? La réponse fait intervenir une nouvelle opération : la fonction de Grundy de la position dans laquelle la pièce de la ligne i et de la colonne j est noire et toutes les autres sont blanches est donnée par i⊗j, où ⊗ désigne la multiplication de nim (la position en question est en un certain sens le produit du jeu de nim ayant une seule ligne à i allumettes et du jeu de nim ayant une seule ligne à j allumettes).

On peut définir l'addition et la multiplication de nim sans faire intervenir de jeux, en se rappelant ce que signifie la fonction de Grundy :

• La somme de nim x⊕y de deux nombres x et y est le plus petit nombre qui n'est pas de la forme x′⊕y pour un x′<x ni de la forme x⊕y′ pour un y′<y.
• Le produit de nim x⊗y de deux nombres x et y est le plus petit nombre qui n'est pas de la forme (x′⊗y) ⊕ (x′⊗y′) ⊕ (x⊗y′) pour des x′<x et y′<y.

(Cette définition a un sens par induction mutuelle sur les deux variables, et il n'y a pas besoin d'ajouter les contraintes x⊕0=x ou x⊗0=0, elles découlent des définitions si on réfléchit correctement sur l'ensemble vide. Il se trouve que la première définit le « ou exclusif » ; la seconde est bien plus intéressante.)

Les définitions ci-dessus, comme le jeu du rectangle de pièces d'Othello/reversi et comme le jeu de nim, ont un sens transfini, c'est-à-dire si x et y sont des ordinaux. Pour le jeu, on suppose que j'ai affaire à un rectangle infini de pièces dont les lignes et colonnes sont indicées par des ordinaux, toutes sont blanches sauf un nombre fini, et les règles sont précisément les mêmes (on peut retourner une pièce, ou deux sur la même ligne ou colonne, ou quatre aux coins d'un rectangle, toujours à condition que celle ayant la ligne et colonne portant les numéros les plus élevés passe de noir à blanc).

Ce qui est étonnant, et à mon avis un des « miracles » les plus épatant des mathématiques, c'est que cette définition très simple conduise à une structure extraordinairement riche : la classe des ordinaux (ou, si on n'aime pas les classes, l'ensemble des ordinaux inférieurs à n'importe quel cardinal régulier Ω fixé) forme un corps algébriquement clos de caractéristique 2 pour l'addition et la multiplication de nim. On peut être plus précis : les entiers de 0 à 2^2r−1 forment un corps isomorphe à 𝔽_2^2r (le corps fini ayant 2^2r éléments), l'ensemble de tous les entiers naturels (l'ordinal ω, si on veut) forme un corps qui est la clôture quadratique 𝔽_2^2∞ de 𝔽₂, l'ordinal ω^ωω forme la clôture algébrique de 𝔽₂, l'ordinal ω^ωωω forme le corps des fractions rationnelles sur ce dernier (et avec l'ordinal ω^ωω pour indéterminée), l'ordinal ω^ωωω+1 forme la clôture parfaite de ce corps de fractions rationnelles, l'ordinal ε₀ en forme la clôture quadratique, et on conjecture que le petit ordinal de Veblen en forme la clôture algébrique (après ça, les choses ne sont plus vraiment si intéressantes : l'ordinal ω₁, par exemple, est la clôture algébrique du corps des fractions rationnelles en ℵ₁ indéterminées sur 𝔽₂, et la même chose vaut pour tout cardinal). Quand je dis on conjecture, c'est Henrik Lenstra qui fait cette conjecture (et je suis d'accord avec lui) : Conway, lui, avait proposé l'ordinal de Feferman-Schütte, c'est certainement une erreur (et c'est tellement rare qu'il en fasse pour mériter être signalé). Et on peut vraiment faire des calculs là-dedans, qui sont plus ou moins compliqués selon les ordinaux impliqués, et ces calculs ont vraiment une incidence sur le jeu de retournement de pièces dans un tableau transfini : par exemple, le fait que ε₀^⊗3=ω^ωω (où ε₀^⊗3 signifie ε₀⊗ε₀⊗ε₀), qui repose vraiment sur le fait que ε₀ est quadratiquement clos, signifie que le second joueur a une stratégie gagnante dans la position où les deux seules pièces noires seraient en (ε₀, ε₀²) et en (1, ω^ωω), mais cette stratégie gagnante passera vraiment par le fait de savoir résoudre des équations quadratiques dans ε₀.