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

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 les notations suivantes :
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).

# Générateur d'un tour
Generator_one_game = function (Pb, Pa = c(1/4, 1/4, 1/2)){
  # On tire aléatoirement le geste des joueurs selon leur propabilité
  a = sample(c('R', 'P', 'S'), 1, T, Pa);
  b = sample(c('R', 'P', 'S'), 1, T, Pb);
  # Si B gagne 
  if((b == 'R' && a == 'S') || (b == 'P' && a == 'R') || (b == 'S' && a == 'P')){ 
    gain = 1;
  }
  else {
    # Si B pert
    if((b == 'R' && a == 'P') || (b == 'P' && a == 'S') || (b == 'S' && a == 'R')){
      gain = -1;
    }
    else { # Sinon il y a égalité
      gain = 0;
    }
  }
  # On retourne le gain du tour
  gain;
}

# Générateur d'une partie à N tour(s)
Generator_n_game = function (N = 1000, Pb, Pa = c(1/4, 1/4, 1/2)){
  gains = c();
  # On itère pour générer autant de tours qu'il faut.
  for(i in 1:N){
    #On stock les gains de chaque tour
    gains = c(gains, Generator_one_game(Pb, Pa));
  }
  # On retourne le gain moyen
  mean(gains);
}

# On simule 100 parties
N = 100
esp = c();

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

mean(esp);
## [1] -0.00205
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, Generator_n_game(Pb = c(1/3, 1/3, 1/3)));
}

mean(esp);
## [1] -0.005

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, 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, Generator_n_game(N = 1000, Pb = c(1, 0, 0)));
}
mean(esp);
## [1] 0.24818

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 :

X = 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, Generator_n_game(Pb = c(1/4, 1/4, 1/2), Pa = c(1/3, 1/3, 1/3)));
}

mean(esp);
## [1] -0.00019
plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(-0.5, 0.5), esp);

N = 100
esp = c();

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

mean(esp)
## [1] -0.00223

On a, comme précédemment, une espérance de 0 pour un joueur A biaisé ou non.

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 ?

plot(xlab = 'Combinaisons', ylab = 'Esperance', Simulation(N = 10000, Pa = c(1/3, 1/3, 1/3)));

En utilisant la même méthode que précédement on voit, grâce au graphe, qu’aucune combinaison n’est particuliairement intéressante. Les points sont dispaché aléatoirment sur le graphe. Donc, aucune stratégie optimale n’est envisageable pour le joueur B.

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}{3}) + (y \times \frac{1}{3}) + ((1-x-y) \times \frac{1}{3}) \\ = 1 \\ \\ P(X = 0) = (P(BR) \cap P(AR)) \cup ((P(BP) \cap P(AP)) \cup (P(BS) \cap P(AS)) \\ = (x \times \frac{1}{3}) + (y \times \frac{1}{3}) + ((1-x-y) \times \frac{1}{3}) \\ = 1 \\ \\ P(X = -1) = (P(BR) \cap P(AP)) \cup ((P(BP) \cap P(AS)) \cup (P(BS) \cap P(AP)) \\ = (x \times \frac{1}{3}) + (y \times \frac{1}{3}) + ((1-x-y) \times \frac{1}{3}) \\ = 1 \\ \\ \end{equation}\]

On a donc la loi de probabilité suivante :

X = xi X = 1 X = 0 X = -1
\(P(X = x_i)\) \(1\) \(1\) \(1\)

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

\[\begin{equation} E(X) = \sum_{i=1}^{3} P(X = x_i) \times x_i\\ = 0 \\ \\ \end{equation}\]

On voit très clairement que peut importe ce que joue B il aura toujours une espérance de 0.

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 moyenne de gain proche 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){
  # Premier tour on fait un papier
  if(length(past) < 1){
    'P';
  }
  else {
    # On initialise les compteurs
    cmp = c(0, 0, 0);
    # On parcourt la sauvegarde past et pour chaque valeur,
    # on incrémente les compteurs correspondants
    for(i in 1:length(past)){
      if (past[i] == 'R'){
        cmp[1] = cmp[1] + 1;
      }
      if (past[i] == 'P'){
        cmp[2] = cmp[2] + 1;
      }
      if (past[i] == 'S'){
        cmp[3] = cmp[3] + 1;
      }
    }
    
    # On cherche le plus grand compteur
    if(cmp[1] > cmp[2] && cmp[1] > cmp[3]){
      # Si c'est le compteur de Pierre => On joue Papier
      'P';
    }
    else {
      if(cmp[2] > cmp[3]){
      # Si c'est le compteur de Papier => On joue Ciseau
        'S';
      }
      else {
      # Si c'est le compteur de Ciseau => On joue Pierre
        'R';
      }
    }
  }
}

Si la sauvegarde est vide, alors on joue papier (pierre étant le plus joué des symboles, pour les humains, pour ouvrir un match). Si on a une sauvegarde alors on va compter le nombre occurences 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.

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

One_game = function(Pa, past = NULL){
  # On tire aléatoirement le geste du joueurs A selon Pa
  a = sample(c('R', 'P', 'S'), 1, T, Pa) ;
  # On utilise l'algorithme pour le joueur B
  b = Algorithm(past) ;
  # Si B gagne 
  if((b == 'R' && a == 'S') || (b == 'P' && a == 'R') || (b == 'S' && a == 'P')){ 
    gain = 1;
  }
  else {
    # Si B pert
    if((b == 'R' && a == 'P') || (b == 'P' && a == 'S') || (b == 'S' && a == 'R')){
      gain = -1;
    }
    else { # Sinon il y a égalité
      gain = 0 ;
    }
  }
  list(gain, a);
}

N_games = function(N = 1000, Pa = c(1/4, 1/4, 1/2)){
  past = c();
  gain = c();
  # On itère pour générer autant de tours qu'il faut.
  for(i in 1:N){
    # On stock les gains et le coup courant de chaque tour
    res = One_game(Pa, past);
    gain = c(gain, res[[1]]);
    past = c(past, res[[2]]);
  }
  # On retourne le gain moyen
  mean(gain);
}

N = 100
esp = c();
# On simule 100 parties 
for(i in 1:N){
  esp = c(esp, N_games());
}
mean(esp);
## [1] 0.25041
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.

  1. 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 1 000 tours, il prend énormément de temps à s’éxécuter. Pour essayer de résoudre ce probème on peut limiter la parcours de la sauvegarde, pour la visiter complètement a chaque fois. On doit malgré tout faire attention à ne pas en parcourir trop peu.

  1. Vous évaluerez la performance de votre nouvel algorithme contre un joueur biaisé qui jouerait avec P(A) = (1/4, 1/4, 1/2).
Algorithm = function(past = NULL){
  # Premier tour on fait un papier
  if(length(past) < 1){
    'P';
  }
  else {
    # On initialise les compteurs
    cmp = c(0, 0, 0);
    start = 1; 
    end = length(past)
    # Si on a plus de 50 valeurs
    if(end > 50){
      # On commence l'iteration a end - 50 
      start = length(past) - 50;
    }
    # On parcourt les 50 derniere valeurs de la sauvegarde past et pour chaque valeur,
    # on incrémente les compteurs correspondants
    for(i in start:end){
      if (past[i] == 'R'){
        cmp[1] = cmp[1] + 1;
      }
      if (past[i] == 'P'){
        cmp[2] = cmp[2] + 1;
      }
      if (past[i] == 'S'){
        cmp[3] = cmp[3] + 1;
      }
    }
    
    # On cherche le plus grand compteur
    if(cmp[1] > cmp[2] && cmp[1] > cmp[3]){
      # Si c'est le compteur de Pierre => On joue Papier
      'P';
    }
    else {
      if(cmp[2] > cmp[3]){
      # Si c'est le compteur de Papier => On joue Ciseau
        'S';
      }
      else {
      # Si c'est le compteur de Ciseau => On joue Pierre
        'R';
      }
    }
  }
}

One_game = function(Pa, past = NULL){
  # On tire aléatoirement le geste du joueurs A selon Pa
  a = sample(c('R', 'P', 'S'), 1, T, Pa) ;
  # On utilise l'algorithme pour le joueur B
  b = Algorithm(past) ;
  # Si B gagne 
  if((b == 'R' && a == 'S') || (b == 'P' && a == 'R') || (b == 'S' && a == 'P')){ 
    gain = 1;
  }
  else {
    # Si B pert
    if((b == 'R' && a == 'P') || (b == 'P' && a == 'S') || (b == 'S' && a == 'R')){
      gain = -1;
    }
    else { # Sinon il y a égalité
      gain = 0 ;
    }
  }
  list(gain, a);
}

N_games = function(N = 1000, Pa = c(1/4, 1/4, 1/2)){
  past = c();
  gain = c();
  # On itère pour générer autant de tours qu'il faut.
  for(i in 1:N){
    # On stock les gains et le coup courant de chaque tour
    res = One_game(Pa, past);
    gain = c(gain, res[[1]]);
    past = c(past, res[[2]]);
  }
  # On retourne le gain moyen
  mean(gain);
}

N = 100
esp = c();
# On simule 100 parties 
for(i in 1:N){
  esp = c(esp, N_games());
}
mean(esp);
## [1] 0.24148
plot(xlab = 'Parties', ylab = 'Esperance', ylim = c(0, 0.5), esp);