Pierre, feuille, ciseaux…

Et de très intéressant… aurait dû ajouter Goethe : ainsi les mathématiciens ont transformé un jeu d’enfants Pierre-feuille-ciseaux en un riche modèle des interactions animales.

L’Américaine Andrea Farina, vainqueur du championnat du monde en 2007.
© RPS Championship

Qui n’a joué à ce jeu ? La pierre (P) casse les ciseaux, les ciseaux (C) découpent la feuille et la feuille (F) enveloppe la pierre. Deux joueurs, placent chacun leur main droite dans le dos, et choisissent l’un des trois symboles : le poing fermé pour la pierre, la main allongée pour la feuille, deux doigts en forme de ciseaux. Les deux joueurs dévoilent leur choix en avançant la main, parfois en proférant un cri. Si les deux choix sont identiques, ils recommencent, sinon le joueur qui détient le symbole le plus fort des deux a gagné le coup.

Le jeu est ancien et l’on en trouve des traces en Chine dès l’époque Ming (1368-1644). Il est connu dans le monde entier et ses variantes sont innombrables. On y joue avec un plus grand nombre de symboles, on ajoute le puits, le feu, l’eau, etc., ou alors avec d’autres triplets. Dans une version japonaise, les trois symboles sont le guerrier, le tigre et la mère du guerrier. Il y a aussi le feu, le serpent et l’eau, et encore le serpent, la grenouille et la limace.

Parmi les stratégies du type « jouer P avec la probabilité x, jouer F avec la probabilité y, jouer C avec la probabilité z », nommées stratégies mixtes, la stratégie correspondant aux coefficients x = y = z = 1/3 est imbattable : si vous l’adoptez, tout joueur sera, à la longue, ex æquo avec vous ; il ne pourra ni vous battre… ni même perdre s’il le souhaitait. Cette stratégie ne résoudra pourtant pas toutes les questions que pose le jeu. D’une part, un être humain est incapable d’engendrer dans sa tête des choix vraiment aléatoires avec des probabilités fixées à l’avance : celui qui souhaite jouer la stratégie mixte 1/3-1/3-1/3 ne le peut pas ! D’autre part, les joueurs humains utilisent l’information sur les coups déjà joués : ils ne peuvent pas s’en empêcher même s’ils essayent.

Le jeu est en partie psychologique et il y a parfois mieux à faire que la stratégie 1/3-1/3-1/3. Si, par exemple, vous remarquez que votre adversaire n’utilise pas P, alors en jouant invariablement C vous gagnerez toujours (s’il joue F, vous gagnez, s’il joue C, le coup est nul). Bien sûr, il risque de s’apercevoir de votre tactique et de se mettre à jouer P, ce qui vous perdra !

Certains logiciels jouent mieux que les êtres humains, car en repérant les régularités qu’ils adoptent (même quand ils font tout pour ne pas être régulier) leur attitude donne un léger avantage à une machine attentive et bien programmée. Le programme Sagace de Christophe Meyer exploite ainsi les faiblesses humaines.

Comme nous allons le voir dans la suite de cet article, joué sur un graphe, le jeu en apparence simplet engendre des comportements collectifs inattendus et délicats à élucider. Certains mécanismes découverts lors de récentes études expliquent les phénomènes de synchronisation et d’uniformisation et éclairent le maintien de la diversité dans le monde biologique.

Les règles du combat

Dans le jeu sur un graphe, un ensemble de points est fixé, les nœuds du graphe. Sur chacun est placé un symbole de type P (pierre), F (feuille) ou C (ciseaux). Certains couples de points sont reliés par les arcs du graphe.

Cette disposition constitue la configuration initiale dont l’évolution se fait selon un processus aléatoire : un nœud N est choisi au hasard équitablement (chaque nœud a la même probabilité d’être choisi) parmi tous les nœuds et un nœud N’ directement relié à N est choisi au hasard équitablement aussi. Si les deux symboles portés par N et N’ sont de même force, rien ne se produit, sinon le plus faible des deux symboles est remplacé par le plus fort qui occupe alors les deux nœuds N et N’. On recommence, en choisissant un nouveau nœud au hasard, etc. Les combats successifs permettent au gagnant de chaque rencontre d’occuper le terrain de l’adversaire. Ce processus d’évolution est répété un très grand nombre de fois (voir un exemple sur la figure ci-dessous).

Le jeu sur un anneau. Un anneau est composé de 12 nœuds chacun lié à ses deux voisins. Au départ on place 4 P, 4 C et 4 F. Le jeu consiste à tirer au hasard un arc liant deux nœuds, puis à faire jouer l’un contre l’autre les deux symboles (F l’emporte sur P, P l’emporte sur C et C l’emporte sur F). Le symbole qui gagne occupe alors les deux nœuds. Selon le hasard qui fait jouer ainsi les nœuds les uns contre les autres, soit le jeu préserve la variété, les trois symboles coexistent toujours, soit l’un des symboles finit par disparaître, ce qui entraîne la disparition d’un second symbole, tout l’anneau étant alors occupé par un symbole unique et inamovible (cette occupation unique devient quasi certaine quand le nombre de tirages d’arcs tend vers l’infini).

Dans cet exemple, le combat revient à choisir au hasard deux nœuds voisins de l’anneau, ce qui conduit soit au statu quo si les nœuds portent le même symbole, soit à un gain de territoire pour le plus fort. Si tout s’équilibrait, les zones ne feraient que se déplacer, chacune gardant en moyenne 4 éléments et tournant dans le sens des aiguilles d’une montre. Cependant, les tirages au sort des combats ne donnent pas des résultats parfaitement réguliers : les tailles des zones tenues par les C, les P et les F fluctuent et ces fluctuations s’amplifient. Inévitablement l’une des trois zones disparaît, ce qui entraîne la disparition d’une seconde zone et il ne reste plus qu’un seul symbole sur tout le terrain. Si la zone qui disparaît en premier est celle des C, les F envahissent tout ; si la zone des P disparaît, les C envahissent l’anneau et si les F disparaissent, les P dominent totalement et définitivement.

Dans le cas d’une configuration initiale irrégulière de C, de F et de P sur un anneau (même beaucoup plus grand) qu’on remplit en tirant au hasard les emplacements des C, des F et des P, l’évolution est de même type. Les déplacements de frontières des différentes zones homogènes amènent assez rapidement une configuration uniforme.

Cette évolution à long terme vers un gagnant définitif (imprévisible) est bien plus générale et se produit pour tout graphe connexe (un graphe connexe est un graphe d’un seul tenant, c’est-à-dire tel que deux nœuds sont toujours reliés par au moins un chemin). Le résultat est : « Pour tout graphe connexe et toute configuration initiale de pierres de feuilles et de ciseaux sur le graphe, la probabilité pour que le système se retrouve au bout d’un temps fini dans un état uniforme (l’un des symboles occupant tous les nœuds) est de 100 pour cent ». (Voir la démonstration exposée ci-dessous sous le titre On peut toujours uniformiser.)

Notons que cela n’interdit pas qu’il existe des suites de tirages particuliers assurant le maintien indéfini des trois symboles sur le graphe (tout comme si vous lancez un dé, vous pouvez obtenir une série ne comportant que des 6). Si l’on considère le graphe circulaire envisagé plus haut et que les arcs sont tirés les uns après les autres en tournant dans le sens des aiguilles d’une montre, il restera toujours des exemplaires des trois symboles. Le sens du résultat d’évolution à long terme est que ce type de suites de tirages préservant la diversité possède une probabilité nulle de se poursuivre à l’infini.

Vérification expérimentale

Nous allons voir que la réalité expérimentale est encore plus intéressante que la théorie mathématique qui indique un peu sèchement qu’au bout d’un certain temps, le système s’uniformise totalement.

Nous allons d’abord observer l’évolution de graphes complets, c’est-à-dire de graphes dont chaque nœud est relié à chaque autre (graphes ayant donc n(n – 1)/2 arcs pour n nœuds). De façon à visualiser les changements nous utilisons une grille carrée où deux cases sont liées qu’elles soient côte à côte sur le dessin ou qu’elles ne le soient pas.

Le jeu sur un graphe complet (où chaque nœud est relié à chaque autre). Pour visualiser l’évolution, on représente le graphe comme si les nœuds étaient disposés sur un damier. On part d’une configuration aléatoire des trois symboles Pierre, feuille, ciseaux (on utilise pour chacun une couleur, rouge, blanc ou bleu). On représente l’évolution en dessinant une étape du graphe tous les 100 combats. Dans un premier temps, le graphe reste à peu près homogène avec 33 pour cent de chacun des symboles. Au bout de 10 étapes (donc 1 000 combats sur un arc) la couleur bleue domine. Deux cents combats plus tard le rouge domine. Puis c’est le blanc, puis le bleu, cette fois définitivement. Dans le cas de graphes de taille plus grande, la phase d’uniformisation partielle avec domination cyclique d’un symbole dure plus longtemps avant la victoire définitive d’un des symboles. Les simulations de cette figure ont été réalisées par Rémi Dorat.

La figure ci-dessus représente l’évolution d’un graphe complet de cent nœuds. On part d’une configuration aléatoire : rouge pour le symbole Pierre, blanc pour Feuille, bleu pour Ciseaux. Puis on tire successivement 100 arcs du graphe où les combats correspondants sont joués, ce qui donne une nouvelle répartition. Au bout de 17 étapes de 100 combats aléatoires (donc 1 700 combats) le graphe est devenu uniformément bleu : les Ciseaux ont gagné. On voit cependant que l’évolution est passée par une phase d’oscillation généralisée : sur le dixième dessin, les cases en bleu dominent largement, puis sur le dessin 12, c’est au tour des cases rouges d’être majoritaire, avant de laisser la place au dessin 14 aux cases blanches, avant enfin le retour de la domination bleue, cette fois définitive. Pour des graphes complets plus grands, le phénomène de synchronisation est encore plus net et le temps nécessaire avant son interruption par la domination totale d’un symbole devient long car la phase de domination tournante possède un très grand nombre d’étapes.

Ce mouvement tournant où chacun des trois symboles prend le dessus à tour de rôle s’explique partiellement : les Feuilles vivent en exploitant les Pierres, et si les Feuilles se mettent à dominer elles éliminent presque totalement les Pierres ; la situation créée est alors favorable aux Ciseaux qui n’ont plus à craindre les Pierres et qui rencontrent avec une fréquence croissante les Feuilles qu’ils éliminent ; les Ciseaux deviennent donc plus nombreux se multipliant aux dépens des Feuilles. Cette domination des Ciseaux est favorable aux Pierres (plus fort que les Ciseaux) qui deviennent alors majoritaires un peu plus tard, etc.

Reste que cette explication est partielle, car si elle justifie que cela tourne dès que l’un des symboles domine, elle n’indique pas pourquoi l’un des symboles prend rapidement le dessus engendrant l’oscillation synchronisée de tout le graphe : on pourrait imaginer que tout s’équilibre en gros et que les écarts s’effacent vite dès qu’ils se produisent. Nous allons d’ailleurs voir plus loin des graphes d’un autre type où l’équilibre des effectifs est préservé sur des longues périodes.

Dans la nature un tel phénomène de domination cyclique a été plusieurs fois observé. Le lézard californien, Uta stansburiana, étudié par B. Siverno et C. Lively présente ce comportement de domination cyclique car il y a trois sortes de mâles qui semblent pris dans un jeu sans fin de Pierre-feuille-ciseaux sur un graphe. L’accouplement est à l’origine du cycle car, dans cette cruciale compétition, les mâles à gorge orange l’emportent sur les mâles à gorge bleue qui eux-mêmes dominent les mâles à bandes jaunes qui à leur tour sont plus efficaces sexuellement que les mâles à gorge orange.

Les lézards

Le détail de leur curieux jeu est le suivant. Les mâles à gorge bleue possèdent des harems composés de trois femelles environ et ne cherchent à défendre que de petits territoires. Quand ils sont les plus nombreux, les mâles à gorges orange, qui eux sont particulièrement agressifs, réussissent à s’imposer faisant disparaître la presque totalité des mâles à gorge bleue. Les lézards orange ont un tempérament dominant à cause d’une forte concentration en testostérone. Cela les conduit d’ailleurs à constituer des harems ayant jusqu’à sept femelles et à exercer leur domination sur de vastes territoires. Ils se substituent donc aux mâles à gorge bleue dont le nombre faiblit rapidement sans toutefois s’annuler. Interviennent alors les mâles à bandes jaunes qui s’introduisent dans les camps des mâles à gorge orange en se faisant passer pour des femelles. Ces mâles à bandes jaunes deviennent de plus en plus nombreux et un moment arrive où ils sont majoritaires. Cela laisse réapparaître les mâles à gorge bleue, car ceux-ci savent reconnaître les mâles travestis et les chassent. Cela conduit au retour de la situation initiale avec une majorité de mâles à gorge bleue. Comme dans le cas de nos graphes complets un cycle répété de configurations où dominent successivement chacune les trois catégories de mâles se poursuit sans interruption sur les territoires étudiés.

À une échelle bien plus petite, dans le domaine de la chimie, les réactions de Belousov-Zhabotinskii peuvent s’interpréter comme la manifestation d’un jeu de Pierre-feuille-ciseaux joué à l’échelle microscopique entre composants chimiques. Dans ce cas cependant, aucun composant ne devient globalement dominant et c’est plutôt à une coexistence des compétiteurs qu’on assiste, ceux-ci se regroupant par zones homogènes mobiles créant un jeu animé de dessins étonnants qu’on a associé à l’idée même de phénomène complexe.

Il est simple d’obtenir l’équivalent de cette dynamique chimique dans le monde abstrait des graphes du jeu Pierre-feuille-ciseaux : il suffit de ne pas considérer des graphes complets, mais des graphes réguliers comme ceux correspondant aux cases d’un damier. Chaque case est reliée à ses huit voisines et non plus à toutes les cases comme précédemment.

Le jeu sur un graphe-damier où chaque case du damier n’est liée qu’à ses huit voisins. Au départ, le damier est rempli aléatoirement par les trois symboles Pierre, feuille, ciseaux. L’évolution fait apparaître des zones homogènes, qui se déplacent tout en gardant une taille à peu près constante. Aucun symbole ne domine. En théorie, la domination totale et définitive d’un symbole se produit au bout d’un temps fini avec une probabilité de 100 %. En pratique, ce moment vient si tardivement que l’on considère que les trois symboles coexistent. Les relations de domination cyclique entre souches ou espèces dans le monde vivant sont l’une des causes du maintien de la diversité biologique. Le cas du lézard californien Uta stansburiana est frappant car trois variétés de lézards semblent y jouer à Pierre-feuille-ciseaux.

La figure ci-dessus montre des configurations typiques observées après un long moment d’évolution lorsque l’on considère des graphes-damiers de ce type. Cette fois, la représentation du graphe sur un damier prend tout son sens puisque les nœuds du graphe ne sont reliés qu’aux huit nœuds correspondant aux huit cases voisines. Au début, le système est placé dans un état totalement mélangé (1/3-1/3-1/3). Rapidement apparaissent des zones homogènes des trois couleurs et ces zones se déplacent et changent de forme de manière incessante tout en gardant des caractéristiques globales stables : la taille des zones homogènes est à peu près constante, ainsi que leur vitesse de déplacement et le type de motifs dessinés. Ici, aucun symbole ne domine les autres. L’évolution se traduit par des mouvements ininterrompus des frontières interzones. La zone de séparation entre Pierres et Feuilles se déplace car les Pierres reculent devant les Feuilles ; de même, les Feuilles reculent devant les Ciseaux et les Ciseaux devant les Pierres. L’examen détaillé des effectifs montre une oscillation limitée autour de 1/3 de la proportion de chacun des symboles. Cette fluctuation apparaît comme une variation statistique inévitable qui ne prenant pas d’ampleur ne conduira en pratique jamais à la domination d’un symbole.

Temps de convergence différents

Les deux cas rencontrés, oscillation synchronisée de tout le graphe ou formation de zones homogènes mobiles, correspondent à deux modes de la dynamique d’évolution des graphes de Pierre-feuille-ciseaux. Dans les deux types de graphes, nous savons qu’à long terme l’un des états envahit tout. Cependant le temps nécessaire pour que se produise cette domination définitive est très différent dans les deux cas. Dans le cas des graphes complets, ce temps augmente lentement en fonction de la taille du graphe. Dans le cas des graphes-damiers, l’instant de la stabilisation est repoussé bien plus loin, si bien qu’en pratique, le système reste dans un état mixte où les trois symboles coexistent.

La théorie nous indique pourtant que l’un des états finit toujours par dominer ; la simulation nous montre qu’avec les graphes complets cette domination arrive rapidement, alors qu’avec les graphes-damiers, sa venue est tellement éloignée dans le temps que c’est une stabilisation avec coexistence des trois états qu’il faut considérer comme l’évolution normale à moyen terme de la dynamique du graphe. Un travail détaillé d’étude des caractéristiques de ces dynamiques a été mené par Rémi Dorat à coup de simulations massives et prolongées. Il montre que le temps d’uniformisation croit exponentiellement dans le cas des graphes-damiers.

La situation de coexistence des trois symboles est sans doute une explication du maintien de la diversité dans certaines situations biologiques. Le terrain où trois espèces se rencontrent (les dominations se conformant à un schéma circulaire du type Pierre-feuille-ciseaux), est assimilable à un graphe de type graphe-damier. La dynamique de domination montre alors sur le terrain des motifs plus ou moins semblables à ceux vus lors des simulations.

Benjamin Kerr, Margaret Riley, Marcus Feldman et JM Bohannan, dans un article de la revue Nature, proposent une telle interprétation de leur expérience réalisée avec trois souches d’Escherichia coli en relation non-transitive comme les symboles Pierre-feuille-ciseaux. La conclusion de leur étude est conforme à ce qui est montré par les simulations. Lorsque l’espace où est réalisée l’expérience est petit et, plus généralement, lorsque les relations entre souches sont assimilables à celle décrite par un graphe complet, l’une des souches domine rapidement. En revanche, lorsque les interactions se déroulent sur un espace plus grand, cette fois assimilable à un graphe de type damier, les trois souches coexistent avec des mouvements des zones occupées par chacune d’elles, mouvements assez semblables à ceux vus lors des simulations.

Des études sur des graphes intermédiaires entre les graphes complets et les graphes damiers ont été réalisées par György Szabó, Attila Szolnoki, Rudolf Izsák. Divers phénomènes de transition de phases ont pu être mis en évidence, et ils permettent de mieux comprendre toutes ces dynamiques discrètes nées d’un jeu élémentaire. La science n’a jamais fini d’étudier les jeux : même les plus simples suggèrent des modèles explicatifs utiles.

Une première version de ce document est parue dans la rubrique « Logique et calcul » de la revue Pour la Science n° 364 de février 2008.