Lire & Voir : Jeux, Sports

Turing machine : saurez-vous trouver le code ?

Fabien Gridel, Yoann Levet (Scorpion Masqué, 2022)

Le principe du jeu : dans Turing Machine, l’objectif est de trouver, avant ses adversaires si on est en mode compétitif, un code de trois chiffres, chacun allant de 1 à 5. Au premier abord cela semble bien simple, mais l’intérêt du jeu arrive. Pour deviner le code, on interroge un proto-ordinateur (en carton) composé de 4 à 6 vérificateurs. Chaque vérificateur va tester un critère sur le code, et un seul code (parmi les 5³ = 125 possibles) satisfait tous ces critères. Cela a toujours l’air simple ? Et si je vous dis qu’une carte critères n’en comporte pas un mais plusieurs, et que c’est à vous, en testant plusieurs combinaisons, de trouver lequel !

Un premier exemple : une carte critères s’intéresse à comparer un des chiffres du code à « 1 ». Les 3 critères figurant sur la carte sont : bleu = 1, jaune = 1, violet = 1 ;

On sait alors que la carte va valider tous les codes qui satisfont un critère précis parmi ces trois, mais on ne sait pas lequel. En particulier on sait déjà qu’un des trois chiffres est à 1. À vous donc de tester des codes avec un des chiffres à 1 jusqu’à en trouver un qui passera le test du vérificateur et vous révèlera le chiffre qui doit être à 1. Si le code 213 passe le test, alors c’est que le critère testé est : jaune (le deuxième chiffre) = 1, et on a trouvé le critère testé par la carte. On sait donc que n’importe quel autre code avec le chiffre du milieu à « 1 » passera ce test, par exemple 515. Si au contraire notre code 213 ne passe pas le test, on va essayer un autre code avec un  « 1 » ailleurs. Par exemple 125. S’il passe le test, on sait que le code aura son premier chiffre (le bleu) à « 1 » sinon on sait que c’est le troisième chiffre qui vaut « 1 » .

Un exemple plus complexe : une autre carte s’intéresse à comparer la valeur de l’un des trois chiffres à 4. Dans ce cas, on ne vous dit ni quel chiffre on compare à 4, ni le résultat de la comparaison. Si le code 354 passe le test c’est que le critère testé est soit « le premier chiffre est < 4 », soit « le deuxième chiffre est > 4 » ou encore « le troisième chiffre est égal à 4 ». En faisant varier un seul des trois chiffres, on peut voir si le résultat du test change (auquel cas on a trouvé le chiffre testé et le critère). Si par exemple le code 554 ne passe pas le test, comme il ne diffère que d’un chiffre de 354 qui passait le test, c’est que la carte vérifie le premier chiffre, et que le critère (qui est vrai pour 354, faux pour 554 et compare un chiffre à 4) est « le premier chiffre est < 4 ».

Vous pensez avoir trouvé le critère testé par un vérificateur ? Super, il vous reste à faire de même pour tous les autres vérificateurs afin d’en déduire le code.

À chaque tour de jeu, chaque joueur choisit un code de trois chiffres, et le teste sur un maximum de 3 vérificateurs. Quand l’un des joueurs pense avoir trouvé le code, il le teste sur tous les critères. Si tous passent, il ou elle a gagné. Sinon la partie continue avec les autres joueurs. Et si deux trouvent au même tour, les ex-aequos sont départagés au nombre de tests effectués au cours de la partie.

Le guide de règles contient 20 problèmes, rangés par difficulté et par importance du hasard dans la phase de recherche. C’est très peu mais ce n’est pas grave, car le site contient un livret imprimable de près de 500 nouveaux problèmes et un générateur permettant de choisir son mode de jeu et la difficulté souhaitée et de générer des problèmes.

Et si votre cerveau ne chauffe pas encore assez, deux modes de jeu supplémentaires sont proposés. Pour le premier on met deux cartes critères devant chaque vérificateur au lieu d’une (et donc il faut trouver quel test est effectué parmi tous ceux proposés par chacune des deux cartes). Pour le deuxième c’est encore pire : on ne vous dit plus devant quel vérificateur mettre quelle carte critères ! Vos tests successifs doivent vous permettre petit à petit de décider la place de chaque carte (ainsi que le critère qu’elle teste comme d’habitude) afin de retrouver le code.

Vous vous demandez quel est l’intérêt scientifique du Turing machine ? Dans ce jeu, on passe son temps à faire des déductions et à croiser des informations. Les compétences en logique et en raisonnement, si importantes en mathématiques et informatique, sont donc renforcées grâce à ce jeu.
De plus on réfléchit aussi beaucoup au jeu de test qui va nous permettre, non pas de corriger un programme qu’on vient d’écrire, mais de deviner le programme (que l’on connaît seulement au travers d’indices via les cartes critères) qui tourne devant nous. Cela ressemble beaucoup au test en boîte noire (black box testing) où l’on s’assure de la correction d’un système sans avoir accès au code mais juste en jouant sur les entrées qu’on donne au système (ici les codes que l’on teste) et en observant les sorties (ici si le code passe ou non les tests).

Matériel : j’ai été séduite par le matériel de jeu. Choisir un code c’est superposer trois cartes multi-perforées ne laissant plus apparaître qu’un seul trou. Et tester un critère revient à superposer notre code à une carte de vérification (choisie parmi une centaine suivant le problème) couverte de croix rouges et de coches vertes. Le signe apparaissant dans le trou du code nous donne la réponse au test.

Retour de nos testeurs : testé et approuvé entre amis (dans un séjour regroupant bien plus de boîtes de jeux que de personnes présentes). Même après l’effet découverte (jeu en rupture autour de Noël, d’autres joueurs en avaient entendu parler mais pas pu l’acheter) la boîte est rarement restée fermée. L’âge minimal annoncé de 14 ans n’a pas été une limite. Avec accompagnement, la plus jeune de 10 ans s’est lancée et a pu jouer en mode coopératif puis sur des niveaux faciles en autonomie.

Point négatif : parce qu’il en fallait bien un, ma principale critique porte sur le nom du jeu. Je m’attendais à voir un lien avec une machine de Turing (un ruban, des programmes à exécuter ou à écrire) et je ne l’ai pas trouvé. De même, parler d’interroger une intelligence artificielle pour tester une condition simple me semble franchement exagéré. Cependant, comme on me l’a signalé, cela veut dire que maintenant le nom Turing « fait vendre » et c’est en soi déjà une petite victoire.

Marie Duflot-Kremer

 Le Stratège

Bennett Miller (2011)

Le Stratège ou Moneyball (de son titre original) est un film américain de Bennett Miller inspiré de faits réels, où l’on suit l’histoire de Billy Beane, dirigeant de l’équipe de baseball professionnelle des Oakland Athletics. L’intrigue met l’accent sur la stratégie qu’il a mise en place basée sur une analyse novatrice des statistiques pour manager, recruter, transférer et licencier ses joueurs.

Le baseball est un des sports majeurs aux États-Unis parmi les moins connus en Europe. La collecte de statistiques sur les rencontres et leur publication dans les journaux est une tradition qui remonte au moins à 1858 avec Henri Chadwick selon la page Wikipedia. L’analyse de ces statistiques s’est même faite son nom, la sabermétrie. Sa quête est d’identifier la ou les statistiques clefs de la victoire d’une équipe ou de la compétence d’un joueur. Une fois un modèle d’analyse posé, le traitement de données qu’autorise l’informatique permet de distinguer rapidement de la multitude les meilleurs joueurs selon les critères fixés. Penser différemment peut être un avantage dans ce contexte car les prix et salaires des joueurs s’ajustent à leur compétence supposée selon le modèle dominant qui n’est pas forcément mathématique. Une distorsion sur l’estimation des joueurs avec ses concurrents peut être un avantage décisif si son modèle d’analyse reste pertinent.

Le personnage principal du film est un dirigeant appartenant à un petit marché donc son budget est plus petit que celui de ses adversaires. C’est ce qui l’amène à chercher une telle distorsion pertinente. La technique n’est pas le sujet principal du livre, même si l’interprète du rôle principal, Brad Pitt, a l’occasion de méditer sur un coefficient binomial et qu’un ordinateur permet d’accélérer des traitements auparavant manuels. Ce qui est illustré au cours de l’histoire ce sont les réactions au changement de point de vue à l’intérieur du club, dans les médias, dans les autres clubs : toutes ces conséquences bien pratiques de l’application d’une nouvelle théorie. L’histoire individuelle des personnages a aussi une forte influence sur leurs réactions. Ces allers-retours entre le modèle d’analyse et ses conséquences sur la réalité sont pour moi le cœur du sujet agréablement traité dans cette œuvre. Ce film semble avoir fait entrer dans la culture populaire l’impression que les statisticiens, au delà de leur amour de la manipulation des chiffres, pouvaient avoir un rôle à jouer dans l’organisation du sport professionnel. Cependant d’autres lectures m’incitent à suggérer que l’équilibre atteint actuellement entre les diverses expertises n’est pas aussi extrême que celui proposé dans le film.

Sorti en 2011, le film évoque une saison du tout début des années 2000 et est une adaptation d’un livre, Moneyball: The Art of Winning an Unfair Game, écrit par Michael M. Lewis en 2003. Cet auteur est un économiste de formation, brièvement trader, qui s’épanouit comme journaliste et conteur à opinions dans des essais dont la forme tend vers le roman. Ses livres partent souvent d’une documentation fouillée mettant en avant des faits marquants. Selon certains de ses détracteurs la sélection des faits est parfois trop orientée pour accompagner la narration. Une autre interprétation est que les sujets traités sont discutables et que cette sélection est aussi la manifestation d’une opinion. Malgré ces réserves, le résultat est souvent une belle histoire enthousiasmante, à l’échelle du point de vue d’un humain qui la vit ou la lit.

Ici, le film fait en se basant sur le livre une nouvelle sélection et force probablement le trait vers le conte mais il reste la moelle des questionnements initiaux. Comment une interprétation radicalement différente des données peut-elle donner un avantage industriel dans la prise de décision ? Comment cette interprétation est-elle reçue par le milieu ? A-t-elle des limites pour ne pas devenir dogmatique ? Un sujet qui pourrait paraître bien austère mais qui est ici incarné dans le milieu du baseball professionnel américain et ouvert vers la vie personnelle du personnage principal. Connaissant à peine les règles du baseball, je ne dispose pas des compétences pour juger les controverses d’interprétation des faits sportifs.

Le sport professionnel donne les moyens et la légitimité pour la collecte systématique d’informations de plus en plus précises sous la forme de statistiques. Ces statistiques sont ensuite interprétées par les fans, les entraîneurs, les dirigeants, les joueurs et leurs agents. La multiplicité de ces interprétations de statistiques intermédiaires est le signe qu’aucun modèle ne fait consensus. Aurions-nous un débat public avec une population motivée et un cadre pour la méthode scientifique ? Une opportunité à ne pas gâcher.

Yvan Le Borgne

La petite histoire du ballon de foot 

Étienne Ghys (Éditions Odile Jacob, janvier 2023)

Sauriez-vous dessiner un ballon de football ? Par exemple, celui avec des pièces blanches et des pièces noires, qu’on appelle Telstar, qui date de 1970 (coupe du monde de football masculin à Mexico) et qui a perduré jusqu’au Tricolore en 1998 (coupe du monde en France). Pas si simple ! En lisant ce petit livre sur les ballons de football, vous découvrirez que ce ballon Telstar est composé de 32 pièces, les noires ayant cinq côtés et les blanches en ayant six. Ne vous fiez pas aux pancartes indiquant les stades de football en Angleterre, car les dessins sont faux ! Un comble au pays du football. Mais les mathématiques sont formelles : il est impossible de construire un ballon avec seulement des hexagones à six côtés.

Le ballon Telstar, avec ses pentagones et hexagones, répond au petit nom mathématique de « icosaèdre tronqué ». C’est difficile à imaginer, mais le livre est truffé de dessins qui visualisent très bien toutes les opérations géométriques utilisées pour construire le ballon.

Pourquoi un icosaèdre et pas un autre volume ? L’icosaèdre, sorte de dé à 20 faces toutes triangulaires, fait partie de la famille des polyèdres, ces solides avec plusieurs faces planes. Il fait aussi partie de la famille des cinq solides de Platon, qui sont des polyèdres particuliers. L’auteur explique pourquoi il n’existe pas de polyèdre avec seulement des faces hexagonales, donc pourquoi le ballon de football des pancartes anglaises n’est qu’un dessin… Par contre, il est possible de tronquer un polyèdre, comme pour le ballon Telstar. Et l’icosaèdre tronqué est presque rond, c’est utile pour un ballon de football… D’autres exemples de solides tronqués, issus des travaux d’Archimède, sont illustrés dans le livre.

Un icosaèdre tronqué et un ballon de football de type Telstar.
Crédit Image : Dyfsunctional, Public domain, via Wikimedia Commons.

Après cette digression géométrique, le livre revient aux ballons des coupes du monde de football. À partir de 2006, chaque coupe du monde a son propre ballon, révélé peu avant la compétition. En 2006 (coupe du monde en Allemagne), le ballon Teamgeist a quatorze pièces et est inspiré d’un octaèdre tronqué. L’octaèdre, qui est aussi un des solides de Platon, a huit faces triangulaires. Une fois tronqué, le solide a six faces carrées et huit faces hexagonales. Mais l’innovation repose dans la forme des pièces, dont les côtés sont des courbes. Le ballon Al Rihla de 2022 (coupe du monde au Qatar) est aussi inspiré de volumes tronqués, mais il va plus loin en brisant des symétries, avec des pièces légèrement différentes. De plus, ce ballon est connecté et envoie ses trajectoires en wifi.

Les ballons de football des coupes du monde.
Crédit Image : © FIFA

À propos de trajectoires, les joueurs ne manquent pas de commenter celles du ballon à chaque coupe du monde. Poursuivons la lecture et quittons la géométrie pour faire un peu de physique. Sans résistance de l’air, le ballon suivrait une trajectoire en cloche (parabolique), comme l’a expliqué Galilée. La trajectoire du ballon est en réalité sensible à la viscosité de l’air. Ainsi que l’a observé Eiffel, le ballon ralentit beaucoup s’il est frappé lentement et très peu s’il est frappé fort, car l’air autour du ballon est plus ou moins turbulent. Un ballon lisse serait trop peu freiné, il doit donc être un peu rugueux. Le ballon Telstar l’est grâce à ses coutures. Vous avez sans doute remarqué que le ballon Al Rihla de 2022 est piqueté de petites alvéoles, un peu comme une balle de golf, pour augmenter la rugosité du ballon. Enfin, l’analyse physique ne serait pas complète sans parler des effets de rotation du ballon imprimés par le tir du joueur. Vous avez sûrement en mémoire des buts marqués grâce à un effet de spin, buts qui sont entrés dans la légende…

Pour conclure, ce livre d’Étienne Ghys revient sur des notions de géométrie. Rappelons qu’un ballon de football est fabriqué en s’inspirant d’un polyèdre. Tout segment reliant deux points du ballon reste à l’intérieur, le ballon est donc mathématiquement convexe. Il est aussi rigide, non flexible. Mais est-ce toujours le cas ? Oui, le mathématicien Cauchy a démontré vers 1813 que tout polyèdre convexe est rigide. À l’inverse, il a fallu attendre 1977 pour que le mathématicien Connelly construise un polyèdre non convexe et flexible. Avec Sabitov et Walz, il a aussi démontré, 20 ans plus tard, qu’un polyèdre flexible se déforme en gardant un volume constant. Résultat facile à énoncer mais dont l’auteur qualifie la démonstration de grandiose.

Terminons par le ballon Brazuca, le préféré de l’auteur (coupe du monde 2014 au Brésil). Il est formé de six faces, tout comme un cube. L’astuce est de courber les faces dans l’espace, comme avec certains origamis. Grâce à la magie de la géométrie, le ballon Brazuca est presque sphérique, sans le gonfler. Il ne vous reste plus qu’à imaginer le prochain ballon de football (coupe du monde 2026 en Amérique)…

Jocelyne Erhel

À la découverte de Turing Tumble

Alyssa & Paul Boswell (Upper Story LLC, 2019)

Ce texte est une adaptation de l’article « À la découverte du jeu Turing Tumble » de Natacha Portier, paru sur Interstices.

Le jeu se présente sous la forme d’un grand plateau presque vertical dans lequel de petites pièces en plastique coloré peuvent s’encastrer. Ces pièces jouent le rôle de portes logiques, de mémoire mais aussi de fils transmettant l’information et l’énergie. En haut, on range les billes, rouges d’un côté, bleues de l’autre. Ce sont ces billes qui en cascadant de haut en bas du plateau font bouger les pièces. Une bille qui arrive en bas déclenche le départ de la bille suivante par un astucieux mécanisme reliant le bas au haut du plateau. Chaque énigme est un casse-tête : une situation de départ et un ensemble de pièces utilisables sont proposés. Comment placer les pièces sur le plateau pour obtenir le résultat souhaité ? Ce résultat peut être une alternance de billes de couleur à l’arrivée, ou bien une position des pièces dont l’orientation sur le plateau change au passage des billes. Pour les quatre premières énigmes, un seul type de pièce est utilisé, et on découvre progressivement comment guider les billes sur le plateau.

© Turing Tumble LLC, tous droits réservés.

Ensuite une nouvelle pièce est proposée, qui permet aux chemins des billes de se croiser. Enfin on découvre une nouvelle pièce, le bit, qui peut bouger et stocker de l’information après le passage d’une bille : pointe-t-il à gauche ou à droite ?
Grâce au bit, on peut créer des registres sur le plateau : un registre constitué de trois bits permet de stocker en binaire un entier entre 0 et 7. En créant deux registres, on peut comparer des entiers, les additionner et les multiplier. Il y a aussi une pièce qui capture les billes pour arrêter un calcul, et des engrenages pour faire des calculs encore plus sophistiqués.

Un peu de science sur le jeu

Essayons maintenant de comprendre comment le Turing Tumble permet de faire des calculs. Ne pourrait-on pas faire plus simple, par exemple un ordinateur en papier ? On peut écrire un programme sur du papier. On peut aussi coder l’entrée d’un programme et même la sortie, comme une ligne de texte ou une image. Mais le problème, c’est que les calculs ne se font pas tout seuls ! Une fois le programme et les entrées écrites, vous pouvez attendre longtemps en regardant la feuille, mais rien à faire, le résultat n’apparaît pas comme par magie… Il manque de l’énergie ainsi qu’un automate qui lise les entrées, le programme et fasse le calcul. C’est d’ailleurs bien comme ça qu’Alan Turing avait imaginé un ordinateur, bien avant que la technologie ne nous permette d’en fabriquer un : les données (le programme, l’entrée, la sortie, le brouillon) sont stockées sous la forme de lettres écrites sur un ruban de papier, et une tête de lecture/écriture fait évoluer ces données en suivant des règles bien précises, des règles « automatiques ». Par exemple, lorsque nous posons sur le papier une addition comme nous l’avons appris à l’école primaire, la tête de lecture/écriture c’est nous ! Nous utilisons nos yeux, notre cerveau, notre main et un crayon, et à la fin le résultat est inscrit sur notre feuille. Comment cela se passe-t-il dans les ordinateurs actuels ? Ce sont les transistors qui jouent à la fois le rôle du papier qui contient l’information et de l’automate qui exécute le calcul ! Les transistors sont disposés sous la forme d’un circuit dans lequel l’électricité circule. Elle fournit l’énergie nécessaire aussi bien pour calculer que pour écrire dans la mémoire. Dans le Turing Tumble, c’est l’énergie mécanique qui permet de stocker de l’information et de faire les calculs. En tombant, une bille peut changer l’orientation des pièces du plateau : c’est l’écriture dans la mémoire. Le trajet d’une bille dépend de l’état du plateau et les actions qu’elle déclenche sur son passage sont donc différentes : c’est le calcul.

Le plateau du Turing Tumble peut être comparé à un circuit imprimé, qui permet de maintenir en place et de relier entre eux un ensemble de composants électroniques. Sur ce plateau, on peut fixer des pièces de plastique. La plus simple est la rampe (en vert, voir la photo ci-dessous), qui permet de guider les billes qui descendent sur le plateau. Les rampes permettent, comme les fils conducteurs d’un circuit imprimé, de faire circuler l’énergie et l’information. Il y a ensuite les croisements (en orange) : comme leur nom l’indique, ce sont des pièces qui permettent aux chemins de billes matérialisés par les rampes de se croiser sans interférer. Ce ne sont pas des croisements au sens des routes. Les billes ne peuvent pas changer de chemin comme le ferait une voiture à un croisement. Ce sont plutôt des ponts qui permettent à ces routes de se croiser tout en s’ignorant. Comment cela se passe-t-il dans un circuit imprimé ? Il y a en fait plusieurs plans parallèles. C’est ce qui permet aux fils conducteurs de se croiser sans se gêner. La pièce introduite ensuite est le bit (en bleu). Alors que la rampe et le croisement sont fixes sur le plateau, le bit a deux positions. Quand il pointe sur la droite, il envoie la bille sur la gauche et se met à pointer à gauche. Symétriquement, quand il pointe sur la gauche, il envoie la bille sur la droite et change de position. On voit ici que le bit permet de tester une condition : si pointe à droite, alors envoie la bille à gauche, sinon envoie la bille à droite. C’est une fonction très utile dans les langages de programmation !

Photo © Natacha Portier

On peut également comparer le bit à un interrupteur : comme un transistor dans un ordinateur, il a deux états différents. Un interrupteur laisse passer le courant ou le bloque, un bit envoie une bille à droite ou à gauche. Mais l’analogie n’est pas parfaite, car utiliser un interrupteur ne change pas son état, alors qu’on a vu qu’une bille passant par un bit fait changer la direction dans laquelle il pointe. La prochaine bille le traversant n’ira donc pas dans la même direction. L’état d’un transistor au contraire est contrôlé indépendamment. Cependant les bits du Turing Tumble, comme les transistors dans un ordinateur, permettent de créer des compteurs, des registres et des mémoires. Imaginons par exemple qu’on souhaite compter le nombre de billes qui descendent sur le plateau, et que ce nombre est au maximum de 15. On va créer un registre pour compter les billes. Ce registre est constitué de quatre bits sur le plateau, qui représenteront les 4 chiffres binaires qui permettent de représenter un entier entre 0 et 15. Il reste à ajouter des rampes et des croisements de façon à ce que le passage d’une bille ajoute 1 à cet entier. C’est le challenge numéro 21 sur les 60 que compte le jeu !

Quelques références

• Le site de Turing Tumble
  Outre le livre d’énigmes fourni avec le jeu, vous pouvez trouver sur le site un guide pratique avec des explications des énigmes et des exercices supplémentaires, ainsi qu’un guide pour éducateurs qui permet de faire le lien entre les énigmes et les notions informatiques. Vous pouvez acheter les fichiers qui permettent d’imprimer en 3D les pièces. Une version du jeu en français du Québec est sortie au printemps 2020. Le jeu est recommandé par ses créateurs à partir du CE2.
• Un simulateur en ligne du Turing Tumble
  L’école dans laquelle Pablo intervient est anglophone. Parmi les ateliers, il propose aussi les jeux Code Combat et Hacknet ainsi que des ateliers d’informatique débranchée.