DM1 PS
Servan CHARLOT Zoran CHANET
2-23 novembre 2017
Question 1
On commence par créer une fonction qui génère un lancer avec la répartition fréquentielle donnée en argument. La somme des trois arguments doit être égale à 1.
unLancer=function(Pp, Pf, Pc){
tirage=runif(1)
if(tirage <= Pp){
"P"
} else if(tirage > Pp && tirage <= Pf+Pp){
"F"
} else if(tirage > Pf+Pp){
"C"
}
}On écrit ensuite une fonction qui simule une manche entre deux joueurs. Elle prend en paramètres J1 et J2 qui sont des tableaux de 4 cases, respectivement leur score et la probabilité de sortir un des coups pierre, feuille ou ciseaux, dans cet ordre. Elle renvoie un tableau de deux cases contenant les points à ajouter au score du J1 et du J2 respectivement.
uneManche=function(J1,J2){
return = c()
resultJ1=unLancer(J1[2],J1[3],J1[4])
resultJ2=unLancer(J2[2],J2[3],J2[4])
if(resultJ1 == "P"){
if(resultJ2 == "P"){
return = c(0,0)
} else if(resultJ2 == "F"){
return = c(-1,1)
} else if(resultJ2 == "C"){
return = c(1,-1)
}
} else if(resultJ1 == "F"){
if(resultJ2 == "P"){
return = c(1,-1)
} else if(resultJ2 == "F"){
return = c(0,0)
} else if(resultJ2 == "C"){
return = c(-1,1)
}
} else if(resultJ1 == "C"){
if(resultJ2 == "P"){
return = c(-1,1)
} else if(resultJ2 == "F"){
return = c(1,-1)
} else if(resultJ2 == "C"){
return = c(0,0)
}
}
return
}On peut maintenant créer une fonction qui repète N manches en mettant à jour les scores de nos deux joueurs. Elle prend en paramètre deux tableaux de trois cases contenant les probabilités de faire pierre, feuille ou ciseaux dans cet ordre, pour chacun des joueurs. Elle renvoie un tableau de 5 cases qui correspondent au score du J1, au score du J2, à la probabilité estimée de victoire du J1, à la probabilité estimée de victoire du J2, et à la probabilité estimée de match nul.
jeu=function(ProbaJ1, ProbaJ2,N){
J1 = c(0,ProbaJ1)
J2 = c(0,ProbaJ2)
nbWinJ1 = 0
nbWinJ2 = 0
for (i in 1:N){
resManche=uneManche(J1,J2)
J1[1] = J1[1] + resManche[1]
if(resManche[1] == 1){
nbWinJ1 = nbWinJ1 + 1
}
J2[1] = J2[1] + resManche[2]
if(resManche[2] == 1){
nbWinJ2 = nbWinJ2 + 1
}
}
probaWinJ1 = nbWinJ1/N
probaWinJ2 = nbWinJ2/N
probaMatchNul = 1-probaWinJ1-probaWinJ2
c(J1[1],J2[1],probaWinJ1,probaWinJ2,probaMatchNul)
}On lance maintenant la simulation avec les paramètres de la question 1-1
ProbaJ1 = c(1/4,1/4,1/2)
ProbaJ2 = c(1/4,1/4,1/2)
N = 10000
resultatJeu=jeu(ProbaJ1,ProbaJ2,N)
EsperanceGainJ2 = resultatJeu[4] - resultatJeu[3]
"Esperance de gain du J2 dans le cas ProbaJ1 = 1/4 1/4 1/2"## [1] "Esperance de gain du J2 dans le cas ProbaJ1 = 1/4 1/4 1/2"EsperanceGainJ2## [1] 0.0097EsperanceGainJ2 = c();
for(i in 1:100){
resultatJeu=jeu(ProbaJ1,ProbaJ2,100)
EsperanceGainJ2[i] = resultatJeu[4] - resultatJeu[3]
}
plot(EsperanceGainJ2, main = "Esperances de gain de J2(biaisé) sur plusieurs parties dans le cas 1-1");
abline(h = mean(EsperanceGainJ2),col="red");
On estime donc l’espérance à 0.
On relance la simulation avec les paramètres de la question 1-2.
ProbaJ1 = c(1/4,1/4,1/2)
ProbaJ2 = c(1/3,1/3,1/3)
N = 10000
resultatJeu=jeu(ProbaJ1,ProbaJ2,N)
EsperanceGainJ2 = resultatJeu[4] - resultatJeu[3]
"Esperance de gain du J2 dans le cas ProbaJ1 = 1/3 1/3 1/3"## [1] "Esperance de gain du J2 dans le cas ProbaJ1 = 1/3 1/3 1/3"EsperanceGainJ2## [1] 0.0016EsperanceGainJ2 = c();
for(i in 1:100){
resultatJeu=jeu(ProbaJ1,ProbaJ2,100)
EsperanceGainJ2[i] = resultatJeu[4] - resultatJeu[3]
}
plot(EsperanceGainJ2, main = "Esperances de gain de J2(non biaisé)\nsur plusieurs parties dans le cas 1-2");
abline(h = mean(EsperanceGainJ2),col="red");
On estime l’espérance à 0 ici aussi.
On fait maintenant varier les paramètres initiaux du joueur 2 comme l’indique la question 1-3.
N = 1000
esperances = c()
for(pierre in 0:10/10){
for(feuille in 0:10/10){
ProbaJ2 = c(pierre,feuille,1-pierre-feuille)
resultatJeu=jeu(ProbaJ1,ProbaJ2,N)
esperances = c(esperances,resultatJeu[4] - resultatJeu[3])
}
}
plot(esperances, main = "Esperances de gain de J2(non biaisé)\nlors des variations de x et y")
Dans ce graphe, on affiche l’espérance en fonction des itérations de notre boucle. Il y a 11 itérations de pierre et 11 itération de feuille par itérations de pierre. On remarque donc 11 motifs décroissants se répéter et se ressérer vers la fin, avec une tendance croissante. On peut déduire des motifs que les espérances sont moins bonnes si on joue trop la feuille. On peux aussi déduire que les espérances sont meilleures si on joue plus souvent la pierre, vu que plus on avance dans les itérations de pierre plus elles sont bonnes. Pour maximiser son espérance, il faut donc souvent opter pour la pierre, ce qui parait logique car dans cette configuration, le joueur A fait les ciseaux une fois sur deux.
Pour répondre à la question 1-5, optons pour une approche mathématique du problème. On peut représenter la situation sous la forme d’un arbre de probabilités. Avec cette représentation, on obtient la formule suivante pour la probabilité de victoire du joueur 2.
\(P(Player2Win) = P(P_a \cap F_b) + P(F_a \cap C_b) + P(C_a \cap P_b)\) \(= P(P_a) * P(F_b|P_a) + P(F_a) * P(C_b|F_a) + P(C_a) * P(P_b|C_a)\) \(= P(P_a) * P(F_b) + P(F_a) * P(C_b) + P(C_a) * (P_b)\) car indépendance de Xa et Xb.
Avec le même type de formule, en adaptant les règles, on trouve P(Player2Lose). On se sert de ces deux probabilités pour calculer l’espérance.
\(EsperanceGainJ2 = (gain possible) * P(Player2Win) - (wager) * P(Player2Lose)\) \(= P(Player2Win) - P(Player2Lose)\) \(= \frac{y}{4} + \frac{(1-x-y)}{4} + \frac{x}{2} - (\frac{(1-x-y)}{4} + \frac{x}{4} + \frac{y}{2})\) \(= (x-y)/2\)
On valide bien la conclusion ci-dessus avec ce resultat, pour maximiser l’espérance de gain, il faut maximiser la probabilité de jouer pierre (et minimiser la probabilité de jouer feuille).
On refait maintenant les expériences avec un joueur non-biaisé.
ProbaJ1 = c(1/3,1/3,1/3)
ProbaJ2 = c(1/4,1/4,1/2)
N = 10000
resultatJeu=jeu(ProbaJ1,ProbaJ2,N)
EsperanceGainJ2 = resultatJeu[4] - resultatJeu[3]
"Esperance de gain du J2 dans le cas ProbaJ1 = 1/4 1/4 1/2"## [1] "Esperance de gain du J2 dans le cas ProbaJ1 = 1/4 1/4 1/2"EsperanceGainJ2## [1] 0.0017EsperanceGainJ2 = c();
for(i in 1:100){
resultatJeu=jeu(ProbaJ1,ProbaJ2,100)
EsperanceGainJ2[i] = resultatJeu[4] - resultatJeu[3]
}
plot(EsperanceGainJ2, main = "Esperances de gain de J2(biaisé) sur plusieurs parties\ndans le cas du joueur non biaisé");
abline(h = mean(EsperanceGainJ2),col="red");
ProbaJ2 = c(1/3,1/3,1/3)
resultatJeu=jeu(ProbaJ1,ProbaJ2,N)
EsperanceGainJ2 = resultatJeu[4] - resultatJeu[3]
"Esperance de gain du J2 dans le cas ProbaJ1 = 1/3 1/3 1/3"## [1] "Esperance de gain du J2 dans le cas ProbaJ1 = 1/3 1/3 1/3"EsperanceGainJ2## [1] -0.0129EsperanceGainJ2 = c();
for(i in 1:100){
resultatJeu=jeu(ProbaJ1,ProbaJ2,100)
EsperanceGainJ2[i] = resultatJeu[4] - resultatJeu[3]
}
plot(EsperanceGainJ2, main = "Esperances de gain de J2(non biaisé) sur plusieurs parties\ndans le cas du joueur non biaisé");
abline(h = mean(EsperanceGainJ2),col="red");
N = 1000
esperances = c()
for(pierre in 0:10/10){
for(feuille in 0:10/10){
ProbaJ2 = c(pierre,feuille,1-pierre-feuille)
resultatJeu=jeu(ProbaJ1,ProbaJ2,N)
esperances = c(esperances,resultatJeu[4] - resultatJeu[3])
}
}
plot(esperances,main = "Esperances de gain de J2(non biaisé) en faisant varier x et y")
abline(h = mean(esperances),col="red");
Dans ce cas là, lorsque les deux joueurs jouent au hasard, les espérances sont nulles et on ne remarque pas de motif particulier sur le graphe, donc peu importe la stratégie du joueur B, il a la même chance de gagner.
Question 2
Code source nécessaire pour faire tourner certains bots. Il génère des coups qui correspondent a des numéros plutôt qu’à des lettres.
joueur = function (n = 1, p = 1/3, f = 1/3, c = 1/3){
x = runif(n)
r = c()
for(i in 1:n)
if(x[i]<=p)
r[i] = 0 # pierre
else if(x[i]<=f+p)
r[i] = 1 # feuille
else
r[i] = 2 # ciseaux
return(r)
}Ce bot joue le contre au coup le plus utilisé (donc supposé le plus probable) par l’adversaire.
esperanceLearning = function(n = 100, p = 1/4, f = 1/4, c = 1/2){
events = c(0,0,0)
jA = joueur(n,p,f,c)
r = 0
for(i in 1:n){
if(max(events) == events[3])
jB = 0
else if(max(events) == events[2])
jB = 2
else
jB = 1
events[jA[i]+1] = events[jA[i]+1]+1
if(jB == ((jA[i]+1) %% 3))
r = r+1
else
r = r-1
}
return(r/n)
}
r = c()
for(i in 1:1000)
r[i] = esperanceLearning(i)
plot(r, main = "Esperances de gain du bot selon le nombre de coups par match", xlab="Nombre de coups par match", ylab = "Esperance de gain du bot");
abline(h=0, col="red")
Cet algorithme ne pourrait pas vaincre un humain qui en comprend le fonctionnement (il suffit de jouer feuille deux fois puis pierre trois fois puis ciseaux deux fois (ou bien égaliser le nombre de coups joués pour chaque figure à n’importe quel moment de la partie) puis alterner ciseaux-feuille-pierre). De plus, il n’est pas très efficace contre un joueur biaisé.
On ecrit un autre bot qui va adopter la strategie suivante. Il retient chaque coups de son adversaire pour pouvoir re-calculer a chaque tour à quelle frequence il joue quoi. Sachant cela, il adapte sa frequence à celle de son adversaire de la manière suivante : Il regarde quel est le choix C1 le plus fait par le J1 et note sa frequence F1; Il regarde quel est le choix C2 le moins fait par le J1 à une frequence F2; Il regarde le choix C3 restant à une frequence F3; Et il va dorenavant jouer le choix gagnant face au C1 à une frequence F1, le choix perdant face au C1 à une frequence F2, et il va jouer le choix restant à une frequence F3.
bot1 = function(ProbaJ1,N){
ProbaJ2 = c(1/3,1/3,1/3)
MemJ1 = c()
EstimProbaJ1 = c()
NbWinJ1 = 0
NbWinJ2 = 0
esperancesTabJ2 = c()
gainJ2 = c()
# Une itération par tour de jeu
for(i in 1:N){
resultJ1 = unLancer(ProbaJ1[1],ProbaJ1[2],ProbaJ1[3])
resultJ2 = unLancer(ProbaJ2[1],ProbaJ2[2],ProbaJ2[3])
# On garde en mémoire tous les coups du J1
MemJ1 = c(MemJ1,resultJ1)
# Recalcul de l'estimation de la fréquence de jeu de J1 à chaque tour
EstimProbaJ1 = c(
sum(MemJ1 == "P")/i,
sum(MemJ1 == "F")/i,
sum(MemJ1 == "C")/i
)
# Remplacement de la probabilité du J2
ProbaJ2 = c(EstimProbaJ1[3],EstimProbaJ1[1],EstimProbaJ1[2]);
# Règles du jeu pour attribuer les victoires.
if(resultJ1 == "P"){
if(resultJ2 == "F"){
NbWinJ2 = NbWinJ2 + 1
} else if(resultJ2 == "C"){
NbWinJ1 = NbWinJ1 + 1
}
} else if(resultJ1 == "F"){
if(resultJ2 == "P"){
NbWinJ1 = NbWinJ1 + 1
} else if(resultJ2 == "C"){
NbWinJ2 = NbWinJ2 + 1
}
} else if(resultJ1 == "C"){
if(resultJ2 == "P"){
NbWinJ2 = NbWinJ2 + 1
} else if(resultJ2 == "F"){
NbWinJ1 = NbWinJ1 + 1
}
}
# On stocke toutes les espérances dans un tableau à chaque tour.
esperancesTabJ2 = c(esperancesTabJ2, NbWinJ2/i - NbWinJ1/i)
gainJ2 = c(gainJ2,NbWinJ2-NbWinJ1)
}
# Et on le return.
esperancesTabJ2
#gainJ2
}On remarque sur le graphe ci-dessous que l’espérance de gain du J2 tend vers un nombre supérieur à 0.
ProbaJ1 = c(1/2,1/2,0)
resultBot=bot1(ProbaJ1,1000)
"Dernier calcul d'esperance de gain du joueur 2 :"## [1] "Dernier calcul d'esperance de gain du joueur 2 :"resultBot[length(resultBot)]## [1] 0.241plot(resultBot, main = "Esperances de gain du bot selon\nle nombre de coups joués precedemment",ylab = "Esperances de gain J2")
abline(h=0, col="red")
Il obtient de meilleurs résultats quand le J1 joue très souvent un choix particulier.
ProbaJ1 = c(1/10,1/10,8/10)
resultBot=bot1(ProbaJ1,1000)
"Dernier calcul d'esperance de gain du joueur 2 :"## [1] "Dernier calcul d'esperance de gain du joueur 2 :"resultBot[length(resultBot)]## [1] 0.503plot(resultBot,main = "Esperances de gain du bot selon\nle nombre de coups joués precedemment",ylab = "Esperances de gain J2")
abline(h=0, col="red")
On va essayer une approche différente pour notre second bot. La stratégie ici est de regarder quel coup a fait l’adversaire, et d’augmenter la probabilité de jouer son contre (et diminuer la probabilité de jouer le choix qui se fait contrer) par une constante.
bot2 = function(ProbatJ1,N){
ProbaJ2 = c(1/3,1/3,1/3)
EstimProbaJ1 = c()
NbWinJ1 = 0
NbWinJ2 = 0
esperancesTabJ2 = c()
for(i in 1:N){
resultJ1 = unLancer(ProbaJ1[1],ProbaJ1[2],ProbaJ1[3])
resultJ2 = unLancer(ProbaJ2[1],ProbaJ2[2],ProbaJ2[3])
shiftUp = 0
shiftDown =0
if(resultJ1 == "P"){
if(resultJ2 == "F"){
NbWinJ2 = NbWinJ2 + 1
} else if(resultJ2 == "C"){
NbWinJ1 = NbWinJ1 + 1
}
newProbF = ProbaJ2[2] + 0.1
newProbC = ProbaJ2[3] - 0.1
if(newProbF > 1 | newProbC < 0){
if(newProbF > 1) shiftUp = 1 - ProbaJ2[2]
if(newProbC < 0) shiftDown = ProbaJ2[3]
shift = min(shiftUp,shiftDown)
newProbF = ProbaJ2[2] + shift
newProbC = ProbaJ2[3] - shift
}
ProbaJ2 = c((1-newProbF-newProbC),newProbF,newProbC)
} else if(resultJ1 == "F"){
if(resultJ2 == "P"){
NbWinJ1 = NbWinJ1 + 1
} else if(resultJ2 == "C"){
NbWinJ2 = NbWinJ2 + 1
}
newProbC = ProbaJ2[3] + 0.01
newProbP = ProbaJ2[1] - 0.01
if(newProbC > 1 | newProbP < 0){
if(newProbC > 1) shiftUp = 1 - ProbaJ2[2]
if(newProbP < 0) shiftDown = ProbaJ2[3]
shift = min(shiftUp,shiftDown)
newProbC = ProbaJ2[2] + shift
newProbP = ProbaJ2[3] - shift
}
ProbaJ2 = c(newProbP,(1-newProbP-newProbC),newProbC)
} else if(resultJ1 == "C"){
if(resultJ2 == "P"){
NbWinJ2 = NbWinJ2 + 1
} else if(resultJ2 == "F"){
NbWinJ1 = NbWinJ1 + 1
}
newProbP = ProbaJ2[1] + 0.1
newProbF = ProbaJ2[2] - 0.1
if(newProbP > 1 | newProbF < 0){
if(newProbP > 1) shiftUp = 1 - ProbaJ2[2]
if(newProbF < 0) shiftDown = ProbaJ2[3]
shift = min(shiftUp,shiftDown)
newProbP = ProbaJ2[2] + shift
newProbF = ProbaJ2[3] - shift
}
ProbaJ2 = c(newProbP,newProbF,(1-newProbP-newProbF))
}
esperancesTabJ2 = c(esperancesTabJ2, NbWinJ2/i - NbWinJ1/i)
}
print(NbWinJ2);
esperancesTabJ2
}On remarque que ce bot n’est pas très efficace. Il parvient à maintenir l’espérance de gain à 0, et donc de toujours gagner autant qu’il perd. Il ne decends pas trop en dessous de 0, ne monte pas trop au dessus de 0 mais il n’apprend pas à monter.
ProbaJ1 = c(1/4,1/4,1/2)
resultBot=bot2(ProbaJ1,1000)## [1] 330"Dernier calcul d'esperance de gain du joueur 2 :"## [1] "Dernier calcul d'esperance de gain du joueur 2 :"resultBot[length(resultBot)]## [1] -0.021plot(resultBot,main = "Esperances de gain du bot selon\nle nombre de coups joués precedemment",ylab = "Esperances de gain J2")
abline(h=0, col="red")
Les deux prochains bots seraient très efficaces contre des humains (qui élaborent une stratégie même inconsciemment) mais sont de piètre facture contre un ordinateur jouant aléatoirement.
Ici le robot joue le contre au symbole le plus joué par le joueur après son dernier symbole joué (si je répète souvent la séquence pierre - feuille, le robot jouera ciseaux après que j’aie joué pierre).
maxLigMatn3 = function(i,m){
return(max(m[i,1],max(m[i,2],m[i,3])))
}
esperanceLearning = function(n = 100, p = 1/4, f = 1/4, c = 1/2){
events = matrix(seq(0,0,0),nrow=3,ncol=3)
jA = joueur(n,p,f,c)
r = 0
last = 0
for(i in 1:n){
if(maxLigMatn3(last+1,events) == events[3,1])
jB = 1
else if(maxLigMatn3(last+1,events) == events[3,2])
jB = 2
else
jB = 0
events[last+1,jA[i]+1] = events[last+1,jA[i]+1]+1
last = jA[i]
if(jB == ((jA[i]+1) %% 3))
r = r+1
else
r = r-1
}
return(r/n)
}
r = c()
for(i in 1:1000)
r[i] = esperanceLearning(i)
plot(r, main = "Esperances de gain du bot selon le nombre de coups par match", xlab="Nombre de coups par match", ylab = "Esperance de gain du bot");
abline(h=0, col="red")
Cet algorithme ne pourrait pas vaincre un humain très attentif : il suffit donc au joueur d’alterner souvent les séquences. De plus, il est inefficace contre un joueur aléatoire (biaisé ou non), car il est rare que des séquences se répètent, donc l’apprentissage est inefficace.
Ici le robot joue la contre au symbole le plus joué par le joueur après le dernier symbole joué par le robot (si je joue souvent ciseaux après qu’il ait joué feuille, le robot jouera pierre après avoir joué pierre).
maxLigMatn3 = function(i,m){
return(max(m[i,1],max(m[i,2],m[i,3])))
}
esperanceLearning = function(n = 100, p = 1/4, f = 1/4, c = 1/2){
events = matrix(seq(0,0,0),nrow=3,ncol=3)
jA = joueur(n,p,f,c)
r = 0
last = 0
for(i in 1:n){
if(maxLigMatn3(last+1,events) == events[3,1])
jB = 1
else if(maxLigMatn3(last+1,events) == events[3,2])
jB = 2
else
jB = 0
events[last+1,jA[i]+1] = events[last+1,jA[i]+1]+1
last = jB
if(jB == ((jA[i]+1) %% 3))
r = r+1
else
r = r-1
}
return(r/n)
}
r = c()
for(i in 1:1000)
r[i] = esperanceLearning(i)
plot(r, main = "Esperances de gain du bot selon le nombre de coups par match", xlab="Nombre de coups par match", ylab = "Esperance de gain du bot");
abline(h=0, col="red")
Cet algorithme ne pourrait pas vaincre un humain très attentif : il suffit au joueur d’alterner souvent les séquences De plus, il est inefficace contre un joueur aléatoire, car il est très rare que des séquences se répètent, donc l’apprentissage est inefficace