Pierre - Feuille - Ciseaux

Le Shifoumi ou Pierre-feuille-ciseaux (PFC) est un des jeux les plus rudimentaires qui soient.
Chaque joueur a trois possibilités : Pierre, feuille et ciseaux

Les règles du jeu sont simples :

• la pierre bat les ciseaux (en les émoussant)
•  les ciseaux battent la feuille (en la coupant)
• la feuille bat la pierre (en l’enveloppant). 

Ainsi chaque coup bat un autre coup, fait match nul contre le deuxième (son homologue) et est battu par le troisième. Autrement dit nous avons à faire un jeu de hasard parfaitement équilibré dont aucun des coups n'est plus fort qu'un autre.

Toutefois des chercheurs ont réussi à mettre au point un ordinateur contre lequel tout être humain fini par perdre s'il joue suffisamment longtemps. En effet il est impossible pour un être humain de jouer ces trois coups totalement au hasard. Une tendance pour l'un de ces coups ou un schéma conscient ou non se met forcément en place. L'ordinateur est programmé pour reconnaitre ces schémas et ainsi peut déterminer quelles coups jouer pour gagner.

Des études ont en effet montré qu'en moyenne les gens jouaient : Feuille à 29,6% - Pierre à 35,4% - Ciseaux à 35%. De plus les hommes ont tendance à jouer Pierre pour le premier coup. 


Bien passons à la seconde étape..
Vous avez peut-être entendu parler des variantes de ce jeu ? Notamment le : Pierre, Feuille, Ciseaux, Lézard, Spock (PFCLS) ? Non ? Alors sans plus attendre regardez cet extrait de The Big Bang Theory (VO) où Sheldon explique les règles de ce Shifoumi amélioré.

A nouveau, dans cette variante, chaque coup est équivalent aux autres, il permet de gagner avec probabilité 2/5, de perdre avec probabilité 2/5 et de faire match nul avec probabilité 1/5.

Nous touchons ici à la théorie des graphes orientés. Ci contre, on observe le graphe complet K5. Si on veut construire des graphes similaires avec une probabilité égal de gagner ou de perdre pour chaque symbole, il faut donc utiliser des graphes complets avec un nombre impair de sommet. C'est à dire un graphe à 2k+1 sommets et 2 k² + k arêtes. (k=1 pour le PFC et k=2 pour le PFCLS)


Un autre exemple de généralisation : Le pierre-pistolet-éclair-diable-dragon-eau-air-papier-éponge-loup-arbre-humain-serpent-ciseaux-feu.
Ce graphe correspond à k=7.

Dobble

Parlons un peu du Dobble. Un jeu de société qui se range dans la catégorie des jeux de rapidité.

Le "dobble" et sa variante commerciale le "dobble kids" est un jeu très simple composé de cartes.
Le dobble classique comporte 55 cartes et sur chacune de ces cartes, il y a exactement 8 symboles.
La propriété essentielle sur laquelle est fondé le jeu, est qu'il y a toujours un et un seul symbole en commun entre deux cartes...


Le dobble kids vérifie la même propriété, mais il ne comporte que 30 cartes et il n'y a que 6 symboles sur chaque cartes.

Comment ce jeu est construit ? Combien y'a t-il de symbole ? Comment peut-on faire pour construire des dobble avec encore plus de symboles par carte ?

Nous allons voir cela tout de suite, mais avant de passer à la théorie, il faut savoir que ceux qui ont conçu le dobble l'ont fait sans l' optimiser, à croire qu'ils ont fait ça en essayant les combinaisons au hasard.

Il y a en effet 30 cartes au "dobble kids" et 55 au "dobble classique" alors qu'il devrait y en avoir respectivement 31 et 57 sans même que l'on ait besoin de rajouter de symboles...
Le plus étrange c'est que ces nombres 37 et 57 correspondent aussi au nombre symbole apparaissant dans le jeu ! L'explication de ce phénomène est expliqué dans le paragraphe ci-dessous.


Construisons notre Dobble généralisé !

Considérons l'ensemble (Fq)², avec q une puissance d'un nombre premier. (Pour dobble kids : q = 5, pour dobble classique q = 7)
A chaque point de cet ensemble va correspondre une carte et à chaque droite du plan va correspondre un symbole. Il y a q+1 droites passant par un point donné, donc q+1 symboles par carte. De plus par deux points passe une unique droite. Donc deux cartes ont toujours exactement un unique symbole en commun.
On peut ensuite rajouter à notre construction un point à l'infini dans chacune des q+1 directions. Et on construit une "droite" qui passe par ces q+1 points à l'infini. Il est aisé de voir que toutes les propriétés précédentes sont conservés. Au total on obtient q² + q + 1 points et autant de droites.


Ou plutôt construisons le dobble kids...

 Nous allons ici construire d'une manière assez surprenante une version simplifié du Dobble car ne contenant que 25 cartes. Pour cela il nous faut représenter chacune de ces cartes par des points et les placer sous la forme d'un carré ayant pour côté 5.

Dans cette figure on peut construire des objets que l'on appelle "droites", mais qui peuvent être en plusieurs "morceaux". Ces droites au nombre de 30 passent toutes par 5 points (un de chaque colonne/ligne). Ces 30 droites sont représentées ci-contre :

A chacune de ces droites va correspondre un symbole et donc si un point est sur la droite, on dira qu'il y a le symbole correspondant sur cette carte.

Grâce au schéma ci-dessus, il est clair que sur chaque carte il y a exactement 6 symboles !

Mais le fait le plus intéressant n'est pas là ! On remarque en effet que si l'on sélectionne deux points au hasard parmis les 25, alors on découvre qu'il n'y a qu'une seule droite qui passe par ces deux points. Et c'est là la propriété du Dobble : A chaque fois que l'on prend deux cartes elles ont un et un seul symbole en commun !
 
Cela nous fait donc 25 cartes. Mais je vous ai dit que l'on peut construire un "Dobble kids" à 31 cartes. Il nous manque donc encore 6 cartes pour que le jeu soit complet !

Ces 6 cartes ne sont pas représentées par des points mais par des directions... En effet lorsque l'on regarde les 6 schémas ci-dessus chacun d'eux correspond à une direction. Il y a 6 directions donc 6 cartes supplémentaires.

Et comme dans chaque direction il y a 5 droites, cela nous fait 5 symboles pour ces nouvelles cartes. Or, il nous en faut 6, comme pour les autres... La solution ? On crée un 31ième symbole qui sera le symbole commun à chacune de ces 6 nouvelles cartes. Et voilà ! Maintenant, la construction est véritablement terminée : vous voici avec un dobble de 31 cartes !

Résoudre un jeu

Quoi résoudre un jeu ? C'est possible ça ?
Oui, il s'agit d'une expression purement mathématiques.

Le plus simple pour comprendre ce que cela signifie est de commencer par considérer des jeux combinatoires abstraits, c'est à dire des jeux :

• opposant généralement deux joueurs ou deux équipes (ou bien un joueur humain seul contre un ordinateur « intelligent ») ;
• dans lequel les joueurs ou équipes jouent à tour de rôle ;
• dont tous les éléments sont connus (jeu à information complète) ;
• où le hasard n'intervient pas pendant le déroulement du jeu.

 Lorsque plus de deux joueurs ou équipes participent, un aspect diplomatique ou relationnel empêche le classement du jeu comme purement combinatoire.

Les échecs, les dames, le jeu de go, le puissance 4 sont des exemples de tels jeux... A l'inverse le backgammon, le tarot, le yams, le jungle speed ou le scrabble ne sont pas des jeux combinatoires abstraits.


On dit qu'un jeu est résolu lorsque l'on a trouvé une méthode pour gagner à coup sûr, ou que l'on a démontrer qu'il n'existe pas de telles méthodes. Grâce à l'essor de l'informatique et aux capacités de calculs toujours plus grande, beaucoup de jeux ont été résolu ces dernières années. Mais certains résistent encore !


Puissance 4

Le jeu qui date de 1974 a été résolu de façon exacte en 1988, indépendamment par James D. Allen et par Victor Allis avec des calculs informatiques.

Conclusion de leurs travaux : Le joueur qui commence gagne !
Si le premier coup est la colonne du milieu et que le premier joueur joue parfaitement, il gagnera à chaque fois ! Si le premier coup est la colonne 3 ou la colonne 5, alors le second joueur peut arracher le match nul et si le premier coup est dans une autre colonne, alors le second joueur peut gagner.

Le logiciel libre : Mustrum ( téléchargeable gratuitement ici : http://mustrum.updatestar.com/fr ) est un logiciel ayant une connaissance complète du jeu. Réglé en difficulté infini, le logiciel gagnera donc systématiquement s'il commence.


Awalé

Jeu de combinatoire très répandu sur le continent africain.
Ce jeu fut résolu en 2002 par John W. Romein and Henri E. Bal à l'aide d'une grappe de 144 processeurs.
Pour résoudre le jeu, il fut utilisé des bases de données correspondant à toutes les configurations possibles avec un nombre de graine fixé. La plus grosses base de donnée est celle correspondant à 48 graines avec plus de 200 billions de possibilités. Jamais une telle capacité de mémoire n'avait été utilisé en théorie des jeux jusque là.

Conclusion de leurs travaux : Si chaque joueur joue à la perfection, peut importe qui commence, il y aura toujours match nul.


Les dames, les échecs, le jeu de go...

Nous atteignons ici les limites de  l'informatique. Actuellement la question de la solvabilité du jeu de dames, des echecs ou encore du jeu de go sont totalement hors de portée des ordinateurs actuels.