Titre de l’article publié en 1901

par Charles L. Bouton dans le journal The Annals of Mathematics.

Il est difficile de dater la première apparition d’un jeu, surtout quand celui-ci peut se jouer avec des objets quelconques (des pièces, des allumettes, des cailloux, des jetons, des crottes de chèvre…) et sur n’importe quel support (une table, dans le métro ou à même le sol). C’est le cas pour le jeu de Nim dont on date l’origine en 1901, seulement parce que c’est la première fois qu’il est appelé de la sorte dans un article qui expose sa résolution complète, rédigé par le mathématicien d’Harvard Charles Leonard Bouton (1869 – 1922). Le nom « Nim » suscitera quelques interrogations – certains y verront une origine chinoise – et l’explication la plus probable serait que le mot nim vienne de l’impératif du verbe allemand nehmen (qui signifie prendre) : nimm. Bouton a effectivement passé quelques années à Leipzig où il a obtenu son doctorat. Voici donc la description qu’il donne du jeu de Nim : deux joueurs A et B s’opposent autour d’une table sur laquelle sont placés trois tas d’objets, disons des jetons. Le nombre de jetons contenus dans chaque tas est arbitraire et diffère au début du jeu. Le joueur dont c’est le tour sélectionne un des tas et retire autant de jetons qu’il veut : un, deux,…, ou le tas en entier. La règle essentielle à respecter est que les jetons ne sont ôtés que d’un seul tas, et au moins un jeton doit être retiré. Bouton se place dans la version normale du jeu, celle où le joueur prenant le (ou les) dernier(s) jeton(s) gagne la partie [2].

La solution – comprenez « la stratégie pour gagner à chaque fois » – au jeu de Nim repose, d’une part, sur les propriétés des positions gagnantes et perdantes que nous allons définir dans un instant et, d’autre part, sur l’utilisation du système binaire. On définit ici une position gagnante comme étant une position qui présente une stratégie gagnante pour le joueur qui vient de jouer. Une position sera dite perdante si elle ne présente pas de stratégie gagnante au joueur qui vient de la jouer. (On trouve aussi dans la littérature les définitions inversées, tout dépend du point de vue qu’on adopte : celui du joueur qui a joué ou celui qui va jouer). Les positions gagnantes et perdantes présentent des propriétés très intéressantes qui permettent de comprendre la résolution du jeu de Nim et des jeux combinatoires en général :

1. Si le joueur A laisse une position gagnante sur la table, B ne pourra pas laisser de position gagnante.
2. Si le joueur A laisse une position gagnante sur la table, et que B diminue un des tas, A pourra toujours diminuer un des deux autres tas et laisser une position gagnante.

Pour résumer : d’une position gagnante, on ne peut atteindre qu’une position perdante, mais d’une position perdante, il est possible d’atteindre une position gagnante. Ce résultat peut se représenter par l’arbre ci-dessous :

Arbre représentant les propriétés des positions gagnantes et perdantes

Le joueur confronté à une position gagnante G n’aura pas d’autre possibilité que de laisser une position perdante P à son adversaire qui lui, en revanche, pourra atteindre une nouvelle position gagnante G.

Ainsi, le joueur qui se place dans une position gagnante peut y rester tout au long de la partie et la remporter, quoi que joue son adversaire et à condition de ne pas commettre d’erreur. (D’où la fameuse réplique d’un des personnages du film d’Alain Resnais de 1961 L’Année dernière à Marienbad : « Je peux perdre. Mais je gagne toujours. » [3]).

Maintenant, le tout est de savoir comment déterminer si une position est gagnante ou perdante. C’est là que le système binaire intervient. Nous caractérisons une position par un triplet dont chaque composante indique le nombre de jetons restant dans un tas, par exemple (9, 5, 12). Pour savoir si (9, 5, 12) est une position gagnante, on transcrit dans un premier temps toutes les composantes dans le système binaire. On obtient 1001, 101 et 1100. Ensuite, on pose l’addition de ces trois nombres, en respectant l’alignement des colonnes de la même unité. Puis, on additionne les chiffres de chaque colonne et on prend le résultat modulo 2 (on ne tient pas compte des retenues). Voilà ce qu’on obtient pour la position (9, 5, 12) :

Quand les sommes de chacune des colonnes se ramènent toutes à 0, alors les trois tas forment une position gagnante, sinon, si il y a un 1 en résultat d’une des colonnes, ou plusieurs, la position est perdante. Dans notre exemple, (9, 5, 12) est donc une position gagnante. Le joueur qui joue vers cette position prend alors l’avantage. Les propriétés des positions gagnantes et perdantes s’expliquent maintenant plus facilement avec le système binaire : en effet, quel que soit le tas choisi par B après que A ait laissé une position gagnante, et quel que soit le nombre de jetons qu’il retire, une des composantes du nombre binaire correspondant verra un de ses 1 changé en 0, et non l’inverse. (En effet, un 0 changé en 1 signifierait un accroissement du nombre de jetons dans le tas correspondant.) Il suffit alors à A de repérer dans quelle colonne a eu lieu un tel changement et de prendre le nombre de jetons adéquat pour rétablir un 0 à la place de ce 1. Il en résulte qu’en présence de deux joueurs qui connaissent la stratégie, le premier perd ou gagne selon la qualité de la position de départ.

L’addition des tas transcrits en binaire présentée ci-dessus est maintenant couramment appelée Nim-somme ou Nim-addition dans le vocabulaire de la théorie des jeux combinatoires, c’est dire la place importante qu’occupent le jeu de Nim et le travail d’analyse de Bouton dans le développement de la théorie !

On conçoit tout à fait que cette approche du jeu de Nim par le système binaire ne soit pas adaptée à des élèves de cycle 4, mais elle permet aux enseignants qui voudraient l’introduire et le pratiquer en classe de mieux comprendre les qualités intrinsèques de ce jeu et de sa résolution. Nous pensons néanmoins qu’il est possible de « faire sentir » aux élèves les propriétés des positions gagnantes et perdantes et de réussir à en déterminer les plus simples. Après quelques parties jouées, les élèves se rendent vite compte que laisser la position (1, 1) à leur adversaire leur permet de gagner la partie, mais qu’en revanche la position (1, 1, 1) les fait perdre. En poussant un peu plus loin, on trouve que la position (2, 2) est une position gagnante, et plus généralement toute position de la forme (n, n), car il suffit de retirer du tas que l’adversaire n’a pas touché le même nombre de jetons que lui a retiré, et rétablir ainsi l’équilibre entre les deux tas. Au delà de cet aspect, la pratique du jeu de Nim tel qu’il est présenté par Bouton reste un bon entraînement au calcul mental et développe des capacités d’abstraction (imaginer ce que l’adversaire va jouer pour mieux le contrer). En classes de collège, il sera sûrement plus judicieux de se tourner vers des jeux de Nim plus simples, parfois appelés jeux de soustraction [4], et qui se trouvent être les ancêtres du jeu de Nim, car bien antérieurs à ce dernier.

retour en début de partie
retour au début de l’article

Problème arithmétique XIX

proposé par Claude-Gaspard Bachet (https://fr.wikipedia.org/wiki/Claude-
Gaspard_Bachet_de_Méziriac) dans son ouvrage de 1612, Problemes plaisans et delectables, qui se font par les nombres.

Les jeux auxquels nous allons nous intéresser maintenant sont considérés comme les ancêtres du jeu de Nim, dans la mesure où ce sont des configurations particulières où il n’y a qu’un seul tas d’objets. Cependant, les toutes premières occurrences ne présentent pas le jeu avec des objets qu’on retire, ni même ne présentent un jeu d’ailleurs... En effet, on les retrouve dans le cadre des récréations mathématiques au début du 16^e siècle puis aux siècles suivants, notamment dans les problèmes dits « arithmétiques ». Contrairement à ce que leur nom pourrait suggérer, les problèmes arithmétiques ne sont pas destinés à faire travailler individuellement le lecteur sur une notion mathématique particulière. Leur pratique n’est pas solitaire et s’apparente davantage à résoudre mystérieusement et spectaculairement une difficulté devant une assistance pour qui la solution paraît introuvable. La forme problématique donnée aux récréations permet, d’une part, d’exciter la curiosité (aspect ingénieux), et d’autre part, de satisfaire le désir de savoir (aspect plaisant). N’est-ce-pas là tout l’intérêt de développer une véritable culture ludico-mathématique ?

Donc, dans les premières récréations [5] (Luca Pacioli en 1508 puis Claude-Gaspard Bachet en 1612), le jeu est présenté de manière plus abstraite : on propose à deux personnes d’atteindre un nombre $n$ fixé à l’avance en additionnant à tour de rôle des chiffres compris entre 1 et $k$, $k$ étant également fixé à l’avance. Le premier joueur qui atteint $n$ remporte la partie.

Cette version additive est équivalente dans sa résolution à un jeu de Nim à un seul tas, duquel on ne peut retirer plus qu’un certain nombre de jetons (version soustractive). Cette variante du jeu de Nim se prête beaucoup mieux à une activité au niveau collège, surtout pour le codage, un tas étant représenté par un nombre, ce qui enlève beaucoup de difficultés de représentations de données. Par ailleurs, elle permet un entraînement ludique au calcul mental nécessitant peu de moyens. L’intérêt de cette récréation est qu’elle présente – tout comme le Nim de Bouton – une stratégie gagnante : il existe des positions gagnantes qui, à condition de bien jouer pour les atteindre, permettent de gagner à chaque fois, quoi que joue l’adversaire. Voyons comment les déterminer, intuitivement d’une part, avec l’exemple ci-dessus, puis dans le cas général.

Intuitivement :

Pour résoudre la version additive, il faut raisonner « en partant de la fin », on dit qu’on fait un raisonnement rétrograde : si je ne veux pas que mon adversaire gagne en atteignant 30, je dois lui proposer le plus grand nombre tel qu’en lui ajoutant 1, 2, 3, 4, 5 ou 6 il ne puisse atteindre 30. Ce nombre est 23, car quel que soit le nombre qu’il ajoute à 23, il obtiendra un nombre supérieur ou égal à 24, mais inférieur ou égal à 29. Je pourrai alors compléter la somme jusqu’à 30 au tour suivant. En raisonnant de la même façon avec 23 – qui est donc une position gagnante – on trouve que la position gagnante précédente est 16, puis 9, puis 2. Ainsi, si je m’arrange pour atteindre le premier une de ces positions, puis les suivantes, j’arriverai à 30 le premier.

Cas général :

La première position gagnante à atteindre est celle obtenue après avoir enlevé un certain nombre de fois $k +1$ , jusqu’à ce qu’on ne puisse plus le faire. Cela revient à déterminer le reste de la division euclidienne de $n$ par $k +1$. Si ce reste est nul, la première position gagnante est $k +1$ elle-même (dans ce cas, il vaut mieux laisser commencer son adversaire), sinon c’est le reste (et dans ce cas, il est préférable de commencer pour atteindre dès le début une position gagnante).

Cette variante du jeu de Nim peut se pratiquer avec différentes valeurs pour $n$ et $k$. Pacioli, le premier chez qui on trouve cette récréation, la propose avec $n=30$ et $k =6$. Bachet la reprend en prenant pour valeurs $n=100$ et $k =10$ , et c’est la configuration qui sera la plus largement répandue dans les ouvrages de récréations mathématiques aux siècles suivants – très certainement parce que le genre des récréations mathématiques évolue peu du début du 17^e siècle à la fin du 18^e siècle, et qu’il se réduit pour l’essentiel à une collection de problèmes déjà publiés. Mais, libre à chacun de choisir ses propres valeurs, d’où l’intérêt d’utiliser des simulateurs aléatoires dans ce type de jeux pour générer des nombres différents à chaque partie.

L’article de Bouton, publié dans The Annals of Mathematics, n’est pas passé inaperçu, et peu de temps après sa publication, d’autres mathématiciens s’y intéressent en apportant de légères modifications dans les règles initiales, ce qui aboutit à de nouvelles résolutions. Voyons le cas du Nim de Wythoff, également appelé le Wythoff’s Queens.

retour en début de partie
retour au début de l’article

Cette variante du Nim de Bouton est due au mathématicien néerlandais Willem Abraham Wythoff (1865 – 1939) qui publie un article en 1907 pour la revue Nieuw Archief voor Wiskunde. Les règles du jeu sont les suivantes : deux joueurs ont face à eux deux piles contenant chacune un nombre arbitraire de jetons. Les joueurs prennent alternativement un nombre de jetons dans une des deux piles OU prennent le même nombre de jetons dans les deux tas. Le gagnant est celui qui prend le (ou les) dernier(s) jeton(s). Nous travaillerons sur la version analogue au Nim de Wythoff, appelée Wythoff’s Queens, car elle permet une représentation visuelle plus parlante.

Dans le Wythoff’s Queens, une reine est placée n’importe où sur un plateau de jeu quadrillé, et l’objectif pour les deux joueurs est de l’amener sur la case en bas à gauche. Le premier qui y arrive remporte la partie. La reine ne peut être déplacée que vers l’ouest (à l’horizontale), vers le sud (à la verticale) ou vers le sud-ouest (en diagonale) d’autant de cases voulues, comme le montre la figure ci-dessous :

Déplacements possibles de la reine dans le jeu du Wythoff’s Queens.

La reine se déplace vers l’ouest, vers le sud ou en diagonale vers le sud-ouest.

Les coordonnées de la reine sur le plateau de jeu correspondent aux deux tas de jetons dans le Nim de Wythoff ; quand on retire des jetons d’un seul tas, la reine se déplace horizontalement ou verticalement, et quand on retire un même nombre de jetons des deux tas, la reine se déplace diagonalement. On vous propose de jouer au jeu de Wythoff à cette adresse :

http://irem.univ-reunion.fr/spip.php?article857

La résolution de ce jeu est également basée sur les propriétés des postions gagnantes et perdantes, qu’il est facile de représenter sur le plateau quadrillé. Une fois de plus, on raisonne en partant de la fin par le raisonnement rétrograde suivant : la position finale gagnante à atteindre est la case de coordonnés (0,0), représentée en rouge sur la figure ci-dessous. Si je ne veux pas que mon adversaire l’atteigne, je ne dois pas placer la reine sur les lignes horizontale, verticale et diagonale qui mènent directement à cette case (elles sont représentées en bleu sur la figure ci-dessous).

Positions perdantes et but à atteindre

La case rouge est la position gagnante finale à atteindre. Les cases bleues sont les positions perdantes sur lesquelles je ne dois pas placer la reine, au risque que mon adversaire la mène sur la case (0,0) et gagne.

Les positions gagnantes suivantes apparaissent automatiquement comme étant les cases (2,1) et (1,2), représentées en rouge sur la figure ci-dessous (il y a bien sûr une symétrie des positions gagnantes de part et d’autre de la droite y=x ). En menant le même raisonnement, pour éviter que mon adversaire n’atteigne une de ces positions, je ne dois pas le laisser sur une des lignes représentées en bleu clair sur la figure ci-dessous :

Positions perdantes et gagnantes

En rouge les positions gagnantes, en bleu foncé les positions perdantes qui mènent à (0,0), en bleu clair les positions perdantes qui mènent à (1,2) et (2,1).

En travaillant ainsi itérativement, on trouve que les positions gagnantes sont (0,0), (1,2), (3,5), (4,7), (6,10), etc. ainsi que leur symétrique. Pour la suite de la résolution, on ne considérera que les positions où l’abscisse de la coordonnée est inférieure à l’ordonnée. Si on assigne un rang $n$ à chaque position, on peut représenter les positions gagnantes dans un tableau :

Une fois déterminées les premières positions gagnantes, on peut remarquer les choses suivantes :

• l’ordonnée $y$ se trouve en additionnant à l’abscisse $x$ la valeur du rang de la position. Ex : au rang 3, l’ordonnée de la position vaut $7 = 4 + 3$.
• l’abscisse $x$ d’un rang correspond au plus petit nombre qui n’apparaît pas dans les coordonnées des rangs précédents. Ex : l’abscisse au rang 3 est égale à 4, et 4 est le plus petit entier qui n’apparaît pas dans la liste {0,1,2,3,5}.

On peut alors définir les coordonnées des positions gagnantes suivantes par récursivité. Pour aller plus loin, et pour trouver une position gagnante sans avoir à calculer les précédentes, voici la méthode expliquée par Wythoff qui fait appel au nombre d’or, $\varphi=\dfrac{1+\sqrt{5}}{2}$, ainsi qu’à la fonction partie entière, $\left[x\right] = \max_{n \in \mathbf{Z}}\left\lbrace n ; n\leqslant x \right\rbrace$. Wythoff montre dans son article de 1907 que les coordonnées des positions gagnantes au rang $n$ se génèrent grâce aux formules suivantes : $\left[\varphi\times n \right]$ pour l’abscisse $x$ et $\left[\varphi\times n \right]+n$ pour l’ordonnée $y$. On retrouve ainsi les mêmes valeurs que trouvées précédemment par récursivité :

Le Wythoff’s Queens est analysé dans des ouvrages mathématiques traitant de la théorie des graphes et de ses applications, par Claude Berge ou Rufus Isaacs dans les années 1960 notamment. On trouve également des variantes à ce jeu en modifiant les déplacements de la reine sur le plateau selon ses coordonnées. La version sur plateau permet une meilleure visualisation de ce qui se passe dans le jeu – pour anticiper les coups de son adversaire – ainsi qu’une meilleure compréhension de comment obtenir les positions gagnantes. L’explication avec le nombre d’or est évidemment plus difficile à mettre en place, et même Wythoff se garde bien d’expliquer comment il a trouvé cette solution ! Toujours est-il que le jeu de Wythoff fut d’un intérêt considérable pour l’étude des séquences complémentaires.

Notons que le cadre dans lequel est ré-exploité le Nim de Bouton et sa résolution de 1901 est différent de celui des récréations mathématiques que nous avons abordé au début de l’article. Dans ce nouveau contexte, le jeu n’est plus pratiqué à des fins purement ludiques et pédagogiques, il devient plutôt un prétexte pour présenter un résultat mathématique. Restent publiés néanmoins des ouvrages de récréations mathématiques dans lesquels on trouve d’autres variantes du jeu de Nim. C’est le cas par exemple du Der Letzte gewinnt ! (Le dernier gagne ! en allemand) présenté par Wilhelm Ahrens en 1910.

retour en début de partie
retour au début de l’article

Illustration du jeu : Der Letzte gewinnt !

Rangée de 9 cases supportant 3 pierres situées sur les cases d, f et i.

Dans la configuration de jeu présentée ci-dessus, deux joueurs choisissent alternativement une des trois pierres et la déplacent d’autant de cases voulues, seulement dans le sens de la flèche, c’est-à-dire de la droite vers la gauche. La pierre choisie peut être amenée sur une case déjà occupée, ou bien sauter par dessus une autre pierre. Le joueur qui amène la dernière pierre sur la case a remporte la partie. Comment être sûr de gagner à chaque fois ? Vous commencez à comprendre l’astuce ? Les pierres situées sur les cases d, f, et i sont respectivement à une distance de 3, 5 et 8 cases de a. Ainsi, une autre façon de voir ce jeu est de considérer que c’est le Nim de Bouton avec 3 tas contenant respectivement 3, 5 et 8 jetons. Il suffit alors de raisonner comme précédemment avec le système binaire et la Nim-somme.

De tels jeux, qui dans la forme sont assez éloignés du jeu de Nim mais qui se ramènent en réalité à une configuration particulière de celui-ci, sont actuellement appelés des NimIn (pour NimIncognito !). Le jeu ouest africain recensé en 1955 par Charles Béart, le Tiouk-Tiouk, que nous allons présenter dans un instant, en est un.

retour en début de partie
retour au début de l’article

Le Tiouk-Tiouk se pratique sur une grille quadrillée carrée, qui peut parfaitement se dessiner dans le sable par exemple, comprenant 6, 8, 10 ou 12 rangées (il faut un nombre pair de rangées). Sur la première rangée on dispose des graines, une graine par case, et sur la dernière on dispose des bâtonnets, également un par case. Le premier joueur, N, se voit attribuer les graines et le second, S, les bâtonnets, comme le montre la figure ci-dessous :

Position initiale

Tiouk-Tiouk sur une grille $10\times 10$

Chaque joueur, à tour de rôle, peut déplacer un de ses pions dans une colonne en avant ou en arrière, d’autant de cases voulues, mais sans sauter par-dessus le pion du partenaire. Le joueur qui arrive à bloquer tous les pions de l’autre remporte la partie. Du fait que l’on puisse aussi bien avancer que reculer ses pions, le Tiouk-Tiouk paraît plus difficile dans sa résolution, mais il n’en est rien. Il suffit de « traduire » la grille en un jeu de Nim comportant 6, 8, 10 ou 12 tas (qui correspond au nombre de colonnes dans la grille) contenant chacun le même nombre de jetons 4, 6, 8 ou 10 (qui correspond à l’écart initial entre chaque graine et chaque bâtonnet sur une même colonne). À cause de la parité, la configuration initiale est une position gagnante – car la Nim-somme d’un même nombre effectuée un nombre pair de fois est égale à 0. Il est donc préférable de laisser son adversaire commencer la partie et de jouer en symétrique dans une autre colonne que celle dans laquelle il a joué.

Les jeux que nous venons d’exposer, le Nim et ses variantes, ont pour intérêt de présenter une stratégie gagnante. Donc, correctement programmées, des machines peuvent être conçues pour se confronter à l’homme. Ce fut le cas quand les techniques ont été suffisamment développées pour fournir les matériaux adéquats à la création d’automates et de machines, puis d’ordinateurs, capables de jouer à ces jeux contre l’homme, et de gagner à chaque fois. Plus d’infos dans le paragraphe sur les automates
retour en début de partie
retour au début de l’article

Le Turc

marionnette mécanique construite en 1769 par le baron von Kempelen pour jouer aux Échecs. Cette machine est considérée comme une des premières à jouer aux Échecs, seulement c’était une véritable mystification, car un homme se trouvait caché dans la structure de l’automate !

Le joueur d’échec

Nous l’avons déjà souligné au début de l’article, les jeux combinatoires peuvent, en théorie, être entièrement analysés en dénombrant toutes les positions de jeu possibles. Pour les Échecs ce nombre est bien trop important pour envisager une représentation complète de l’arbre de jeu. En revanche, certaines fins de parties – configurations particulières après un nombre avancé de coups et des pièces en moins – sont plus facilement analysables. C’est le cas par exemple de la fin de partie qui oppose le roi et la tour blancs contre le roi noir et qui fut analysée puis jouée par un automate (un vrai !) créé au début du 20^e siècle par l’ingénieur espagnol Leonardo Torres y Quevedo (1852 – 1836) : el Ajedrecista (le joueur d’Échecs).

L’automate de Torres (vu de face et de dos dans les figures en fin d’article) fonctionne grâce à un système électromécanique plutôt simple : à chaque position du système – c’est-à-dire à chaque position de jeu – correspond un électro-aimant qui entre en activité par des connexions électriques au moment où les commutateurs sont dans une position donnée. Par exemple, dans la figure ci-dessous, il y a trois commutateurs M, N et P et le second entraîne dans son mouvement un autre commutateur N’, le troisième entraîne les commutateurs P’, P’’, P’’’, P^iv et P^v. Comme M peut prendre les positions A ou B, N les positions E, F ou G, et P les positions R, S, T ou U, le système admet en tout vingt-quatre positions différentes, et à chaque position correspond un électro-aimant qui entre en activité dès que le courant est établi.

Schéma montrant comment on peut déterminer 24 opérations différentes selon les commutateurs activés.

Futur projet de techno ?

Les règles suivies par l’automate – qui joue les Blancs étant donné que cette fin de partie est gagnante pour les Blancs ! – sont les suivantes :

Le règles suivies par l’automate de Torres pour le déplacement du roi et de la tour blancs selon la position du roi noir, joué par l’adversaire humain.

Torres était convaincu qu’il était toujours possible, d’un point de vue théorique, de déterminer des règles qui dicteraient la conduite d’un automate, ce dernier procédant « en tout comme un être intelligent qui suit certaines règles ». Il était bien conscient des difficultés que pouvaient présenter la réalisation de tels appareils, mais il n’a jamais remis en doute sa possibilité théorique. En cela, on voit l’inspiration qu’il a puisée des travaux antérieurs du mathématicien anglais Charles Babbage (1791 – 1871) sur sa Machine Analytique.

L’automate de Charles Babbage

La machine analytique de Babbage est reconnue par les constructeurs d’ordinateurs comme une préfiguration des calculatrices modernes sur le plan des concepts, de l’organisation logique et des principes mathématiques (et non techniques). Afin de financer ce projet de toute une vie – qui n’aboutira malheureusement jamais, faute de moyens – Babbage envisage de créer un automate capable de jouer au Tic-Tac-Toe (Morpion). Son engouement pour les Échecs et autres jeux de plateau le fait se pencher sur l’étude mathématique des jeux de stratégies. Il comprend rapidement que le nombre de combinaisons est bien trop élevé pour le jeu d’Échecs, mais pour le Tic-Tac-Toe, ce nombre est « relativement insignifiant ». La notion fondamentale dans la réalisation d’un programme capable de jouer à un jeu de stratégie est celle d’instruction conditionnelle, que Babbage traduit sous la forme d’une liste de questions que l’on doit considérer :

[…] si n’importe quelle position de l’homme sur le plateau est assumée (que cette position soit possible ou impossible), alors si l’automate peut jouer correctement un premier coup, il doit être capable de gagner la partie, toujours en supposant que, sous la contrainte de la position donnée par l’homme, la déduction soit possible.
Quel que soit le coup joué par l’automate, un autre coup sera joué par son adversaire. Maintenant, cet état altéré du plateau correspond à l’une des nombreuses positions de l’homme pour lesquelles, d’après le paragraphe précèdent, l’automate est supposé capable d’agir.
Donc la question se réduit à jouer le meilleur coup selon n’importe quelle combinaison de positions de l’homme.
Maintenant les diverses questions que l’automate doit considérer sont de cette nature :

1. La position de l’homme, telle qu’elle se présente devant Automate sur le plateau, est-elle une position possible ? C’est-à-dire, une qui est en accord avec les règles du jeu ?
2. Si c’est le cas, Automate a-t-il déjà perdu la partie ?
3. Sinon, Automate a-t-il alors gagné la partie ?
4. Sinon, peut-il gagner au prochain coup ? Si c’est le cas, jouer ce coup.
5. Sinon, son adversaire peut-il, s’il a le trait, gagner la partie.
6. Si c’est le cas, l’Automate doit l’en empêcher si possible.
7. Si son adversaire ne peut gagner la partie au prochain coup, l’Automate doit examiner s’il peut jouer un coup tel que, s’il est autorisé à jouer deux coups successifs, il pourrait au second avoir deux façons différentes de remporter la partie ; et si chacun de ces cas fait défaut, l’Automate doit examiner à l’avance trois coups successifs, ou plus. [6]

Par ailleurs, Babbage était persuadé qu’un tel automate lui rapporterait de nombreux bénéfices lors d’expositions au grand public, car il attirerait les enfants qui y amèneraient leurs parents, mais aussi les parents qui y amèneraient leurs enfants ! Malheureusement pour lui, le projet n’aboutit pas, et il abandonne l’idée de construire son automate quand il apprend que d’autres machines (une qui écrit des vers en latin et une autre qui parle allemand) n’ont jamais été financées, et que l’exposition la plus rentable du moment est celle d’un nain dénommé Général Tom Pouce…

L’automate de Babbage n’a donc jamais vu le jour, et on ne peut savoir le succès qu’il aurait connu s’il avait été exposé au grand public. En revanche, les premières machines pour jouer au jeu de Nim, quoique construites plus tardivement, eurent beaucoup de succès, et leurs expositions à des salons et des foires scientifiques contribuèrent à propager ce jeu combinatoire au delà de la sphère des mathématiciens.

Notes de travail de Babbage

Les notes de travail de Babbage ont été redécouvertes par l’historien de l’informatique Doron Swade qui estime la taille de la machine à jouer au Tic-Tac-Toe, si elle avait été construite, équivalente à un réfrigérateur-congélateur avec près de mille roues dentées mobiles et de leviers, actionnés manuellement par des manivelles.

Le Nimatron

Au printemps 1940, une machine électromécanique destinée à jouer au jeu de Nim (et rien d’autre), le Nimatron, est inventée par deux employés des laboratoires de recherche de l’entreprise Westinghouse Electric durant leur pause déjeuner. Elle a été exposée à New York lors d’une foire mondiale où elle a joué plus de 100 000 parties et gagné près de 90 000. La plupart des défaites du Nimatron ont eu lieu contre les organisateurs de l’exposition pour convaincre les gens que la machine pouvait être battue – ces derniers étaient évidemment persuadés du contraire ! Le Nimatron était considéré comme une sorte d’aide au calcul de l’avenir, qui serait au service de n’importe quelle famille moyenne du Middleton. Chaque visiteur ayant eu le courage d’affronter la machine ressortait avec un bouton autocollant clamant « j’ai vu l’Avenir ».

Le Nimatron pesait près d’une tonne et proposait de jouer à un jeu de Nim à quatre tas, chaque tas possédant un maximum de sept jetons, en version normale. Les jetons étaient représentés par des lampes qui s’éteignaient à mesure que les jetons étaient retirés.

La configuration initiale était telle que le joueur humain – qui commençait la partie – pouvait obtenir une position gagnante (la Nim-somme était non nulle). Faute d’espace, il n’y avait qu’un ensemble de 9 configurations initiales possibles, qui s’enchaînaient les unes à la suite des autres : (7, 6, 3, 4) ; (3, 4, 7, 5) ; (2, 7, 5, 3) ; (6, 5, 4, 3) ; (3, 2, 4, 7) ; (2, 7, 5, 4) ; (3, 7, 6, 1) ; (6, 2, 1, 7) et (2, 5, 6, 4). Chaque lampe était connectée à un circuit contrôlé par les relais A1 à A7 pour la première colonne a, B1 à B7 pour la deuxième colonne b, C1 à C7 pour la troisième colonne c, et D1 à D7 pour la quatrième colonne d, ces relais étant eux-mêmes contrôlés par les relais maîtres : A pour a, B pour b, C pour c et D pour d.
D’autres relais, AZ, BZ, CZ et DZ étaient actionnés si le nombre de lampes allumées dans les colonnes a, b, c, d contenaient une puissance zéro de 2 (Z pour Zero power of 2). De même pour les relais AF, BF, CF et DF si les colonnes contenaient une puissance un de 2 (F pour First power of 2) et pour les relais AS, BS, CS et DS si les colonnes contenaient une puissance deux de 2. (Le nombre maximal de lampes étant 7, soit 111 en binaire, il n’était pas nécessaire d’utiliser des puissances supérieures). Pour bien jouer, la machine devait compter si une puissance de 2 apparaissait un nombre pair ou impair de fois. Si les trois puissances apparaissaient un nombre pair de fois – signifiant que son adversaire lui avait laissé une position gagnante – la machine jouait aléatoirement, sinon elle analysait dans quelle colonne il fallait intervenir pour obtenir un nombre pair de puissances.

Brevet du Nimatron

schéma représentant la machine de face et de profil droit.

Le Nimatron fut la première machine conçue pour jouer au Nim. Elle inspira la construction, en 1951, du Nimrod, également destiné à ne jouer qu’au Nim (mais aussi en version misère ou à d’autres variantes). De nombreuses informations, ainsi qu’une brochure décrivant la machine et son fonctionnement, sont disponibles à cette adresse : http://goodeveca.net/nimrod/. Le Nimrod et le Nimatron connurent un réel succès auprès du public lors de foires et de salons scientifiques. Ceci explique peut-être la création et la commercialisation au début des années 1960 de variantes du jeu de Nim, mais sur des supports entièrement mécaniques, car bien moins chères à produire !

Dr. Nim

Dr. Nim est un jeu fabriqué et commercialisé dans le milieu des années 1960 par E.S.R., Inc., entreprise spécialisée dans la manufacture de jeux éducatifs. Il se joue à un joueur, qui joue contre le Dr. Nim, en version normale ou misère, et se ramène à un jeu de Nim à une pile contenant jusqu’à vingt jetons, dont on peut en retirer un, deux ou trois.

Support en plastique rouge du jeu Dr. Nim.

Dr. Nim se présente sous la forme d’un support en plastique rouge, laissant tomber un ensemble de billes à travers divers leviers de couleur blanche, chacun pouvant se positionner de deux façons différentes. Ce dispositif de commutation est un montage flip-flop (bascule à deux états stables, tel un interrupteur) et permet, dans un circuit électronique, de réaliser la numération binaire. Il fut inventé en 1918 par le physicien britannique Franck Wilfred Jordan.

Le joueur qui affronte Dr. Nim choisit de faire tomber une, deux ou trois billes dans le système (le levier situé en bas à gauche du support permet de choisir quel joueur a la main, Dr. Nim ou Player) en actionnant une, deux ou trois fois la gâchette située en bas à droite du support. Quand c’est au Dr. Nim de jouer, il suffit d’actionner la gâchette une seule fois et il décide lui-même de faire tomber une, deux ou trois billes.

La version classique du jeu consiste à placer initialement, quinze billes dans la gouttière en haut du support, à positionner les leviers comme le montre la figure ci-dessous et à jouer en version misère.

Position initiale des leviers pour jouer contre Dr. Nim avec quinze billes en version misère.

Le manuel d’utilisation du Dr. Nim propose une liste de variations de la version classique selon le nombre de billes initialement engagées dans la gouttière, le positionnement des leviers et la version classique ou misère. Contrairement au Nim de Bouton, où le joueur qui connaît la stratégie peut déterminer la nature de la position initiale et donc choisir de jouer en premier ou non, il est possible à celui qui défie Dr. Nim de se mettre en position gagnante dès son premier coup (qu’il joue premier ou second). Cela signifie que le mécanisme de Dr. Nim a été conçu pour laisser une chance à son adversaire de jouer vers une position gagnante alors que lui aurait pu la jouer en premier. En revanche, une fois cette chance passée, Dr. Nim devient impitoyable et gagnera toujours la partie ! Toutes ces explications sont fournies dans le manuel d’utilisation et, contrairement à certaines règles de jeux parfois bien minimalistes, celui-ci consiste en un document pédagogique richement fourni. En effet le manuel, qui comporte vingt-trois pages au format A4, a pour objectif de faire comprendre aux joueurs, quel que soit leur âge, le fonctionnement du jeu ainsi que le raisonnement sous-jacent au mécanisme.

La première page du manuel d’utilisation de Dr. Nim.

Les auteurs s’appliquent à présenter les règles du jeu de Nim, puis à fournir un grand nombre d’informations sur la résolution logique du jeu, sur le programme qui a été implémenté pour jouer contre une personne, sur sa programmation sur ordinateur, etc. (On peut trouver l’intégralité du manuel à l’adresse suivante : http://www.one-leggedsandpiper.com/Christmas/Presents/Dr-Nim-Manual.pdf).

Enfin, des réflexions d’ordre plus général sont abordées, sur la nature de la pensée, sur la nécessité du langage pour penser, sur les mécanismes du cerveau. Le manuel cherche à poser des questionnements majeurs autour de la programmation informatique des jeux et de l’intelligence artificielle en général. Au côté ludique qu’offre la pratique du jeu Dr. Nim, vient s’ajouter – grâce au manuel d’utilisation – un caractère mathématico-pédagogique très complet expliquant en détails le fonctionnement de la machine. L’intérêt pédagogique du Dr. Nim est également mis en avant dans la description donnée par son inventeur, John T. Godfrey, dans le brevet qui paraît en 1968. Selon lui, l’arrivée des ordinateurs qui calculent vite a laissé des lacunes dans la capacité des étudiants à comprendre ce qu’est un ordinateur, comment ça fonctionne, quelle sorte de problèmes on peut résoudre avec cet outil, comment on peut lui donner des instructions pour qu’il résolve ces problèmes, etc. Concernant le Dr. Nim, et les autres mécanismes qu’il présente dans son brevet, le fonctionnement en est presque évident ; il ne nécessite pas de connaissances particulières (comme en électronique) à un étudiant pour qu’il comprenne la construction d’un tel mécanisme et ses applications concrètes. De plus, la lenteur d’exécution des opérations permet d’observer en temps réel le fonctionnement de la machine. Par ailleurs, c’est un système peu cher à produire. Godfrey affirme que l’explication des mécanismes de cette machine aide à la compréhension des notions suivantes : l’écriture binaire, les opérations d’addition et de multiplication dans le système binaire, l’action logique d’un circuit composé de bascules, etc.

Brevet du mécanisme du support de jeu du Dr. Nim par John T. Godfrey.

D’autres inventions de la sorte verront le jour jusqu’au début des années 1970 et pour lesquelles la motivation principale est d’ordre pédagogique (et pécuniaire !). Un autre exemple représente ci-dessous la machine de Robert Brass, dont le brevet est publié en 1971.

Machine de Robert Brass

Machine de Robert Brass en 1971 fonctionnant avec un système d’axes et de roues dentées pour actionner le levier en forme de bras (23) qui, en appuyant sur la gâchette (26) fait tomber le nombre de billes voulues de la gouttière (11) dans l’espace pour les recevoir (28).

retour en début de partie
retour au début de l’article

Le jeu de Nim et ses multiples variantes proposent une grande diversité d’activités en classe de mathématiques autour du calcul mental et de l’algorithmique. La pratique du jeu à travers la manipulation d’objets ou de machines (il existe encore des supports de Dr. Nim !) permet une approche nouvelle de certaines notions mathématiques parfois mal ressenties par les élèves. Nous espérons que le contenu de cet article offrira aux enseignants des ressources qu’ils pourront s’approprier et sur lesquelles ils pourront s’appuyer pour préparer leurs séquences, car nous sommes persuadés – comme le souligne Éric Trouillot dans son article http://revue.sesamath.net/spip.php?article749 – que le jeu reste la meilleure antidote aux effets anxiogène des mathématiques !