DM1: Pierre Feuille Ciseaux
LAFRASSE Cédric TERRIER Bastien
Objectifs : Dans ce DM on s’intéresse au jeu de Pierre Papier Ciseaux et on cherche à savoir quelle est la bonne stratégie à avoir. On se concentre sur la version (non violente!) dite “à somme nulle” où le gagnant empoche 1 alors que le perdant perd 1. En cas d’égalité, personne ne perd ni ne gagne rien.
Question 1: Les joueurs sans mémoire
Le joueur biaisé :
- Commençons par estimer, grâce à une simulation, le gain du joueur B lorsque il joue contre le joueur A. Les deux joueurs n’ont pas de mémoire et ils ont une probabilité de 0.25 de jouer Pierre, 0.25 de jouer Feuille et 0.5 de jouer Ciseau. Soit la variable B, qui représente les gains du joueur B. Nous allons répéter n fois une partie de Pierre Feuille Ciseaux en nous intéressant seulement aux gains du joueur B.
n_parties = function (nombre=10000,proba_A=c(0.25,0.25,0.5),proba_B=c(0.25,0.25,0.5)){
B=0;
for(i in 1:nombre){
elementA=sample(size = 1,x = c('P','F','C'),prob = proba_A);
elementB=sample(size = 1,x = c('P','F','C'),prob = proba_B);
#B remporte la partie
if( (elementA=='P'&&elementB=='F') || (elementA=='C'&&elementB=='P') || (elementA=='F'&&elementB=='C') ) {
B=B+1;
}
#B perd la partie
if( (elementA=='P'&&elementB=='C') || (elementA=='F'&&elementB=='P') || (elementA=='C'&&elementB=='F') ) {
B=B-1;
}
#sinon il y a match nul donc pas de points sont attribués
}
B/nombre
}
n_parties()## [1] 0.0046Par simulation, on observe une espérance de gain nulle. Lorsque le joueur B rencontre le joueur A dans ces conditions (avec les mêmes probabilités) le jeu est équilibré donc l’espérance de gain est nulle.
- Maintenant, nous voulons connaître l’espérance des gains de B lorsque B à une probabilité de 0.3 de jouer Pierre, 0.3 de jouer Feuille et 0.3 de jouer Ciseau.
n_parties (proba_B = c(1/3,1/3,1/3))## [1] 0.0039Par simulation, on observe une espérance de gain nulle. Il semblerait que le jeu reste équilibré.
- Nous allons estimer l’espérance de gain du joueur B avec les différentes stratégies possibles. Pour cela, nous devons énumérer tous les cas possibles et simuler un nombre suffisant de parties pour chaque configuration. La fonction esp_gain_b nous donne une matrice (data frame) contenant les probabilités de la configuration (ex 0.1 ; 0.3 ; 0.6) et l’esperance du gain associé.
esp_gain_b = function(proba_a=c(1/4,1/4,1/2)){
esp_b = c();
x = 0;
y = 0;
i = 1;
dataF = c();
dataP = c();
dataC = c();
while(x<=1){
while(y<=1 && x+y<=1){
val3 = 1 - x - y;
if(val3<0) val3 = 0;
dataP[i] = x;
dataF[i] = y;
dataC[i] = val3;
esp_b[i] = n_parties (proba_B = c(x,y,val3),proba_A = proba_a)
i = i + 1;
y = y + 0.1;
}
y = 0;
x = x + 0.1;
}
return(data.frame(dataP,dataF,dataC,esp_b));
}
data_frame=esp_gain_b()Nous pouvons alors analyser les résultats obtenus à l’aide de graphes.
with(data_frame,plot(dataF,esp_b,xlab = "Probabilité de jouer Feuille",ylab = "Espérance de gain de B"))
Tout d’abord, on observe que l’espérance de gain est forte lorsque la probabilité de jouer Feuille est nulle. Le joueur B doit donc éviter à tout prix de jouer Feuille pour maximiser ses gains.
with(data_frame,plot(dataP,esp_b,xlab = "Probabilité de jouer Pierre",ylab = "Espérance de gain de B"))
Ensuite, plus la probabilité de jouer Pierre est forte, plus le joueur B à de chances de gagner. Il doit donc jouer Pierre le plus de fois possible.
regression<- lm(esp_b ~ dataC ,data = data_frame)
with(data_frame,plot(dataC,esp_b,xlab = "Probabilité de jouer Ciseau",ylab = "Espérance des gains de B"))
abline(regression,col="red")
Enfin, on observe que la probabilité de jouer Ciseaux n’a pas d’’importance’influences sur l’espérance de gain du joueur B. En moyenne, le joueur B ne va pas gagner de points.
La stratégie optimale pour B est donc de jouer uniquement Pierre. En effet, cela est compréhensible car A a une probabilité plus élevé de jouer Ciseaux. Donc l’espérance de gain sera plus élevé quand Pierre aura le plus de chance d’être joué. On peut noter qu’il ne faut en aucun cas jouer la Feuille car on a de très gros risques de perdre (comme le joueur A joue souvent Ciseaux). La configuration optimale du joueur B est donc de jouer Pierre avec une probabilité de 1 (d’où x=1 et y=0). Par simulation on observe une espérance associée de 0.25 environ (nous regardons la première ligne lorsque l’attribut espérance du data_frame est rangé en ordre décroissant.
Essayons maintenant de retrouver tous ces résultats à l’aide d’un calcul exact. Soit une partie de Pierre Feuille Ciseaux une expérience aléatoire et soient A et B deux variables aléatoires correspondant respectivement au choix entre Pierre, Feuille ou Ciseaux des joueurs A et B. Soient (1/4,1/4,1/2) et (x,y,1-x-y) les probabilités de A et de B de choisir entre Pierre, Feuille et Ciseaux. Nous cherchons une configuration (stratégie) pour que B soit gagnant, cela revient à trouver la configuration qui maximise l’espérance de gain du joueur B, soit X cette espérance. On a alors \(X=gains * Probabilité De Gagner - pertes * Probabilité De Perdre\) D’où \(X= P((B='F') \cap (A='P')) + P((B='P') \cap (A='C')) + P((B='C') \cap (A='F')) - P((B='F') \cap (A='C')) - P((B='C') \cap (A='P')) - P((B='P') \cap (A='F'))\). Nous savons à ce stade que A et B sont indépendants car le choix du joueur B et totalement indépendant du choix du joueur A. Donc on obtient : \(X=P(B='F') * P(A='P') + P(B='P') * P(A='C') + P(B='C') * P(A='F') - P(B='F') * P(A='C') - P(B='C') * P(A='P') - P(B='P') * P(A='F') = y/4 + x/2 + (1-x-y)/4 -y/2 - (1-x-y)/4 - x/4 = x/4 - y/4.\) Or nous souhaitons maximiser l’espérance (MAX (X)). Pour maximiser cette soustraction, nous devons maximiser x et minimiser y. On doit alors mettre x à 1 et y à 0. L’espérance de gain associée à cette stratégie est alors de 0.25.
Le joueur non biaisé :
Reprennons les mêmes questions que précédemment avec le joueur A non biaisé, c’est à dire avec la même probabilité de jouer Pierre Feuille ou Ciseaux(1/3,1/3,1/3).
- Nous estimons l’esperance de gain du joueur B grâce à la fonction que nous avons faite dans la partie précedente. On a P(B)=(1/4,1/4,1/2).
n_parties(proba_A = c(1/3,1/3,1/3))## [1] 0.002Par simulation, on observe une espérance de gain nulle. Une telle configuration semble conduire à un jeu équilibré.
- Nous estimons l’esperance de gain du joueur B grâce à la fonction que nous avons faite dans la partie précedente. On a P(B)=P(A)=(1/3,1/3,1/3).
n_parties(proba_A = c(1/3,1/3,1/3), proba_B = c(1/3,1/3,1/3))## [1] 0.0077Par simulation, on observe une espérance de gain nulle. Une telle configuration semble aussi conduire à un jeu équilibré.
data_frame_2=esp_gain_b(proba_a = c(1/3,1/3,1/3))Nous pouvons alors analyser les résultats obtenus à l’aide de graphes.
regression<- lm(esp_b ~ dataF ,data = data_frame_2)
with(data_frame_2,plot(dataF,esp_b,xlab = "Probabilité de jouer Feuille",ylab = "Espérance des gains de B"))
abline(regression,col="red")
regression<- lm(esp_b ~ dataP ,data = data_frame_2)
with(data_frame_2,plot(dataP,esp_b,xlab = "Probabilité de jouer Pierre",ylab = "Espérance des gains de B"))
abline(regression,col="red")
regression<- lm(esp_b ~ dataC ,data = data_frame_2)
with(data_frame_2,plot(dataC,esp_b,xlab = "Probabilité de jouer Ciseau",ylab = "Espérance des gains de B"))
abline(regression,col="red")
Dans les graphes ci-dessus, on ne peut pas distinguer de stratégies pour maximiser les gains de B. En moyenne, ce jeu est équilibré, l’espérance de gain est nulle.
Nous ne pouvons pas trouver de stratégie optimale pour le joueur B car le jeu est équilibré et les joueurs n’ont pas de mémoire.
Essayons maintenant de retrouver ce résusltat d’un calcul exact. Soit une partie de Pierre Feuille Ciseauxune expérience aléatoire et soit A et B deux variables aléatoires correspondant respectivement au choix entre Pierre, Feuille ou Ciseauxdes joueurs A et B. Soient (1/3,1/3,1/3) et (x,y,1-x-y) les probabilités de A et de B de choisir en Pierre, Feuille et Ciseau. Nous cherchons une configuration (stratégie) pour que B soit gagnant, cela revient a trouver la configuration qui maximise l’espérance de gain du joueur B, soit X cette espérance. On a alors \(X=gains x probabilité de gagner - perte x probabilité de perdre = P((B='F') \cap (A='P')) + P((B='P') \cap (A='C')) + P((B='C') \cap (A='F')) - P((B='F') \cap (A='C')) - P((B='C') \cap (A='P')) - P((B='P') \cap (A='F')).\) Nous savons à ce stade que A et B sont indépendants car le choix du joueur B et totalement indépendant du choix du joueur A. Donc on obtien :\(X=P(B='F') * P(A='P') + P(B='P') * P(A='C') + P(B='C') * P(A='F') - P(B='F') * P(A='C') - P(B='C') * P(A='P') - P(B='P') * P(A='F') = y/3 + x/3 + (1-x-y)/3 -y/3 - (1-x-y)/3 - x/3 = 0\). Donc X=0. L’espérance est donc nulle, il n’y a pas de stratégie à avoir.
Au final, un joueur non biaisé ne peut ni perdre ni gagner car nous venons de prouver que le jeu est équilibré (espérance de gain est nulle).
Question 2: Apprentissage
1 et 2. Dans cette partie, nous allons simuler une liste de coup aléatoire pour le joueur A. Comme le joueur A est un humain, nous pouvons suspecter une mauvaise uniformité. La stratégie la plus naïve peut être de garder la même stratégie. C’est à dire jouer uniquement le même coup pour maximiser les gains du joueur B. Cependant, nous jouons contre un être humain disposant d’une mémoire. Nous adoptons alors la stratégie suivante, nous allons jouer pour contrer le manque d’uniforminté. Par exemple, si on observe chez l’adversaire une probabilité 0.6 de jouer Pierre alors nous allons jouer Feuille à une probabilité de 0.6.
generation = function (nombre_coups=10000,proba_A=c(1/4,1/4,1/2)){
l<-list()
for(i in 1:nombre_coups){
l[length(l)+1]=sample(size = 1,x = c('P','F','C'),prob = proba_A);
}
return (l)
}
apprentissage = function (nombre_coup=10000,proba_a=c(0.354,0.296,0.35)) {
l=generation(nombre_coups = nombre_coup, proba_A = proba_a);
coups_A<-list();
proba_P=1/3;
proba_F=1/3;
proba_C=1/3;
B=0;
gain_B=c();
E_gain_B=c();
nbr_P=0;
nbr_F=0;
nbr_C=0;
for(i in 1:nombre_coup){
#Tirage de Pierre Feuille Ciseau
elementA=l[i];
elementB=sample(size = 1,x = c("P","F","C"),prob = c(proba_P,proba_F,proba_C));
coups_A[i]=elementA;
#Etude fréquentielle du joueur A
if(coups_A[i]=='P'){
nbr_P=nbr_P+1;
}
else if (coups_A[i]=='F'){
nbr_F=nbr_F+1;
}
else {
nbr_C=nbr_C+1;
}
proba_P = nbr_C/length(coups_A);
proba_F = nbr_P/length(coups_A);
proba_C = nbr_F/length(coups_A);
# Calcul du gain de B
if( (elementA=="P"&&elementB=="F") || (elementA=="C"&&elementB=="P") || (elementA=="F"&&elementB=="C") ) {
B=B+1;
}
if( (elementA=="P"&&elementB=="C") || (elementA=="F"&&elementB=="P") || (elementA=="C"&&elementB=="F") ) {
B=B-1;
}
#Mémorisation du gain
E_gain_B[i]=B/i;
gain_B[i]=B;
#On passe au coup suivant
l[-1];
}
plot (gain_B,xlab =" Temps (nombre de tours)",ylab = "Gain du joueur B")
plot (E_gain_B,xlab =" Temps (nombre de tours)",ylab = "Espérance du gain du joueur B")
abline(h=mean(E_gain_B),col="red")
}
apprentissage(nombre_coup=10000,proba_a=c(0.25,0.25,0.5))
Lorsque nous testons notre algorithme sur le vecteur de probabilité (0.25,0.25,0.5), on observe que l’espérance de gain est toujours positive (pour un certain nombre de lancés car il faut “laisser le temps de l’apprentissage”). Si le nombre de partie est suffisante (pour avoir une analyse fréquentielle représentative de l’adversaire) et si nous jouons suffisamment de fois, alors nous sommes certain de gagner contre notre adversaire.
- D’apèrs la world papaer society, l’humain aura les probabilités (0.354,0.296,0.35) de jouer respectivement (Pierre, Feuille, Ciseaux). Nous pouvons alors tester notre algorithme avec ces probabilités.
apprentissage()
Après plusieurs expériences, nous ne pouvons pas aboutir à des conclusions formelles. En effet, les fréquences du joueur A sont trop proches pour que notre algorithme batte l’humain à tous les coups. Nous pouvons l’améliorer en regardant les cas où le joueur A joue deux fois le même symbole. En effet, l’être humain aura une faible tendance à jouer le même symbole plus de deux fois. On peut alors anticiper le prochain coup. Par exemple, si le joueur A a déjà joué 3 fois Feuille, il est peut probable qu’il joue encore Feuille. Nous pouvons alors diminuer la probabilité des Ciseaux et augmenter la probabilité de la Pierre. Pour cela, nous devons faire attention à la génération des coups du joueur A. En effet, la génération n’est plus vraiment aléatoire. On fait l’hypothèse que le joueur jouera très rarement 4 symboles identiques (successivement).
generation_humain = function (nombre_coups=1000,proba_A=c(1/4,1/4,1/2)){
#nous obligeons la génération à ne jamais fournir une suite successive de plus de 3 mêmes symboles
l=generation(nombre_coups,proba_A)
for(i in 1:nombre_coups){
if(i>3 && (l[i]=='F' && l[i-1]=='F'&& l[i-2]=='F') ) {
l[i]=sample(size = 1,x = c("P","C"),prob = c(0.5,0.5));
}else if (i>3 && (l[i]=='P' && l[i-1]=='P'&& l[i-2]=='P') ){
l[i]=sample(size = 1,x = c("P","C"),prob = c(0.5,0.5)); }
else if (i>3 && (l[i]=='C' && l[i-1]=='C'&& l[i-2]=='C') ) {
l[i]=sample(size = 1,x = c("P","C"),prob = c(0.5,0.5)); }
}
return (l)
}
apprentissage_humain = function (nombre_coup=10000,proba_a=c(0.354,0.296,0.35)) {
l=generation_humain(nombre_coups = nombre_coup, proba_A = proba_a);
coups_A<-list();
proba_P=1/3;
proba_F=1/3;
proba_C=1/3;
B=0;
gain_B=c();
E_gain_B=c();
nbr_P=0;
nbr_F=0;
nbr_C=0;
for(i in 1:nombre_coup){
#Tirage de Pierre Feuille Ciseau
elementA=l[i];
elementB=sample(size = 1,x = c("P","F","C"),prob = c(proba_P,proba_F,proba_C));
coups_A[i]=elementA;
if ( i>3 && coups_A[i]=='F' &&coups_A[i-1]=='F'&&coups_A[i-2]=='F' ){
nbr_F=nbr_F+1;
proba_F = nbr_P/length(coups_A);
#Si le joueur A a déjà joué 3 fois Feuille, il est peut probable qu'il joue encore Feuille. Diminuons alors la probabilité des Ciseaux et augmentons la probabilité de la Pierre.
elementB=sample(size = 1,x = c("P","F","C"),prob = c(proba_P+0.75*proba_C,proba_F,proba_C-0.75*proba_C));
}
else if ( i>3 && coups_A[i]=='P' &&coups_A[i-1]=='P'&&coups_A[i-2]=='P' ){
nbr_P=nbr_P+1;
proba_P = nbr_C/length(coups_A);
#Si le joueur A a déjà joué 3 fois Pierre, il est peut probable qu'il joue encore Pierre. Diminuons alors la probabilité de la Feuille et augmentons la probabilité des Ciseaux.
elementB=sample(size = 1,x = c("P","F","C"),prob = c(proba_P,proba_F-0.75*proba_F,proba_C+0.75*proba_F));
}
else if ( i>3 && coups_A[i]=='C' &&coups_A[i-1]=='C'&&coups_A[i-2]=='C' ){
nbr_C=nbr_C+1;
proba_C = nbr_F/length(coups_A);
#Si le joueur A a déjà joué 3 fois Ciseaux, il est peut probable qu'il joue encore Ciseaux. Diminuons alors la probabilité de la pierre et augmentons la probabilité de la feuille
elementB=sample(size = 1,x = c("P","F","C"),prob = c(proba_P-0.75*proba_P,proba_F+0.75*proba_P,proba_C));
}
else{
#Etude fréquentielle du joueur A
if(coups_A[i]=='P'){
nbr_P=nbr_P+1;
}
else if (coups_A[i]=='F'){
nbr_F=nbr_F+1;
}
else {
nbr_C=nbr_C+1;
}
proba_P = nbr_C/length(coups_A);
proba_F = nbr_P/length(coups_A);
proba_C = nbr_F/length(coups_A);
}
# Calcul du gain de B
if( (elementA=="P"&&elementB=="F") || (elementA=="C"&&elementB=="P") || (elementA=="F"&&elementB=="C") ) {
B=B+1;
}
if( (elementA=="P"&&elementB=="C") || (elementA=="F"&&elementB=="P") || (elementA=="C"&&elementB=="F") ) {
B=B-1;
}
#Mémorisation du gain
E_gain_B[i]=B/i;
gain_B[i]=B;
#On passe au coup suivant
l[-1];
}
plot (gain_B,xlab =" Temps (nombre de tours)",ylab = "Gain du joueur B")
plot (E_gain_B,xlab =" Temps (nombre de tours)",ylab = "Espérance du gain du joueur B")
abline(h=mean(E_gain_B),col="red")
}
apprentissage_humain(nombre_coup=10000,proba_a=c(0.25,0.25,0.5))
Finalement, nous observons que notre algorithme final posssède une esperance de gain positive. Nous avons créé un algorithme simple qui arrive à battre un humain (si on suppose que l’être humain a du mal à maintenir l’uniformité).