Q1

Le joueur biaisé

Question 1

On commence par choisir un nombre de parties N que l’on va simuler plus tard :

N = 10000

On écrit ensuite les probabilités des évènements suivant pour chaque joueur : “le joueur choisit de faire pierre”, “le joueur choisit de faire feuille” et “le joueur choisit de faire ciseaux”.

pAb = c(1/4, 1/4, 1/2)
pB1 = c(1/4, 1/4, 1/2)

On peut alors déterminer nos vecteurs de choix :

choixAb = sample(1:3, N, TRUE, pAb)
choixB1 = sample(1:3, N, TRUE, pB1)

Or, on sait que si le joueur B veut gagner, il faut qu’une des combinaison suivantes se présente : il choisit pierre (1) quand l’adversaire choisit ciseaux (3), il choisit feuille (2) quand l’adversaire choisit pierre (1), ou il choisit ciseaux (3) quand l’adversaire choisit feuille (2).

Ainsi, l’espérance de gain du joueur B sera déterminée par l’opération suivante :

sum((choixB1 == 1 & choixAb == 3) | (choixB1 == 2 & choixAb == 1) | (choixB1 == 3 & choixAb == 2)) / N
## [1] 0.3187

Voici donc la fonction correspondante, qui effectue ce calcul sur un échantillon de N parties.

En paramètre, jA et jB sont deux vecteurs de taille 3. Ils contiennent les probabilités de choisir chacun des 3 coups.

esperB = function(jA, jB) {
  choixA = sample(1:3, N, TRUE, jA)
  choixB = sample(1:3, N, TRUE, jB)
  sum((choixB == 1 & choixA == 3) | (choixB == 2 & choixA == 1) | (choixB == 3 & choixA == 2)) / N
}

Pour cette première question, on calcule donc :

esperB(pAb, pB1)
## [1] 0.3103

Ainsi, on obtient quasiment 1/3. Le jeu est donc équitable puisque les deux joueurs jouent de la même manière.

Remarque : on observe que si l’on répète la simulation à plusieurs reprises, alors on n’obtiendra que très rarement une espérance supérieure à 1/3. En fait, on ne peut pas vraiment conclure qu’en moyenne, on va avoir une espérance exactement égale à 1/3, même si celle-ci en est très proche. Elle est plutôt de l’ordre de 0.3100, même s’il serait logique de penser que deux joueurs adoptant la même stratégie auront la même espérance de gain, donc que cette valeur soit de l’ordre de 0.3333.

Question 2

Pour cette seconde question, on a :

pB2 = c(1/3, 1/3, 1/3)
esperB(pAb, pB2)
## [1] 0.3297

On obtient cette fois-ci une valeur légèrement supérieure à la précédente et bien plus proche de 1/3. On peut donc en déduire que le fait qu’un joueur choisisse de jouer de manière totalement aléatoire le favorise par rapport à un joueur biaisé (qui choisit de favoriser un coup).

Remarque : cette fois-ci, si l’on répète plusieurs simulations d’affilée (ou sur un plus grand échantillon), alors on observe que l’on obtient de manière équitable des valeurs inférieures et supérieures à 0.333. Il est donc raisonnable de penser que cette fois-ci, l’espérance de gain du joueur B sera égale à 1/3. Pourtant, les deux joueurs n’ont pas la même stratégie de jeu !

Question 3

Le joueur A a toujours la même probabilité de jouer chacun des 3 coups. Cependant, pour cette question, la probabilité que le joueur B choisisse un coup particulier varie en fonctions de deux variables x et y. Pour calculer ces variables, on doit générer un nombre aléatoire entre 0 et 1 qui évoluera par pas de 0.1. Ainsi, on utilise successivement les fonctions runif et round ; runif nous sert à générer un nombre aléatoire entre 0 et 1, round nous permet d’arrondir ce nombre et d’afficher une seule décimale. C’est ce qui simule le “pas de 0.1”.

Mais il faut faire attention à ne pas obtenir une probabilité pB3 négative ! Cela est impossible, on doit donc exclure cette possibilité. Ainsi, on teste si 1 - x - y est négatif : si c’est le cas, on génère à nouveau x et y, sinon on garde la probabilité pB3 obtenue.

x = round(runif(1, 0, 1), 1)
y = round(runif(1, 0, 1), 1)

while ((1 - x - y) < 0) {
  x = round(runif(1, 0, 1), 1)
  y = round(runif(1, 0, 1), 1)
}
pB3 = c(x, y, 1 - x - y)

L’espérance de gain du joueur B est alors calculée grâce à la fonction précédente :

esperB(pAb, pB3)
## [1] 0.2495

Le résultat obtenu est variable. Si l’on réalise l’expérience plusieurs fois d’affilée, alors on remarque que l’on obtient des espérances parfois supérieures et parfois inférieures à celles précédemment trouvées.

Il faut donc écrire une fonction nous permettant de réaliser la moyenne de toutes ces espérances obtenues pour des valeurs de x et y différentes. On aura ainsi une idée précise de l’efficacité de cette stratégie. On effectue alors un test sur 1000 générations de x et y pour 1000 parties chacunes. Le résultat retourné est la moyenne de l’espérance de gain de B sur toutes les générations réalisées.

test = function(p){
  M = 1:1000
  res = sample(0, 1000, TRUE)
  for(i in M){
    x = 1
    y = 1
    while ((1 - x - y) < 0) {
      x = round(runif(1, 0, 1), 1)
      y = round(runif(1, 0, 1), 1)
    }
    pB = c(x, y, 1 - x - y)
    res[i] = esperB(p, pB)
  }
  print(sum(res)/1000)
}

On applique alors cette fonction au cas du joueur biaisé :

test(pAb)
## [1] 0.3307606

Ainsi, on constaste qu’elle est très proche de 1/3. Par ailleurs, elle reste toujours inférieure à l’espérance trouvée dans le cas d’un joueur B non biaisé.

Cette stratégie consiste, d’après les probabilités données, à ne pas jouer de manière aléatoire, mais au contraire à décider des probabilités des coups que l’on va jouer. C’est certainement celle adoptée par un humain par exemple, car il est incapable de générer du hasard.

Ainsi, en comparant les espérances, on peut en conclure qu’en moyenne le fait de ne pas jouer de manière aléatoire face à un joueur biaisé est moins efficace que lorsque l’on joue au hasard comme peut le faire le poisson chirurgien.

Cependant, si cette espérance est en moyenne égale à 1/3, on a vu qu’elle pouvait varier beaucoup et être parfois bien supérieure à celle obtenue dans le cas d’un jeu au hasard. De ce fait, dans certains cas, le joueur humain peut être dans une position favorable face à un joueur biaisé si ses choix de coup sont adaptés.

Question 4

Il semblerait donc qu’il existe trois grandes catégories de stratégies distinctes pour ce jeu : choisir de favoriser un coup (joueur biaisé, question 1), ne pas choisir de favoriser un coup (joueur non biaisé, question 2), ou choisir les probabilités de chacun des 3 coups (joueur humain, question 3).

Ainsi, il apparaît clairement que la meilleure des manières de gagner contre un joueur biaisé est de jouer au hasard chacun des 3 coups, car c’est dans ce cas précis que l’espérance est la meilleure. C’est donc la stratégie que le joueur B doit adopter (ou du moins, il doit essayer de s’en rapprocher au maximum, car si c’est un humain, alors il est incapable de jouer parfaitement au hasard).

Le joueur non biaisé

Question 1

Il convient d’abord d’écrire les probabilités modifiées du joueur A qui, cette fois-ci, joue de manière totalement aléatoire chacun des 3 coups :

pAnb = c(1/3, 1/3, 1/3)

L’espérance de gain du joueur B est alors donnée par le calcul suivant :

esperB(pAnb, pB1)
## [1] 0.331

Ainsi, cette valeur semble être très proche de 1/3. Elle est au passage légèrement supérieure à celle précédemment trouvée dans le cas où A était un joueur biaisé. La méthode adoptée ici par le joueur B est donc plus efficace face à ce type de joueur.

Question 2

esperB(pAnb, pB2)
## [1] 0.327

Ici, l’espérance semble être égale à 1/3. C’est logique puisque les deux joueurs adoptent la même stratégie, celle de jouer de manière totalement aléatoire.

Question 3

esperB(pAnb, pB3)
## [1] 0.3384

Une fois de plus, l’espérance semble être de l’ordre de 1/3. Pourtant, les deux joueurs n’ont pas la même stratégie de jeu.

Comme précédemment, on peut vérifier ce résultat :

test(pAnb)
## [1] 0.3333225

On trouve donc bien 1/3.

Conclusion : lorsque le joueur A est biaisé, alors la stratégie de jeu que son adversaire doit adopter s’il veut maximiser ses chances de gagner est celle de jouer de manière totalement aléatoire. Il peut prendre le risque de prévoir ses coups à l’avance, mais cette méthode de jeu peut se montrer aussi bien efficace que défaillante, même si en moyenne elle semble envisageable. Lorsque le joueur A est non biaisé, il semblerait que l’espérance de gain pour le joueur B soit quasiment toujours la même, c’est-à-dire égale à 1/3, et ce quelque soit la stratégie de jeu qu’il adopte. Cela signifie qu’il possède tout le temps la même espérance de gain face à quelqu’un qui jouera au hasard à chaque coup ! Ainsi, dans cette situation, le joueur A a autant de chance de perdre que de gagner, tout comme le joueur B.

Q1

Question 1

Essayons a présent de développer une I.A “supérieure” au genre humain dans le cas du jeu du “Pierre, Feuille, Ciseaux”.

Notre algorithme va se baser sur les hypothèses suivantes:

  • un joueur a le choix entre trois coups que l’on appellera, comme précédemment, 1 pour Pierre, 2 pour Feuille et 3 pour Ciseaux

  • la fréquence de jeu du coup X (qui appartient à (1, 2, 3)) est donnée par la formule suivante : (nombre de coups X choisit) / (nombre de parties jouées). Ainsi, si l’on appelle f1, f2 et f3 les fréquences correspondantes à chaque coup, on a f1 + f2 + f3 = 1 (sauf au premier coup)

  • les règles sont les suivantes : 1 perd contre 2 ,2 perd contre 3 et 3 perd contre 1

  • notre robot joue le coup X a une fréquence frX. Ainsi, frX = f(X+1) mod 3

Grâce à la fonction suivante, on établit la stratégie de jeu de notre robot. On va en fait déterminer les probabilités de choix de chacun des coups en fonction de celles de son adversaire, de manière à ce qu’il ait le plus de chances possibles de gagner.

En paramètre, freqJ est un vecteur de taille 3. Il représente la fréquence d’apparition de chacun des coups du joueur adverse.

# freqJ est un vecteur 3 
robotFreq = function(freqJ){
  fr = sample(c(0, 0, 1), 3)
  # si on a un vecteur joueur valide
  if(freqJ[1] + freqJ[2] + freqJ[3] == 1){
    fr[1] = freqJ[3]
    fr[2] = freqJ[1]
    fr[3] = freqJ[2]
  }
  return(fr)
}

Maintenant que notre robot est opérationnel, il nous reste à effectuer une simulation sur un nombre N de parties :

NB = 1000

# p1 est un vecteur 3 et robotFreqFunction est une fonction vecteur 3 -> vecteur 3
simulvsrobot = function(p1, robotFreqFunction){
  yAxis = sample(0, NB, TRUE)
  # mettons N à 1 car esperB l'utilise
  N = 1
  # notre vecteur choixJ enregistre le choix courant du joueur
  choixJ = 0
  # dans choixnb[x], on a le nombre de coups X fait par le joueur
  choixnb = c(0,0,0)
  freqJ = c(0,0,0)
  freqR = c(0,0,0)
  # nombre de parties gagnées par le robot
  nbwin = 0
  for(i in 1:NB){
    # soyons honnêtes avec le joueur en faisant jouer le robot en premier
    freqR = robotFreqFunction(freqJ)
    # on réutilise Q1 question 1 pour déterminer le choix de 1 au moment i
    choixJ = sample(1:3, 1, TRUE, p1)
    
    # on incrémente le bon compteur
    if(choixJ == 1){
      choixnb[1] = choixnb[1]+1
    } else if(choixJ == 2){
      choixnb[2] = choixnb[2]+1
    } else if(choixJ == 3){
      choixnb[3] = choixnb[3]+1
    }
    
    # puis on calcule la fréquence de jeu des trois coups de notre joueur
    freqJ[1] = choixnb[1]/i
    freqJ[2] = choixnb[2]/i
    freqJ[3] = choixnb[3]/i
    
    # et enfin l'espérance de gain courante du robot
    # vu que N = 1, esperB retourne 1 en cas de victoire du robot, 0 sinon
    nbwin = nbwin + esperB(p1, freqR)
    yAxis[i] = nbwin/i
  }
  plot(1:NB, yAxis, xlab = "Parties", ylab =  "EsperanceRobot")
  print("EsperanceRobot finale:")
  print(yAxis[NB])
}

simulvsrobot(c(1/4,3/4,0), robotFreq)

## [1] "EsperanceRobot finale:"
## [1] 0.6276526

Ainsi, on constate que plus l’adversaire de notre robot est biaisé, plus notre robot a de chance de gagner. On a choisi d’utiliser le second ordre pour notre fonction de simulation car il y a plusieurs fonctions possibles pour le calcul de la fréquence de jeu du robot (par exemple, on pourrait coder une fonction qui fait jouer au robot le coup gagnant contre le coup le plus populaire du joueur).

Question 2

simulvsrobot(pAb, robotFreq)

## [1] "EsperanceRobot finale:"
## [1] 0.3764597

On constate que l’espérance de gain de notre robot croît au fur et à mesure qu’il apprend. Cependant, cette croissance semble être bornée.

Question 3

La meilleure façon de jouer contre notre premier robot est de jouer de façon non biaisée, or c’est impossible pour un humain. La machine est donc supérieure à l’homme dans le jeu du “Pierre, Feuille, Ciseaux”. En revanche, un humain pourrait gagner à coup sûr contre la version naïve de notre robot en jouant à une partie n le coup vainqueur contre le coup vainqueur de son coup le plus joué aux n-1 parties d’avant.

Question 4

On obtient un taux de victoire systématiquement supérieur à 1/3 pour un nombre suffisant de parties, cependant l’espérance de gain de notre robot est supérieure à l’espérance de gain d’un joueur jouant équitablement face à un joueur biaisé (cf. Q2 question 1). Mais elle est aussi très proche de l’espérance d’un joueur humain (cf. Q1 question 3).