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 x−y 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).