DM1 PS - Quentin FOMBARON & Guillaume BESNARD - RICM4
Q1
Génération d’une manche (renvoi Pierre, Feuille ou Ciseau avec les probabilités respectives PP, PF et PC)
gen_round = function (PP, PF, PC) {
p = runif(1);
tab = c();
if (p < PP) {
1 ; #Pierre
}
else if (p < PP+PF) {
2; #Feuille
}
else {
3; #Ciseaux
}
}Détermine le gagnant d’une partie (renvoi 1 si J1 gagne, 2 si J2 gagne, 0 en cas de match nul) result -> Matrice de résultat pré-remplie = 0 -> Match nul = 1 -> J1 gagne = 2 -> J2 gagne
winner_is = function (tab_j1, tab_j2) {
win_j1 = 0;
win_j2 = 0;
result = matrix(c(0,2,1,1,0,2,2,1,0), nrow = 3, ncol = 3, byrow = FALSE) ;
for (i in 1:length(tab_j1)) {
if (result[ tab_j2[i] , tab_j1[i] ] == 1) {
win_j1 = win_j1 + 1;
win_j2 = win_j2 - 1;
}
else if (result[ tab_j2[i] , tab_j1[i] ] == 2) {
win_j2 = win_j2 + 1;
win_j1 = win_j1 - 1;
}
}
if (win_j1 > win_j2) { 1 }
else if (win_j1 < win_j2) { 2 }
else { 0 }
}Génére les résultats de N_game partie(s) (renvoi le tableau des résultats de chaque partie)
game = function (P_j1, F_j1, C_j1, P_j2, F_j2, C_j2, N_game) {
tab_r = c();
for (i in 1:N_game) {
tab_r[i] = winner_is(gen_round(P_j1, F_j1, C_j1), gen_round(P_j2, F_j2, C_j2));
}
tab_r;
}Calcule l’espérance de gain de J1 et J2 (renvoi un tableau ou tab_r[1] est l’esperance de gain de J1, et tab_r[2] celle de J2)
esperance = function (tab_g) {
w1 = as.integer(0);
w2 = as.integer(0);
for (i in 1:length(tab_g)) {
if (tab_g[i] == 1) {
w1 = w1 + 1;
}
else if (tab_g[i] == 2) {
w2 = w2 + 1;
}
}
tab_r = c(w1/length(tab_g), w2/length(tab_g));
tab_r
}Question 1
La probabilité n’est pas de (0.5 / 0.5) car il y a une probabilité de match nul lors d’une partie.
Un match null arrive si JA et JB joue Pierre/Pierre, Feuille/Feuille ou Ciseau/Ciseau. Ces probabilités sont respectivement de 1/16, 1/16 et 4/16. Leur somme est donc de 6/16 soit une probabilité de 0.375 d’obtenir un match nul. Il y a donc : (1 - 0.375) = 0.625 => 62.5% de match ayant un gagnant.
Les joueurs ayant la même probabilité pour chaque coup ont autant de chance l’un et l’autre de gagner un match non nul, soit : (0.625 / 2) = 0.3125
On a donc par le calcul l’espérance de gain du joueur B = (0.3125 x 1) + (0.3125 x (-1)) + (0.375 x 0) = 0
On a un système de partie divisé en sous-round.
tab_game = game(1/4, 1/4, 1/2, 1/4, 1/4, 1/2, 1000000);
tab_e = esperance(tab_game);
cat('La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de ', tab_e[1], '.');## La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de 0.312086 .cat('La probabilité de gagner pour le Joueur B avec P(B) = (1/4, 1/4, 1/2) est de ', tab_e[2], '.');## La probabilité de gagner pour le Joueur B avec P(B) = (1/4, 1/4, 1/2) est de 0.313308 .cat('La probabilité d\'un ex aequo est de ', 1-(tab_e[2]+tab_e[1]), '.');## La probabilité d'un ex aequo est de 0.374606 .cat('Donc l\'espérance du Joueur B est de ', tab_e[2]-tab_e[1], '.')## Donc l'espérance du Joueur B est de 0.001222 .Question 2
B gagne pour les coups suivant : PF, FC et CP (avec PF <=> A joue pierre et B joue Feuille). Ainsi, on a P(B gagnant) = P(PA)P(FB) + P(FA)P(CB) + P(CA)P(PB) soit, 1/4 1/3 + 1/4 * 1/3 + 1/2 * 1/3 = 1/3
De la même manière, ex aequo arrive avec les coups suivant : PP, FF, CC, soit P(ex aequo) = 1/4 * 1/3 + 1/4 * 1/3 + 1/2 * 1/3 = 1/3.
D’où P(A gagnant) = 1 - ( P(B gagnant) - P(ex aequo)) = 1/3. On a donc par le calcul l’espérance de gain du joueur B = (1/3 x 1) + (1/3 x (-1)) + (1/3 x 0) = 0
tab_game = game(1/4, 1/4, 1/2, 1/3, 1/3, 1/3, 1000000);
tab_e = esperance(tab_game);
cat('La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de ', tab_e[1], '.');## La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de 0.332674 .cat('La probabilité de gagner pour le Joueur B avec P(B) = (1/3, 1/3, 1/3) est de ', tab_e[2], '.');## La probabilité de gagner pour le Joueur B avec P(B) = (1/3, 1/3, 1/3) est de 0.333601 .cat('La probabilité d\'un ex aequo est de ', 1-(tab_e[2]+tab_e[1]), '.');## La probabilité d'un ex aequo est de 0.333725 .cat('Donc l\'espérance du Joueur B est de ', tab_e[2]-tab_e[1], '.')## Donc l'espérance du Joueur B est de 0.000927 .Question 3
Matrice de l’espérance de gain du Joueur B en fonction de x et y, avec P(A)=(1/4, 1/4, 1/2) et P(B)=(x, y, 1-(x+y))
tab = c();
for (a in 1:(11*11)) {
tab[a] = NA;
}
result = matrix(tab, nrow = 11, ncol = 11);
x = 0;
i = 1;
while(x <= 1) {
y = 0;
j = 1;
while(y <= (1-x) ) {
tab_game = game(1/4, 1/4, 1/2, x, y, 1-x-y, 10000);
tab_e = esperance(tab_game);
result[i, j] = tab_e[2]-tab_e[1];
y = y + 0.1;
j = j + 1;
}
x = x + 0.1;
i = i + 1;
}
rownames(result) <- c(" 0.0 |", " 0.1 |", " 0.2 |", " 0.3 |", " 0.4 |", "x:0.5 |", " 0.6 |", " 0.7 |", " 0.8 |", " 0.9 |", " 1.0 |");
colnames(result) <- c("y : 0.0", "0.1", "0.2", "0.3", "0.4", "0.5", "0.6", "0.7", "0.8", "0.9", "1.0");
cat('Matrice de l\'espérance de gain du Joueur B en fonction de x et y, avec P(A)=(1/4, 1/4, 1/2) et P(B)=(x, y, 1-(x+y)) :\n');## Matrice de l'espérance de gain du Joueur B en fonction de x et y, avec P(A)=(1/4, 1/4, 1/2) et P(B)=(x, y, 1-(x+y)) :result## y : 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
## 0.0 | -0.0077 -0.0344 -0.0475 -0.0846 -0.0928 -0.1033 -0.1463 -0.1801
## 0.1 | 0.0206 -0.0114 -0.0270 -0.0464 -0.0764 -0.1107 -0.1159 -0.1555
## 0.2 | 0.0465 0.0281 0.0087 -0.0383 -0.0416 -0.0834 -0.1018 -0.1234
## 0.3 | 0.0762 0.0427 0.0170 0.0056 -0.0071 -0.0594 -0.0772 -0.1060
## 0.4 | 0.0955 0.0787 0.0431 0.0284 0.0095 -0.0379 -0.0393 NA
## x:0.5 | 0.1256 0.1056 0.0813 0.0534 0.0384 -0.0093 NA NA
## 0.6 | 0.1496 0.1331 0.0976 0.0790 0.0518 NA NA NA
## 0.7 | 0.1806 0.1598 0.1160 0.1152 NA NA NA NA
## 0.8 | 0.1873 0.1666 0.1366 NA NA NA NA NA
## 0.9 | 0.2354 0.1948 NA NA NA NA NA NA
## 1.0 | 0.2411 NA NA NA NA NA NA NA
## 0.8 0.9 1.0
## 0.0 | -0.1981 -0.2222 -0.2627
## 0.1 | -0.1789 -0.1972 NA
## 0.2 | -0.1419 NA NA
## 0.3 | NA NA NA
## 0.4 | NA NA NA
## x:0.5 | NA NA NA
## 0.6 | NA NA NA
## 0.7 | NA NA NA
## 0.8 | NA NA NA
## 0.9 | NA NA NA
## 1.0 | NA NA NAQuestion 4
L’on sait que A jout majoritairement des ciseaux (P = 1/2). Jouant sans mémoire, le plus efficace pour le contrer est donc de jouer constamment Pierre. On voit bien dans notre cas avec x=1 que l’espérance est maximale pour B (avec esperance = 0.2591). Cette logique sera utilisé dans notre algorithme d’apprentissage de la partie 2.
Question 5
P(PB) = x (Probabilité de faire une pierre pour le joueur B) P(FB) = y P(CB) = 1−x−y
On généralise le calcul d’espérance. B gagne pour les coups suivant : PF, FC et CP (avec PF <=> A joue pierre et B joue Feuille). Ainsi, on a P(B gagnant) = P(PA)P(FB) + P(FA)P(CB) + P(CA)P(PB) soit, 1/4 y + 1/4 * (1-x-y) + 1/2 * x
De la même manière, P(A gagnant) = 1/4 * x + 1/2 * y + 1/4 * (1 - x - y).
On à alors Espérance(B) = gain_gagnant * P(B gagnant) + gain_perdant * P(A gagnant) = 1 * P(B gagnant) + -1 P(B gagnant) = y/4 + (1 - x - y)/4 + x/2 - ( x/4 + y/2 + (1 - x - y)/4 ) = x/4 - y/4
On vérifie rapidement nos précédents résultats avec B (1/4, 1/4, 1/2) et B (1/3, 1/3, 1/3). Comme on a x = y, on a donc Espérance(B) = x/4 - y/4 = 0.
On observe aussi que cette formule est cohérente avec notre matrice d’espérence. Par exemple pour x = 0.2 et y = 0.8 on obtiens 0.2/4 - 0.8/4 = -0.15 pour -0.1569 trouvé par notre réalisation (peut être légèrement différent entre simulation).
Question 1’
tab_game = game(1/3, 1/3, 1/3, 1/4, 1/4, 1/2, 1000000);
tab_e = esperance(tab_game);
cat('La probabilité de gagner pour le Joueur A avec P(A) = (1/3, 1/3, 1/3) est de ', tab_e[1],'.');## La probabilité de gagner pour le Joueur A avec P(A) = (1/3, 1/3, 1/3) est de 0.332783 .cat('\nLa probabilité de gagner pour le Joueur B avec P(B) = (1/4, 1/4, 1/2) est de ', tab_e[2],'.');##
## La probabilité de gagner pour le Joueur B avec P(B) = (1/4, 1/4, 1/2) est de 0.333145 .cat('\nLa probabilité d\'un ex aequo est de ', 1-(tab_e[2]+tab_e[1]), '.');##
## La probabilité d'un ex aequo est de 0.334072 .cat('\nDonc l\'espérance du Joueur B est de ', tab_e[2]-tab_e[1], '.')##
## Donc l'espérance du Joueur B est de 0.000362 .Question 2’
tab_game = game(1/3, 1/3, 1/3, 1/3, 1/3, 1/3, 1000000);
tab_e = esperance(tab_game);
cat('La probabilité de gagner pour le Joueur A avec P(A) = (1/3, 1/3, 1/3) est de ', tab_e[1],'.');## La probabilité de gagner pour le Joueur A avec P(A) = (1/3, 1/3, 1/3) est de 0.333807 .cat('\nLa probabilité de gagner pour le Joueur B avec P(B) = (1/3, 1/3, 1/3) est de ', tab_e[2],'.');##
## La probabilité de gagner pour le Joueur B avec P(B) = (1/3, 1/3, 1/3) est de 0.333057 .cat('\nLa probabilité d\'un ex aequo est de ', 1-(tab_e[2]+tab_e[1]),'.');##
## La probabilité d'un ex aequo est de 0.333136 .cat('\nDonc l\'espérance du Joueur B est de ', tab_e[2]-tab_e[1],'.')##
## Donc l'espérance du Joueur B est de -0.00075 .Question 3’
Matrice de l’espérance de gain du Joueur B en fonction de x et y, avec P(A)=(1/3, 1/3, 1/3) et P(B)=(x, y, 1-(x+y))
tab = c();
for (a in 1:(11*11)) {
tab[a] = NA;
}
result = matrix(tab, nrow = 11, ncol = 11);
x = 0;
i = 1;
while(x <= 1) {
y = 0;
j = 1;
while(y <= (1-x) ) {
tab_game = game(1/3, 1/3, 1/3, x, y, 1-x-y, 10000);
tab_e = esperance(tab_game);
result[i, j] = tab_e[2]-tab_e[1];
y = y + 0.1;
j = j + 1;
}
x = x + 0.1;
i = i + 1;
}
rownames(result) <- c(" 0.0 |", " 0.1 |", " 0.2 |", " 0.3 |", " 0.4 |", "x:0.5 |", " 0.6 |", " 0.7 |", " 0.8 |", " 0.9 |", " 1.0 |");
colnames(result) <- c("y : 0.0", "0.1", "0.2", "0.3", "0.4", "0.5", "0.6", "0.7", "0.8", "0.9", "1.0");
cat('Matrice de l\'espérance de gain du Joueur B en fonction de x et y, avec P(A)=(1/3, 1/3, 1/3) et P(B)=(x, y, 1-(x+y)) :\n');## Matrice de l'espérance de gain du Joueur B en fonction de x et y, avec P(A)=(1/3, 1/3, 1/3) et P(B)=(x, y, 1-(x+y)) :result## y : 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
## 0.0 | 0.0024 0.0020 0.0042 -0.0096 0.0115 -0.0048 -0.0015 -0.0091
## 0.1 | 0.0012 -0.0001 0.0198 -0.0037 0.0066 -0.0007 -0.0124 0.0118
## 0.2 | 0.0114 -0.0014 -0.0116 -0.0038 -0.0042 0.0002 -0.0090 -0.0075
## 0.3 | 0.0110 0.0052 0.0057 -0.0182 -0.0049 0.0018 0.0111 0.0042
## 0.4 | 0.0044 0.0008 0.0049 0.0008 -0.0004 -0.0055 0.0154 NA
## x:0.5 | -0.0108 0.0006 -0.0081 -0.0054 -0.0073 -0.0018 NA NA
## 0.6 | -0.0049 0.0018 0.0082 0.0074 0.0033 NA NA NA
## 0.7 | -0.0047 0.0080 -0.0072 0.0197 NA NA NA NA
## 0.8 | -0.0054 0.0093 0.0076 NA NA NA NA NA
## 0.9 | 0.0116 -0.0164 NA NA NA NA NA NA
## 1.0 | 0.0077 NA NA NA NA NA NA NA
## 0.8 0.9 1.0
## 0.0 | 0.0001 -0.0053 0.0082
## 0.1 | -0.0008 0.0002 NA
## 0.2 | -0.0146 NA NA
## 0.3 | NA NA NA
## 0.4 | NA NA NA
## x:0.5 | NA NA NA
## 0.6 | NA NA NA
## 0.7 | NA NA NA
## 0.8 | NA NA NA
## 0.9 | NA NA NA
## 1.0 | NA NA NAQuestion 4’
Il n’y a aucune stratégie gagnante dans ce cas. Un joueur biaisé ou non biaisé ont autant de chance de gagner.
Mais dans les deux cas ils ne gagneront logiquement que très peu sur un grand nombre de parties.
Question 5’
P(PB) = x (Probabilité de faire une pierre pour le joueur B) P(FB) = y P(CB) = 1−x−y
On généralise le calcul d’espérance. B gagne pour les coups suivant : PF, FC et CP (avec PF <=> A joue pierre et B joue Feuille). Ainsi, on a P(B gagnant) = P(PA)P(FB) + P(FA)P(CB) + P(CA)P(PB) soit, 1/3 y + 1/3 * (1-x-y) + 1/3 * x
De la même manière, P(A gagnant) = 1/3 * x + 1/3 * y + 1/3 * (1 - x - y).
On à alors Espérance(B) = gain_gagnant * P(B gagnant) + gain_perdant * P(A gagnant) = 1 * P(B gagnant) + -1 P(B gagnant) = y/3 + (1 - x - y)/3 + x/3 - x/3 - y/3 - (1 - x - y)/3 = 0
L’espérance est bien de 0 pour tout x et tout y, confirmant que la stratégie du joueur B, biaisé ou non n’importera pas.
Q2
Question 1
Comme annoncé précedemment, la meilleure stratégie pour jouer contre un ordinateur sans mémoire est de jouer constamment le coup gagnant contre son coup majoritairement joué. Par exemple, s’il joue une fois sur deux un ciseaux, on jouera constamment une pierre.
Ainsi notre algorithme démarre empiriquement avec une proba de 1/3, 1/3, 1/3 (respectivement pour pierre caillou ciseau) et enchaine les parties.
A l’inverse de précedemment, les coups ne sont pas précalculés. En effet, à chaque round, on mémorise le coup joué par l’ordinateur pour effectuer une analyse statistique de son jeu: dès qu’une probabibilité d’un coup devient plus grande que celles des autres coups, on change la proba à 1 pour le coup gagnat correspondant de B.
Ainsi, on observe parfois une petite oscillation lors des premières parties, mais très rapidement B se met à jouer uniquement le même coup, une fois que la “statistique” du jeu de A s’est “stabilisée”.
Question 2
smart_game = function (P_j1, F_j1, C_j1, N_game) {
tab_r = c();
tab_PJ2 = c(1/3);
tab_FJ2 = c(1/3);
tab_CJ2 = c(1/3);
tab_mem = c();
tab_memJ2 = c(); #Pour un beau graphe
for (i in 1:N_game) {
#Etape 1 : on joue
J1 = gen_round(P_j1, F_j1, C_j1); #Adversaire
J2 = gen_round(tab_PJ2[i], tab_FJ2[i], tab_CJ2[i]);
tab_r[i] = winner_is(J1, J2);
#Etape 2 : on mémorise
tab_mem[i] = J1;
tab_memJ2[i] = J2;
nbr_P = length(tab_mem[tab_mem==1]);
nbr_F = length(tab_mem[tab_mem==2]);
nbr_C = length(tab_mem[tab_mem==3]);
#Etape 3 : on s'améliore
if (nbr_P > nbr_F && nbr_P > nbr_C) {
tab_PJ2[i+1] = 0; tab_FJ2[i+1] = 1; tab_CJ2[i+1] = 0;
}
else if (nbr_F > nbr_P && nbr_F > nbr_C) {
tab_PJ2[i+1] = 0; tab_FJ2[i+1] = 0; tab_CJ2[i+1] = 1;
}
else if (nbr_C > nbr_P && nbr_C > nbr_F) {
tab_PJ2[i+1] = 1; tab_FJ2[i+1] = 0; tab_CJ2[i+1] = 0;
}
else { #En cas d'égalité, on ne change pas les probas
tab_PJ2[i+1] = tab_PJ2[i]; tab_FJ2[i+1] = tab_FJ2[i]; tab_CJ2[i+1] = tab_CJ2[i];
}
}
plot(tab_memJ2, xlim = c(0, 50));
tab_r;
}Question 3
On se rend rapidement compte que notre précedent algorithme ne fonctionnerai pas contre un humain doué de sens. En effet, au bout de 3 ou 4 coups identiques d’affilés, celui-ci se mettrait à changer sa stratégie et contrer ce coup toujours identique.
Question 4
L’espérance de B est moins bonne que celle de notre premier algorithme, mais si l’on pouvait tester contre un réel humain, cet algorithme serait sans doute meilleur. On se rend en effet bien compte que le schémas des choix de l’ordinateur est plus difficilement discernable par un humain tout en restant axé vers une probabilité de coups plus efficaces que l’aléatoire.
graph = function(tab_PJ2, tab_FJ2, tab_CJ2, N_game) {
library(ggplot2);
df = data.frame(N = c(1:(N_game+1)), Pt = tab_PJ2, Ft = tab_FJ2, Ct = tab_CJ2);
ggplot(df, aes(x = N, y = Probabilité, colour = Type)) +
geom_line(aes(y = Pt, colour = "Pierre")) +
geom_line(aes(y = Ft, colour = "Feuille")) +
geom_line(aes(y = Ct, colour = "Ciseau")) ;
}smart_game_human = function (P_j1, F_j1, C_j1, N_game) {
tab_r = c();
tab_PJ2 = c(1/3);
tab_FJ2 = c(1/3);
tab_CJ2 = c(1/3);
tab_mem = c();
tab_memJ2 = c(); #Pour un beau graphe
for (i in 1:N_game) {
#Etape 1 : on joue
J1 = gen_round(P_j1, F_j1, C_j1); #Adversaire
J2 = gen_round(tab_PJ2[i], tab_FJ2[i], tab_CJ2[i]);
tab_r[i] = winner_is(J1, J2);
#Etape 2 : on mémorise
tab_mem[i] = J1;
tab_memJ2[i] = J2;
nbr_P = length(tab_mem[tab_mem==1]);
nbr_F = length(tab_mem[tab_mem==2]);
nbr_C = length(tab_mem[tab_mem==3]);
#Etape 3 : on s'améliore
tab_PJ2[i+1] = nbr_C / length(tab_mem);
tab_FJ2[i+1] = nbr_P / length(tab_mem);
tab_CJ2[i+1] = nbr_F / length(tab_mem);
}
print(graph(tab_PJ2, tab_FJ2, tab_CJ2, N_game));
tab_r;
}On obtient un résultat proche de l’esperance max trouvée précédemment
tab_game = smart_game(1/4, 1/4, 1/2, 10000);
tab_e = esperance(tab_game);
cat('La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de ',tab_e[1], '.');## La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de 0.2513 .cat('La probabilité de gagner pour le Joueur B avec P(B) adaptable est de ',tab_e[2], '.');## La probabilité de gagner pour le Joueur B avec P(B) adaptable est de 0.4967 .cat('La probabilité d\'un ex aequo est de ',1-(tab_e[2]+tab_e[1]), '.');## La probabilité d'un ex aequo est de 0.252 .cat('Donc l\'espérance du Joueur B est de ', tab_e[2]-tab_e[1], '.')## Donc l'espérance du Joueur B est de 0.2454 .tab_game_human = smart_game_human(1/4, 1/4, 1/2, 10000)
tab_e = esperance(tab_game_human);
cat('La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de ',tab_e[1], '.');## La probabilité de gagner pour le Joueur A avec P(A) = (1/4, 1/4, 1/2) est de 0.3163 .cat('La probabilité de gagner pour le Joueur B avec P(B) adaptable est de ',tab_e[2], '.');## La probabilité de gagner pour le Joueur B avec P(B) adaptable est de 0.3714 .cat('La probabilité d\'un ex aequo est de ',1-(tab_e[2]+tab_e[1]), '.');## La probabilité d'un ex aequo est de 0.3123 .cat('Donc l\'espérance du Joueur B est de ', tab_e[2]-tab_e[1], '.')## Donc l'espérance du Joueur B est de 0.0551 .