
- 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 20e 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’’’, Piv et Pv. 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 :
- 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 ?
- Si c’est le cas, Automate a-t-il déjà perdu la partie ?
- Sinon, Automate a-t-il alors gagné la partie ?
- Sinon, peut-il gagner au prochain coup ? Si c’est le cas, jouer ce coup.
- Sinon, son adversaire peut-il, s’il a le trait, gagner la partie.
- Si c’est le cas, l’Automate doit l’en empêcher si possible.
- 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