\(\\\)
\(\\\)
\(\\\)
\(\\\)
\(\\\)
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.
\(\\\)
\(\\\)
\(\\\)
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.
\(\\\)
\(\\\)
\(\\\)
\(\\\)
\(\\\)
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.
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.
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);