David Madore's WebLog: Pierre-Papier-Ciseaux, thème et variations

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #1829 [older|newer] / Entrée #1829 [précédente|suivante]:

(mercredi)

Pierre-Papier-Ciseaux, thème et variations

Le jeu de Pierre-Papier-Ciseaux est probablement le deuxième jeu le plus simple de l'Univers. Avant d'en parler, je devrais donc commencer par décrire le premier, qui n'a pas de nom à ma connaissance, et je manque d'inspiration pour lui en trouver un. Les règles sont : l'un des deux joueurs (convenu à l'avance, disons Alice) choisit en secret le nom de l'un des deux joueurs, tandis que l'autre joueur (disons Bob) choisit soit le mot perd soit le mot gagne ; si la phrase formée des deux mots choisis est Alice gagne ou Bob perd, alors Alice gagne, tandis que si c'est Alice perd ou Bob gagne, alors Bob gagne. De façon plus abstraite : chacun des deux joueurs choisit un bit en secret, on calcule le XOR de ces bits, et s'il vaut 0 c'est Alice qui gagne tandis que s'il vaut 1 c'est Bob (ou toute autre convention équivalente choisie à l'avance). Ce jeu fait partie des jeux dits à somme nulle, c'est-à-dire que les joueurs sont exactement adversaires, les gains de l'un étant par définition les pertes de l'autre (par opposition à un jeu comme le dilemme du prisonnier, où il est possible pour que les deux joueurs gagnent ou perdent dans différentes proportions, et il y a donc un sens à chercher à coopérer) ; et à information incomplète imparfaite, parce que les deux joueurs choisissent leur option simultanément, donc dans l'ignorance du choix de l'autre (par opposition aux jeux à information parfaite, comme les échecs, qui sont l'objet de la théorie combinatoire des jeux). En pratique, le choix simultané peut se faire en écrivant sur un papier (si on est très formaliste, dans un pli scellé), ou, si on est cryptographe, en utilisant une fonction de hachage pour s'engager sur un choix sans divulguer celui-ci. Ou en montrant simultanément un choix de la main (par exemple, Alice pourrait pointer du doigt l'un des deux adversaires, tandis que Bob fait le signe du pouce vers le haut ou vers le bas).

La stratégie à suivre est tout à fait évidente : si Bob avait connaissance du nom choisi par Alice, il aurait intérêt à choisir perd lorsque Alice choisit Alice et gagne lorsque Alice choisit Bob ; donc Alice ne doit pas divulguer la moindre information sur son choix, et doit choisir aléatoirement et de façon équiprobable, indépendante des choix précédents, le nom qu'elle choisit ; Bob, évidemment, a intérêt à choisir aléatoirement entre gagne et perd. On dit qu'on a affaire là à la stratégie (mixte) optimale[#] du jeu pour l'un et l'autre joueur (qui se caractérise formellement par le fait qu'il s'agit d'une distribution de probabilité sur les options du jeu dont l'espérance de gain contre n'importe quelle option de l'adversaire est au moins aussi bonne que celle de toute autre telle distribution). Les deux stratégies optimales jouées l'une contre l'autre constituent un équilibre de Nash, mais la notion en question est un peu idiote dans le cas d'un jeu à somme nulle à cause d'un théorème de von Neumann qui assure, pour parler de façon très vague, que dans ce cas les stratégies optimales des deux joueurs se répondent bien l'une à l'autre (en maximisant le pire gain possible on maximise précisément le gain contre la stratégie optimale de l'adversaire). Le jeu très simple dont j'ai parlé est à valeur nulle, c'est-à-dire que quand les deux joueurs jouent leur stratégie optimale, aucun n'est privilégié, ce qui est le cas si, mais pas seulement si, il existe une symétrie totale entre les joueurs.

Ce jeu a beau être très simple, et sa stratégie optimale évidente, quand on y joue dans la vraie vie, tirer des valeurs au hasard n'est ni très facile ni très satisfaisant, et on se retrouve à jouer sur la psychologie de l'adversaire (comme dans la célèbre Battle of Wits de Princess Bride), surtout quand on joue plusieurs coups de suite : chacun essaie de se prévoir quel sera le choix de l'autre (en tenant compte du fait que l'autre essaie de prévoir, etc.), et de choisir le coup gagnant en fonction de cela. Je me souviens avoir joué à une variante de ce jeu contre un ami quand j'étais petit (sous la forme : mon adversaire choisit une carte dans un jeu et je dois deviner si elle est rouge ou noire), et avoir gagné une vingtaine de fois d'affilée, si bien que mon ami commençait à se dire que je lisais dans ses pensées. Mais bon, ce petit jeu n'a de sens que parce qu'on joue contre un humain qui joue aussi au même petit jeu : si l'un des deux joueurs tire son choix aléatoirement, l'autre n'a rien d'intelligent à faire, dans tous les cas son espérance de gain sera nulle. Autant jouer à pile ou face, et, bien sûr, c'est essentiellement ce qu'on est en train de faire.

Le jeu de Pierre-Papier-Ciseaux est seulement différent en ce qu'on a symétrie entre les joueurs : contrairement au jeu précédent, les deux joueurs ont les mêmes options, Pierre, Papier et Ciseaux (et on joue généralement avec des signes codifiés de la main). Les options elles-mêmes admettent une symétrie d'ordre 3 : le Papier bat la Pierre, les Ciseaux battent le Papier, et la Pierre bat les Ciseaux ; deux options identiques font match nul ; il n'y a évidemment pas une option qui batte les deux autres. La stratégie optimale, nécessairement la même pour les deux joueurs à cause de la symétrie, et qui peut donc se caractériser par le fait qu'il s'agit d'une distribution de probabilités sur les options qui assure un gain positif ou nul contre toute option de l'adversaire, est évidemment de jouer chacun de Pierre, Papier et Ciseaux avec probabilité 1/3 (et, comme toujours, indépendamment à chaque coup). Comme pour le jeu précédent, quand on y joue dans la vraie vie, il y a souvent un élément de psychologie qui intervient, on peut se rendre compte par exemple que son adversaire préfère telle ou telle option et chercher à jouer celle qui la bat, ou bien au niveau méta chercher à faire croire à son adversaire qu'on préfère telle option pour qu'il joue celle qui la bat et soi-même jouer la troisième, et ainsi de suite. Cet aspect psychologique fait l'intérêt (très relatif…) du jeu entre humains, mais pour l'analyse mathématique, il est purement parasite. Et si on n'a aucune information sur l'adversaire, il n'y a vraiment rien de mieux à faire que de jouer selon la stratégie optimale abstraite, i.e., au hasard.

[Ajouté 2011-01-20 : webcomic pertinent…]

Le jeu de Pierre-Papier-Ciseaux est rapidement très ennuyeux, et des gens ont cherché à le rendre plus intéressant. Certains essaient de le faire en renommant simplement les options : par exemple, certains enfants jouent à Papier-Ciseaux-Puits, qui est exactement le même jeu si ce n'est que Pierre s'appelle Puits. Mais rapidement, il devient tentant d'étendre l'ensemble des options. Si on a joué à Pierre-Papier-Ciseaux et à Papier-Ciseaux-Puits, il est tentant de jouer à Pierre-Papier-Ciseaux-Puits : il reste un duel à résoudre, et on le résout en disant que la Pierre tombe dans le Puits (donc perd contre lui). Quelle est la stratégie gagnante à Pierre-Papier-Ciseaux-Puits ? On peut la calculer en utilisant la théorie générale de la programmation linéaire (spécifiquement l'algorithme du simplexe), mais la solution est assez claire si on se rend compte que l'option Puits domine l'option Pierre (quelle que soit l'option choisie par l'adversaire, jouer Puits est au moins aussi bon que jouer Pierre, et dans certains cas c'est strictement meilleur) : donc la stratégie optimale ne joue jamais Pierre, et du coup il est évident qu'elle joue Papier, Ciseaux et Puits de façon équiprobable (probabilité 1/3 chacun). Si on va jouer à ce jeu contre quelqu'un d'un peu naïf, il y a de fortes chances pour qu'il ne se rende pas compte qu'il ne faut jamais choisir Pierre, et en jouant Papier, Ciseaux et Puits de façon équiprobable on obtiendra statistiquement un gain contre lui.

J'ai aussi entendu parler de la variante suivante : à côté de Pierre, Papier et Ciseaux, on rajoute une nouvelle option, disons Maman, qui bat à la fois Pierre, Papier et Ciseaux ; puis, comme il faut bien que Maman ne soit pas imbattable, on ajoute une option Chocolat, qui bat Maman ; en revanche, n'importe quoi d'autre bat Chocolat, et Maman bat tout sauf Chocolat. La stratégie optimale est évidente quand on y réfléchit un peu (ce que j'encourage le lecteur à faire avant de lire ce qui suit) : il suffit de se rendre compte qu'on a en fait affaire à un jeu de Pierre-Papier-Ciseaux sur deux niveaux, sur le premier niveau on a maman-chocolat-(pierre+papier+ciseaux), et sur le second niveau, on a Pierre-Papier-Ciseaux tels que nommés ; du coup, la stratégie optimale joue chacune des options Maman et Chocolat avec probabilité 1/3, et chacune des options Pierre, Papier et Ciseaux avec probabilité 1/9. (Pour vérifier que c'est bien une stratégie optimale, il suffit de vérifier que son gain contre n'importe quelle option fixée de l'adversaire est positif ou nul — en l'occurrence, toujours nul.) C'est intéressant, parce que les gens ne s'imaginent généralement pas trop ce résultat (ils ont tendance à prévoir une distribution plus uniforme, dans le jeu que je viens de décrire, et notamment avec trop peu de Chocolat et trop de Pierre, Papier et Ciseaux).

Mais ce qui rend Pierre-Papier-Ciseaux intellectuellement satisfaisant, ce n'est pas seulement que les deux joueurs jouent des rôles symétriques, mais que c'est aussi le cas des trois options (formellement, pour chaque paire (x,y) d'options, il existe une permutation des options, envoyant x sur y, et qui préserve la matrice du jeu ; en l'occurrence, les permutations préservant la matrice du jeu sont les permutations cycliques de Pierre-Papier-Ciseaux). Si on cherche à faire un jeu semblable avec cinq options, autrement dit si on cherche à orienter toutes les arêtes et diagonales d'un pentagone (i.e., fabriquer un tournoi sur cinq sommets) de façon à ce que tous les sommets jouent un rôle symétrique (dans le sens que je viens de définir), il y a une unique façon de faire, comme il est assez facile de s'en convaincre (il y a forcément une permutation cyclique des cinq options qui les laisse invariantes, on peut les numéroter 0,1,2,3,4 selon cet ordre cyclique, on peut supposer sans perte de généralité que 1 bat 0, donc 2 bat 1, 3 bat 2, 4 bat 3 et 0 bat 4, et il reste simplement à décider si 0 bat 2 ou 2 bat 0 ; or si on décide que 0 bat 2, disons, quitte à renuméroter 0,1,2,3,4 en 0,2,4,1,3, on se ramène à l'autre situation). Ce jeu a connu une certaine popularité nerdesque sous le nom de Pierre-Papier-Ciseaux-Lézard-Spock (décidément, Wikipédia a des articles sur n'importe quoi) ; évidemment, la stratégie optimale est, à cause de la symétrie entre les options, de toutes les jouer de façon équiprobable (c'est-à-dire avec probabilité 1/5). En revanche, si on veut 7 options, il y a deux jeux (tournois) essentiellement différents : l'un d'entre eux est assez évident et consiste à dire que 3, 2 et 1 battent 0 (donc aussi : 4, 3 et 2 battent 1 ; 5, 4 et 3 battent 2 ; 6, 5 et 4 battent 3 ; 0, 6 et 5 battent 4 ; et ainsi de suite cycliquement) ; l'autre, en revanche, où 1, 2 et 4 battent 0, est plus intéressant car il a plus de symétries (il en a 21 alors que le précédent n'a que les 7 permutations cycliques des 7 options). Reste à trouver sept noms populaires à mettre sur les options (heureusement ce n'est pas ça qui manque : les sept péchés capitaux ? les sept nains ?) de façon à justifier ces relations précises, et à populariser le jeu…

Ceux qui savent ce que ceci signifie pourront considérer plus généralement le tournoi suivant : si q est une puissance d'un nombre premier qui est congrue à 3 modulo 4, sur le corps à q éléments on peut définir la relation x bat y lorsque xy est un carré (non nul) dans ce corps ; alors ce tournoi a un multiple de q·(q−1)/2 automorphismes ; je suis sûr qu'il y a toutes sortes de choses très élégantes à en dire.

Quant à ceux qui trouvent dommage que les mathématiques arrivent pour nous dire il faut jouer au hasard à un jeu où on espérait faire preuve de psychologie, je peux proposer le jeu très simple suivant dont je ne sais absolument pas faire l'analyse mathématique : Alice et Bob disposent chacun initialement d'un certain nombre (entier, égal) de points, et à chaque tour chacun décide secrètement le nombre de points qu'il va engager pour ce tour, ce nombre de point sera forcément perdu pour lui aux tours suivants (i.e., décompté de son total), mais le gagnant du tour est celui qui a engagé strictement plus de points que l'autre ; on continue jusqu'à ce que les deux joueurs engagent tous les deux zéro points (ce qui est nécessairement le cas s'il leur reste zéro points) pendant un nombre de tours convenu à l'avance, et le gagnant est alors celui qui a gagné le plus grand nombre de tours (indépendamment du nombre de points par lesquels il les a gagnés, ou du nombre de points restants s'il y en a). Il existe de nombreuses variantes de ce jeu, toujours dans l'esprit engager des points augmente les chances de gagner un tour mais affaiblit pour les tours suivants. (En théorie ce genre de jeux serait susceptible d'être amené à l'analyse comme une matrice de gain de toutes les stratégies déterministes possibles d'Alice contre toutes les stratégies déterministes possibles de Bob, mais en pratique cette matrice serait d'une taille monstrueuse.) Je n'ai aucune idée de ce qu'il faut faire pour bien jouer (j'ai vaguement pensé essayer de faire tourner sur ordinateur un algorithme évolutif pour déterminer de bonnes stratégies, mais je n'ai jamais mis en pratique).

[#] J'écris la stratégie optimale, mais elle peut très bien ne pas être unique dans un jeu à somme nulle général (l'ensemble des stratégies optimales forme un convexe). Ceci étant, dans les jeux en tournoi, comme je les suppose implicitement, à l'exemple de Pierre-Papier-Ciseaux (formellement : les deux joueurs ont le même ensemble d'options, et le gain d'une option sur une autre vaut toujours ±1, sauf quand les deux options sont la même auquel cas il vaut 0), la stratégie optimale est effectivement unique, cf. le théorème 1.4 page 21 de ce papier (Fundamentals of Social Choice Theory, de Roger Myerson).

↑Entry #1829 [older|newer] / ↑Entrée #1829 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées