Turing Machine
Turing Machine est un jeu de déduction qui peut se jouer en solo, en coopération ou en compétition jusqu’à 4 joueurs. J’ai fait découvrir ce jeu à des enseignants-chercheurs de mon établissement à propos de cours sur la programmation de recherche de solution optimale. Nous réfléchissons à utiliser le jeu dans le cadre de ce cours. Si vous avez des idées activités liées à l’apprentissage de la programmation à l’aide de Turing Machine, n’hésitez pas a commenter ci-dessous !
But du jeu
Le but du jeu est de trouver le seul code de 3 chiffres (de 111 à 555) qui réussit le test de tous les vérificateurs de la machine. Chaque machine se compose de 4 à 6 vérificateurs, chaque vérificateur étant associé une carte Critères (ce qui varie dans les versions extrême et cauchemars du jeu). A chaque tour de jeu, chaque joueur peut soumettre à la machine une proposition de 3 chiffres symbolisés par un triangle, un carré et un rond correspondant respectivement au premier, deuxième et troisième chiffre de sa proposition. Chaque vérificateur questionné répondra si la proposition réussit ou ne réussit pas le test. Pour une présentation plus complète, je vous propose celle de Ludochrono mais ce n’est pas nécessaire pour lire la suite du billet :
Le but de ce billet n’est pas de vous expliquer les règles mais de partager une réflexion sur les usages possibles du jeu Turing Machine dans l’enseignement supérieur. Pour cela, il nous faut un peu mieux comprendre le jeu à travers l’exemple ci-dessous.
Exemple de machine à 4 vérificateurs et 4 cartes Critères
Chaque vérificateur est lié à une seule carte Critère. La carte Critère décrit les items que le vérificateur va tester. Une carte Critère comprend a minima 2 critères. A vous de trouver celui que le vérificateur teste.
Par exemple dans la machine illustrée ci-dessus (problème 1 proposé dans la règle du jeu, code A43 Y6L. Cette feuille de notes a été générée sur ce site), le vérificateur A teste la valeur du carré (deuxième nombre dans la proposition du joueur) par rapport à la valeur 4. Le joueur qui propose 142 au vérificateur A et qui réussit le test (le vérificateur répond Réussi) sait que le second chiffre du code a trouver est 4.
Ce vérificateur est qualifié de simple car ses critères couvrent l’entièreté des réponses possibles : carré est soit inférieur à 4, soit égal à 4, soit supérieur à 4. Le test d’un vérificateur sera réussit pour un seul des 3 critères. Les 3 autres vérificateurs de cette machine sont également simples. Pour le vérificateur D, strictement plus petit exclu l’égalité.
Déroulement d’une partie
A chaque tour de jeu, chaque joueur va
- écrire une proposition de code à 3 chiffres ;
- tester ce code sur un maximum de 3 vérificateurs de la machine. Chaque vérificateur répond si la proposition réussit ou ne réussit pas le test. La réponses que donne un vérificateur ne renseigne pas directement sur le code proposé, mais sur le critère que le vérificateur teste ;
- pouvoir tester s’il a trouvé la solution au code mais s’il échoue, il est éliminé.
Ensuite un nouveau tour commence et ainsi de suite jusqu’à ce que au moins un joueur trouve le code ou qu’il ne reste qu’un seul joueur non éliminé. Entre amis s’il y a un vainqueur, les autres joueurs peuvent continuer à jouer jusqu’à ce que chacun trouve le code. En cas d’égalité, le vainqueur est celui qui a trouvé le bon code en interrogeant le minimum de vérificateurs. Pour limiter ce nombre d’interrogations, le joueur peut déduire les critères. Attention : consacrer trop de temps à la déduction peut casser le rythme du jeu. Entre amis, les joueurs peuvent définir comme vainqueur le joueur qui trouve le code le plus rapidement en utilisant un minimum d’interrogation. Si vous voulez découvrir la règle complète, mais ce n’est pas nécessaire pour lire la suite du billet, je vous propose la Vidéorègle de Yahndrev :
Déduire les critères
Comme précisé dans la page 4 de la règle, « Tous les vérificateurs sont essentiels pour trouver le code final. » Sachant que chaque vérificateur est indispensable et qu’un seul code respecte tous les critères, il est possible d’identifier un critère qui rendrait une autre carte Critère / vérificateur associé inutile. De facto, ce critère doit être faux. Dans notre exemple ci-dessus, le vérificateur B teste le nombre de chiffres 3 dans le code. La carte Critère D dit qu’un des chiffres du code est strictement plus petit que les 2 autres. Si le critère 333 est vrai alors le vérificateur D n’apporte aucune information pour trouver le code (il est même impossible à résoudre). Le vérificateur D est essentiel, donc le critère 333 de la carte Critère B ne peut pas être celui que le vérificateur B teste. Inutile de le tester, le joueur peut le rayer des critères utiles pour trouver le code.
Des critères de la carte Critère D impactent le vérificateur C et vous permettent d’exclure certains critères. Pouvez-vous les trouver avant de lire la solution ci-dessous ? L’analyseur de partie en ligne illustré ci-dessous vous permet de lister les déductions possibles de chaque machine.
L’analyseur de partie illustré ci-dessus a été créé par Patrice Gauchon. Le but du jeu est bien entendu de faire fonctionner ses petites cellules grises, comme Agatha Christie le fait dire à Hercule Poirot. L’analyseur permet de confronter sa démarche avec celle de l’analyseur en fin de partie. Alla-Maria Savidy (Université de Montpellier, UFR Pharmacie) va plus loin et explique remarquablement bien sa démarche pour résoudre deux problèmes sans interroger la machine ici et ici.
Vérificateurs difficiles
A partir des cartes de Critères numéro 26, les critères du vérificateur ne couvrent plus l’ensemble des solutions comme c’était le cas pour les vérificateurs simples. Avec une carte Critère difficile, les critères testés sont indépendants les uns des autres. Donc le résultat d’une proposition testée par ce vérificateur ne permet pas de tirer de conclusion sur les autres critères testés par ce vérificateur. Mais pour chaque vérificateur un seul critère est interrogé et est vrai. Par exemple pour la carte de gauche, si le critère testé par ce vérificateur est triangle=1 et si la proposition 512 ne réussit pas le test, cela ne signifie pas que carré soit égal ou différent de 1. La non réussite signifie que le critère testé n’est pas carré=1. Le joueur n’a pas d’information sur les autres critères. Si le critère testé est triangle=1, cela signifie même que carré ou rond peuvent être égal à 1 (exemple du Défieur 2 jeux).
La carte de droite est également un vérificateur difficile. La règle reste identique : pour chaque vérificateur un seul critère est interrogé et est vrai. C’est avec ces cartes Critères difficile que le paradoxe du faux (voir ci-dessous) est essentiel à bien comprendre.
Le paradoxe du Faux
La machine ne teste pas une proposition ! Chaque vérificateur vérifie la proposition par rapport à ce qu’il teste, critère et valeurs (de triangle, carré ou rond). Cela conduit souvent à une mauvaise interprétation des non réussite à un test. Une explication officielle sous forme d’un complément à la règle est proposée sur https://turingmachine.info/files/rules/TuringMachine_ParadoxeFaux_FR.pdf
Conclusion
Dans le cadre d’un cours de programmation de recherche de solution optimale, une idée serait de faire jouer les étudiants pour répondre à des questions comme :
- Quelle est la meilleure première proposition compte tenu des cartes Critères d’une machine donnée ?
- Quel vérificateur interroger pour réduire au maximum l’incertitude à partir d’une proposition donnée ?
- Quelle proposition permet pour une machine donnée de réduire au maximum l’incertitude ?
C’est à partir d’analyse et de déduction que les étudiants pourront répondre à ces questions évoquées. Grâce à l’analyseur de Patrice Gauchon ou aux explications d’Alla-Maria Savidy, les étudiants pourront confronter leur travail à celui d’experts et l’améliorer.
Turing Machine est un jeu exceptionnel. Pour comprendre à quel point, faites quelques parties et regardez la vidéo en anglais de Adventures in Creative Software
Turing Machine est un jeu créé par Fabien Gridel et Yoann Levet, illustré par Sébastien Bizos, et édité par Le Scorpion Masqué. Il se joue de 1 à 4 joueurs à partir de 14 ans. Il est disponible sur Board Game Arena
Idées et expériences 