Des jeux aux nombres surréels

Piste rouge Le 9 septembre 2015  - Ecrit par  Lisa Rougetet Voir les commentaires

Dans cet article je me propose d’expliquer comment la recherche de la simplicité dans la description des parties de Dominos a amené John Conway à étendre la notion de nombre, et à créer la théorie des nombres « surréels ».

« Au commencement, tout n’était que vide et chaos. Et J. H. W. H. Conway créa les nombres. »

(Donald Knuth, 1974)

Comment réussir à déterminer à l’avance qui sera le gagnant de la partie de Dominos de la Figure 1 grâce aux nombres et aux opérations mathématiques ? C’est ce que nous allons essayer d’expliquer à travers cet article qui présente les origines et le développement de la théorie des nombres surréels de John Conway, et son application à l’analyse des jeux dits « combinatoires ».

Les jeux combinatoires se définissent par les propriétés suivantes : ils opposent exactement deux joueurs qui jouent alternativement, il n’y a pas de hasard, et l’information est complète, c’est-à-dire qu’à tout moment de la partie, les deux joueurs ont la même connaissance de l’état du jeu. C’est le cas du Puissance 4, du Morpion, des Échecs, des Dames, etc.


Figure 1 : Sur un plateau d’Échecs, deux joueurs appelés Gauche et Droite doivent placer à tour de rôle un de leurs dominos (aucune considération n’est portée aux valeurs inscrites sur les pièces). Gauche peut placer ses pièces selon un axe nord-sud et Droite selon un axe est-ouest. Un domino couvre exactement deux cases du plateau. Le but est de recouvrir deux cases adjacentes vides et le premier joueur qui ne peut plus placer de domino perd la partie. Source : Berlekamp et al., 2001

Quand les jeux se décomposent

Tout d’abord, un jeu combinatoire - qui peut se retrouver sous de nombreuses formes diverses et variées - se représente mathématiquement par un arbre, appelé arbre de jeu. C’est une représentation visuelle de tous les coups, et donc de toutes les positions, possibles du jeu. Le noeud initial représente la position initiale du jeu, avant qu’un des joueurs n’ait joué. Les branches émergeant d’un noeud le relie à d’autres qui représentent les positions autorisées pour le joueur selon les règles fixées au départ. Par exemple, la Figure 2 représente l’arbre de jeu d’une fin de partie de Morpion quand c’est au joueur qui a la croix de jouer (essayez de représenter l’arbre de jeu en entier pour le Morpion, et vous comprendrez pourquoi nous avons choisi une fin de partie !). On peut voir assez facilement quelles sont les différentes issues de cette partie et remarquer que le joueur qui a la croix peut éviter la défaite en rendant la partie nulle.


Figure 2 : Arbre de jeu d’une fin de partie au Morpion. Source : Interstices

Une simplification essentielle dans l’analyse des jeux – et c’est ce qui a permis à Conway de construire les nombres surréels – est de considérer qu’un même jeu est composé de plusieurs autres, qu’il est la somme de jeux plus petits et donc plus simples à analyser. En effet, un jeu combinatoire comme le jeu de Dominos présenté ci-dessus peut être découpé en plusieurs composantes, « morceaux de plateau », plus petites et indépendantes les unes des autres dans le sens où si on joue dans l’une d’elles, on ne modifie pas les autres (on dit que ces composantes sont disjointes). Il suffit alors « d’analyser » les composantes une à une et de « sommer » leur résultat pour comprendre la situation générale sur le plateau et déterminer quel joueur a l’avantage ou non. Un coup légal pour Gauche et Droite sera donc joué dans une et une seule des composantes du jeu initial. À chaque tour, le joueur choisit sa composante, joue, et perd celui qui ne peut plus jouer du tout.

Conway appelle cette décomposition la somme disjointe $G + H$ des jeux $G$ et $H$ et donne un exemple avec un jeu de Dominos.

La plupart des explications fournies par Conway part de constats ordinaires, s’appuie sur le bon sens de tout un chacun pour montrer que rien ne relève d’une quelconque intuition transcendante, réservée à quelques génies, mais de la logique même :

« En fait il arrive souvent dans certains jeux de la vraie vie qu’une position se divise en une somme disjointe, parce qu’il est évident que pour une raison quelconque les coups joués dans une composante de la position n’affectent pas les autres composantes. Considérons par exemple le jeu suivant avec des dominos, suggéré par Göran Andersson. »

(John Conway, 1976)

Après un certain temps de jeu, comme le montre la Figure 1, les cases libres sur le plateau sont généralement dans des régions séparées et le jeu devient alors somme de jeux « plus petits », un pour chaque région. Conway se propose d’analyser les régions les plus simples qu’on puisse trouver. Une région composée d’une seule case ☐ ne propose aucune possibilité de jeu, ni pour Gauche, ni pour Droite. On peut par exemple lui associer la valeur $0$ et négliger de telles régions, car aucun des deux joueurs ne peut placer de pièce. Pour les régions qui présentent deux ou trois cases à la verticale et aucune horizontale, il y a un coup possible pour Gauche mais aucun pour Droite, on peut leur associer la valeur $1$. De façon similaire, la région ☐☐☐☐ peut prendre pour valeur $-2$, car Gauche ne dispose d’aucun coup et Droite peut jouer vers deux positions possibles ☐☐ ou ☐+☐ . En sommant les valeurs de toutes les régions, on obtient alors un nombre qui détermine l’état du jeu en général : si le nombre est positif, Gauche a l’avantage, s’il est négatif, c’est Droite qui a l’avantage. Mais qu’en est-il des régions plus « compliquées » où à la fois Gauche et Droite peuvent jouer ? Pour répondre à cette question, nous devons vous en dire un peu plus sur les nombres surréels et leur construction.

Découverte des nombres surréels grâce au jeu de Go


John Horton Conway, mathématicien britannique né en 1937, s’est rendu célèbre en dehors du monde mathématique grâce à des récréations mathématiques et par son invention du Jeu de la vie (Life en anglais) dans les années 1970. Il a également apporté de significatives contributions en mathématiques pures dans divers domaines tels que la théorie des groupes (en 1967 il découvre un nouveau groupe, important pour ses propriétés de symétrie, qui sera appelé the Conway’s Constellation), la théorie des nombres, la théorie des noeuds, la théorie des formes quadratiques, et notamment - celle qui suscite le plus notre intérêt - la théorie des jeux.

Conway mène ses études à Cambridge et soutient une thèse en 1964 sous la direction de Harold Davenport (1907 - 1969), président de la London Mathematical Society de 1957 à 1969, dans le domaine de la théorie des nombres, sur les ensembles ordonnés homogènes (un ensemble ordonné est muni d’une relation d’ordre qui permet de comparer les éléments de l’ensemble de manière cohérente, par exemple la relation $\leq$ entre les entiers naturels). C’est en résolvant un problème posé par ce dernier sur la décomposition de chaque entier en somme de trente-sept nombres, tous élevés à la puissance cinq, que Conway s’intéresse aux ordinaux transfinis (c’est-à-dire aux ordinaux appartenant à un ensemble ordonné infini). À cette même époque, Conway est un fervent joueur de Backgammon – il passe des heures à y jouer dans la salle commune de Cambridge [1] – mais c’est son intérêt pour le jeu de Go qui l’amène à se pencher sur la théorie des jeux combinatoires.

En jouant régulièrement avec deux joueurs de très haut niveau – l’un est le champion national anglais – Conway remarque que les fins de parties au Go apparaissent, comme pour le jeu de Dominos ci-dessus, comme la somme disjointe de jeux plus petits. Pour analyser ces composantes disjointes, c’est-à-dire leur affecter une valeur qui représentera la force de la position pour un joueur donné, Conway utilise des nombres, car il se rend compte qu’à certains jeux peuvent s’associer certains nombres, des entiers naturels, des rationnels, des dyadiques selon les cas (nous expliquerons par la suite comment se déterminent ces nombres), et que l’addition usuelle s’applique aussi aux composantes disjointes du jeu global.

C’est grâce à l’étude minutieuse de cette analogie, qui va se révéler profonde, entre les jeux, les nombres et l’opération somme que Conway obtient un tout nouvel ensemble de nombres qui sont très vite appelés « surréels ».

L’appellation ne vient pas de Conway, mais du mathématicien et informaticien américain Donald Knuth (né en 1938) qui publie en 1974 « Surreal Numbers, how two ex-students turned on to pure mathematics and found total happiness » (« Les Nombres Surréels, ou comment deux anciens étudiants découvrirent les mathématiques pures et vécurent heureux »). Ce sont les premiers écrits à paraître sur le sujet – Conway se qualifie lui-même de très paresseux quand il s’agit de publier – sous la forme originale d’une « nouvelle mathématique » mettant en scène deux personnages principaux, Alice et Bill, qui revivent la construction des nombres surréels suite à la découverte d’une pierre sur laquelle est écrit : « Au commencement, tout n’était que vide et chaos, et J. H. W. H. Conway créa les nombres. ».

Il peut paraître tout de même un peu surprenant de découvrir qu’en fin de compte Conway ne cherchait pas à développer cette nouvelle structure des nombres surréels, mais seulement à analyser le jeu de Go ! Il en fut d’ailleurs le premier surpris :

« La théorie fut un véritable choc pour moi. C’était bizarre… fou, mais c’était vrai ! C’était comme grimper au sommet d’une tige de haricot, et là se dressait un château enchanté. Je n’avais aucune idée de ce à quoi m’attendre. Toutes les règles avaient changé, comme par magie. C’est comme un nouveau monde. »

(John Conway interviewé par Charles Seife, 1994)

Et il explique dans la préface de l’ouvrage récapitulant son travail, intitulé « On Numbers and Games » : « Ce livre a été écrit pour apporter de la lumière sur une relation existant entre deux matières favorites de l’auteur – la théorie des nombres transfinis et celle des jeux mathématiques. ».

La simplicité avant toute chose


La théorie développée dans « On Numbers and Games » constitue un développement important que Conway explique ainsi :

« Vous pouvez la voir comme une extension des nombres réels, mais elle présente aussi une qualité surréelle. De nouveaux nombres apparaissent – et personne ne les avait jamais vus auparavant. Mais ils existent. Les nombres déjà trouvés découlent de la définition – tous les nombres réels et même les ordinaux transfinis comme $\omega$. »

(John Conway interviewé par Charles Seife, 1994)

Cette découverte des nombres surréels généralise admirablement la construction des nombres réels par les coupures de Dedekind.

Les coupures de Dedekind

La méthode introduite en 1876 par le mathématicien allemand Richard Dedekind, appelée la « méthode des coupures », est en réalité une tentative de définition de la droite géométrique, vue comme une infinité de points finement serrés pour former une ligne lisse sans le moindre trou, et ce à partir d’objets mathématiques élémentaires : les nombres rationnels et la notion d’ensemble. Dedekind est guidé par l’intuition géométrique qu’un point $M$ sur une droite partage les points de celle-ci en deux classes : ceux à droite de M et ceux à gauche de $M$. Il définit ainsi une coupure d’un ensemble totalement ordonné $E$ comme le couple $(A, B)$, avec $A$ et $B$ deux sous-ensembles de $E$ formant une partition de $E$, et tels que tout élément de $A$ est strictement inférieur à tout élément de $B$ – propriété qu’on retrouve dans la construction des nombres surréels de Conway.

La coupure conceptualise quelque chose qui se trouverait entre $A$ et $B$, mais qui ne serait pas nécessairement un élément de $E$. C’est ce qu’il advient quand Dedekind prend pour $E$ l’ensemble des nombres rationnels qu’il complète par la création de nombres irrationnels entre les rationnels. Les coupures qui déterminent un nombre rationnel – par exemple $(A, B)$ où $A$ est l’ensemble des rationnels inférieurs ou égaux à $4$ et $B$ l’ensemble des rationnels supérieurs strictement à $4$ représente le rationnel $4$ – possède la propriété suivante : ou bien il existe un plus grand élément dans $A$, ou bien il existe un plus petit élément dans $B$. Réciproquement, une coupure qui vérifie cette propriété définit un nombre rationnel.

Mais il existe des coupures qui ne possèdent pas cette propriété. Par exemple, en prenant pour $A$ l’ensemble des rationnels qui sont négatifs et des rationnels positifs dont le carré est strictement inférieur à $2$, et pour $B$ l’ensemble des rationnels positifs donc le carré est supérieur à $2$ : cette coupure représente le nombre $\sqrt{2}$, irrationnel car il n’existe pas de plus grand élément dans $A$, ni de plus petit élément dans $B$.

Les travaux de Conway furent très bien reçus par la collectivité des mathématiciens, plus particulièrement par les logiciens et les théoriciens des ensembles. Le spécialiste des mathématiques récréatives Martin Gardner dira de « On Numbers and Games » que c’est un « Conway millésimé : profond, révolutionnaire, troublant, original, impressionnant, spirituel et crépitant d’outrageux jeux de mots à la Carroll » (Martin Gardner, 1997) .

Conway considère néanmoins modestement son travail, car une fois les nombres définis comme des forces de positions dans certains jeux [2], les propriétés et opérations arithmétiques habituelles en découlent presque immédiatement :

« La simplicité du procédé [de construction des nombres surréels] est incroyable. »

(John Conway interviewé par Jorge Nuno Silva, 2005)

La simplicité est une caractéristique essentielle des travaux de Conway. De même qu’il est primordial pour lui d’attirer l’attention des jeunes collégiens, lycéens et étudiants par des jeux, des énigmes et autres divertissements mathématiques, il faut également montrer qu’on a compris les choses en les rendant transparentes. Conway cherche constamment à avoir une meilleure compréhension de ce qu’il sait déjà et à travailler les mathématiques de manière plus visuelle et intuitive. Toujours est-il qu’il prend du plaisir à expliquer son travail autour des nombres surréels et qu’il s’est véritablement amusé dans la rédaction de son ouvrage. Il conseille aux lecteurs « davantage intéressés à jouer qu’à philosopher sur les nombres » de commencer d’emblée avec le chapitre 7 qui entame la réflexion sur les jeux. Comme nous aimons philosopher sur les nombres, voici avant tout une brève explication sur la construction des nombres surréels.

Construisons des nombres surréels avec Conway

« Dedekind ajoute de nouveaux nombres entre les rationnels. Cantor en ajoute au delà des entiers. J. Conway en insère partout. »

(Jean-Paul Delahaye, 2008)

La construction des nombres de Conway est basée sur une seule règle, semblable à celle introduite par Dedekind lorsqu’il définit ses coupures :

Règle fondamentale : Si on se donne deux ensembles, un à gauche noté $L$ ($L$ pour Left) et un à droite noté $R$ ($R$ pour Right), pour lesquels tout élément de $L$ est inférieur à chaque élément de $R$, alors il existe un nombre, noté $\{L|R\}$, qui désigne le « nombre le plus simple » entre ces deux ensembles.

Tous les nombres surréels sont construits par cette règle. Si $x$ est égal au nombre $\{L|R\}$, on désigne par $x^L$ un élément qui appartient à $L$ et par $x^R$ un élément qui appartient à $R$. Formellement, « on dit que $x \geq y$ si et seulement si (aucun $x^R \leq y$ et $x \leq$ aucun $y^L$ ) », comme cela est illustré sur la figure suivante [3] :

Selon cette règle, chaque nombre s’écrit sous la forme $\{L|R\}$ où $L$ et $R$ sont deux ensembles de nombres déjà construits. La question que Conway se pose alors est « comment la construction peut-elle s’opérer alors qu’initialement aucun nombre n’a été construit ? ». La réponse réside dans le fait qu’avant l’existence d’un nombre quelconque, il y a l’ensemble vide. La construction du premier nombre se fait alors en prenant les ensembles $L$ et $R$ tous deux égaux à l’ensemble vide. Conway appelle ce nombre $0$ :

\[0 = \{ | \}.\]

$0$ est-il bien un nombre ? Oui, car on ne peut avoir l’inégalité $0^L\geq 0^R$, étant donné qu’il n’y a rien dans les ensembles $0^L$ et $0^R$ ! De plus, $0$ vérifie les propriétés habituelles d’addition, de multiplication, d’inverse. « Donc le nombre $0$ a au moins quelques unes des propriétés que nous connaissons et aimons. », dit-il. La simplicité avant toute chose !

De là, tout se déduit en plaçant les nombres nouvellement créés aux extrémités de l’arrangement droite-gauche. Par exemple, l’expression $\{0| \}$ avec l’ensemble vide à droite définit le nombre $1$ et $\{ |0\}$ définit $-1$ :
\[1 = \{0| \}, -1 = \{ |0\}. \]

Par ce procédé inductif [4], Conway est capable de définir tous les entiers, toutes les fractions, tous les irrationnels, l’ensemble des nombres transfinis de Cantor, celui des infinitésimaux et « les classes infinies de nombres étranges jamais vus auparavant par l’homme, tels que $\sqrt[3]{(\omega + 1)} - \frac{\pi}{\omega}$ où $\omega$ est le premier ordinal infini de Cantor. ». Ces nouveaux nombres enrichissent l’imaginaire mathématique.

Conway voit la création de ces nombres comme une naissance progressive qui peut se représenter sous la forme de l’arbre de la Figure 3 : au jour $0$ est créé le nombre $0$, puis de ce nœud initial émergent deux ramifications pour la création au jour $1$ des nombres $1$ et $-1$ correspondant respectivement aux coupures $\{0| \}$ et $\{ |0\}$. À la fin du jour $1$ il y a trois nombres : $-1$, $0$ et $1$.

Le jour $2$ voit naître les nombres $-2$ et $2$, ainsi que les deux nombres surréels insérés dans chaque intervalle entre les trois nombres créés au jour $1$. On obtient alors :
\[\{-1|0\}=-1/2, \{0|1\}=1/2\]
À la fin du jour $2$ il y a les sept nombres suivants : $-2$, $-1$, $-1/2$, $0$, $1/2$, $1$ et $2$.
À la fin du jour $3$, on trouve les nombres : $-3$, $-2$, $-3/2$, $-1$, $-3/4$, $-1/2$, $-1/4$, $0$, $1/4$, $1/2$, $3/4$, $1$, $3/2$, $2$ et $3$.


Figure 3 : L’arbre des nombres surréels créés au jour 3 à partir des nombres construits précédemment. À vous d’en continuer la construction ! Source : Conway, 1976

En continuant ainsi le processus, au jour $n$ ont été créés tous les nombres $\{L|R\}$ pour lesquels chaque élément des deux ensembles $L$ et $R$ a déjà été construit au jour antérieur. Par exemple, $3/2=\{1|2\}$ est créé au jour $3$ à partir des nombres $1$ et $2$ nés les jours précédents. $n$ et $-n$ sont les deux derniers nombres créés, et tout autre nombre est la moyenne arithmétique de ceux situés à sa droite et à sa gauche au jour d’avant (la moyenne arithmétique de deux éléments est obtenue en divisant par deux leur somme).

Au fur et à mesure que les jours s’écoulent, naissent les nombres de la forme ±$k$/$2^n$ où $k$ est un entier naturel, appelés les nombres rationnels dyadiques. Un nombre rationnel dyadique s’écrit sous la forme d’une fraction avec au dénominateur une puissance de $2$ et au numérateur un entier relatif quelconque.

Ce qui fait la richesse - et la difficulté - de cette construction réside dans le fait que le processus de création ne se limite pas à la création des nombres les jours finis, car au delà, si on réitère le processus une infinité de fois, il y a le jour $\omega$. Ce jour-là, est créé $\omega$ lui-même qui est plus grand que tous les nombres entiers, et qui est représenté par $\{0,1,2,3,…| \}$. De la même façon, est créé $-\omega$ qui est plus petit que tous les nombres entiers. Le jour $\omega$ voit également naître les nombres réels manquants, l’irrationnel $\sqrt{2}$ par exemple, obtenus grâce aux coupures avec les nombres dyadiques créés antérieurement.

Voilà créés les nombres surréels de Conway grâce à une double généralisation des constructions proposées par Dedekind et Cantor près d’un siècle avant.

Voyons à présent comment ces nombres trouvent une application dans l’analyse des jeux combinatoires [5].

L’application des nombres surréels aux jeux


Les nombres surréels sont utilisés par Conway dans la deuxième partie de son ouvrage « On Numbers and Games » pour mesurer la valeur de la force des positions de certains jeux qui sont « dans l’esprit, plus proches des Échecs que du Football » où s’affrontent deux joueurs, souvent appelés Gauche et Droite ou respectivement Noirs et Blancs, Vertical et Horizontal, ou Arthur et Bertha. La sympathie de Conway se tourne de manière générale vers Gauche (Left) (faut-il y voir une tendance politique ??), c’est-à-dire que les valeurs données sont à interpréter du point de vue du joueur Gauche (si le nombre est positif, il a l’avantage, sinon c’est Droite qui l’a). Conway définit ensuite les positions de jeu, et pour une certaine position $P$, les règles du jeu autorisent à Gauche un certain ensemble d’options noté $P^L$, et pour Droite un autre ensemble d’options noté $P^R$.

On voit déjà émerger l’analogie avec les nombres et les ensembles droite/gauche présentés précédemment. Ainsi, n’importe quelle position $P$ est complètement déterminée par ses options pour Gauche et celles pour Droite, et Conway s’autorise à écrire $P = \{P^L | P^R \}$. Par exemple, $P = \{A,B,C | D \}$ signifie qu’à partir de la position $P$, Gauche peut atteindre une des positions $A$, $B$ ou $C$ (et seulement celles-là) alors que Droite ne peut atteindre que la position $D$.

Un jeu finit quand un des joueurs ne peut plus jouer. C’est le cas de la configuration $\{ \: | U, V, W \}$ quand c’est à Gauche de jouer. Conway prend pour convention que le jeu est fini : les joueurs sont en effet « tous les deux des hommes très occupés, avec d’importantes responsabilités politiques » !

Comme nous l’avons expliqué précédemment avec le jeu du Morpion, les différentes options disponibles pour Gauche et Droite à partir d’une position $P$ peuvent être représentées sous la forme d’un arbre : les positions sont les nœuds et les coups possibles sont les branches qui relient ces nœuds. Conway prend pour convention de représenter les coups de Gauche par des branches inclinées vers la gauche et inversement pour Droite. La Figure 4 ci-dessous montre les quatre configurations de jeux les plus simples possibles, écrites à la fois sous la forme d’un arbre et en utilisant les notations du système de Conway. L’arbre se lit de bas en haut : le premier noeud est la position initiale du jeu, et selon si la branche émergeant de ce noeud monte vers la droite ou monte vers la gauche, un coup est possible pour Droite ou pour Gauche, respectivement.

Figure 4 : Les jeux les plus simples représentés sous forme d’arbres. « Le jeu le plus simple de tous est la fin de partie 0. Je vous offre courtoisement le premier coup de ce jeu, et exige que vous le jouiez. Vous perdez bien évidemment, parce que $0$ est défini comme le jeu pour lequel il n’est jamais possible de jouer. Dans le jeu $1= \{ 0| \: \}$ , il y a un coup légal pour Gauche, ce qui termine le jeu, mais à aucun moment il n’y a de coup légal pour Droite. Si je joue Gauche, et vous Droite, et que vous avez à nouveau le droit de jouer en premier (ce qui est juste car vous avez perdu au jeu précédent), vous perdrez à nouveau, étant incapable de jouer, même à partir de la position initiale. Pour vous prouver mes compétences, je vais maintenant entamer le jeu à partir de la même position, jouer mon coup légal vers $0$, et vous exiger de jouer le vôtre. Bien sûr vous êtes à présent en train de suspecter le fait que Gauche gagne toujours, donc pour notre prochain jeu, $-1$, vous pouvez jouer Gauche et moi Droite ! Pour le dernier de nos exemples, le nouveau jeu $* = \{0|0\}$, vous pouvez jouer le rôle que vous souhaitez, à condition que vous me laissiez le privilège de jouer le premier. » Source : Conway, 1976

Attention ! Certains jeux correspondent à un nombre, et d’autres non. En effet, dans la première partie de « On Numbers and Games » portant uniquement sur les nombres, Conway explique que pour l’expression $\{L|R\}$ représente un nombre, il faut vérifier la condition que tous les éléments de $L$ soient strictement inférieurs à chaque élément de $R$. En revanche, dans la théorie plus générale développée dans la deuxième partie de son livre, Conway explique que quand la condition sur $L$ et $R$ est omise, on obtient la notion plus générale d’un jeu. Par exemple, $* = \{0|0\}$ n’est pas un nombre, car il ne respecte pas la règle fondamentale, on a en effet $0\leq 0$. C’est pour cette raison qu’on le symbolise par $*$, mais dans la pratique « ludique », il désigne la situation particulière d’un jeu pour laquelle le premier joueur est gagnant. Ce jeu sera appelé par Conway « fuzzy » (« confus »).

En résumé, dans le jeu $0$, il existe une stratégie gagnante pour le second joueur – car le premier ne peut jouer donc il perd en premier. Dans le jeu $1$, il y a une stratégie gagnante pour Gauche quel que soit le joueur qui commence – en effet Droite n’a aucun coup à jouer. Réciproquement, dans le jeu $-1$, il y a une stratégie gagnante pour Droite. Et enfin dans le jeu $*$ , il y a une stratégie gagnante pour le premier joueur – car en jouant le premier, on joue l’unique possibilité de jeu qui mène au jeu $0$. Conway introduit alors les notations correspondantes :

  • $G >0$ ($G$ est « positif ») s’il existe une stratégie gagnante pour Gauche
  • $G < 0$ ($G$ est « négatif ») s’il existe une stratégie gagnante pour Droite
  • $G = 0$ ($G$ est « zéro ») s’il existe une stratégie gagnante pour le deuxième joueur
  • $G \parallel 0$ ($G$ est « confus », « fuzzy ») s’il existe une stratégie gagnante pour le premier joueur.

Il combine ensuite ces notations pour obtenir $G \geq 0$ ($G > 0$ ou bien $G =0$ ), $G \leq 0$, $G \rhd 0$ ($G > 0$ ou bien $G \parallel 0$), et $G \lhd 0$. Par exemple, $G \geq 0$ signifie que si Droite commence, il existe une stratégie gagnante pour Gauche, tandis que $G \rhd 0$ signifie qu’il existe une stratégie gagnante pour Gauche si celui-ci commence. Grâce à ces notations, Conway établit une sorte de classification des jeux selon les possibilités des deux joueurs et il montre que chaque jeu $G$ appartient à l’une des classes décrites ci-dessus. Ce résultat est particulièrement intéressant, car il montre l’aspect « déterminé » des jeux combinatoires, à savoir qu’en présence de deux joueurs qui savent parfaitement jouer et qui ne commettent aucune erreur, il est possible - en théorie - de déterminer qui sera le gagnant sans même jouer la partie. Ensuite, il en déduit des résultats, sous forme de théorèmes, qui permettent de connaitre la nature de la somme de deux jeux quand on connait la nature de ceux-ci. Par exemple, « si $G$ et $H$ sont des jeux positifs ou zéros, alors le jeu $G+H$ est aussi positif ou zéro », ou encore « si $H$ est un jeu zéro, alors le jeu $G+H$ est de même nature que $G$ ». Cela permet ainsi d’analyser la nature du jeu global en sommant la nature des jeux disjoints qui le composent.

Conway précise que dans la deuxième partie de son ouvrage « On Numbers and Games » la plupart des valeurs rencontrées pour donner la force des positions de jeux sont les nombres réels « ordinaires », et non des surréels créés à partir de l’ordinal de Cantor $\omega$. Cela est dû au fait que la majorité de ces jeux sont finis. Mais on pourrait envisager de façon abstraite le jeu $\omega=\{1,2,3,...|\}$ qui présente une infinité de positions pour Gauche (et aucune pour Droite) et le représenter par l’arbre suivant (ce jeu deviendrait éternellement répétitif et ennuyeux, surtout pour Droite !) :

JPEG - 23.6 ko

Figure 6 : L’arbre de $\omega=\{1,2,3...|\}$. Source : Conway, 1976

Pour en revenir aux Dominos

Dans l’introduction, nous avions laissé en suspens la question de l’analyse des régions plus « compliquées » du jeu de Dominos, dans lesquelles Gauche et Droite peuvent jouer. Grâce aux nombres surréels, nous pouvons à présent y arriver. Reprenons les bases : nous avions proposé de donner la valeur $0$ à la région ☐, cette valeur est justifiée par le fait que ni Gauche ni Droite ne peuvent jouer, leurs ensembles d’options $P^L$ et $P^R$ se résument à l’ensemble vide, et on obtient $\{ | \}=0$. De même, les régions avec deux ou trois cases verticales et aucune horizontale donnent une possibilité de jeu pour Gauche - celle d’arriver à la position où aucun des joueurs ne peut jouer, soit le jeu $0$ - et aucune pour Droite, soit $ \{0| \}=1$. La région ☐☐☐☐ a pour valeur $ \{ |0, -1\}=-2$ du fait que Droite peut jouer vers les positions ☐☐ $= -1$ ou ☐+☐ $=0$.
Voici quelques exemples d’analyse de régions où Gauche et Droite ont tous deux la possibilité de jouer et qui vous permettront d’analyser le plateau représenté à la Figure 1 :


Figure 5 : Cette région a pour valeur $*$ car chacun des joueurs peut accéder à la position ☐ et c’est le premier à placer un domino qui remporte la position. Source : Berlekamp et al., 2001


Figure 6 : Ici, le joueur Gauche peut accéder à la position $1$ et par symétrie, Droite peut accéder à la position $-1$. La valeur de la position est donc $\{1| -1\}=0$, le deuxième joueur gagne. Source : Berlekamp et al., 2001


Figure 7 : Gauche a à sa disposition deux coups : un premier qui l’amène à la position ☐☐ $= -1$ (ce qui est stupide car il laisse alors Droite remporter la partie), et un deuxième (plus sensé) qui l’amène à ☐+☐ $=0$. Droite n’a en revanche qu’un coup disponible qui l’amène à la position 1. La valeur de cette région est donc $\{-1, 0 |1\}= 1/2$, ce qui signifie que Gauche possède un avantage d’un demi coup sur Droite dans cette région. Source : Berlekamp et al., 2001

Ainsi, si au cours d’une partie de Dominos, la configuration de la Figure 7 se présente sur le plateau de jeu, en même temps que ☐☐☐☐, il suffit de sommer leurs valeurs respectives pour obtenir la valeur de la configuration générale. On obtient alors $1/2-2=-3/2$ qui est négatif, donc Droite a trois demi coups d’avance et peut remporter la partie, quel que soit le joueur qui commence.

Conway se détache ensuite du cadre du jeu de Dominos et s’intéresse à des sommes de jeux simples. Par exemple, dans le jeu $1+1$, Gauche peut jouer vers $1+0$ ou $0+1$ selon s’il agit dans la première ou la deuxième composante de la somme. Étant donné que Droite ne peut rien faire, on a alors que $1+1 =\{1,1| \}$. Les deux coups pour Gauche sont similaires et on peut donc simplifier $1+1= \{1| \}$ qui vaut $2$. En réécrivant le jeu $1-1$ comme $1+(-1)$, on constate que Gauche n’a qu’un coup possible vers $0 + (-1)$, ce qui fait gagner Droite, et que Droite ne peut que jouer vers la position $1+0$, ce qui fait gagner Gauche. Aucun des deux joueurs ne veut donc commencer à jouer, car le deuxième est vainqueur, le jeu vaut donc $\{-1|1\}= 0$. De manière similaire, $* + * = \{* | *\}$, car $*$ signifie la victoire pour le premier joueur. On a donc $* + * = 0$.

On peut aussi vérifier que $1/2+1/2=1$ en utilisant la représentation avec des arbres. Dans la Figure 8 sont dessinées les trois composantes du jeu $1/2+1/2-1$, les lettres désignent les différentes positions du jeu. On montre alors que ce jeu est égal au jeu $0$, celui pour lequel le deuxième joueur possède une stratégie gagnante.

JPEG - 23.3 ko

Figure 8 : Preuve stratégique que $1/2+1/2=1$. La position initiale est donnée par $(a,b,c)$. Regardons dans un premier temps ce qu’il se passe si Gauche joue en premier. S’il joue de $a$ vers $d$ (ce qui revient au même que de $b$ vers $e$, et ce sont les seules possibilités), Droite répond en jouant de $b$ vers $h$ et Gauche ne pourra que jouer de $h$ vers $j$, ce qui laisse Droite remporter la partie avec le dernier coup $c$ vers $f$. Si Droite commence de $b$ vers $h$, Gauche répond en jouant $a$ vers $d$ et remporte la partie (en jouant $h$ vers $j$) après que Droite ait joué son seul coup possible, $c$ vers $f$. Maintenant, si Droite commence de $c$ vers $f$ (le cas où Droite commence de $a$ vers $g$ est équivalent au cas précédent, étant donné que les deux jeux $1/2$ sont équivalents), Gauche répond de $a$ vers $d$, puis Droite de $b$ vers $h$, et Gauche conclue la partie avec $h$ vers $j$. Dans tous les cas, il existe une stratégie gagnante pour le deuxième joueur, donc le jeu $1/2+1/2-1$ est bien égal au jeu $0$.

Qu’est-ce que ces égalités signifient ?

« Il existe une célèbre histoire d’une petite fille qui jouait à une sorte de combat simultané contre deux grands maîtres d’Échecs (sûrement un grand concept !). Comment se fait-il qu’elle réussisse à remporter un des deux matchs ? Anne-Louise jouait les Noirs contre Spassky, les Blancs contre Fisher. Spassky jouait en premier, et Anne-Louise copia simplement son mouvement lors de son premier coup contre Fisher, puis copia la réponse de Fisher lors de sa réponse au premier coup de Spassky, etc. »

(John Conway, 1976)

Tout cela pour dire qu’avant de s’avouer vaincu parce qu’on se retrouve à disputer simultanément deux parties d’Échecs devant des champions internationaux, mieux vaut avoir lu Conway et simplifier le problème en somme de composantes disjointes !

Nous n’irons pas plus loin dans l’explication de la théorie profondément travaillée et complète de « On Numbers and Games ». L’approche que nous avons réalisée nous a tout de même permis d’effleurer la richesse du travail de Conway, dans lequel les nombres s’identifient aux jeux d’une manière tout à fait naturelle – sous réserve d’y consacrer un peu de temps…

Bêtises ou mathématiques ?


En conclusion générale de son livre, Conway pose quelques interrogations mais « laisse ces questions à d’autres, qui trouveront certainement plein d’autres problèmes sur lesquels réfléchir, et d’émerveillements pour les étonner et les amuser dans le monde curieux des jeux. ». Car pour Conway, les grandes théories découlent de l’analyse des choses simples et il considère que tout le monde peut rencontrer de nouveaux jeux et tenter de découvrir leurs propriétés grâce aux théories existantes. Lors d’une conférence sur les récréations mathématiques donnée en septembre 1976 à l’université de Miami, Conway finit sur ces mots :

« Les théories peuvent être appliquées à des centaines et des milliers de jeux – de petites choses vraiment jolies ; vous pouvez en inventer encore et encore et encore. C’est particulièrement jubilatoire quand vous trouvez un jeu auquel quelqu’un a déjà réfléchi sans en faire probablement grand chose, que vous découvrez que vous pouvez mettre en marche une de ces théories automatiques, trouver la valeur de quelque chose, et dire, « Ah ! Droite a 47/64 coups d’avance, et donc elle gagne. » »

(John Conway, 1978)

Richard Guy affirmera : « Est-ce-que toutes ces bêtises ont quelque chose à voir avec les mathématiques ? Bien sûr que oui ! Bien sûr car ce sont des mathématiques ! ». Avec Conway, il est impossible de tracer une barrière entre les choses triviales et les résultats mathématiques profonds ; pour lui il n’en existe pas [6]. C’est par l’analyse des jeux les plus simples qu’il a réussi à construire une base solide sur laquelle il a pu, grâce à son système gauche-droite, broder de nouveaux jeux, et élever minutieusement un vaste et fantastique édifice. Il ne prétend pas pour autant avoir couvert tout le domaine des jeux et c’est non sans humour qu’il le mentionne dans « On Numbers and Games » :

« Seul un certain sentiment d’inachèvement nous incite à ajouter un dernier théorème. THÉORÈME 100. Ceci est le dernier théorème dans ce livre. (La preuve est évidente.) »

(John Conway, 1976)

Conway dit avoir rédigé « On Numbers and Games » - qui comporte environ deux cent vingt pages - en une semaine seulement, sous prétexte de se libérer l’esprit afin de se consacrer au projet commun qu’il mène au même moment avec Elwyn Berlekamp et Richard Guy sur le « Winning Ways for Your Mathematical Plays », paru en 1982 après seize années d’écriture, ouvrage encore actuellement considéré comme LA référence conseillée pour s’initier aux jeux combinatoires et à leur analyse. « On Numbers and Games » apporte un degré d’abstraction et de généralisation sans précédent à la récente théorie des jeux combinatoires [7]. Plus récemment, la théorie des jeux combinatoires continue d’avancer grâce à la programmation informatique et à la théorie des graphes, et des colloques sont régulièrement organisés - à Lisbonne cette année par exemple.

Références :


CONWAY John [1976], On Numbers and Games, Londres, Academic Press Inc., 1976


CONWAY John [1978], « A Gamut of Game Theories », Mathematics Magazine, Vol. 51, No. 1, janvier 1978, pp. 5-12


BERLEKAMP Elwyn et al. [2001], BERLEKAMP Elwyn et CONWAY John et GUY Richard, Winning Ways for your mathematical plays, Vol. 1, 2nd Edition, Wellesley (Massachusetts), A K Peters, 2001


DELAHAYE Jean-Paul [2008], « Surréalisme mathématique », Pour la Science, No. 372, octobre 2008, pp. 104-109


GARDNER Martin [1997], Penrose Tiles to Trapdoor Ciphers, Washington D.C., The Mathematical Association of America, édition revue de celle de 1989 publiée par W. H. Freeman, New York, 1997


GUY Richard [1982], « John Horton Conway : Mathematical Magus », The Two-Year College Mathematics Journal, Vol. 13, No. 5, novembre 1992, publié par Mathematical Association of America, pp. 290-299


KNUTH Donald [1974], Surreal Numbers, Addison-Wesley Publishing Company Inc., 1974


SEIFE Charles [1994], « Mathemagician », The Sciences, Vol. 34, Issue 3, mai-juin 1994, pp. 12-15


SILVA Jorge Nuno [2005], « Breakfast with John Horton Conway », Newsletter of the European Mathematical Society, Issue 57, septembre 2005, pp. 32-34

Post-scriptum :

Je tiens à remercier chaleureusement les relecteurs de cet article : amic pour sa (double) lecture attentive et Maxime Bourrigan pour les nombreux liens qu’il m’a transmis. Un grand merci également à Patrick Popescu-Pampu qui m’a sollicitée pour écrire cet article et m’a soutenue au cours de sa rédaction. Enfin, je remercie Jérôme Buzzi pour m’avoir aidée à rendre cet article le plus accessible possible.

Article édité par Patrick Popescu-Pampu

Notes

[1Une salle commune dans une université est un lieu de convivialité où se retrouvent les étudiants en dehors de leurs heures de cours pour travailler, échanger, se divertir... C’est généralement un lieu intellectuellement très stimulant.

[2Chaque position de jeu confère un avantage à l’un ou à l’autre des deux joueurs. Cet avantage se quantifie grâce à un nombre qui indique quel joueur est en position de force par rapport à l’autre. On parle aussi de valeur d’une position.

[3Elle a été dessinée par Patrick Popescu-Pampu.

[4Toute l’astuce - et la difficulté - réside dans le fait que les définitions d’un nombre surréel et de la relation d’ordre sont récursives, donc tout se définit progressivement, la relation d’ordre et les nombres eux-mêmes. Pour plus de précisions, nous renvoyons le lecteur à la page suivante sur les nombres surréels.

[5Pour une approche complémentaire sur les nombres surréels et les opérations que l’on peut effectuer (somme, multiplication, puissance), nous renvoyons au blog de David Madore.

[6Voici une vidéo récente très intéressante (en anglais) dans laquelle Conway parle de sa carrière et expose sa vision des mathématiques.

[7En effet, on date sa naissance mathématique « officielle » à 1901 avec la publication par le mathématicien Charles Leonard Bouton d’un article sur l’analyse et la résolution complète du jeu de Nim.

Partager cet article

Pour citer cet article :

Lisa Rougetet — «Des jeux aux nombres surréels» — Images des Mathématiques, CNRS, 2015

Crédits image :

Image à la une - Le logo illustre l’arbre des nombres de John Conway, créés jour après jour, représentant les nombres entiers, rationnels, dyadiques, réels, les ordinaux et les nombres surréels. Source : On Numbers and Games de John Conway, 1976.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM