EZ-ZINE Najwa
DM : Rock Paper Scissors
EXERCICE 1
Le joueur biaisé
Le calcul de l’espérance se fait en utilisant la formule suivante :
\(\sum_{i=1}^\infty x_{i}*p_i\)
Autrement dit,\(\sum_{i=1}^\infty (i)*p(Gain=i)\)
Nous avons donc besoin de calculer la probabilité de toutes les issues du jeu. On va donc calculer la probabilité de gagner 1 euro, de perdre 1 euro ou bien de ne rien gagner ni perdre.
On peut modéliser une partie avec un joueur A \(P_{(A)}=(\frac{1}{4},\frac{1}{4},\frac{1}{2})\) et un joueur B \(P_{(B)}=(\frac{1}{4},\frac{1}{4},\frac{1}{2})\) de la façon suivante :
Donc, P(Gain = 0) = Probabilité d’avoir ex aequo avec Pierre, Feuille et ciseaux. Les événements sont indépendants. 
Donc on peut dire :
\(P(Gain=0)=0.25*0.25+0.25+*0.25+0.5*0.5=0.375\)
De la même façon,
\(P(Gain=-1)=0.25*0.5+0.25*0.25+0.5*0.25=0.3125\)
\(P(Gain=+1)=0.25*0.25+0.25*0.5+0.5*0.25=0.3125\)
On applique maintenant la formule de l’espérance :
\(E(X)=0*P(Gain=0)+1*P(Gain=1)-1*P(Gain=-1)\)
\(E(X)=0*0.375+1*0.3125-1*0.3125\)
\(E(X)=0\) Donc l’espérance est nulle.
- De la même façon avec un joueur A \(P_{(A)}=(\frac{1}{4},\frac{1}{4},\frac{1}{2})\) et un joueur B \(P_{(B)}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})\) :
\(P(Gain=0)=0.25*\frac{1}{3}+0.25*\frac{1}{3}+0.5*\frac{1}{3}\)
\(P(Gain=-1)=0.25*\frac{1}{3}+0.25*\frac{1}{3}+0.5*\frac{1}{3}=\frac{1}{3}\)
\(P(Gain=+1)=0.25*\frac{1}{3}+0.25*\frac{1}{3}+0.5*\frac{1}{3}=\frac{1}{3}\)
On applique maintenant la formule de l’espérance :
\(E(X)=0*P(Gain=0)+1*P(Gain=1)-1*P(Gain=-1)\)
\(E(X)=0*0.375+1*0.3125-1*0.3125\)
\(E(X)=0\)
Donc, l’espérance à nouveau est nulle. 3.4.&5. On peut modéliser \(P_{(B)}=(x,y,1-x-y)\) par l’arbre suivant :
Ainsi, \(P(Gain=0)=0.25*x+0.25y+0.5*(1-x-y)=-0.25*x-0.25y+0.5\)
\(P(Gain=-1)=0.25*(1-x-y)+0.25*x+0.5*y=0.25+0.25y\)
\(P(Gain=+1)=0.25y+0.25*(1-x-y)+0.5*x=0.25+0.25*x\)
On applique maintenant la formule de l’espérance :
\(E(X)=0*P(Gain=0)+1*P(Gain=1)-1*P(Gain=-1)\)
$E(X)=0(-0.25x-0.25y+0.5)+1(0.25+0.25x)-1*(0.25+0.25y)
\(E(X)=0.25x-0.25y\)
Le max de E(X) est atteint pour x=1 et y=0, pour une valeur de 0.25 et une probabilité \(P_{(B)}=(1,0,0)\)
Analyse du résultat :
Si le joueur A joue plus souvent ciseaux, alors jouer feuille me ferait perdre. Donc, il faut réduire l’apparition de feuille. Maintenant, si je joue Ciseaux c’est match nul je n’accroîs pas mon gain et si je joue Pierre je gagne. C’est ce que nous la formule : pour augmenter mon gain, il faut jouer Pierre.
SIMULATION On utilise la fonction sample pour simuler N parties de Pierre-Feuille-Ciseaux. C’est une fonction uniforme et nous allons l’utiliser pour piocher au hasard un coup à jouer. Vérification sample uniforme
#On crée un vecteur de proba (1/3,1/3,1/3)
prob=c('P','F','C');
#On vérifie qu'il s'agit bien des probabilité associé aux événements
Verification_proba= function (N=100){
#Compteur pour pierre feuille et ciseaux
c=0
p=0
f=0
#Sur N tirages on compte le nombre de feuille, pierre et ciseaux apparu
for(i in 1:N){
take1 = sample (prob,1,TRUE)
if (take1=='P') {
p=p+1}
if(take1=='F'){
f=f+1}
if(take1=='C'){
c=c+1
}
}
#Calcul des apparitions
c(p/N,f/N,c/N)
}
#On retrouve bien à peu près (1/3,/1/3,1/3)
Verification_proba(10000)## [1] 0.3402 0.3299 0.3299SIMULATION POUR ESPERANCE A = 0.25/0.25/0.5 & B = 0.25/0.25/0.5
#En effet, Pour créer un vecteur de probabilité 0.25/0.25/0.5 il faut juste que sur 4 possibilités 2 soit Ciseaux, 1 pierre et feuille
probA = c('P','F','C','C');
probB = c('P','F','C','C');
Tirages= function(N=100){
#Data
nb_won=0
total_gain=0
nb_lost=0
tie=0
#Liste de coups joués
playerA=c()
playerB=c()
#Jeu à N parties :
for (i in 1:N){
# take1 = coup joué par le joueur A
take1 = sample (probA,1,TRUE)
# take2 = coup joué par le joueur B
take2 = sample (probB,1,TRUE)
#Ajout du coup joué dans le liste des coups joués.
playerA=c(playerA,take1)
playerB=c(playerB,take2)
#Calcul du gain :
#Si les 2 coups sont différents (il y a un gagnant & un perdant)
if (take1!=take2){
#Si le joueur A a joué Pierre
if (take1=='P'){
#Si le joueur B a joué Ciseaux
if (take2=='C'){
#Le joueur A a gagné. Donc le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost + 1
}
#Sinon le joueur B a gagné
else {
total_gain = total_gain + 1
nb_won = nb_won + 1
}
}
#Sinon, si le joueur A a joué Feuille
else if (take1=='F'){
#Si le joueur B a joué Pierre
if(take2=='P'){
# Alors, le joueur A a gagné et le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost + 1
}
else{
#Sinon le joueur B a gagné
total_gain = total_gain + 1
nb_won = nb_won + 1
}
}
else {
#Sinon, le joueur A a joué Ciseaux
#Si le joueur B a joué Feuille
if (take2=='F'){
#Le joueur A a gagné et le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost +1
}
else {
#Sinon, le joueur B a gagné
total_gain = total_gain + 1
nb_won = nb_won + 1
}
}
}
else {
#Si les 2 coups sont identiques, personne ne gagne
tie=tie+1
}
}
#Gain moyen, nb de parties gagnées, perdues, égalité, et somme pour vérification
#Vérification = somme de perdues, égalité, gagnées vaut nombre de parties jouées.
c(total_gain/N, nb_won,nb_lost,tie, nb_lost+nb_won+tie)
}
Tirages(1000)## [1] -0.003 299.000 302.000 399.000 1000.000Comme prévu, l’espérance avoisine 0.
SIMULATION POUR ESPERANCE A = 0.25/0.25/0.5 & B = 0.3/0.3/0.3
probA = c('P','F','C','C');
probB = c('P','F','C');
Tirages(1000)## [1] 0.004 327.000 323.000 350.000 1000.000Comme prévu à la question 2, l’espérance avoisine 0.
Le joueur non biaisé
- On peut modéliser une partie avec un joueur A \(P_{(A)}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})\) et un joueur B \(P_{(B)}=(\frac{1}{4},\frac{1}{4},\frac{1}{2})\) de la façon suivante :
Les événements sont indépendants. Donc on peut dire :
\(P(Gain=0)=\frac{1}{3}*0.25+\frac{1}{3}*0.25+\frac{1}{3}*0.5=\frac{1}{3}\)
De la même façon,
\(P(Gain=-1)=\frac{1}{3}*0.5+\frac{1}{3}*0.25+\frac{1}{3}*0.25=\frac{1}{3}\)
\(P(Gain=+1)=\frac{1}{3}*0.25+\frac{1}{3}*0.5+\frac{1}{3}*0.25=\frac{1}{3}\)
On applique maintenant la formule de l’espérance :
\(E(X)=0*P(Gain=0)+1*P(Gain=1)-1*P(Gain=-1)\) \(E(X)=0*\frac{1}{3}+1*\frac{1}{3}-1*\frac{1}{3}\) \(E(X)=0\) Donc l’espérance est nulle.
- De la même façon avec un joueur A \(P_{(A)}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})\) et un joueur B \(P_{(B)}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})\) :
\(P(Gain=0)=\frac{1}{3}*(\frac{1}{3}+\frac{1}{3}+\frac{1}{3})=\frac{1}{3}\)
\(P(Gain=-1)=\frac{1}{3}*(\frac{1}{3}+\frac{1}{3}+\frac{1}{3})=\frac{1}{3}\)
\(P(Gain=+1)=\frac{1}{3}*(\frac{1}{3}+\frac{1}{3}+\frac{1}{3})=\frac{1}{3}\)
On applique maintenant la formule de l’espérance :
\(E(X)=0*P(Gain=0)+1*P(Gain=1)-1*P(Gain=-1)\)
\(E(X)=0*\frac{1}{3}+1*\frac{1}{3}-1*\frac{1}{3}\)
\(E(X)=0\)
Donc, l’espérance à nouveau est nulle.
3.4.&5. On peut modéliser \(P_{(B)}=(x,y,1-x-y)\) par l’arbre suivant :
\(P(Gain=0)=\frac{1}{3}*x+\frac{1}{3}y+\frac{1}{3}*(1-x-y)=\frac{1}{3}\)
\(P(Gain=-1)=\frac{1}{3}(1-x-y)+\frac{1}{3}*x+\frac{1}{3}*y=\frac{1}{3}\)
\(P(Gain=+1)=\frac{1}{3}y+\frac{1}{3}*(1-x-y)+\frac{1}{3}*x=\frac{1}{3}\)
On applique maintenant la formule de l’espérance :
\(E(X)=0*P(Gain=0)+1*P(Gain=1)-1*P(Gain=-1)\)
\(E(X)=0*\frac{1}{3}+1*\frac{1}{3}-1*\frac{1}{3}\)
\(E(X)=0\)
Peu importe la façon du joueur B, l’espérance vaut 0. En effet la formule de l’espérance ne dépend ni de x ni de y. Donc, il n’existe pas de stratégie optimale.
Il est possible pour un joueur de gagner ou de perdre. Car il existe un chemin qui permet de perdre et un chemin qui permet de gagner (plus qu’un). Même si les probabilités liés à ces chemins sont faibles il est toujours possible de les emprunter. De la même façon qu’un chemin de très forte probabilité peut ne pas être emprunter. Il s’agit de probabilités. Forcer le joueur à perdre n’est possible que si l’on empêche d’utiliser un des 3 coups (probabilité = 0) et que l’on force l’adversaire à utiliser le coup gagnant (probabilité = 1). Ce qui reviendrait à supprimer un chemin.
PARTIE 2 : APPRENTISSAGE
1. Le programme va analyser les coups de A pour essayer de deviner les probabilités avec lesquelles il joue pour pouvoir choisir les coups gagnants. Par exemple, si A tire plus souvent feuille, je tire plus souvent ciseaux.
#Donne le prochain coup à jouer en fonction de la probabilité du joueur adverse
play = function(prob=c(1/3,1/3,1/3)){
#On prend la plus grande probabilité
max = max(prob)
#On joue le coup gagnant face au coup le plus probable
if(prob[1]==max) {next_played='F' }
else if(prob[2]==max) {next_played='C' }
else if(prob[3]==max) {next_played='P' }
#next played est le coup conseillé
next_played
}
#Test pour une probabilité de 1 de jouer Ciseaux
#Resultat attendu : Pierre
play(c(0,0,1))## [1] "P"#Test pour une probabilité de 1 de jouer Ciseaux
#Resultat attendu : Feuille. En effet ici, les 3 événements sont équiprobables donc on pourrait tirer au hasard parmis les 3 mais une étude suggére que lorsque l'on ne sait pas quoi faire, il vaut mieux jouer feuille
#Donc quand les probabilités sont égales on joue feuille.
play(c(1/3,1/3,1/3))## [1] "F"#playerX = proba du joueur X
#played = coup joué
#times = nombre de coups joués
#Recalcule les fréquences (probas) de A
adjust=function(playerX=c(),played='',times=10){
if(played=='P'){
playerX[1]=(playerX[1]*(times-1)+1)/times
playerX[2]=(playerX[2])*(times-1)/times
playerX[3]=(playerX[3])*(times-1)/times
}
else if(played=='F'){
playerX[1]=(playerX[1])*(times-1)/times
playerX[2]=(playerX[2]*(times-1)+1)/times
playerX[3]=(playerX[3])*(times-1)/times
}
else if(played=='C'){
playerX[1]=(playerX[1])*(times-1)/times
playerX[2]=(playerX[2])*(times-1)/times
playerX[3]=(playerX[3]*(times-1)+1)/times
}
playerX
}
#Test après 6 tours, si mes probas initiales sont de (0.4/0.4/0.2) et que j'ai joué C alors mes nouvelles stats sont de (1/3,1/3,1/3)
adjust(c(0.4,0.4,0.2),played='C',times=6)## [1] 0.3333333 0.3333333 0.3333333#Au début, si mes probas initiales sont de (0,0,0) et que j'ai joué F alors mes nouvelles stats sont de (0,1,0)
adjust(c(0,0,0),played='F',times=1)## [1] 0 1 0Version 1 ne reconnait que les pattern distancés de 2.
#Cette fonction prend la liste des coups : data; le numéro de coup actuel : current_position, et la liste des probabilités
pattern_recognition = function (data=c(),current_position=0,playerXA=c()){
#On cherche des motifs quand on a plus de 12 éléments
pattern_soluce=' '
if(current_position>=12){
i=2
k=2
#On cherche sur les coups déjà joué si le coup tout les 2 coups est le même 3 fois d'affilé.
while(data[current_position-2]==data[current_position-2*k]&&k<4){
k=k+1
}
#Si c'est le cas alors on a un motif, et on suppose que le coup joué va être le même
if(k==4){
if(data[current_position-i]=='P'){
pattern_soluce='F'
}
else if(data[current_position-i]=='F'){
pattern_soluce='C'
}
else {
pattern_soluce='P'
}
pattern_soluce
}
else{
play(playerXA)
}
}
else{
play(playerXA)
}
}Version 2 : On tente d’identifier des pattern un peu plus larges.
adv_pattern_recognition = function (data=c(),current_position=0,playerXA=c()){
pattern_soluce=' '
i=2
k=2
if(current_position>=21){
while(pattern_soluce==' ' && i<5){
while(data[current_position-i]==data[current_position-i*k]&&k<4){
k=k+1
}
if(k==4){
if(data[current_position-i]=='P'){
pattern_soluce='F'
}
else if(data[current_position-i]=='F'){
pattern_soluce='C'
}
else {
pattern_soluce='P'
}
pattern_soluce
}
i=i+1
}
}
else{
play(playerXA)
}
pattern_soluce
}Cette fonction joue en apprenant.
learning = function(N=10000){
#Data
nb_won=0
total_gain=0
nb_lost=0
tie=0
graph_won=c(0)
#Liste de coups joués
playerA=c()
playerB=c()
#Initilisation des probabilités
playerXA=c(0,0,0)
playerXB=c(0,0,0)
#Jeu à N parties :
for (i in 1:N){
# take1 = coup joué par le joueur A
take1 = sample (probA,1,TRUE)
playerA=c(playerA,take1)
#Calcul proba de A
playerXA=adjust(playerXA,take1,i)
#Choix de mon coup
take2=play(playerXA)
#Ajout du coup joué dans le liste des coups joués.
playerB=c(playerB,take2)
#Si les 2 coups sont différents (il y a un gagnant & un perdant)
if (take1!=take2){
#Si le joueur A a joué Pierre
if (take1=='P'){
#Si le joueur B a joué Ciseaux
if (take2=='C'){
#Le joueur A a gagné. Donc le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost + 1
graph_won=c(graph_won,(total_gain/i))
}
#Sinon le joueur B a gagné
else {
total_gain = total_gain + 1
nb_won = nb_won + 1
graph_won=c(graph_won,total_gain/i)
}
}
#Sinon, si le joueur A a joué Feuille
else if (take1=='F'){
#Si le joueur B a joué Pierre
if(take2=='P'){
# Alors, le joueur A a gagné et le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost + 1
graph_won=c(graph_won,total_gain/i)
}
else{
#Sinon le joueur B a gagné
total_gain = total_gain + 1
nb_won = nb_won + 1
graph_won=c(graph_won,total_gain/i)
}
}
else {
#Sinon, le joueur A a joué Ciseaux
#Si le joueur B a joué Feuille
if (take2=='F'){
#Le joueur A a gagné et le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost +1
graph_won=c(graph_won,total_gain/i)
}
else {
#Sinon, le joueur B a gagné
total_gain = total_gain + 1
nb_won = nb_won + 1
graph_won=c(graph_won,(total_gain)/i)
}
}
}
else {
#Si les 2 coups sont identiques, personne ne gagne
tie=tie+1
graph_won=c(graph_won,total_gain/i)
}
}
plot(graph_won,xlab = "évolution du gain sur N parties")
graph_won
#Gain moyen, nb de parties gagnées, perdues, égalité, et somme pour vérification
c(total_gain/N, nb_won,nb_lost,tie, nb_lost+nb_won+tie)
}
learning(1000)
## [1] 0.28 518.00 238.00 244.00 1000.00- On remarque une espérance de gain de 0.25 environ contre 0.
- L’algorithme présente en effet une faille. Quand tous les événements sont équiprobables, il joue feuille. Donc, un être humain assez intelligent pour jouer selon un motif de manière à ce que l’algorithme pense que l’humain joue \(P(\frac{1}{3},\frac{1}{3},\frac{1}{3})\) puis jouer au bon moment ciseaux va tout gagner. On peut pour l’améliorer, implémenter une détection de motifs.
OPTIMISATION AVEC PATTERN RECOGNITION
learning = function(N=10000, playerA,adv=FALSE){
#Data
nb_won=0
total_gain=0
nb_lost=0
tie=0
graph_won=c(0)
#Liste de coups joués
playerB=c()
#initialisation des probabilités
playerXA=c(0,0,0)
playerXB=c(0,0,0)
#Jeu à N parties :
for (i in 1:N){
# take1 = coup joué par le joueur A
take1 = playerA[i]
#calcul des nouvelles fréquences de A
playerXA=adjust(playerXA,take1,i)
#Choix de la fonction de pattern recognition
if(adv){
#version avancée:
take2=adv_pattern_recognition(playerA,i,playerXA)
}
else {
#version 2-décalé :
take2=pattern_recognition(playerA,i,playerXA)
}
#Ajout du coup joué dans le liste des coups joués.
playerB=c(playerB,take2)
#Calcul du gain :
#Si les 2 coups sont différents (il y a un gagnant & un perdant)
if (take1!=take2){
#Si le joueur A a joué Pierre
if (take1=='P'){
#Si le joueur B a joué Ciseaux
if (take2=='C'){
#Le joueur A a gagné. Donc le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost + 1
graph_won=c(graph_won,(nb_won/i))
}
#Sinon le joueur B a gagné
else {
total_gain = total_gain + 1
nb_won = nb_won + 1
graph_won=c(graph_won,nb_won/i)
}
}
#Sinon, si le joueur A a joué Feuille
else if (take1=='F'){
#Si le joueur B a joué Pierre
if(take2=='P'){
# Alors, le joueur A a gagné et le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost + 1
graph_won=c(graph_won,nb_won/i)
}
else{
#Sinon le joueur B a gagné
total_gain = total_gain + 1
nb_won = nb_won + 1
graph_won=c(graph_won,nb_won/i)
}
}
else {
#Sinon, le joueur A a joué Ciseaux
#Si le joueur B a joué Feuille
if (take2=='F'){
#Le joueur A a gagné et le joueur B a perdu
total_gain = total_gain - 1
nb_lost = nb_lost +1
graph_won=c(graph_won,nb_won/i)
}
else {
#Sinon, le joueur B a gagné
total_gain = total_gain + 1
nb_won = nb_won + 1
graph_won=c(graph_won,(nb_won)/i)
}
}
}
else {
#Si les 2 coups sont identiques, personne ne gagne
tie=tie+1
graph_won=c(graph_won,nb_won/i)
}
}
plot(graph_won)
graph_won
#Gain moyen, nb de parties gagnées, perdues, égalité, et somme pour vérification
c(total_gain/N, nb_won,nb_lost,tie, nb_lost+nb_won+tie)
}TESTS 2-décalé pattern
N=300
#Sur une séquence sans motif, on utilise l'algorithme classique qui apprend les fréquences et on gagne une partie sur 2 environ.
learning(N,playerA=rep(c('P','F','C','C','P','F'),N/6),FALSE)
## [1] 0.3633333 158.0000000 49.0000000 93.0000000 300.0000000#Avec motif, le gain est beaucoup plus important.
playerA=rep(c('P','F'),N/2)
learning(N,playerA,FALSE)
## [1] 0.9833333 295.0000000 0.0000000 5.0000000 300.0000000On peut avoir un gain jusqu’à 75% plus haut avec la nouvelle version.
TESTS adv pattern
N=300
#Sur une séquence sans motif, on utilise l'algorithme classique qui apprend les fréquences et on gagne une partie sur 2 environ.
learning(N,playerA=rep(c('P','F','C','C','P','F'),N/6),TRUE)
## [1] 0.53 206.00 47.00 47.00 300.00#Avec motif, le gain est beaucoup plus important.
playerA=rep(c('P','F'),N/2)
learning(N,playerA,TRUE)
## [1] 1 300 0 0 300Les résultats de cette fonction ne sont pas concluants. En effet, on voit que 100% des parties sont gagnées lorsqu’un motif est présent. Ce qui est peu probable.
QUESTION
Stratégie non aléatoire
On peut s’inspirer du théorème de Shannon et procéder de la façon suivante:
Au début, j’observe le comportement de mon adversaire et essaie d’identifier des motifs. Pendant cette phase je choisis mes coups au hasard. Dans une seconde phase, je réagis au comportement de mon adversaire. S’il garde toujours le même coup alors je garde aussi le même coup (qui me permet de gagner). S’il change de comportement, je change aussi.