L'incroyable IA de 1950 qui pouvait jouer GTO ou exploitant !

• 27 février 2020
• petiteglise
• 2324
•  PA  1
• 3 Commentaires

Nous sommes en 1950. John Nash vient de publier la théorie de l'équilibre qui porte son nom. Dans les laboratoires Bell, pépinière pour pionniers surdoués de l'informatique, un certain Hagelbarger crée une machine capable de jouer GTO ou exploitant. Son ami, le génie Claude Shannon, l'améliorera ensuite avant de dévoiler ses secrets dans un article intitulé "a Mind-Reading (?) machine".

Le plus simple des jeux à stratégie mixte

Pierre-Feuille-Ciseaux est l'exemple toujours rabâché pour illustrer le jeu le plus simple avec un équilibre de Nash comme solution optimale. Peut-on imaginer encore plus simpliste que jouer pierre, feuille et ciseaux chacun avec une fréquence de 1/3 ? Et bien oui ! Je vous présente le jeu des pièces appareillées.

• Deux personnes s'affrontent avec des pièces de monnaie.
• Les joueurs choisissent le côté de leur pièce (pile ou face) .
• Les deux joueurs montrent leur pièce au même moment.
• Un joueur (désigné à l'avance) remporte les deux pièces si elles sont appareillées (pile-pile ou face-face). C'est le matcher.
• L'autre joueur remporte les deux pièces si elles sont désappareillées (pile-face ou face-pile). C'est le mismatcher.

Le tableau des gains :

Il s'agit du tableau des gains de base, en version symétrique. On peut imaginer des versions dissymétriques où les gains ne sont pas tous égaux, voire où un camp est Ev+.

Ici la stratégie GTO est évidemment de jouer pile et face chacun à une fréquence de 50%.

Il est difficile d'imaginer que l'on puisse véritablement avoir un edge face à un humain "compétent". Mais déjà à l'époque, il était connu que les humains étaient incapables de simuler le hasard. Hagelbarger, un ingénieur des fameux Bell Labs a décidé d'exploiter ce biais en créant son outguessing machine, sa machine anticipatrice.

La première IA à pouvoir jouer GTO ou exploitant

La machine est basée sur la prémisse que les humains n'allaient pas jouer GTO. Partant de là, elle appliquait deux principes :

1.  Pour ne pas être exploitable, quand la machine était perdante, elle jouait GTO, c'est à dire pile ou face à 50%.
2. Dès que la machine était gagnante, elle essayait d'exploiter son adversaire en tentant de prédire ses coups.

Hagelbarger a rendu sa machine attractive et ludique : elle était bordée d'une rangée de 25 ampoules vertes et d'une rangée de 25 ampoules rouges. A chaque fois que la machine remportait un coup, une ampoule rouge s'allumait et à chaque fois que l'humain remportait un coup, une ampoule verte s'allumait. Le but était d'allumer sa rangée en entier avant la machine. Hagelbarger a fait tester sa machine par ses collègues. Certains essayaient de prédire les coups de la machine, d'autres de simuler au mieux le hasard pour être inexploitables. 

Au final, après 9 795 parties (en 25 pile ou face), la machine en a gagnées 5 218 soit 53.3%. Un avantage suffisant pour être significatif.

Le génie Claude Shannon

Albert Einstein avait dit de Claude Shannon qu'il était "très, très brillant". Et encore, c'était avant que Shannon ne publie The Mathematical Theory of Communication considéré comme l'ouvrage fondateur de l'informatique moderne. Shannon était un collègue et ami de Hagelbarger aux Bell Labs, où on lui pardonnait toutes ses excentricités, comme arriver en retard, partir en avance, déambuler dans les couloirs en monocycle tout en jonglant, créer des inventions plus ou moins utiles comme un des premiers programmes d'échecs (Roi+Tour vs Roi), un robot solveur de Rubik's cube ou une souris mécanique capable de trouver son chemin dans un labyrinthe. Son invention la plus connue et la moins utile est la surréaliste Ultimate Machine (ou machine laisse-moi-tranquille) : l'utilisateur appuye sur l'interrupteur, le bras de la machine sort de la boîte, réappuye sur l'interrupteur et retourne se cacher dans la boite qui se referme...

La outguessing machine de Hagelbarger a évidemment tout de suite plu à Shannon, qui n'a pas pu s'empêcher de l'améliorer. 

La version de Shannon a fait sensation dans les laboratoires Bell. Les scientifiques remplis de curiosité et de fierté ont défilé tour à tour pour affronter la machine, mais aucun n'a pu rivaliser. Ici le choix était gauche ou droite, que l'on indiquait avec un ancêtre de joystick, mais le principe était le même qu'au jeu des pièces appareillées. On a cru un moment que la machine avait trouvé son maître quand un mathématicien du nom de Hirzebruch a remporté les 13 premières parties d'affilée ! Mais l'IA s'est adaptée et a remporté 16 des 17 parties suivantes ! Le mathématicien n'a ensuite jamais pu revenir au score. 

Hagelbarger et Shannon ont évidemment fait jouer leurs machines l'une contre l'autre. La "Mind-Reading (?) " de Shannon a battu la "Outguessing" de Hagelbarger 55% à 45%.

Seul Shannon lui-même arrivait à battre son invention.

Vous pouvez jouer en ligne contre une version de la Mind-Reading (?) Machine de Shannon.

Le secret de ces IA avant l'heure

La machine de Shannon est d'autant plus impressionnante qu'elle disposait d'une mémoire de seulement 16 bits, soit 2 octets ! (Au passage, c'est à The Mathematical Theory of Communication de Shannon que l'on doit la popularisation du concept de bit)

Shannon avait divisé l'historique des résultats en 8 configurations distinctes. Pour chacune de ces configurations, la machine enregistrait les deux derniers choix de l'adversaire. 0 si le joueur rejouait la même chose, 1 si le joueur changeait. 8*2 paires de 0 et 1 = 16 bits soit 2 octets, le compte est bon. 

Voici une représentation de la mémoire de la machine.

L'algorithme est simplissime : si l'utilisateur a été consistent pour une configuration donnée lors de ses avant-dernier et dernier choix, la machine considère qu'il le sera à nouveau. Si l'utilisateur n'a pas été consistent ou si la machine n'a pas encore d'info enregistrée, elle tire au sort son coup.
Dans l'exemple donné, on remarque que les deux dernières fois que l'humain a gagné, rejoué et gagné, il a ensuite changé. La machine considère donc que lorsque ce cas se présentera encore, l'humain sera consistent et changera une nouvelle fois.
Au début, la machine joue au hasard, le mathématicien susmentionné a donc eu pas mal de chances de gagner ses 13 premières parties !

Évidemment, en connaissant l'algorithme, on peut battre la machine et même marquer jusqu'à 75% des points. Se souvenir de tous les résultats de tête est néanmoins complexe, même pour quelqu'un de la trempe de Shannon et le créateur de la machine ne la battait que de 60% environ.

La machine disposait d'un compteur de victoires et de défaites. Au total, elle a gagné 5010 parties, en a perdues 3507, pour un score de 59% ! Un sacré edge pour une machine avec 2 octets de mémoire jouant à un jeu si simpliste face à la crème des mathématiciens et informaticiens de l'époque !

L'erreur de Hagelbarger était d'avoir voulu réaliser une machine trop complexe : en partant des mêmes 8 situations, la machine enregistrait les 4 derniers choix et calculait le pourcentage de chaque choix. Plus le pourcentage était élevé, plus la machine considérait comme probable que ce choix soit effectué à nouveau. En outre, comme expliqué plus haut, la machine disposait d'une stratégie défensive consistant à jouer de manière aléatoire quand elle était perdante. La machine de Hagelbarger parait plus subtile, nuancée, en un mot meilleure que celle de Shannon, mais les résultats ont donné raison à ce dernier.

Les biais humains au jeu des pièces appareillées

• Le matcher (celui qui remporte les pièces si elles sont appareillées) a en moyenne un meilleur score que le mismatcher.
• La raison est que le mismatcher essaye d'être aléatoire et le matcher tente de prédire ce que l'autre va faire. Autrement dit, il vaut mieux essayer de jouer exploitant que d'essayer de jouer GTO.
• Quand un humain essaye d'être aléatoire à pile ou face, il va avoir tendance à trop alterner. Sur un grand nombre de faux tirages de pile ou face, il y aura trop peu souvent 3, 4 ou 5 fois consécutives le même résultat par exemple.
• Même face à un jeu purement aléatoire (et donc ici GTO), les humains croient détecter des patterns et tentent de s'adapter.
• Quand on change les gains, par exemple le matcher gagne 3 en cas de pile/pile, 1 en cas de face/face, le mismatcher remporte 2 en cas de pile/face ou face/pile, les joueurs s'adaptent mal.

Bon après tout, il n'est pas si surprenant que les humains soient biaisés et se fassent exploiter par une machine, même si le fait qu'elle n'ait que 2 octets de mémoire mette un petit coup à l'ego. Après tout, notre cerveau n'a pas évolué pour comprendre les probabilités et si l'on est moins bon que les machines, on est évidemment les meilleurs du règne animal, vrai ?

Et bien non...

Vous savez peut-être que les chimpanzés nous battent aux jeux de mémoire à court terme, comme cliquer sur des nombres croissants qui ont été flashés une seconde.

Sachez que nos cousins sont bien meilleurs que nous aux jeux des pièces appareillées, dans une version où il faut cliquer sur des carrés à gauche ou à droite de l'écran ! Dans une étude publiée dans Nature, les chercheurs ont dévoilé que les chimpanzés ont fait mieux que des étudiants aux jeux des pièces appareillées, non seulement dans sa version symétrique (gain de 1 pour le matcher et le mismatcher) mais aussi dans des versions dissymétriques où l'équilibre de Nash n'est pas trivial. Les singes s'adaptaient très vite aux changements de gains. Même avec des gains dissymétriques où Nash ne consiste pas à jouer 50-50, les singes jouaient bien plus proches de la GTO que les humains !

Malheureusement, il n'y a encore pas eu à ma connaissance de match entre la machine de Shannon et un chimpanzé ! 

J'espère que cet article aura intéressé le joueur de poker que vous êtes, à défaut de vous avoir fait progresser. Il pourra cependant être utile de vous rappeler que nous sommes tous bien plus mauvais aux jeux de prédictions et bien moins capables de générer du hasard que nous le croyons. On comprend mieux pourquoi tous les bons joueurs de poker, dont tous les membres du team ATM, jouent toujours avec un générateur de nombres aléatoires à leurs cotés !

Pour aller plus loin :
Rock breaks scissors de William Poundstone.
Matching Pennies sur Wikipedia.
Chimpanzee choice rates in competitive games match equilibrium game theory predictions