Robots imbattables, championnats et tournois de programmes : le Pierre Feuille Ciseaux pris au sérieux
Un jeu de cour d'école peut-il occuper des chercheurs en robotique, des organisateurs de championnats, deux maisons de vente aux enchères et des programmeurs du monde entier ? Le Pierre Feuille Ciseaux l'a fait. Ces histoires ont un point commun : chacune répond à sa façon à la même question, « comment gagner à un jeu où, en théorie, personne ne peut gagner à coup sûr ? ». Les réponses sont surprenantes : en trichant sur le temps, en lisant les humains, ou en exploitant les plus faibles.
Le robot de Tokyo qui gagne à chaque fois
En juin 2012, le magazine IEEE Spectrum présente un robot du laboratoire de Masatoshi Ishikawa, à l'université de Tokyo : une main mécanique à plusieurs doigts, reliée à une caméra rapide, qui joue au janken contre un humain et gagne toutes les manches. Selon l'article, il ne lui faut qu'une milliseconde pour reconnaître la forme de ta main, et quelques millisecondes de plus pour former le geste qui la bat.
L'équipe a décrit le système en 2015 dans un article présenté à la conférence HRI (Yugo Katsuki, Yuji Yamakawa et Masatoshi Ishikawa), au titre sans détour : un système de Pierre Feuille Ciseaux « avec 100 % de victoires ». Les chiffres y sont précis. La caméra analyse la main humaine toutes les 2 millisecondes : elle compte les doigts tendus et en déduit le geste. La main du robot, capable de refermer ses articulations de 180 degrés en 0,1 seconde, commence à bouger environ 30 millisecondes après que l'humain a commencé à changer la forme de sa main, et termine son mouvement en 30 millisecondes. L'humain, lui, met environ 60 millisecondes à achever son geste. Les deux mains finissent donc presque en même temps, et à l'œil, rien ne trahit le décalage.
Le « 100 % » est le chiffre annoncé par le laboratoire, pas le résultat d'un test indépendant. Mais il n'a rien de mystérieux, car le robot ne devine rien : il regarde ta main se former et réagit.
Réagir n'est pas deviner
Pourquoi ne voit-on pas la tricherie ? Parce qu'un humain réagit beaucoup plus lentement. Robert Kosinski et John Cummings (université de Clemson), qui s'appuient sur de nombreuses études, rappellent que le temps de réaction simple d'un jeune adulte à un signal lumineux est en moyenne d'environ 190 millisecondes, et qu'il s'allonge encore quand il faut reconnaître ce qu'on voit avant de répondre. Une étude de 2015 sur des étudiants en médecine (Jain et coll.) cite une moyenne de 180 à 200 millisecondes pour un signal visuel.
Le robot démarre donc environ six fois plus tôt qu'un humain ne pourrait seulement commencer à réagir à un signal visuel. Pendant ces 180 millisecondes, sa caméra a analysé ta main 90 fois. Ce n'est pas une prouesse de stratégie, c'est un changement de règle : le PFC suppose que les deux gestes sont choisis en même temps, sans voir celui de l'autre. Supprime cette simultanéité, et le jeu n'a plus rien de hasardeux. C'est exactement ce que les chercheurs voulaient démontrer : une interaction homme-robot plus rapide que la perception humaine, avec des applications envisagées dans l'industrie.
Toronto, Las Vegas : les championnats humains
Côté humains, la compétition « sérieuse » a surtout vécu dans les années 2000, avec une bonne dose d'humour revendiqué. La World RPS Society, basée à Toronto et animée par les frères Douglas et Graham Walker, organise en 2002 son premier « championnat du monde » dans un bar loué pour l'occasion. Selon le Seattle Times, le vainqueur, Pete Lovering, repart avec 1 200 dollars canadiens et une médaille d'or. L'année suivante, le journal annonce près de 1 000 joueurs attendus pour un premier prix de 5 000 dollars canadiens, des arbitres formés et un règlement qui définit chaque geste. La pierre, par exemple, est un poing fermé dont le pouce repose au moins à la hauteur du doigt le plus haut.
Dans l'enquête que leur a consacrée le site Priceonomics en 2014, Douglas Walker raconte qu'ils auraient été contents de voir venir 25 ou 30 amis. Le même article décrit l'ambiance comme un mélange de convention de science-fiction et de soirée arrosée, et indique que la société est depuis largement en sommeil.
Aux États-Unis, la USA Rock Paper Scissors League, sponsorisée par la bière Bud Light, a couronné son premier champion national le 9 avril 2006 au Mandalay Bay de Las Vegas, avec 50 000 dollars à la clé. La finale a été diffusée sur la chaîne A&E. Pour 2007, la marque annonçait des qualifications locales dans 325 villes, réservées aux plus de 21 ans, et le même premier prix de 50 000 dollars. Ces gains spectaculaires sont donc ceux d'une opération de sponsoring pour une bière, pas les revenus d'un sport installé, et la ligue a depuis disparu.
2005 : des tableaux de Cézanne joués aux ciseaux
Fin avril 2005, le Wall Street Journal raconte une drôle d'histoire. Takashi Hashiyama, président de Maspro Denkoh, une entreprise japonaise de matériel de télévision, veut vendre aux enchères la collection impressionniste de sa société. Elle comprend un paysage de Cézanne estimé jusqu'à 16 millions de dollars, ainsi que des œuvres de Picasso et de Van Gogh. Incapable de choisir entre Christie's et Sotheby's, il leur demande de s'affronter au Pierre Feuille Ciseaux. D'après le journal, repris par la presse américaine, les présidents des filiales japonaises des deux maisons ont dû écrire leur choix sur un papier plutôt que de montrer leur main.
Christie's a écrit Ciseaux, Sotheby's Feuille : Christie's a remporté la vente. Le récit le plus connu, repris notamment par Mental Floss, ajoute que Christie's avait consulté les jumelles de 11 ans d'un collègue, Flora et Alice, pour qui la pierre était trop évidente et les ciseaux battaient la feuille. Côté Sotheby's, on aurait expliqué qu'il s'agissait d'un jeu de hasard et qu'on n'y avait pas beaucoup réfléchi. Ces détails viennent de la presse et ne sont pas vérifiables autrement. L'anecdote ne prouve rien sur la stratégie : sur une seule manche, chaque geste avait une chance sur trois de gagner, quelle que soit la réflexion derrière. Elle montre en revanche le réflexe de tout joueur humain face à un autre humain : chercher à deviner ce que l'autre va croire.
1999 : la compétition des programmes
Reste la question la plus intéressante : un programme peut-il battre ses adversaires au PFC sans voir leur main ? En septembre 1999, Darse Billings, chercheur à l'université de l'Alberta, organise la First International RoShamBo Programming Competition. Chaque programme affronte tous les autres en matchs de 1 000 manches, et un match n'est gagné que si l'écart dépasse 50 manches.
Billings prévient les candidats dans la FAQ du concours : inutile d'envoyer un programme qui joue au hasard. Il est assuré de finir au milieu du classement, parce qu'il ne peut pas exploiter les programmes faibles. Le hasard ne perd contre personne, mais il ne gagne contre personne non plus. Pour monter au classement, il faut lire les adversaires prévisibles, et ne pas devenir prévisible soi-même.
Le vainqueur, Iocaine Powder, écrit par Dan Egnor, tire son nom de la scène de la coupe empoisonnée du film Princess Bride (1987), où deux personnages essaient de deviner ce que l'autre a deviné. Le programme cherche dans l'historique les suites de coups déjà vues, puis se demande à quel niveau de raisonnement l'adversaire se trouve : se contente-t-il de prédire mes coups, ou prédit-il que je le prédis ? Il garde la méthode qui a le mieux marché jusque-là. À la deuxième édition, en juillet 2000, Iocaine Powder termine troisième, derrière Greenberg d'Andrzej Nagorko et Meminator de Doug Meserve.
Refaire l'expérience : biais, hasard et tournoi
Nous avons rejoué ces idées avec un petit programme. D'abord, un joueur qui joue Pierre une fois sur deux, contre un adversaire qui compte ses gestes et joue ce qui bat le plus fréquent. Le compteur repère vite la pierre et joue Feuille : le joueur perd 38,4 % des 10 premières manches, puis, une fois lu, une manche sur deux, n'en gagnant qu'une sur quatre (avec ses Ciseaux) et faisant nul une sur quatre. Ensuite, un joueur qui tire au hasard, un tiers chacun, contre les mêmes adversaires : il gagne, fait nul et perd un tiers des manches, quoi qu'ils fassent. C'est le calcul exact, que la simulation retrouve. Enfin, un mini-tournoi de six programmes, chacun contre chacun en matchs de 1 000 manches et avec la règle des 50 manches d'écart, répété 200 fois :
| Rang | Programme | Solde moyen de manches par tournoi | Matchs gagnés / nuls / perdus |
|---|---|---|---|
| 1 | Joue ce qui bat le dernier coup adverse | +1 615 | 54,2 % / 45,0 % / 0,8 % |
| 2 | Compte les gestes adverses | +522 | 40,2 % / 19,3 % / 40,5 % |
| 3 | Cycle Pierre, Feuille, Ciseaux | +165 | 20,3 % / 78,9 % / 0,8 % |
| 4 | Hasard pur | +2 | 3,0 % / 94,9 % / 2,1 % |
| 5 | Pierre une fois sur deux | -308 | 1,2 % / 64,4 % / 34,4 % |
| 6 | Toujours Pierre | -1 996 | 0,5 % / 58,7 % / 40,8 % |
Le programme au hasard finit exactement là où Billings l'annonçait, au milieu, avec un solde proche de zéro et presque uniquement des matchs nuls. Les deux premiers ont gagné leurs points sur le dos des joueurs prévisibles. Ce classement dépend évidemment des participants choisis : c'est toute la leçon des tournois de programmes, où l'on ne gagne qu'en exploitant les faibles.
Ce qu'il faut retenir, et ce que fait notre ordinateur
- Le robot de Tokyo ne prédit rien : il voit ta main se former et réagit en quelques dizaines de millisecondes, bien plus vite que les 180 à 200 millisecondes d'un temps de réaction humain.
- Les grands championnats ont été des événements à moitié sérieux, et les plus gros gains venaient d'un sponsor.
- Contre un humain, on cherche à deviner l'autre, comme Christie's en 2005, mais une seule manche reste un tirage au sort.
- Contre des programmes, le hasard ne perd pas mais ne gagne pas : la victoire va à ceux qui lisent les autres.
L'ordinateur de notre Pierre Feuille Ciseaux en ligne est du côté des programmes de 1999, pas du robot de Tokyo : il choisit son geste à partir de tes seuls coups passés, sans jamais voir celui que tu joues. En Facile, il tire au hasard ; en Normal, il contre un geste que tu viens de jouer deux fois de suite ; en Difficile, à partir de la 4e manche, il compte plutôt tes gestes et cherche si tes trois derniers coups sont déjà apparus dans la partie. Le hasard reste ton bouclier, comme l'explique notre article sur l'équilibre de Nash, et notre guide de stratégie t'aide à passer de la défense à la lecture de l'adversaire.
Sources
- Evan Ackerman, « Robot Hand Beats You at Rock, Paper, Scissors 100% Of The Time », IEEE Spectrum, 26 juin 2012 : spectrum.ieee.org
- Yugo Katsuki, Yuji Yamakawa, Masatoshi Ishikawa, « High-speed Human / Robot Hand Interaction System: Rock-Paper-Scissors Robot System with 100% Winning Rate », HRI'15 Extended Abstracts, ACM, 2015, p. 117-118 : doi.org/10.1145/2701973.2701984
- Bob Kosinski et John Cummings, « The Scientific Method: An Introduction Using Reaction Time », dans Tested Studies for Laboratory Teaching, ABLE, vol. 20, p. 63-84 :ableweb.org
- A. Jain et coll., « A comparative study of visual and auditory reaction times… », International Journal of Applied and Basic Medical Research, 2015, 5(2) : pmc.ncbi.nlm.nih.gov
- « Settling auction house feud was kid's stuff » (Brooks Barnes et Miho Inada, The Wall Street Journal), The Spokesman-Review, 1er mai 2005 : spokesman.com
- « Business deal is child's play », Associated Press, NBC News, 29 avril 2005 : nbcnews.com
- Article de Mental Floss sur la partie de 2005 entre Christie's et Sotheby's, juin 2015 : mentalfloss.com
- « World championship draws Rock, Paper, Scissors fans », The Seattle Times, 19 octobre 2003 : seattletimes.com
- « Inside the World of Professional Rock Paper Scissors », Priceonomics, 2014 : priceonomics.com
- « Bud Light Readies Rock Paper Scissors Events », Chief Marketer, 7 décembre 2006 : chiefmarketer.com
- « USA Rock Paper Scissors League », Wikipédia (anglais) : en.wikipedia.org
- ICGA, page RoShamBo (compétitions de 1999 et 2000, programmes et résultats) : icga.org ; sommaire de l'ICGA Journal, vol. 23, n° 1, mars 2000 (articles de D. Billings et D. Egnor) : icga.org
- Darse Billings, FAQ du concours publiée sur comp.ai.games, septembre 1999 : groups.google.com
- « Playing Iterated Rock-Paper-Scissors with an Evolutionary Algorithm », IJCCI 2019, SciTePress, p. 205-212 : scitepress.org