DM PS : Pierre Feuille Ciseaux

\(\\\)
\(\\\)
\(\\\)
\(\\\)
\(\\\)

Question 1 :

Le joueur biaisé

On suppose que le joueur A joue avec probabilités P(A) = (1/4, 1/4, 1/2). On va, dans la suite du DM, considérer la notation suivante :
jR : “Le joueur j joue pierre (Rock)”,
jP : “Le joueur j joue papier (Paper)”,
jS : “Le joueur j joue ciseaux (Scissors)”, où j prendra les valeurs A ou B.

1. Estimer l’espérance de gain du joueur B contre le joueur A lorsque P(B) = (1/4, 1/4, 1/2).

Generator_one_game = function (Pb, Pa = c(1/4, 1/4, 1/2)){
  a = sample(c('R', 'P', 'S'), 1, T, Pa);
  b = sample(c('R', 'P', 'S'), 1, T, Pb);
  if((b == 'R' && a == 'S') || (b == 'P' && a == 'R') || (b == 'S' && a == 'P')){ 
    gain = 1;
  }
  else {
    if((a == 'R' && b == 'S') || (a == 'P' && b == 'R') || (a == 'S' && b == 'P')){
      gain = -1;
    }
    else {
      gain = 0;
    }
  }
  gain;
}

Generator_n_game = function (N = 1000, Pb, Pa = c(1/4, 1/4, 1/2)){
  gains = c();
  for(i in 1:N){
    gains = c(gains, Generator_one_game(Pb, Pa));
  }
  gains;
}

N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(Generator_n_game(Pb = c(1/4, 1/4, 1/2))));
}

mean(esp);

## [1] -0.00282

plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.5, 0.5), esp);

Lorsqu’on simule 100 parties de 1000 tours en mémorisant les gains finaux de B, on voit que, en faisant la moyenne, l’espérance est de 0. De plus, grâce au graphe, on remarque qu’il n’y a pas une grande variation entre les valeurs. On peut donc en déduire que l’espérance de gain de B est de 0 dans ces conditions.

2. Même question lorsque P(B) = (1/3, 1/3, 1/3).

N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(Generator_n_game(Pb = c(1/3, 1/3, 1/3))));
}

mean(esp);

## [1] -0.00274

Une nouvelle fois, on voit, en faisant la moyenne, que l’espérance de gain du joueur B tourne au alentour de 0.

3. Estimer l’espérance de gain du joueur B tel que P(B)=(x, y, 1−x−y) lorsque x et y varient entre 0 et 1 par pas de 0.1 ?

Simulation = function(N = 5000, Pa = c(1/4, 1/4, 1/2)){
  # Creation de 2 tableaux allant de 0 a 1 avec un pas de 0.1
  x = seq(from = 0, to = 1, by = 0.1);
  y = seq(from = 0, to = 1, by = 0.1);
  esp = c();
  # On parcourt les 2 tableaux
  for(i in 1:length(x)){
    for(j in 1:length(y)){
      # Pour toutes les combinaison de x et y possibles (avec 1-x-y >= 0), ...
      if((1-x[i]-y[j]) >= 0){
        # ... on simule une partie 1000 et on mets la moyenne de gain dans le tableau esp
        esp = c(esp, mean(Generator_n_game(N, c(x[i], y[j], (1-x[i]-y[j])), Pa)));
      }
    }
  }
  esp;
}

plot(xlab = 'Combinaisons', ylab = 'Esperance', Simulation());

En faisant un simple graphe de l’espérance en fonction des combinaisons de probabilités, on voit très facilement que c’est le dernier test qui donne à B la meilleure espérance de gains, soit quand P(B) = (1, 0, 0). Ce résultat n’est peut être pas évident au premier coup d’oeil, mais lorsqu’on lit le code de la fonction ‘Simulation()’ tout devient plus claire.
En effet, on commence par créer deux tableaux, x et y, qui contiennent des valeurs allant de 0 à 1, avec un pas de 0.1. On parcourt ensuite toutes les valeurs de x et de y, via deux boucles imbriquées, en stockant, pour chaque valeurs possibles l’espérance engendrée, et enfin on affiche le graphe des esperances en fonction des différents tests.
Et enfin, comme énoncé plus haut, on voit avec le graphe que c’est la derniere combinaison qui a de meilleurs resultats (soit x = 1 et y = 0).

N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(Generator_n_game(N = 1000, Pb = c(1, 0, 0))));
}
mean(esp);

## [1] 0.25141

Pour vérifier le resultat prédécent, on vérifie en faisant une simple simulation ci-dessus, on voit que l’espérance du joueur B ne jouant que Pierre a un espérance d’environ 0.25, ce qui concordonne avec le résultat précédent.

4. Déduisez-en la stratégie optimale pour le joueur B.

Si le joueur A est biasé et qu’il joue ciseaux le plus souvent, le joueur B devrait tout le temps jouer pierre. En effet, en ayant cette stratégie, il gagnera ainsi la moitié du temps, et perdra un quart du temps, il aura donc un gain moyen de \(\frac{1}{2} - \frac{1}{4} = \frac{1}{4}\) (ce que l’on retrouve avec la question précédente).

5. Retrouver et vérifier les résultats précédents à l’aide d’un calcul exact de ces espérances (i.e, en obtenant une formule dépendant de x et de y).

Soit X la variable aléatoire suivant la loi suivante :

\(X = 1\), si B gagne,

\(X = 0\), si il y a égalité,

\(X = -1\), si B perd.

On calcule maintenant les probabilités associées aux valeurs prises par X.

\[\begin{equation} P(X = 1) = (P(BR) \cap P(AS)) \cup ((P(BP) \cap P(AR)) \cup (P(BS) \cap P(AP)) \\ = (x \times \frac{1}{2}) + (y \times \frac{1}{4}) + ((1-x-y) \times \frac{1}{4}) \\ = \frac{2x + y + 1 - x - y}{4} = \frac{1 + x}{4} \\ \\ P(X = 0) = (P(BR) \cap P(AR)) \cup ((P(BP) \cap P(AP)) \cup (P(BS) \cap P(AS)) \\ = (x \times \frac{1}{4}) + (y \times \frac{1}{4}) + ((1-x-y) \times \frac{1}{2}) \\ = \frac{x + y + 2 - 2x - 2y}{4} = \frac{2 - x - y}{4} \\ \\ P(X = -1) = (P(BR) \cap P(AP)) \cup ((P(BP) \cap P(AS)) \cup (P(BS) \cap P(AP)) \\ = (x \times \frac{1}{4}) + (y \times \frac{1}{2}) + ((1-x-y) \times \frac{1}{4}) \\ = \frac{x + 2y + 1 - x - y}{4} = \frac{1 + y}{4} \\ \\ \end{equation}\]

On a donc la loi de probabilité suivante :

xi	X = 1	X = 0	X = -1
\(P(X = x_i)\)	\(\frac{1 + x}{4}\)	\(\frac{2-x-y}{4}\)	\(\frac{1 + y}{4}\)

On peut maintenant calculer l’espérance \(E(X)\)

\[\begin{equation} E(X) = \sum_{i=1}^{3} P(X = x_i) \times x_i\\ = 1 \times \frac{1 + x}{4} + 0 \times \frac{2 - x - y}{4} + (-1) \times \frac{1 + y}{4}\\ = \frac{1 + x}{4} - \frac{1 + y}{4} = \frac{x - y}{4} \\ \\ \end{equation}\]

On voit très clairement que plus B jouera Pierre, plus son espérance d’avoir un gain sera grande. De plus, l’espérance ne peut dépacer une valeur de 1/4, car x et y, étant des propabilités, varient entre 0 et 1.

\(\\\)
\(\\\)
\(\\\)

Le joueur non biaisé

1. Mêmes questions que précédemment mais lorsque le joueur A est non biaisé, i.e., lorsque P(A) = (1/3, 1/3, 1/3).

N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(Generator_n_game(Pb = c(1/4, 1/4, 1/2), Pa = c(1/3, 1/3, 1/3))));
}

mean(esp);

## [1] 0.00124

plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.5, 0.5), esp);

N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(Generator_n_game(Pb = c(1/3, 1/3, 1/3), Pa = c(1/3, 1/3, 1/3))));
}
plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.5, 0.5), esp);

2. Un joueur non biaisé peut-il perdre ? Peut-il gagner ?

Oui un joueur peut perdre ou gagner lors d’une partie, évidemment, cepandant, si nous parlons, d’un très grand nombre de partie un joueur non biasée aura une espérance de gain de 0.

\(\\\)
\(\\\)
\(\\\)
\(\\\)
\(\\\)

Question 2 : Apprentissage

1. Proposez un algorithme qui “apprenne” les fréquences de jeu d’un adversaire et s’y adapte optimalement en permanence.

L’idée de l’agorithme est qu’on va, à partir d’une sauvegarde des symboles précédemment joués par l’adversaire, déduire de la probabilité d’apparition de chaque symboles. L’algorithme proposé est donc le suivant :

Algorithm = function(past = NULL){
  if(length(past) < 1){
    'P';
  }
  else {
    Pb = c(0, 0, 0);
    start = 1;
    end = length(past)
    if(end > 50){
      start = length(past) - 50;
    }
    for(i in start:end){
      if (past[i] == 'R'){
        Pb[1] = Pb[1] + 1;
      }
      if (past[i] == 'P'){
        Pb[2] = Pb[2] + 1;
      }
      if (past[i] == 'S'){
        Pb[3] = Pb[3] + 1;
      }
    }
    
    if(Pb[1] > Pb[2] && Pb[1] > Pb[3]){
      'P';
    }
    else {
      if(Pb[2] > Pb[3]){
        'S';
      }
      else {
        'R';
      }
    }
  }
}

Si la sauvegarde est vide, alors on joue papier (pierre étant le plus joué des symboles pour ouvrir un match). Si on a une sauvegarde alors on va prendre les 50 dernieres valeurs (si elles exitent) et compter le nombre occurence de chaque symbole. Il nous suffit maintenant de trouver celui qui apparait le plus et de le contrer avec le bon symbole. Il nous reste qu’à l’utiliser dans une fonction qui simulera une partie.

One_game = function(Pa = c(1/4, 1/4, 1/2), past = NULL){
  b = Algorithm(past)
  a = sample(c('R', 'P', 'S'), 1, T, Pa);
  gain = 0;
  if((b == 'R' && a == 'S') || (b == 'P' && a == 'R') || (b == 'S' && a == 'P')){ 
    gain = 1;
  }
  else {
    if((a == 'R' && b == 'S') || (a == 'P' && b == 'R') || (a == 'S' && b == 'P')){
      gain = -1;
    }
  }
  list(gain, a);
}

2. Évaluer le gain de votre algorithme contre un joueur biaisé qui jouerait avec P(A) = (1/4,1/4,1/2).

N_games = function(N = 5000, Pa = c(1/4, 1/4, 1/2)){
  past = c();
  gain = c();
  for(i in 1:N){
    res = One_game(Pa, past);
    gain = c(gain, res[[1]]);
    past = c(past, res[[2]]);
  }
  gain;
  mean(gain);
}

N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(N_games()));
}

plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(0, 0.5), esp);

Avec notre algorithme, nous obtenons une espérance avoisinant les 0.25 de gain, ce qui est, d’après les questions précédentes une bonne performance.

3. N’hésitez pas à visualiser l’évolution du jeu au cours du temps. Votre algorithme a-t-il une chance de battre un humain pas trop bête? Comment pourriez-vous simplement l’améliorer?

N = 100;
esp = c();

for(i in 1:N){
  esp = c(esp, mean(N_games(Pa = c(1/3, 8/27, 10/27))));
}

plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.1, 0.2), esp);

esp = c();

for(i in 1:N){
  esp = c(esp, mean(N_games(Pa = c(1/3, 1/3, 1/3))));
}

plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.2, 0.2), esp);

Comme on le voit plus haut, notre algorithme est en moyenne capable de battre un joueur humain pas trop bète, c’est à dire, dont les probabilités sont proches de l’uniformité. De plus, contre un joueur non biaisé, notre algorithme à une espérance de 0. Cependant, notre algorithme n’est pas performant pour ce qui est du temps d’execution, en effet lorsqu’on lui demande de faire des parties de 5 000 tours, il prend énormément de temps à s’éxécuter.

4. Vous évaluerez la performance de votre nouvel algorithme contre un joueur biaisé qui jouerait avec P(A) = (1/4, 1/4, 1/2).

\(\\\)
\(\\\)
\(\\\)
\(\\\)
\(\\\)

Question 3 : Big Bang Theory

On va considérer la notation suivante :
jR : “Le joueur j joue pierre (Rock)”,
jP : “Le joueur j joue papier (Paper)”,
jSc : “Le joueur j joue ciseaux (Scissors)”,
jL : “Le joueur j joue lézard (Lizard)”,
jSp : “Le joueur j joue Spock (Spock)”, où j prendra les valeurs A ou B.

On va tout d’abord créer des fonctions permettant la simulation du jeu avec un joueur A biaisé : P(A) = (0.1, 0.1, 0.1, 0.1, 0.6)

Generator_one_game2 = function (Pb, Pa = c(0.1, 0.1, 0.1, 0.1, 0.6)){
  a = sample(c('R', 'P', 'Sc', 'L', 'Sp'), 1, T, Pa);
  b = sample(c('R', 'P', 'Sc', 'L', 'Sp'), 1, T, Pb);
  # On énumere tout les cas resultant à la victoire de B
  if((b == 'R' && a == 'Sc') || (b == 'R' && a == 'L') || (b == 'P' && a == 'R') || (b == 'P' &&  a == 'Sp') || (b == 'Sc' && a == 'P') || (b == 'Sc' && a == 'L') || (b == 'Sp' && a == 'Sc') && (b == 'Sp' || a == 'P') || (b == 'L' && a == 'P') || (b == 'L' && a == 'Sp')){ 
    gain = 1;
  }
  else {
    # On énumere tout les cas resultant à la perte de B
    if((b == 'R' && a == 'P') || (b == 'R' && a == 'Sp') || (b == 'P' && a == 'Sc') || (b == 'P' && a == 'L') || (b == 'Sc' && a == 'Sp') || (b == 'Sc' && a == 'P') || (b == 'Sp' && a == 'L') || (b == 'Sp' &&a == 'P') || (b == 'L' && a == 'P') || (b == 'L' && a == 'Sc')){
      gain = -1;
    }
    else {
      gain = 0;
    }
  }
  gain;
}

Generator_n_game2 = function (N = 1000, Pb, Pa = c(0.1, 0.1, 0.1, 0.1, 0.6)){
  gains = c();
  for(i in 1:N){
    gains = c(gains, Generator_one_game2(Pb, Pa));
  }
  gains;
}

N = 100;
esp = c();

for(i in 1:N){
  esp = c(esp, mean(Generator_n_game2(Pb = c(1/5, 1/5, 1/5, 1/5, 1/5))));
}
plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.5, 0.5), esp);

On va estimer l’espérance de gain de B tel que P(A) = (0.1, 0.1, 0.1, 0.1, 0.6) et P(B) = (x, y, z, t, 1-x-y-z-t). Soit X la variable aléatoire suivant la loi suivante :

\(X = 1\), si B gagne,
\(X = 0\), si il y a égalité,
\(X = -1\), si B perd.

On calcule maintenant les probabilités associées aux valeurs prises par X.

\[\begin{equation} P(X = 1) = (P(BR) \cap P(ASc)) \cup (P(BR) \cap P(AL)) \cup ((P(BP) \cap P(AR)) \cup ((P(BP) \cap P(ASp)) \\ \cup (P(BSc) \cap P(AP)) \cup (P(BSc) \cap P(AL)) \cup (P(BL) \cap P(AP)) \cup (P(BL) \cap P(ASp)) \\ \cup (P(BSp) \cap P(ASc)) \cup (P(BSp) \cap P(AR)) \\ = 0.1 \times x + 0.1 \times x + 0.1 \times y + 0.6 \times y + 0.1 \times z + 0.1 \times z + \\ 0.1 \times t + 0.6 \times t + 0.1 \times (1-x-y-z-t) + 0.1 \times (1-x-y-z-t) \\ = \frac{2x + 7y + 2z + 7t + 2 - 2x - 2y - 2z - 2t}{10} = \frac{2 + 5y + 5t}{10} \\ \\ P(X = 0) = (P(BR) \cap P(AR)) \cup ((P(BP) \cap P(AP)) \cup (P(BSc) \cap P(ASc)) \cup ((P(BL) \cap P(AL)) \\ \cup (P(BSp) \cap P(ASp)) \\ = (0.1 \times x) + (0.1 \times y) + (0.1 \times z) + (0.1 \times t) + (0.6 \times (1-x-y-z-t)) \\ = \frac{x + y + z + t + 6 - 6x - 6y - 6z - 6t}{10} = \frac{6 - 5x - 5y - 5z - 5t}{10} \\ \\ P(X = -1) = (P(BR) \cap P(AP)) \cup (P(BR) \cap P(ASp)) \cup ((P(BP) \cap P(ASc)) \cup ((P(BP) \cap P(AL)) \\ \cup (P(BSc) \cap P(AR)) \cup (P(BSc) \cap P(ASp)) \cup (P(BL) \cap P(AR)) \cup (P(BL) \cap P(ASc)) \\ \cup (P(BSp) \cap P(AP)) \cup (P(BSp) \cap P(AL)) \\ = 0.1 \times x + 0.6 \times x + 0.1 \times y + 0.1 \times y + 0.1 \times z + 0.6 \times z + \\ 0.1 \times t + 0.6 \times t + 0.1 \times (1-x-y-z-t) + 0.1 \times (1-x-y-z-t) \\ = \frac{7x + 2y + 7z + 2t + 2 - 2x - 2y - 2z - 2t}{10} = \frac{2 + 5x + 5z}{10} \\ \\ \end{equation}\]

On a donc la loi de probabilité suivante :

xi	X = 1	X = 0	X = -1
\(P(X = x_i)\)	\(\frac{2 + 5y + 5t}{10}\)	\(\frac{6 - 5x - 5y - 5z - 5t}{10}\)	\(\frac{2 + 5x + 5z}{10}\)

On peut maintenant calculer l’espérance \(E(X)\)

\[\begin{equation} E(X) = \sum_{i=1}^{3} P(X = x_i) \times x_i\\ = 1 \times \frac{2 + 5y + 5t}{10} + (-1) \times \frac{2 + 5x + 5z}{10} = \frac{y + t - x - z}{2} \\ \\ \end{equation}\]

Le gain du joueur sera donc plus grand si, sur un grand nombre de tours, il ne joue que Papier et Lézard. On peut donc faire un algorithme similaire au précédent pour gagner contre un humain, il nous suffit seulement d’ajouter les cas du Lézard et de Spock.

L’idée de l’agorithme reste la même qu’on va sauvegarder des symboles joués de A et en déduire de la probabilité d’apparition de chaque symboles. L’algorithme proposé est donc le suivant :

Algorithm2 = function(past = NULL){
  if(length(past) < 1){
    'P';
  }
  else {
    Pb = c(0, 0, 0, 0, 0);
    start = 1;
    end = length(past)
    if(end > 50){
      start = length(past) - 50;
    }
    for(i in start:end){
      if (past[i] == 'R'){
        Pb[1] = Pb[1] + 1;
      }
      if (past[i] == 'P'){
        Pb[2] = Pb[2] + 1;
      }
      if (past[i] == 'Sc'){
        Pb[3] = Pb[3] + 1;
      }
      if (past[i] == 'L'){
        Pb[4] = Pb[4] + 1;
      }
      if (past[i] == 'Sp'){
        Pb[5] = Pb[5] + 1;
      }
    }
    
    if(Pb[1] > Pb[2] && Pb[1] > Pb[3] && Pb[1] > Pb[4] && Pb[1] > Pb[5]){
      sample(c('P', 'Sp'), 1, T); #On choisit aléatoirement de symbole à jouer
    }
    else {
      if(Pb[2] > Pb[3] && Pb[2] > Pb[4] && Pb[2] > Pb[5]){
        sample(c('Sc', 'L'), 1, T);
      }
      else {
        if(Pb[3] > Pb[4] && Pb[3] > Pb[5]){
          sample(c('R', 'Sp'), 1, T);
        }
        else {
          if(Pb[4] > Pb[5]){
            sample(c('R', 'Sc'), 1, T);
          }
          else {
            sample(c('P', 'L'), 1, T);
          }
        }
      }
    }
  }
}

One_game2 = function(Pa = c(1/10, 1/10, 1/10, 1/10, 3/5), past = NULL){
  b = Algorithm2(past)
  a = sample(c('R', 'P', 'Sc', 'L', 'Sp'), 1, T, Pa);
  if((b == 'R' && a == 'Sc') || (b == 'R' && a == 'L') || (b == 'P' && a == 'R') || (b == 'P' &&  a == 'Sp') || (b == 'Sc' && a == 'P') || (b == 'Sc' && a == 'L') || (b == 'Sp' && a == 'Sc') && (b == 'Sp' || a == 'P') || (b == 'L' && a == 'P') || (b == 'L' && a == 'Sp')){ 
    gain = 1;
  }
  else {
    if((b == 'R' && a == 'P') || (b == 'R' && a == 'Sp') || (b == 'P' && a == 'Sc') || (b == 'P' && a == 'L') || (b == 'Sc' && a == 'Sp') || (b == 'Sc' && a == 'P') || (b == 'Sp' && a == 'L') || (b == 'Sp' &&a == 'P') || (b == 'L' && a == 'P') || (b == 'L' && a == 'Sc')){
      gain = -1;
    }
    else {
      gain = 0;
    }
  }
  list(gain, a);
}

N_games2 = function(N = 1000, Pa = c(1/10, 1/10, 1/10, 1/10, 3/5)){
  past = c();
  gain = c();
  for(i in 1:N){
    res = One_game2(Pa, past);
    gain = c(gain, res[[1]]);
    past = c(past, res[[2]]);
  }
  gain;
  mean(gain);
}


N = 100
esp = c();

for(i in 1:N){
  esp = c(esp, mean(N_games2()));
}

plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(0, 1), esp);