Autour du théorème de Sprague-Grundy

Le développement de la théorie des jeux combinatoires au XXe siècle

Piste rouge Le 20 octobre 2016  - Ecrit par  Lisa Rougetet Voir les commentaires

Ce n’est vraiment qu’à partir de la fin du XIXe et du début du XXe siècle que la spécificité des jeux combinatoires est explicitée. Ils deviennent alors de véritables objets d’étude, nourrissant le développement d’une théorie mathématique consacrée à leur analyse. Le théorème de Sprague-Grundy, énoncé de manière indépendante en 1935 par Roland Sprague et en 1939 par Patrick Grundy, est un résultat fondamental de cette théorie.

Introduction

Entre 1976 et 1982 paraissent deux ouvrages fondamentaux dans le domaine de la théorie des jeux combinatoires : Winning Ways for Your Mathematical Plays, rédigé par les mathématiciens Elwyn Berlekamp (né en 1940), Richard Guy (né en 1916) et John Conway (né en 1937), et On Numbers and Games par John Conway. Ces trois hommes sont considérés comme les pères fondateurs de la théorie des jeux combinatoires et soulignent lors de la parution de leur ouvrage qu’à l’instar de l’analyse combinatoire, lentement et difficilement approuvée par grand nombre de « mathématiciens sérieux » (Berlekamp & al, 2001, p. xv), la considération des jeux combinatoires et de leur théorie s’est révélée encore plus laborieuse. L’analyse des jeux combinatoires telle qu’elle a été proposée par Berlekamp, Guy et Conway s’appuie sur une approche algébrique abstraite, dont des résultats de la théorie axiomatique des ensembles. Ces derniers, datant de la première moitié du XXe siècle, ont fourni les outils et les structures nécessaires à l’analyse complète des jeux combinatoires.

JPEG - 262 ko
Figure 1.
Premières de couverture des quatre volumes de la seconde édition (2001, 2003, 2003 et 2004).
JPEG - 23.6 ko
Figure 2.
Couverture de la seconde édition de l’ouvrage On Numbers and Games de Conway, parue en 2000.

Dans ces ouvrages, les auteurs proposent une définition des jeux combinatoires - qui correspond à celle utilisée actuellement - et en présentent leur analyse. Un jeu combinatoire oppose deux joueurs, jouant alternativement et à découvert (on dit que l’information est complète), il n’y a pas de hasard et le gagnant est souvent déterminé par le dernier coup, selon que le jeu est pratiqué en version normale (le dernier joueur pouvant jouer gagne) ou en version misère (le dernier joueur à jouer perd). Si le terme « combinatorial game » apparaît au début des années 1970 dans les ouvrages anglophones [1], puis est traduit en français vers la fin des années 1970 [2], d’autres expressions sont utilisées plus tôt, comme « jeu de combinaisons » par Édouard Lucas à la fin du XIXe [3].
De par l’absence de hasard et de l’alternance des coups entre les deux joueurs, il est possible, en théorie, de dénombrer toutes les positions pouvant se présenter dans une partie de jeu et envisager un chemin optimal qui mène à une position finale gagnante. Mais on comprend rapidement que le nombre de positions possibles dans un jeu est souvent considérablement élevé (près de $10^{120}$ aux Échecs par exemple), et que des méthodes d’analyse autre que le dénombrement s’avèrent nécessaires. L’idée principale de la théorie des jeux combinatoires est donc d’attribuer des valeurs aux différentes positions de jeu, et de travailler avec ces valeurs pour déterminer l’issue d’une partie (gagnante, perdante ou nulle) à partir de n’importe quelle position. Pour ce faire, deux étapes se succèdent : 1) réduire les jeux et leurs configurations à des formes canoniques facilement exploitables, 2) travailler avec des classes de jeux équivalents. Cette démarche, basée sur la résolution du jeu de Nim par Charles L. Bouton en 1901, est explicitée sous la forme d’un théorème énoncé indépendamment par Roland Sprague en 1935, puis par Patrick Grundy en 1939.

Première résolution complète d’un jeu combinatoire : Bouton et le jeu de Nim

Le jeu de Nim avant la résolution de Bouton

Avant la publication de l’article de Bouton, le jeu de Nim – dont l’appellation date également de 1901 – est traité dans des cas particuliers, notamment dans des ouvrages de récréations mathématiques à partir du XVIe siècle [4]. Par exemple, dans ses Problemes plaisans et delectables qui se font par les nombres de 1612, Claude-Gaspar Bachet de Méziriac propose le problème suivant (Bachet, 1612, p. 99-103) :

Si deux ont proposé entre eux, de dire chacun l’un après l’autre alternativement un nombre à plaisir, qui toutefois ne surpasse pas un certain nombre précis, pour voir ajoutant ensemble les nombres qu’ils diront qui arrivera plutôt à quelque nombre prescrit ; faire si bien qu’on arrive toujours le premier au nombre destiné.

Bachet considère le cas où deux personnes doivent atteindre 100 en additionnant des nombres compris entre 1 et 10. Il explique que pour « vaincre infailliblement », il faut ajouter 1 au nombre à ne pas dépasser, qui est 10 ici, et ôter continuellement 11 du nombre destiné 100. Il obtient les nombres 89, 78, 67, 56, 45, 34, 23, 12 et 1 qui sont ceux qu’il faut atteindre pour arriver le premier à 100. Ce problème proposé en version additive dans les mathématiques récréatives peut se traduire en version soustractive [5] : 100 jetons sont disposés sur une table et les joueurs, à tour de rôle, retirent entre 1 et 10 jetons, celui qui prend le(s) dernier(s) jeton(s) gagne. Cette configuration est aujourd’hui considérée comme un jeu de Nim simplifié, car il n’y a qu’un seul tas de jetons. La première résolution complète du jeu de Nim (avec plusieurs tas contenant un nombre quelconque de jetons) paraît dans le journal mathématique américain The Annals of Mathematics, rédigée par le mathématicien d’Harvard, Charles Leonard Bouton en 1901 (Bouton, 1901).

Biographie de Bouton

Charles Leonard Bouton est né le 25 avril 1869, et grandit à St. Louis, Mississipi, au sein d’une famille plutôt aisée. Il arrive à Harvard à partir de 1894 où il passe deux ans à la Graduate School et obtient à la fin de sa deuxième année une bourse pour étudier à l’étranger. À cette époque, l’activité mathématique américaine est fortement influencée par les théories allemandes, et de nombreux étudiants américains, attirés par de meilleures opportunités offertes dans les universités germaniques, partent à l’étranger étudier dans les branches mathématiques les plus avancées (Parshall & Rowe, 1994). Après l’obtention de son doctorat à Leipzig en 1898, période durant laquelle il travaille avec le norvégien Sophus Lie (1842-1899), Bouton retourne à Harvard et se consacre avec beaucoup de zèle à ses enseignements, cherchant toujours « à susciter l’intérêt des débutants en leur montrant un modèle ou un diagramme ou un exemple éclairant d’une nouvelle théorie [...] » (Osgood & al, 1922). Quand on regarde ses publications, essentiellement dans The Annals of Mathematics et Bulletin of the American Mathematical Society, il apparaît que l’article sur le jeu de Nim et sa résolution n’est pas vraiment en adéquation avec les thèmes abordés par Bouton dans ses autres articles, ni avec ses travaux mathématiques en général [6]. Par ailleurs, Bouton ne fait référence à aucun travail antérieur, ce qui rend assez difficile de trouver une explication à cette publication singulière. Nous pouvons néanmoins avancer une ou deux pistes : d’une part, le milieu académique américain au début du XXe siècle connaît une phase de réforme qui permet l’émergence de riches activités de recherche : nombreuses publications, création de communautés scientifiques professionnelles et spécialisées, mise en place de colloques ouverts à un large public, etc. (Parshall & Rowe, 1994, p. xvi). Le plein essor mathématique de ce début de XXe siècle constitue très certainement un terrain favorable à la parution d’articles sur des thèmes plus originaux comme celui que traite Bouton. D’autre part, la fin du XIXe siècle et le début du XXe voient un regain d’intérêt pour les mathématiques récréatives, à la fois aux États-Unis et en Europe. En France par exemple, ce retour est marqué par la volonté d’introduire de nouvelles pratiques pédagogiques, en abordant des notions mathématiques par des problèmes amusants et attractifs qui s’inscrivent dans l’histoire des mathématiques (Barbin & Guitart, 2016). On trouve trace de cet intérêt dans les productions de l’Association Française pour l’Avancement des Sciences créée en 1872 pour promouvoir la science auprès d’un large public, ainsi que dans la presse populaire de l’époque (Les Tablettes du chercheur par exemple) où une place importante est donnée aux jeux d’esprit et de combinaisons ainsi qu’aux récréations scientifiques [7].

Le travail de Bouton sur le jeu de Nim

L’article de Bouton présente le jeu de Nim et son analyse dans un cadre général, avec des données numériques quelconques, et non plus sur un exemple particulier comme ce fut le cas dans les récréations mathématiques. C’est pour cette raison que l’article de Bouton est considéré comme « fondateur » pour la théorie des jeux combinatoires.

Les règles du jeu de Nim sont les suivantes : on dispose sur une table trois rangées d’objets (des allumettes par exemple), chaque rangée comportant un nombre quelconque d’allumettes : par exemple 7, 5, 3, comme sur la figure ci-dessous. Les deux joueurs, à tour de rôle, sélectionnent une rangée et peuvent retirer autant d’allumettes qu’ils veulent (une, deux, trois… ou toute la rangée). Si la partie est jouée en version normale, le premier qui vide la table gagne [8]. Le jeu peut se pratiquer avec un nombre quelconque de rangées, chacune contenant un nombre quelconque d’allumettes.

PNG - 21.1 ko
Figure 3.
Configuration initiale possible du jeu de Nim de Bouton.

Le but de Bouton est de montrer qu’un joueur peut gagner la partie s’il laisse une certaine configuration de jeu à son adversaire et qu’il ne commet ensuite aucune erreur. Une telle configuration est appelée par Bouton « safe combination » (littéralement « combinaison sûre »). Il affirme être dans ce cas si la somme des nombres d’allumettes contenues dans chaque rangée transcrits en binaire, sans tenir compte des retenues, est nulle. Par exemple, dans la configuration initiale de la figure ci-dessus, on transcrit $7$, $5$ et $3$ en binaire, l’écriture de 7 en binaire est donc 111, celle de 5, 101 et celle de 3, 011. En additionnant ces trois nombres (en alignant bien les mêmes unités entre elles) modulo 2 sans retenue, on obtient $001$. Cette somme n’est pas nulle, donc la position 7, 5, 3 n’est pas une safe combination [9]. Pour qu’elle le devienne, il faudrait transformer un 1 en 0 dans la troisième colonne pour que la somme soit nulle. Cela se traduit par le fait d’enlever une allumette dans un des trois tas. Le joueur qui joue ce coup peut alors remporter la partie en continuant, à chacun de ses coups, d’enlever le nombre d’allumettes nécessaire pour que la somme soit nulle.
Dans le vocabulaire actuel de la théorie des jeux combinatoires, cette opération est appelée Nim-somme, ce qui montre l’importance qu’a le jeu de Nim dans la théorie.

Les contributions post-boutoniennes

La publication de Bouton suscite l’intérêt d’autres mathématiciens en Europe et aux États-Unis qui exposent à leur tour des variantes du jeu de Nim. En 1907, le mathématicien néerlandais Willem Abraham Wythoff (1865-1939), spécialiste de théorie des nombres, propose un Nim (Wythoff, 1907) - il s’inspire ouvertement de l’article de Bouton – dans lequel il n’y a que deux rangées d’objets et les joueurs peuvent retirer autant qu’ils veulent d’une rangée ou bien le même nombre dans les deux rangées.
En 1910, le mathématicien de l’université de Chicago Eliakim Hastings Moore (1862-1932) [10], présente le $Nim_k$ (lu « Nim indice k ») dans lequel il y a un nombre quelconque de rangées et les joueurs peuvent retirer d’une seule rangée ou dans un nombre quelconque, sans excéder k rangées (Moore, 1910) [11].
Notons que les publications de ces résultats se font dans des journaux spécialisés de mathématiques : Wythoff publie dans Nieuw Archif voor Wiskunde, journal de l’académie royale danoise de mathématiques et Moore dans The Annals of Mathematics. L’analyse du jeu de Nim et de ses variantes circule ainsi dans une sphère mathématique « professionnelle », permettant la découverte de liens théoriques avec d’autres jeux.

Vers le théorème de Sprague-Grundy

En 1910, le mathématicien allemand Wilhelm Ahrens (1872-1927) publie son ouvrage Mathematische Unterhaltungen und Spiele sur les jeux et divertissements mathématiques, dans lequel il agrémente le Nim de Bouton et sa théorie d’un jeu nommé Der Letzte gewinnt ! (Le dernier gagne !), qu’il avait initialement proposé sous forme d’exercice aux lecteurs du journal quotidien Danziger Zeitung en 1907 [12].

PNG - 42.4 ko
Figure 4.
Der letzte gewinnt ! dans (Ahrens, 1910, p. 80).

Une rangée de 9 cases, indicées de a à i supporte 3 pierres situées sur les cases d, f, et i. Les joueurs à tour de rôle déplacent une des pierres dans le sens de la flèche. Deux pierres peuvent occuper la même case et une pierre peut sauter par dessus une autre. Le joueur qui amène la dernière pierre sur la case a remporte la partie. Le lien avec le Nim de Bouton est le suivant : il suffit de voir les écarts entre les positions des pierres et la case a comme étant respectivement une rangée d’un jeu de Nim. Les trois positions forment une configuration d’un jeu de Nim à trois rangées, contenant chacune 3, 5 et 8 allumettes. On utilise alors les propriétés des safe combinations et le système binaire pour parvenir à la solution.

Par son analyse du jeu Der Letzte gewinnt !, Ahrens met en avant un aspect particulièrement important de la théorie des jeux combinatoires en montrant qu’un jeu, très éloigné du Nim dans sa forme, se ramène en réalité à une configuration particulière de celui-ci. C’est une des idées fondamentales du théorème de Sprague-Grundy. Par ailleurs, les travaux d’Emanuel Lasker constituent une autre source importante d’inspiration pour Sprague, qui le mentionne dans son article.

JPEG - 13.9 ko
Figure 5.
Le mathématicien et champion d’Échecs Emanuel Lasker.

Emanuel Lasker a été à la fois un mathématicien [13] et un joueur d’Échecs reconnu (il a gardé le titre de champion du monde pendant 27 ans). Il a joué un rôle important dans l’histoire de la construction de la future théorie des jeux combinatoires en rédigeant en 1931 un ouvrage intitulé Brettspiele der Völker (traduit par Jeux de tables de différents pays) dans lequel il analyse des Mathematische Kampfspiele (littéralement jeux de combat mathématiques), repris et approfondis par Sprague quelques années plus tard.

PNG - 233.7 ko
Figure 6.
Couverture du livre d’Emanuel Lasker, Brettspiele der Völker, 1931.

Dans cet ouvrage, Lasker présente l’analyse du Nim de Bouton, mais sans le citer explicitement (contrairement à Wythoff, Moore et Ahrens). Il qualifie l’inventeur du jeu, qui « a trouvé bon ton de préserver son incognito », de « génie ». Lasker envisage ensuite de déduire de ce jeu de Nimm [14] d’autres jeux pour lesquels les règles sont légèrement modifiées. À travers les diverses analyses qu’il en fait, Lasker introduit un vocabulaire qui sera propre à la future théorie des jeux combinatoires tel que position perdante (Verluststellung), position gagnante (Gewinnstellung). Il montre aussi pour chacun des jeux que l’ensemble des positions se divise toujours en un sous-ensemble de positions perdantes et un de positions gagnantes. Dans la terminologie de Lasker, une position est perdante si le prochain joueur à jouer ne dispose pas d’un coup le plaçant dans une situation de jeu favorable. La nature de la position qualifie la situation du joueur qui est sur le point de jouer, ce qui n’est pas le cas chez Bouton qui préconise de laisser à l’adversaire une safe combinaison (« combinaison sûre »). Ainsi, les Verluststellungen de Lasker sont les safe combinations de Bouton : tout dépend de la perspective adoptée, si l’on s’intéresse aux positions qu’on a jouées ou celles qu’on va jouer. Lasker définit également une position gagnante comme une position pour laquelle le joueur qui va jouer peut forcer la victoire [15].

La variante qui présente un intérêt majeur à notre histoire, à qui on donnera ultérieurement le nom de Lasker Nim [16], permet à Lasker de généraliser la détermination de la nature d’une position obtenue par regroupement de positions plus faciles à analyser et dont les natures sont déjà connues. Au Lasker Nim, il y a un nombre quelconque de tas sur la table, chacun contenant un nombre quelconque d’objets. Celui dont c’est le tour peut diviser n’importe quel tas en deux nouveaux tas distincts, ou bien le réduire, c’est-à-dire lui enlever un certain nombre d’objets. Par exemple à partir de la position 1, 2, 3, on peut séparer le tas de 2 en deux tas de 1 ; ou bien séparer le tas de 3 en un tas de 1 et un tas de 2, ou bien réduire un seul des trois tas, comme le montre la figure ci-dessous.

PNG - 419.8 ko
Figure 7.
Coups possibles au Lasker Nim à partir de la position 1, 2, 3.

Lasker cherche alors à déterminer un critère pour définir la nature d’une position qui se décomposerait en deux autres dont on connaît déjà la nature (perdante ou gagnante) [17]. Il constate que l’ajout d’une position perdante à n’importe quelle configuration ne change pas la nature de cette dernière. Par exemple, si 1, 2, 4 et 1, 3, 5 sont des positions perdantes, alors la position 1, 2, 4, 1, 3, 5 l’est également. De même, une position perdante ajoutée à une position gagnante donne à nouveau une position gagnante. Lasker fournit alors un tableau contenant les premières positions perdantes à trois tas au Lasker Nim, ce qui lui permet de déterminer la nature de positions contenant un nombre de tas plus élevé.

PNG - 422.6 ko
Figure 8.
Le tableau des positions perdantes au Lasker Nim (Lasker, 1931, p. 186).

Prenons par exemple la position 2, 3, 4, 5 dont on cherche à savoir si elle est gagnante ou perdante. Elle a la même nature que la position 1, 1, 2, 3, 4, 5, car l’ajout de la position perdante 1, 1 ne change pas la nature de la position initiale. Cette nouvelle position « agrandie » contient la position perdante 1, 2, 4 contenue dans le tableau. Elle peut donc être « omise », et la position initiale a ainsi la même nature que la position 1, 3, 5. Cette dernière étant une position perdante, on peut conclure que la position 2, 3, 4, 5 est perdante.

Il reste alors à considérer la situation où deux positions gagnantes forment une nouvelle position. Son intuition l’amène à penser que le Lasker Nim a « un lien de parenté avec le Nimm. [...] Les deux se jouent avec autant de tas que l’on veut, il est également valable pour les deux jeux que deux positions perdantes assemblées en produisent une nouvelle et que deux tas égaux forment une position perdante. Il me semble que la détermination de la nature de ces jeux est étroitement liée à celle du Nimm. » (Lasker, 1931, p. 186). Il introduit alors la notion d’équivalence entre deux groupes de tas (äquivalente Gruppen) : deux groupes sont équivalents si, dans chaque position perdante dans laquelle un groupe apparaît, on peut le remplacer par l’autre sans que cela ne change la nature de la position. Lasker en déduit que « deux groupes équivalents mis ensemble produisent une position perdante » (Lasker, 1931, p. 186). Ceci pose ensuite la question de l’existence de tas qui ne seraient pas équivalents à un groupe de tas plus petits, et qui seraient, en quelque sorte, les représentants des différentes classes d’équivalence. Lasker introduit alors des tas premiers (prim), les plus petits possibles, auxquels les autres sont équivalents. L’adjectif « premiers » est très certainement utilisé par analogie avec la décomposition d’un nombre entier en produit de facteurs premiers, les nombres premiers étant en quelque sorte les « plus petits possibles » pour n’admettre comme diviseurs que 1 et eux-mêmes. Plus généralement, on trouve dans l’analyse de Lasker de nombreuses analogies de vocabulaire avec l’arithmétique et l’algèbre commutative. Pour le Lasker Nim, les tas premiers sont : 1, 2, 3, 7, 15, 31… et n’importe quel tas est soit équivalent à un de ces tas, soit un groupe composé de ces tas. Par exemple, 4 est équivalent au groupe 1, 2, ou encore 5 est équivalent au groupe 1, 3. Ainsi, chaque configuration est exactement équivalente à une combinaison de tas premiers de taille différente (comme se décompose un nombre entier en produit de facteurs premiers), et il suffit ensuite de travailler avec cette combinaison de tas premiers comme dans le cas du jeu de Nim classique, avec la Nim-somme. Une formulation, actuelle et plus concise de ce raisonnement, est :

[…] une fois que sont déterminés tous les tas premiers d’une variante de Nim, le jeu peut être analysé comme le Nim standard :

  • tout d’abord chaque tas de la configuration est remplacé par des tas premiers équivalents,
  • une fois que cela est fait, on est en présence d’une configuration perdante seulement si chaque tas premier apparaît un nombre pair de fois. (Bewersdorff, 2005, p. 176)

Par exemple, au Lasker Nim, le tas 6 est équivalent au groupe des deux tas premiers 2, 3, donc la position 6 est perdante. La position 8 étant équivalente au groupe 1, 2, 3 sera gagnante.
Ce résultat n’est pas aussi explicite chez Lasker, qui travaille beaucoup « par tâtonnement » (Lasker, 1931, p. 186), même si cet ouvrage montre l’importance de l’étude successive de différents jeux de Nim pour l’analyse d’autres jeux combinatoires.

Par la suite, ces travaux sont lus et approfondis par le mathématicien allemand Roland Sprague (1894-1967) qui arrive en 1935 à la conclusion que « chaque jeu global apparaît comme un Nim généralisé » [18] (Sprague, 1935, p. 441). Pour cela, il introduit la notion de « rang »
d’une position :

Théorème I : pour chaque jeu fini, il peut être affecté aux positions un nombre entier non négatif, appelé « rang », tel que : A) aucune position n’a le même rang que ses descendantes, B) chaque position de rang $R>0$ possède au moins une descendante de rang $P$, avec $0\leq P < R$. (Sprague, 1935, pp. 439-440)

Le rang d’une position donnée est donc déterminé grâce aux rangs de ses descendantes (par la propriété A), le rang de la position finale étant 0 (par la propriété B). Si l’attribution des rangs à un niveau $n$ a été faite, alors le rang d’une position au niveau $n+1$ sera obtenu en prenant le plus petit des nombres 0, 1, 2,... qui manque parmi les rangs de ses descendantes. Par exemple, le rang d’une position dont les positions descendantes ont pour rangs 0, 1, 3, 4 sera 2. Cette méthode est à présent connue sous le nom de la règle du Mex (Minimum EXclu).
Sprague applique cette méthode sur un jeu composé de positions simples, chacune ayant un rang a, b, c... et remarque que : « le jeu global est donc essentiellement équivalent à un jeu avec des tas a, b, c... qu’on peut diminuer à chaque coup, n’importe lequel et à volonté, c’est-à-dire qu’il est équivalent au jeu de Nim » (Sprague, 1935, pp. 440-441). Par exemple, au Lasker Nim, la position ne contenant qu’un tas de 1 admet pour rang 1 (car son unique position descendante est 0 qui a pour rang 0), la position ne contenant qu’un tas de 2 admet pour rang 2 (voir figure) et la position ne contenant qu’un tas de 3 admet pour rang 4 (voir figure). La position 1, 2, 3 au Lasker Nim est donc équivalente à la position 0, 2, 4, soit 2, 4, au Nim classique. La Nim-somme n’est pas nulle (elle est égale à $110$), donc la position 1, 2, 3 n’est pas une position perdante (on ne la retrouve d’ailleurs pas dans le tableau de Lasker).

PNG - 18.2 ko
Figure 9.
Détermination de la valeur du rang de la position ne contenant qu’un tas de 2 objets au Lasker Nim en fonction du rang de ses descendantes.
PNG - 26.8 ko
Figure 10.
Determination du rang de la position ne contenant qu’un tas de 3 objets au Lasker Nim en fonction des rangs de ses descendantes.

Le britannique Patrick Grundy (1917-1959) retrouve ce résultat indépendamment (Grundy, 1939) en 1939 en introduisant les nombres maintenant appelés « de Grundy » (les nombres de Grundy ou Nimbers correspondent aux rangs chez Sprague) [19]. La principale contribution de ces deux hommes, au delà du travail de Lasker, a été de trouver une connexion entre les versions généralisées et la version standard du jeu de Nim. En effet, les variations de Nim affectent plus l’apparence du jeu pour les joueurs que la substance mathématique sous-jacente.

Le théorème de Sprague-Grundy est redécouvert par les mathématiciens Richard Guy et Cedric Smith dans un article qui paraît en 1955 (Guy & Smith, 1955). Cet article, qui présente l’analyse complète ainsi que des conditions de classification des jeux octaux [20], permet la rencontre en 1966 entre Richard Guy et Elwyn Berlekamp lors d’une conférence en analyse combinatoire.
De cette rencontre émerge l’idée d’une collaboration sur l’écriture d’un ouvrage sur les jeux, à laquelle se joint John Conway qui connaît déjà par ailleurs Richard Guy. À l’issue de quinze années de collaboration (1966-1982) entre les hommes est publiée la description des nombreux jeux mathématiques et de leur analyse : Winning Ways for Your Mathematical Plays. Le résultat final est un livre très complet, mêlant théorie et pratique, et regorgeant d’illustrations et de calembours – dont Conway est très friand. Le point central de Winning Ways est la mise en place d’une méthode pour assigner une valeur à un jeu ou à une position de jeu en utilisant les nombres de Grundy. Les auteurs pensent qu’il y a trop de « mathématiques sérieuses » pour considérer Winning Ways comme un livre de mathématiques récréatives, « mais il vous transporte aux frontières de la recherche en théorie des jeux combinatoires, et les nombreux problèmes non résolus stimuleront les découvertes futures. » (Berlekamp & al, 2003, p. xviii).

Conclusion

La théorie des jeux combinatoires est une discipline mathématique « jeune » : même si l’analyse de jeux mathématiques et de problèmes récréatifs n’est pas récente, son développement se concentre essentiellement durant le XXe siècle. L’histoire de cette théorie débute, comme le dirait Lasker, par « tâtonnement », avec l’article de Bouton qui introduit le jeu de Nim et sa résolution, puis grâce aux apports successifs de Wythoff (variante du Nim), Moore (généralisation avec le $Nim_k$), et Ahrens. Peu à peu, une problématique se dégage de ces contributions sporadiques quand Lasker, puis Sprague, envisagent de résoudre des variantes du jeu de Nim en les ramenant à une configuration particulière de ce dernier. La redécouverte du théorème de Sprague-Grundy en 1955 par Guy et Smith avec la classification des jeux octaux, puis la collaboration des trois pères fondateurs permettent de considérer les jeux combinatoires comme de véritables objets mathématiques sur lesquels une théorie se construit.

Références bibliographiques

Ahrens, Wilhelm, 1910. Mathematische Unterhaltungen und Spiele, Leipzig, Berlin : Verlag Von B.G. Teubner, 3ème édition, 1921.

Bachet de Méziriac, Claude Gaspar, 1612. Problèmes plaisants et délectables qui se font par les nombres. Lyon, Pierre Rigaud. Consulter en ligne.

Barbin, Évelyne et Guitard, René, 2016. « Des récréations pour enseigner les mathématiques avec Lucas, Fourrey, Laisant », in Radford, L., Furinghetti, F., & Hausberger, T. (dir.), 2016, Proceedings of the 2016 ICME Satellite Meeting of the International Study Group on the Relations Between the History and Pedagogy of Mathematics, Montpellier, IREM de Montpellier.

Barbin, Évelyne, Goldstein, Catherine, Moyon, Marc, Schwer, Sylviane et Vinatier, Stéphane (dir.), À paraître en 2017, Les travaux combinatoires en France (1870-1914) et leur actualité : un hommage à Henri Delannoy. Limoges, PULIM.

Berlekamp, Elwyn, Conway, John et Guy, Richard, 2001. Winning Ways for Your Mathematical Plays. Vol. 1, 2nd Edition, Wellesley (Massachusetts), A K Peters. La première édition en deux volumes date de 1982.

Berlekamp Elwyn et Conway John et Guy Richard, 2003. Winning Ways for Your Mathematical Plays. Vol. 3, 2nd Edition, Wellesley (Massachusetts), A K Peters.

[↑a et b] Bewersdorff Jörg, 2005. Luck, Logic, and White Lies The Mathematics of Games, Traduit par David Kramer, Wellesley (Massachusetts), A K Peters.

Bouton, Charles L., 1901. « Nim, A Game with a Complete Mathematical Theory », The Annals of Mathematics, vol. 3, n°1/4, p. 35-39. Voir en ligne.

Conway, John, 1976. On Numbers and Games. Londres, Academic Press Inc..

Fourrey, Émile, 1899. Récréations arithmétiques. Paris, Nony. Consulter en ligne.

Grundy, Patrick, 1939. « Mathematics and Games », Eureka, vol. 2, p. 6-8. Consulter en ligne.

Guy, Richard and Smith, Cedric, 1955. « The G-Values of Various Games », Proceedings of the Cambridge Philosophical Society, vol. 52, n°3, p. 514-526.

[↑a et b] Emanuel Lasker, 1931. Brettspiele der Völker. Berlin, August Scherl.

Lucas, Édouard, 1883. Récréations mathématiques, Tome 2. Paris, Gauthier-Villars, 1883, 2e édition : 1896. Consulter en ligne.

[↑a et b] Moore, Eliakim H., 1910. « A Generalization of the Game Called Nim », The Annals of Mathematics, vol. 11, n°3, p. 93-94.

Osgood, William, Coolidge, Julian and Chase, George, 1922. « Charles Leonard Bouton (in memoriam). A Minute read before the Faculty of Harvard University », Bulletin of the American Mathematical Society, vol. 28, p. 123-124.

[↑a et b] Parshall, Karen et Rowe, David, 1994. The Emergence of the American Mathematical Research Community, 1876-1900 : J. J. Sylvester, Felix Klein, and E. H. Moore. Providence/London, AMS/LMS.

Sprague, Roland, 1935. « Über mathematische Kampfspiele », Tohoku Mathematical Journal, vol. 41, p. 438-444.

Wythoff, Willem. 1907. « A Modification of the Game of Nim », Nieuw Archief voor Wiskunde, vol. 7 (2), p. 199-202.

Post-scriptum :

Je remercie vivement Jenny Boucard et Marc Moyon pour leurs diverses relectures, leurs conseils et leur patience, ainsi que les re-relecteurs Emmanuel Beffara, TheBarber, alainfa et un anonyme.

Article édité par Jenny Boucard

Notes

[1Ainsi que le terme « combinatorial game theory » qui apparaît par exemple en 1975 dans le vingt-deuxième volume des Notices of the American Mathematical Society, introduit par Richard Guy.

[2Par exemple, le volume 28 du Bulletin de la Société mathématique de Belgique de 1976 décrit et évalue des « jeux combinatoires (comme le jeu d’échecs entre autres) ».

[3Dans le deuxième tome des Récréations mathématiques, Lucas définit les « jeux de combinaison » comme des jeux ne dépendant pas du hasard, « mais seulement du nombre et de la position » (Lucas, 1883, p. 76).

[4Sur le rôle des récréations mathématiques dans l’histoire, nous renvoyons au dossier spécial Historia Mathematica de 2014, Volume 41, Issue 4.

[5Par exemple, Émile Fourrey, après avoir présenté la version additive, propose une modification en considérant 17 allumettes, chacun des joueurs pouvant en retirer au maximum trois (Fourrey, 1899, p. 48-49).

[6Ses travaux sont davantage portés sur les transformations en géométrie et sur les applications des groupes de transformations aux équations différentielles.

[7Voir à ce sujet le colloque qui s’est tenu à Guéret en octobre 2015, dont les actes paraîtront en 2017 (Barbin & al, 2017).

[8Dans son article, Bouton analyse également le jeu en version misère. Elle n’est pas présentée dans le présent article, mais découle de l’analyse de la version normale.

[9Bouton n’explique pas comment il obtient ce critère pour déterminer si une position est une safe combination ou non. Eric Duchêne, chercheur en théorie des jeux combinatoires, explique que l’idée d’introduire le binaire vient de la remarque suivante : quand on regarde deux rangées, notées a et b, composées chacune de 1 et 1, il existe une unique possibilité pour la troisième rangée c pour que la position (a, b, c) soit une safe combination. Il en est de même quels que soient les nombres dans les rangées a et b. Bouton n’explique pas cela, et je remercie vivement Eric pour cette explication.

[10Moore fut très engagé dans la mise en place d’un cadre institutionnel permettant aux professeurs de pousser les étudiants à un niveau avancé tout en poursuivant leurs propres objectifs de recherche.

[11Le $Nim_k$ de Moore est une généralisation du Nim de Bouton, qui serait alors le $Nim_1$.

[12Ahrens a rédigé la colonne Heimat und Welt, Mittwochs Unterhaltungsbeilage pour huit numéros du journal, entre le 23 janvier et 18 mars 1907.

[13En 1900, Lasker présente une thèse en algèbre commutative, dirigé par Max Noether. En 1905, il introduit la notion d’idéal premier et prouve le théorème de décomposition des idéaux des anneaux de polynômes. Ces travaux sont notamment repris par Emmy Noether (1882-1935). En 1933, quand Hitler accède au pouvoir, Lasker et sa femme se voient obligés de fuir l’Allemagne, et s’exilent à Moscou, où Lasker devient membre de l’Académie des Sciences et redonne des cours de mathématiques (il a alors plus de 60 ans). En 1937, ils quittent la Russie pour les États-Unis où ils décéderont tous les deux.

[14Lasker écrit Nimm. Cette écriture est d’autant plus justifiée que nimm est l’impératif du verbe allemand nehmen qui signifie prendre. Alors que nim n’a aucune signification en anglais.

[15On ne trouve pas de définition équivalente chez Bouton. En revanche, Moore (1910) introduit – en plus de la notion de safe combination – celle de unsafe combination, qui correspondrait aux Gewinnstellungen de Lasker.

[16C’est Jörg Bewersdorff qui attribue cette variante de Nim à Lasker et lui donne le nom de Lasker Nim (Bewersdorff, 2005, p. 174).

[17Par exemple, la position 1, 1, 2, 3, 4 peut se décomposer en deux positions « disjointes » 1, 2 et 1, 3, 4.

[18Par « jeu global », Sprague entend un jeu considéré dans son intégralité, avant qu’il ne soit décomposé en différentes configurations dont on connaît la nature. Son résultat s’applique aux jeux combinatoires dont les coups possibles sont les mêmes pour les deux joueurs (on les appelle des jeux impartiaux), comme le jeu de Nim (mais pas les Dames ou les Échecs par exemple).

[19Sprague publie son article en allemand dans un journal japonais, Tohoku Mathematical Journal, et Grundy dans un magazine destiné à des étudiants de premier cycle universitaire, Eureka, par conséquent à large diffusion. Le contexte historique explique pourquoi Grundy n’a pas eu connaissance de l’article de Sprague, l’accès aux périodiques tel le Tohoku Mathematical Journal devenant de plus en plus difficile dans le monde occidental.

[20Un jeu octal est un jeu combinatoire impartial (quand les coups ne dépendent que de la position) dont les règles autorisent de retirer des objets d’un tas ou de scinder ce même tas en deux. Le Lasker Nim, par exemple, est un jeu octal.

Partager cet article

Pour citer cet article :

Lisa Rougetet — «Autour du théorème de Sprague-Grundy» — Images des Mathématiques, CNRS, 2016

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