J’ai retrouve récemment un article du GLMF qui traitait de cette intelligence artificiel assez étonnante.

En effet Minasi bat quasi systématiquement les joueurs humains au jeu de Pierre-Papier-Ciseaux : une étude portant sur un nombre important de parties montre que Minasi ne perd pratiquement jamais sur une partie d’une centaine de coups. Je me suis empressé de coder un programme exploitant Minasi et les résultats sont la : je n’ai jamais gagné contre elle sur une vingtaine de partie en 10 points gagnant !

Le jeu Pierre-Papier-Ciseaux

Ce jeu (que j’abrégerai désormais PPC) est sans doute l’un des plus simple au monde, deux joueurs choisissent simultanément un coup parmi les trois permis : la pierre(le joueur montre alors son poing fermé), la feuille (la main a plat), et les ciseaux (l’index et le majeur formant une espèce de V). La pierre l’emporte sur les ciseaux, les ciseaux sur la feuille et cette dernière sur la pierre. Si les deux joueurs jouent le même coup, personne ne remporte de points. La partie s’arrête lorsqu’un joueur atteint un nombre de points fixé en début de partie.

D’apparence absolument pas ludique, le jeu devient intéressant si l’on pousse la réflexion un peu plus loin que « je joue au hasard et je prie pour avoir de la chance « , il existe même des championnats du monde de PPC ! Les « champions » essayent de deviner ce que va jouer l’adversaire et réagissent en conséquence, le temps de réflexion est limité et court ce qui oblige les joueurs a compter non seulement sur la stratégie mais aussi sur leur intuition. On remarque donc que le PPC est une forme simplifiée de Poker ou l’on ne garde que l’analyse du comportement du joueur (on peut retarder la divulgation de son coup pour voir les gestes esquissés par son adversaire), l’instinct, et la stratégie en occultant le stress lié a l’argent et le hasard des cartes.

Une partie de PPC analysé : la finale du championnat du monde 2003 entre Krueger et Rigaux

On va utiliser la notation anglaise pour supprimer toutes ambiguïté : R pour pierre(rock), P pour papier(paper) et S pour ciseaux (sissors).

Au début de la partie, Rigaux joue un triplement pierre, imaginant que son adversaire pensera qu’il n’aura pas l’audace de jouer une troisième fois le même coup, Krueger ne se fait pas avoir et joue papier ce qui lui permet de remporter le point. Le quatrième coup est très intéressant, Krueger prends un risque en jouant ciseaux, Rigaux pouvant quadrupler pierre et ainsi gagner le point, mais Krueger pense qu’il n’en aura pas le courage, en effet il vient de perdre le point en jouant pierre… le choix des ciseaux est donc optimal : Krueger fait au pire match nul sur les 2 coups possibles de Rigaux.

Il y a deux possibilités pour analyser le coup de Rigaux, ces deux possibilités sont dépendantes du fait qu’il est perdu le point précédent et a donc un « désavantage psychologique » :

Il a pu joue le coup complètement au hasard (probable)

Il a fait la même réflexion que Krueger mais préfère ne pas risquer le quadruplement de pierre et donc s’assure le match nul.

Le reste de la partie est beaucoup plus difficile a analyser : pour le cinquième coup on pourrait imaginer que Krueger pense que Rigaux va retenter la technique du triplement avec ciseaux cette fois-ci et joue donc papier pour contrer… Je n’ai pas vraiment d’idée pour le reste et je vous laisse le soin de commenter la suite.

Le hasard et l’homme

Faites ce petit test chez vous : essayer de jouer aléatoirement à PPC et regarder le pourcentage de coup que vous avez joués(Bien entendu il ne faut pas tenter de tricher en faisant tout le temps R-P-S-R-P-S… ce n’est plus de l’aléatoire puisqu’une séquence est répétée !) .

Voici ce que j’obtiens :

On est quand même relativement loin de l’aléatoire théorique (33-33-34) !

L’Homme est en effet souvent incapable de comprendre la notion de hasard et a fortiori de le produire et c’est ce qu’exploite Minasi.

Minasi, ou comment détruire tout plaisir ludique

La stratégie optimale pour battre Minasi est de joue complètement au hasard mais on a vu précédemment que le hasard était incompatible avec l’homme : dommage, n’est ce pas ?

Le plaisir de jouer au jeu de PPC vient quand l’on réussit a cacher notre intention a l’adversaire ou quand, au contraire, on découvre celle de notre partenaire et on parvient a la contrer. Le problème c’est que la première source de plaisir est quasiment impossible a atteindre avec Minasi et la seconde complètement impossible ce qui détruit tout plaisir ludique, l’étonnement succède vite a la frustration et on vient a se demander si Minasi ne triche pas (c’est souvent le cas dans des jeux-vidéos comme les STR ou l’IA par exemple ne souffre pas du « brouillard de guerre »).

Minasi fonctionne pourtant d’une façon relativement simple :

• elle stocke en mémoire tout l’historique de la partie sous la forme d’une chaine de caractère du type « PrSpSrSsRp » ou les lettres en majuscules désignent les coups joués par Minasi et ceux en minuscule par le joueur humain.
• Elle va ensuite recherche la plus longue séquence de coup qui s’est déjà produit dans le passé.

  Ex : RsPpPsSrPp : Minasi cherche d’abord une séquence de longueur 1, c’est a dire est ce que ‘p’ a déjà été joué auparavant, elle en trouve une a l’indice 3 (on indice a partir de 0 en informatique). Puis elle cherche une séquence de longueur 2 c’est a dire ‘Pp’, elle en trouve une a l’indice 2. Il n’y a pas de séquence de longueur 3.

• On regarde le coup joué après la séquence repéré et on agit en conséquence.

  Ex : RsPpPsSrPp :le coup joué après la séquence est ’s’, Minasi va donc jouer R pour gagner.

• Si il y a plusieurs séquences, on compte le nombre d’occurrences des coups joués par l’Homme, on tiendra compte uniquement du plus grand.

  Ex : PpPpSrPpSpSsPp : Il y a deux séquences ‘Pp’ suivit de ‘p’ et une séquence ‘Pp’ suivit de ‘r’, Minasi choisira donc de contrer ‘p’ en jouant ‘S’

• Si il y a plusieurs coups avec le même nombre d’occurrence Minasi choisira au hasard entre ceux-ci.

Minasi est donc vulnérable en début de partie ou elle est prévisible, pour la battre au final il faut essayer de gagner un maximum de points au début : pour cela, un crayon et un bout de papier, notez l’historique des coups et réfléchissez comme elle, cela devient bien sur impossible au fur et a mesure de l’évolution de la partie…

le Code Source C++ d’un programme exploitant Minasi

En m’excusant d’avance de la saleté du code.

Show ▼

Sources :

Fabrice Rossi : « l’ordinateur peut-il lire dans votre esprit », GLMF n° 58 p.34

Article wikipedia sur le hasard