Quelle est la probabilité de faire un Yam’s ?

Cette page présente plusieurs façons de calculer la probabilité de faire un Yam's ( ce jeu est également appelé Yahtzee ).

1) Présentation :

Le Yam’s se joue avec 5 dés.
Lorsque vient son tour, le joueur vise une combinaison et marquera des points en rapport avec celle-ci. Il a droit à 3 jets au maximum et peut ne relancer que certains dés.

La combinaison la mieux récompensée est le Yam’s où les 5 dés sont identiques.

Prenons un exemple :
1er lancer : 3 – 4 – 2 – 3 – 5. Les dés gardés sont les deux « 3 ». Les 3 autres dés sont relancés.
2ème lancer : 1 – 2 – 3. Le « 3 » est gardé. Les deux autres dés sont relancés.
3ème lancer : 3 – 1

Résultat : la combinaison finale est :
3 – 3 – 3 – 3 – 1

Ce résultat n’est pas un Yam’s car les cinq dés ne portent pas le même nombre.


L’objet de cette page est de répondre à la question : quelle est la probabilité de produire un Yam’s lorsque vient son tour ?

Il y a plusieurs façons de répondre à cette question :

1) En déroulant informatiquement toutes les parties possibles et en comptabilisant les Yam’s.
2) Par la méthode de Monte-Carlo : cela ressemble à la méthode 1) mais toutes les parties possibles ne sont pas explorées. Seul un sous-ensemble, supposé représentatif, est examiné. On pourra simuler par exemple 100 millions de parties et mesurer expérimentalement la valeur trouvée.
3) Par un raisonnement probabiliste, il suffit d’estimer la probabilité de chaque chemin menant au Yam’s et de faire la somme de ces probabilités.
4) En utilisant le formalisme des processus markoviens, qui simplifie la méthode 3)

Sur cette page, nous allons étudier les méthodes 2), 3) et 4).


2) Simulation par la méthode de Monte-Carlo :

Cette méthode a la vertu de la simplicité. Son point faible est que la solution est une approximation numérique et non pas une valeur exacte. Il est cependant possible de rendre les barres d’erreurs aussi petites que désirées – au prix d’une augmentation du nombre de simulations.

Le programme yams.c (en bas de page) procède à la simulation :

L’exécutable est lancé en ligne de commande. Dans l’exemple ci-dessous, un millions de simulations sont effectuées.

yams –t 1000000

La graine aléatoire peut être modifiée avec l’option –r
Voici un exemple de simulation.

C: >yams -t 100000000
Running Yams with NumDice=5, NumTurns=3, NumTrials=100000000, RandomSeed=1000

Statistics:
Number of Yam's : 4600606
Max rate Yam's : 4.6027%
Avg rate Yam's : 4.6006%
Min rate Yam's : 4.5985%
Std error : 0.0021%
Number of 1's : 201724795
Number of 2's : 201670593
Number of 3's : 201680056
Number of 4's : 201719326
Number of 5's : 201698421
Number of 6's : 201680370
Number of rolls : 1210173561
Rolls / trial : 12.1017

Nous trouvons que la probabilité est proche de 4,600 %. Le programme fournit également une barre d’erreur (« Std error ») relativement étroite : 0,0021% en valeur absolue. Consultez les références citées dans le programme pour plus de précisions et une discussion sur la signification de cette erreur. Il est important de noter principalement que cette valeur doit être prise comme une approximation de l’erreur standard.

On pourra donc écrire :

La colonne de gauche représente le score avant un jet. Chaque case du tableau donne la probabilité de passer d’un score à un autre par un jet de dés.

Exemple : si j’ai une paire (ligne 2), je vais lancer 3 dés et la probabilité de passer à 3 dés identiques est de 80/6³ (colonne 3)

Note : Le score ne peut pas baisser avec le temps. Une case vide représente la valeur zéro

Les bases de la théorie des probabilités nous enseignent que la probabilité d’un état donné peut être calculé en faisant la somme des probabilités des évènements menant à cet état.

Voici pour le Yam’s la liste des 15 chemins conduisant à l’état 5 dés identiques. Chaque rond jaune contient le score courant. Le score initial est de 1. Lorsqu’un Yam’s est obtenu, le score est de 5.

Dans le schéma ci-dessus, le premier cas est : 1 -> 1 -> 1 -> 5

Sur ces 3 jets, les deux premiers ne conduisent qu’à des combinaisons où tous les dés sont différents. Le dernier jet aboutit à un Yam’s.

La probabilité du premier cas est donc le produit triple de :

- la probabilité de passer du score 1 vers lui-même

- la probabilité de passer du score 1 vers lui-même (à nouveau)

- la probabilité de passer du score 1 vers le score 5

Cette quantité vaut:

P11 . P11 . P15 = (120 / 6⁴) (120 / 6⁴) (1/ 6⁴) = 25 / 3779136. Cela est proche de 0,000 0067 (un peu moins d’un millième de pourcent).

Le tableau ci-dessous présente les 15 chemins et leur probabilité respective

Evolution du score sur 3 jets					Probabilité des jets individuels				Probabilité de la séquence
					Jet 1	Jet 2	Jet 3
1	1	1	5		9,259%	9,259%	0,077%		0,001%
1	1	2	5		9,259%	69,444%	0,463%		0,030%
1	1	3	5		9,259%	19,290%	2,778%		0,050%
1	1	4	5		9,259%	1,929%	16,667%		0,030%
1	1	5	5		9,259%	0,077%	100,000%		0,007%
1	2	2	5		69,444%	55,556%	0,463%		0,179%
1	2	3	5		69,444%	37,037%	2,778%		0,714%
1	2	4	5		69,444%	6,944%	16,667%		0,804%
1	2	5	5		69,444%	0,463%	100,000%		0,322%
1	3	3	5		19,290%	69,444%	2,778%		0,372%
1	3	4	5		19,290%	27,778%	16,667%		0,893%
1	3	5	5		19,290%	2,778%	100,000%		0,536%
1	4	4	5		1,929%	83,333%	16,667%		0,268%
1	4	5	5		1,929%	16,667%	100,000%		0,322%
1	5	5	5		0,077%	100,000%	100,000%		0,077%
							Somme		4,603%

La probabilité de faire un Yam’s est la somme des probabilités des 15 cas ci-dessus, soit : 4,603 %

4) Approche markovienne

La théorie des processus markoviens permet d’arriver au même résultat qu’en 2), mais de façon plus simple, et, de plus, fournit quelques informations supplémentaires.

Si nous définissons l’état de notre système comme étant le score, tel que défini en 2), 5 états sont alors accessibles. La matrice de transition de notre système est alors le tableau déjà donné. Ici, cette matrice est notée M.

Le graphe correspondant est :

Rappel de la théorie markovienne :

La probabilité de passer d’un état i à un état j en n étapes est égal à Mⁿ_ij, l’élément de matrice (i,j) de la n-ième puissance de M.

Autrement dit, la probabilité de faire un Yam’s en 3 jets est l’élément de matrice (1,5) de M³.

On a:

La probabilité de faire un Yam’s est donc :

P(Yams) = 347 897 / 7 558 272 ≈ 4,603%

Par ailleurs, la matrice fondamentale de M est :

En faisant la somme des valeurs de la première ligne de cette matrice, il est possible d’affirmer qu’en moyenne, il faut jeter les dés 11,1 fois pour faire un Yam’s.

Annexe 1 : yams.c

Source du programme de simulation du Yam’s par la méthode de Monte-Carlo

/*

 * Yams Monte Carlo Simulation

 * Copyright 2006 by Pictor

 * Distribution is free provided this notice is not removed

 *

 */

#include 

#include 

#include 

#include 

constint NumDice= 5; // How many dice ?

constint NumTurns = 3; // How many attemps to get a Yam ?

constint NumSides = 6; // How many sides on a die ?

void throwDice(int NumRolled, int Dice[], long TotalFreqNumber[])

{

int i;

for (i=(NumDice-NumRolled); i

Dice[i] = 1 + (int)((double)rand() / ((double)RAND_MAX + 1) * NumSides);

TotalFreqNumber[Dice[i]]++;

}

}

int testYam(int Dice[], int* pMaxSide, int* pMaxFreq)

// Returns 1 if there is a Yam's, 0 otherwise

{

int i;

int FreqNumber[NumSides+1];

// Number of times a given number has been thrown (from 1 to 6)

// Compute frequency for each side

// Note: loop is from 1 to 6 rather than from 0 to 5

for (i=1; i<(NumSides+1); i++) {

FreqNumber[i] = 0;

}

for (i=0; i

FreqNumber[Dice[i]]++;

}

// Find the most frequent side and its frequency

// Returns it

*pMaxSide = 0;

*pMaxFreq = 0;

// Note: loop is from 1 to 6 rather than from 0 to 5

for (i=1; i<(NumSides+1); i++) {

if (FreqNumber[i] > *pMaxFreq) {

*pMaxFreq = FreqNumber[i];

*pMaxSide = i;

}

}

if (*pMaxFreq == NumDice) {

return 1;

}

else {

return 0;

}

}

int main(int argc, char* argv[])

{

int NumTrials=3600; // How many throws ?

int i, k, iTurn;

int Dice[NumDice];

int NumRollAgain;

int MaxSide;

int MaxFreq;

int NumYams;

unsigned int RandomSeed=1000;

long TotalFreqNumber[NumSides+1];

long TotalAllSides;

float YamsAvg;

float YamsStdDev;

if (argc > 1)

{

for (i = 1; i < argc; i++)

{

if ((strcmp(argv[i], "-t") == 0) && (i < argc))

{

NumTrials = atol(argv[++i]);

}

else

if ((strcmp(argv[i], "-r") == 0) && (i < argc))

{

RandomSeed = atol(argv[++i]);

srand(RandomSeed);

}

else

if ((strcmp(argv[i], "-h") == 0) && (i < argc))

{

printf("nSyntax : %s [-t Number of throws][-r Random seed][-h]nn", argv[0]);

exit(0);

}

}

}

else

{

// No arguments given: keep default values

}

printf("Running Yams with NumDice=%d, NumTurns=%d, NumTrials=%d, RandomSeed=%dn", NumDice, NumTurns, NumTrials, RandomSeed);

NumYams = 0;

// Note: loop is from 1 to 6 rather than from 0 to 5

for (i=1; i<(NumSides+1); i++) {

TotalFreqNumber[i] = 0;

}

for (k=0; k

iTurn = 1;

throwDice (5, Dice, TotalFreqNumber);

while (iTurn <= NumTurns) {

if (testYam(Dice, &MaxSide, &MaxFreq)) {

NumYams++;

break;

} else

{

// Move most frequent dice to begining of dice[] and roll again others

for (i=0; i

Dice[i] = MaxSide;

}

NumRollAgain = NumDice-MaxFreq;

throwDice (NumRollAgain, Dice, TotalFreqNumber);

iTurn++;

}

}

}

YamsAvg= (float)NumYams /(float)NumTrials;

// Estimate of Standard Error: see

// - “Numerical Recipes in C. The Art of Scientific Computing”, W. Press et al.,

//Cambridge University Press, p. 307 with den=1

// - “A Primer for the Monte Carlo Method”, I. Sobol, CRC Press, pp. 32-33

// (Sobol then builds "probable error" = 0.6745 x Std Err. Not used here)

YamsStdDev = sqrt(1/(float)NumTrials)*sqrt(YamsAvg*(1-YamsAvg));

printf("nStatistics:n");

printf("Number of Yam's : %dn", NumYams);

printf("Max rateYam's : %3.4f%%n", 100.0*(YamsAvg+YamsStdDev));

printf("Avg rateYam's : %3.4f%%n", 100.0*YamsAvg);

printf("Min rateYam's : %3.4f%%n", 100.0*(YamsAvg-YamsStdDev));

printf("Std error: %3.4f%%n", 100.0*YamsStdDev);

// Show statistics for dice rolls

TotalAllSides = 0;

for (i=1; i<(NumSides+1); i++) { // Note: loop is from 1 to 6 rather than from 0 to 5

printf("Number of %d's: %dn", i, TotalFreqNumber[i]);

TotalAllSides += TotalFreqNumber[i];

}

printf("Number of rolls : %dn", TotalAllSides);

printf("Rolls / trial: %3.4fn", (float)TotalAllSides/(float)NumTrials);

}

Haut