Mokshû Patamû
Après une partie contre des banquiers véreux qui n'ont jamais voulu échanger votre Faubourg Saint-Honoré contre leur Boulevard Malesherbes, vous avez choisi de renoncer définitivement à ouvrir cette boîte de ce jeu de l'enfer qu'est le Monopoly. Mais à quoi jouer avec beau-papa en ce dimanche après-midi ? Une partie de Scrabble ? des colons de Catanes ? des Aventuriers du Rail ? Non ! Revenons aux bases, et ouvrons la boîte pleine de poussière qui renferme un vénérable plateau de Serpents et échelles !
Bon, finalement, vous avez débuté le jeu, et vous n'avez maintenant plus qu'une seule envie : que cela se termine ! Mais au fait, combien de temps dure en moyenne une partie de Serpents et échelles ?!
Pour les quelques-uns qui n'ont jamais perdu des heures à tomber en boucle sur la même gueule de serpent, voici ce qu'il faut savoir sur ce jeu :
- Le plateau de jeu est composé de 100 cases, numérotées de 1 à 100.
- Les joueurs, chacun leur tour, lancent le dé, puis déplacent leur pion du nombre de cases indiqué.
- Des serpents et des échelles sont disséminés sur le plateau de jeu. Lorsqu'on arrive au pied d'une échelle, on la monte ; inversement, lorsque l'on tombe sur une tête de serpent, on descend jusqu'à sa queue.
- Le premier joueur à atteindre (ou dépasser) la 100e case est déclaré vainqueur, et félicité pour sa chance au jeu.
- A l'origine, ce jeu est une métaphore indoue du chemin spirituel pour atteindre le Nirvana.
De nombreuses variantes de plateaux de jeu existent, je vais me baser sur la version Hasbro, dont le plateau comporte 9 échelles et 7 serpents, et qui ressemble à ceci :
Au nom de la loi de X
En détaillant un peu le plateau, on peut voir que la centième case peut être atteinte en seulement 7 lancés de dés, en empruntant 3 échelles (l'échelle 1 -> 38, la 51-> 67 et la 71 -> 91). Cependant, il n'y a pas de nombre maximum de coups permettant d'atteindre la dernière case. Heureusement, ce cas est presque impossible.
Finalement, quel est le temps moyen permettant d'atteindre cette centième case ? Les chaînes de Markov sont là pour nous aider à appréhender la situation. Pour comprendre, observons ce qu'il se passe lancé par lancé.
Au début du jeu, les pions sont en dehors du plateau. Au premier lancé de dé, 6 cases sont atteignables (38 (si on obtient 1 au dé, grâce à l'échelle), 2, 3, 14 (4 au dé), 5 ou 6). La probabilité d'atteindre chacune de ces cases après le premier lancé de dé est donc de 1/6 (≈0.17).
Pour ce qui est du deuxième lancé de dé, il faut envisager les 6 cas précédents :
- depuis la case 38, on peut atteindre 39, 40, 41, 42, 43, 44
- depuis la case 2, on peut atteindre 3, 14, 5, 6, 7, 8
- depuis la case 3, on peut atteindre 14, 5, 6, 7, 8, 31
- depuis la case 14, on peut atteindre 15, 6, 17, 18, 19, 20
- depuis la case 5, on peut atteindre 6, 7, 8, 31, 10, 11
- depuis la case 6, on peut atteindre 7, 8, 31, 10, 11, 12
Puisqu'il y a 36 façons de lancer deux fois le dé, chacune de ces cases a pour probabilité 1/36 d'être atteinte par le chemin indiqué. On peut alors remarquer, par exemple, que :
- il n'y a qu'une seule façon d'atteindre la case 42 en deux lancés de dé : sa probabilité est de 1/36 (≈0.03).
- il y a 4 façons d'atteindre la case 6 en deux lancés de dé : la probabilité de cette case est donc de 4/36 (≈0.11).
On pourrait suivre le même raisonnement pour le troisième lancé de dé, mais le décrire entièrement serait trop long. Heureusement, les matrices vont venir prendre le relai. Pour cela, on a besoin de la matrice de transition M du plateau, qui donne la probabilité d'atteindre une case sachant que l'on est sur une autre case.
Pour être plus précis, le coefficient de la ligne I et de la colonne J correspond à la probabilité d'atteindre la J-ième case sachant que l'on se trouve sur la I-ème. A titre d'exemple, le coefficient ligne 2 colonne 3 est 1/6 car il y a une chance sur 6 d'atteindre la case 3 en partant de la case 2.
La matrice finale M contient donc une très grand nombre de 0, beaucoup de 1/6 et quelques valeurs un peu plus grandes (le coefficient ligne 52 colonne 53 vaut 2/6, car il y a deux façons d'atteindre la case 53 depuis la 52). Graphiquement, la matrice ressemble à ceci.
Cette matrice nous permet de calculer la probabilité de chacune des cases pour un nombre de lancé choisi, en utilisant le fait que
U(n+1) = U(n) × M
où U(n) la matrice-ligne qui donne la probabilité de chacune des 100 cases lors du n-ième lancé de dé.
On peut notemment calculer la distribution des probabilités pour 6 ou 7 lancés, ce qui confirme la remarque initiale : il est théoriquement possible de gagner en 7 lancés de dés, mais la probabilité est excessivement faible (0.2 %). Après 7 lancés, on se retrouve plus facilement en case 26...
Le temps d'en finir
Tout ceci ne nous dit pas encore combien de temps on doit se farcir les serpents et les échelles pour en finir avec le jeu. Il ne reste en fait plus qu'à chercher la probabilités d'atteindre la 100e en exactement n lancés de dés, pour toutes les valeurs de n. Aussitôt dit, aussitôt fait :
Ce graphique (et quelques calculs autour des données) nous apprend des choses essentielles :
- Le plus probable est d'atteindre la centième case en 20 lancés de dés
- En moyenne, il faut 36 lancés de dés pour gagner
- Il y a 50% de chances de finir en moins de 29 mouvements
- Il y a 98% de chances d'en finir en moins de 100 mouvements
Oui, mais...
D'aucun me diront que, dans les règles officielles du jeu, il faut atteindre exactement la case 100, sinon la règle "tu dépasses, tu recules" s'applique. Ca change tout !
Qu'il en soit ainsi, je modifie la matrice tout de suite :
Ce qui nous donne ce chouette graphique :
En détaillant en peu les chiffres, on découvre que...
- Le plus probable est d'atteindre la centième case en 22 lancés de dés (et la probabilité est bien plus faible que dans le cas précédent)
- En moyenne, il faut 43 lancés de dés pour gagner
- Il y a 50% de chances de finir en moins de 34 mouvements
- Il y a 94% de chances d'en finir en moins de 100 mouvements
Mouais... Finalement, cette règle supplémentaire a surtout pour effet de rallonger la traîne de la courbe : le cas le plus probable ne change pas, mais les événements très rares le deviennent un petit peu moins.
Sources :
Analysis of Chutes and Ladders, sur DataGenetics
Images :
Snakes_and_ladders
