Pierre, feuille, ciseaux... Et après ?
Il y a de cela 8 ans, j'avais codé une version un peu trop modernisée du chifoumi, et ça ressemblait à ceci.
Ce chifoumi à 10 symboles présente un désavantage majeur : il n'est pas équitable, puisque certains symboles sont en moyenne plus forts que les autres. C'est le cas par exemple de la feuille qui gagne contre 5 des 9 autres symboles, alors que la pierre ne gagne que contre 4 des 9 autres symboles.
On peut le voir sur la matrice des gains du jeu : certaines lignes ont davantage de "1" que les autres.
Matrice des gains : les "1" correspondent à la victoire du joueur, les "-1" à la victoire de l'adversaire et les "0" à une égalité.
Il n'y a qu'une seule façon de régler le problème, c'est d'ajouter un nouveau symbole qui égalise chacune des lignes et colonnes. On peut, par exemple, ajouter le lapin, qui gagnera contre la feuille, les ciseaux, le puits, le pistolet et le sataniste (les justifications sont laissées en exercice au lecteur).
Nouvelle matrice de gain : le jeu est équilibré, puisque chaque ligne contient à présent autant de "1" que de "-1".
Mais au fait, peut-on fabriquer un jeu de Pierre-Feuille-Ciseaux avec autant de symboles que l'on veut ?
Pierre - Feuille - Ciseaux - (...) - (...)
La plus connue des variantes à 4 symboles du chifoumi est celle du "Pierre-Feuille-Ciseaux-Puits". L'ajout du symbole supplémentaire donne cependant un jeu bancal, puisque la pierre devient un symbole stratégiquement inutile (On peut même démontrer que la stratégie optimale au "Pierre-Feuille-Ciseaux-Puits" est de joueur au hasard les symboles, excepté la pierre. Un jour, promis, je ferai un article sur la théorie des jeux...).
Plutôt que de représenter les chifoumis par leur matrice de gains, utilisons plutôt la représentation sous forme de graphe. Dans un graphe de chifoumi ("graphe de tournoi équilibré"), le nombre de flèches pointant sur un sommet doit être égal au nombre de flèches qui en partent. Le graphe du "Pierre-Feuille-Ciseaux-Puits" n'est donc pas un graphe de chifoumi :
La pierre casse les ciseaux ;
La feuille recouvre la pierre et le puits ;
Les ciseaux coupent la feuille ;
Dans le puits tombent la pierre et les ciseaux.
En fait, on peut voir facilement qu'un chifoumi ayant un nombre pair de symboles ne pourra jamais être équitable. En effet, si un nombre pair de symboles est en présence, chaque symbole pourra se battre contre un nombre impair de symboles ; impossible dans ce cas d'avoir autant de victoires que de défaites.
L'autre variante classique du chifoumi, popularisée par la série "The Big Bang Theory" est celle où l'on ajoute les deux symboles "Lézard" et "Spock". Cela produit une version à 5 symboles, qui cette fois-ci est équilibrée.
La pierre casse les ciseaux et écrase le lézard ;
Les ciseaux décapitent le lézard et coupent la feuille ;
Le lézard mange la feuille et empoisonne Spock ;
La feuille désapprouve Spock et recouvre la pierre ;
Spock vaporise la pierre et écrabouille les ciseaux.
Existe-t-il d'autres variantes de chifoumi à 5 symboles qui seraient radicalement différentes du Pierre-Feuille-Ciseaux-Lézard-Spock ? Eh bien... non ! On peut prendre par exemple la variante Singe-Pirate-Robot-Ninja-Zombie.
Le robot écrase le zombie et électrocute le ninja ;
Le zombie attaque le singe et mange le pirate ;
Le singe trompe le ninja et débranche le robot ;
Le ninja attaque le pirate et décapite le zombie ;
Le pirate coule le robot et embroche le singe.
En procédant à un simple changement de nom, on peut voir que ces deux variantes sont en fait exactement les mêmes. On dit alors que les graphes sont isomorphes.
Isomorphisme entre les deux graphes : on commence par renommer les sommets, puis on les déplace en préservant le sens des flèches.
On peut même prouver que si on a un chifoumi équilibré à 5 symboles, il sera forcément isomorphe au pierre-feuille-ciseaux-lézard-Spock. Pour cela, prenons un chifoumi ayant 5 symboles A, B, C, D et E.
La première chose à voir, c'est que le graphe possèdera forcément un 5-cycle, de type A → B → C → D → E → A.
Dans le cas contraire, c'est que l'on a seulement un 4-cycle A→B→C→D→A. Dans ce cas, on aura (A→C ou C→A) et (B→D ou D→B). Sans perte de généralité, supposons que l'on a A→C et B→D. Pour que le chifoumi soit équitable, il faut nécéssairement E→B et C→E, ce qui fait apparaître le 5-cycle A→C→E→B→D→A.
Bref, il y a un 5-cycle. On peut supposer sans perte de généralité que ce 5-cycle est A→B→C→D→E→A. On a alors deux possibilités : soit A→C, soit A→D. On peut alors compléter les graphes en veillant à le construire équilibré, ce qui donne les deux graphes suivants :
Ces deux éventualités donnent deux graphes qui semblent au premier abord différents, mais qui sont bien isomorphes, puisque le premier est isomorphe au Pierre-Feuille-Ciseaux-Lézard-Spock, et que le second l'est au Singe-Pirate-Robot-Ninja-Zombie.
Pierre - Feuille - Ciseaux - (...) - (...) - (...) - (...)
La construction précédente a le mérite de fournir une première méthode générale pour fabriquer un graphe de chifoumi avec n-symboles : il suffit de partir de n symboles disposés en cercle, et de compléter ensuite le graphe. La façon la plus simple de le compléter, c'est de relier chaque symbole aux (n-1)/2 suivants.
C'est ce qu'a fait David C. Lovelace en 2005, en fabriquant un Pierre-Feuille-Ciseaux à 7 symboles (un "7-chifoumi") ;
La pierre éteint le feu, écrase les ciseaux et l'éponge ;
Le feu fait fondre les ciseaux, brûle l'éponge et le papier ;
Les ciseaux coupent l'éponge, le papier et son claquement résonne dans l'air ;
L'éponge mouille le papier, contient des trous d'air et absorbe l'eau ;
Le papier évente l'air, flotte sur l'eau et recouvre la pierre ;
L'air évapore l'eau, érode la pierre et éteint le feu ;
L'eau érode la pierre, éteint le feu et rouille les ciseaux.
Sur le cercle, chaque symbole est relié aux (7-1)/2 = 3 symboles suivants.
... puis à 9 symboles, puis à 11 symboles, puis à 15 symboles, puis à 25 symboles, et même jusqu'à... 101 symboles ! Toutes ces variantes sont créées de la même façon : les n symboles sont disposés en un cercle, ce qui forme un n-cycle, et chaque symbole bat les (n-1)/2 suivants sur ce cercle.
Autre méthode de construction. On peut fabriquer son chifoumi au fur et à mesure, en ajoutant de nouveaux symboles 2 par 2, de façon à ce que le premier symbole ajouté batte la moitié (arrondi à l'entier supérieur) des symboles préexistants, et que l'autre symbole batte la seconde moitié des symboles préexistants, ainsi que le premier symbole ajouté.
Par exemple, partons du classique Pierre, Feuille, Ciseaux. On commence par ajouter deux symboles, l'arbre et le sac plastique.
L'arbre
+ ne craint rien des ciseaux ;
+ domine la pierre ;
- n'est rien sans feuilles ;
(- est pollué par le sac plastique).
Le sac plastique
+ ramasse la feuille ;
- se fait découper par les ciseaux ;
- cède sous le poids de la pierre ;
+ pollue l'arbre.
On peut continuer, en ajoutant deux autres symboles. Disons, la hache et l'homme.
La hache :
+ déchire le sac plastique ;
+ casse les ciseaux ;
+ abat l'arbre ;
- se fait emballer par la feuille ;
- se brise sur la pierre ;
(- est manipulé par l'homme).
L'homme :
+ écrit sur la feuille ;
+ marche sur la pierre ;
- se fait étouffer par le sac plastique ;
- se fait cisailler par les ciseaux ;
- tombe de l'arbre ;
+ manipule la hache.
Le graphe de mon 7-chifoumi.
Et ainsi de suite, pour fabriquer des chifoumis avec toujours plus de symboles !
On peut alors se poser la même question que précédemment. Le 7-chifoumi de Lovelace "Pierre-Feuille-Ciseaux-Air-Eau-Feu-Éponge" est-il équivalent à mon 7-chifoumi "Pierre-Feuille-Ciseaux-Homme-Hache-Arbre-Sac" ?
Cette fois-ci, non ! Et on peut même le prouver, mais il va falloir pour cela compter consciencieusement les différents 5-cycles qui apparaissent dans la structure.
Dans la première, on ne peut compter que 28 5-cycles :
4 des 28 5-cycles du graphe du 7-Chifoumi de Lovelace.
Les 24 autres 5-cycles se retrouvent par rotation (d'angle 360°/7).
Tandis que la deuxième, on peut en compter jusqu'à 36 :
12 des 36 5-cycles du graphe du 7-Chifoumi personnalisé.
Les 24 autres 5-cycles se retrouvent par rotation (d'angle 360°/3)
Les deux graphes n'ont pas le même nombre de 5-cycles, ils sont donc fondamentalement différents, ce qui montre qu'il existe donc au moins deux façons distinctes de construire un 7-chifoumi. Et il en existe même une troisième, celle ayant la structure du plan de Fano (évoquée déjà ici). Cette structure-ci ne peut cependant pas être obtenue par la méthode de construction itérative décrite précédemment.
Le plan de chifoumi-Fano (qui contient 42 5-cycles)
En existe-t-il davantage ? Cette fois-ci, non. Pour le prouver, il faudrait cependant montrer que chacun des 2640 graphes de 7-chifoumi est isomorphe à l'un des trois graphes précédents...
Pierre - Feuille - Ciseaux - (...) - (...) - (...) - (...) - (...) - (...) - ...
À mesure que n augmente, le nombre de graphes de chifoumi à n symboles augmente de façon drastique :
n = 1 → 1 configuration
n = 3 → 1 configuration
n = 5 → 1 configuration
n = 7 → 3 configurations
n = 9 → 15 configurations
n = 11 → 1223 configurations
n = 13 → 1495297 configurations
Pour déterminer ces valeurs, Marc Chamberland et Eugene Herman n'ont pas cherché à calculer l'ensemble des graphes de chifoumi, le temps de calcul aurait été suicidaire (à titre indicatif, il y a 9 307 700 611 292 160 graphes de chifoumi à 13 symboles, analyser chacun d'entre eux aurait demandé des temps de calculs monstrueux). Pour le prouver, ils ont plutôt tenté de déterminer les différents "profils" possibles existants pour les graphes (la façon dont les 3-cycles sont disposés les uns par rapport aux autres), ce qui leur a permis de dénombrer efficacement toutes ces configurations. On ne connaît pas aujourd'hui le nombre de chifoumi distincts à 15 symboles, mais ce qui est sûr, c'est qu'ils sont particulièrement nombreux.
Bref : si vous voulez fabriquer un chifoumi complètement inédit, il vous faudra au minimum 7 symboles !
Sources :
Rock-Paper-Scissors meets Borromean Rings, Marc Chamberland, Eugene A. Herman