Le jeu de l'urne
Lors de la visite au laboratoire d'une brillante élève de seconde (salut Lena !), nous avons inventé ensemble un petit jeu aux apparences simples mais aux implications surprenantes : le jeu de l'urne.
L'idée de départ : peut-on mesurer l'impulsivité d'une personne rien qu'en observant ses choix ? C'est le pari de ce jeu.
Le principe¶
Imaginez une urne opaque contenant autant de balles rouges que noires — disons 8 balles au total, 4 rouges, 4 noires. À chaque tour, vous avez deux options :
- Passer : vous tirez une balle, observez sa couleur, et la mettez de côté. Vous en savez un peu plus sur ce qu'il reste dans l'urne.
- Deviner : vous pariez sur la couleur de la prochaine balle avant de la tirer. Si vous avez raison, vous gagnez autant de points qu'il reste de balles dans l'urne. Si vous avez tort... vous perdez ces mêmes points.
Le dilemme¶
Là où ça devient intéressant : plus vous laissez passer de balles, plus vous avez d'informations et plus votre prédiction devient fiable. Mais les balles restantes sont aussi de moins en moins nombreuses — et donc les points à gagner, de moins en moins élevés.
Il faut donc trouver le bon moment pour se lancer. Trop tôt, c'est risqué. Trop tard, c'est peu rentable. Ce compromis entre exploration (observer pour mieux savoir) et exploitation (agir pour gagner) est précisément ce qui révèle votre niveau d'impulsivité.
Les règles formelles¶
- $N$ balles au total ($N$ pair, ex. $N = 8$), moitié rouges, moitié noires.
- On tire les balles une à une, sans remise. On peut en observer autant qu'on veut avant de décider.
- Quand on choisit de deviner : bonne prédiction → $+k$ points (où $k$ = nombre de balles restantes) ; mauvaise prédiction → $-k$ points.
- L'objectif à long terme : trouver la stratégie qui maximise son score.
La première version¶
Nous avons d'abord donné vie à ce jeu grâce au langage de programmation Scratch, visible ici : scratch.mit.edu/projects/165806365.
Ici, nous allons essayer de l'analyser plus finement.
Par exemple, je choisis de regarder une balle (rouge), puis un seconde (encore rouge), enfin une troisième (noire) - je décide de parier pour une noire, mais une rouge sort: j'ai perdu $8-3=5$ points. Une autre fois, je tire une balle rouge, une autre balle (cette fois noire): je parie noir et c'est la couleur qui sort: je gagne $8-2=6$ points.
Ce jeu parait simple (je suis curieux de savoir s'il existe, le contraire m'étonnerait) - mais son analyse mathématique implique des combinaisons dont le nombre grandit vite: quelle est la stratégie optimale? C'est ce que nous essaierons de faire ici.
Note: ce jeu pourrait paraitre anodin, mais il est révélateur de notre capacité à prendre des décisions par rapport à ce que l'on sait et ce qui pourrait arriver: c'est la base de la théorie de la décision. Cette théorie est notamment essentielle pour comprendre le fonctionnement normal (ou pathologique comme pour la schizophrénie) et de mieux le comprendre (ou le diagnostiquer).
Cette page est un "notebook", c'est-à-dire une page qui combine des commentaires avec des "cellules" contenant du code informatique qui permet de manipuler et représenter explicitement ou visuellement des informations. On peut donc le télécharger et expérimenter ces étapes une par une par soi-même.
quelque bases de programmation¶
Nous allons ici utiliser un langage de programmation pour communiquer avec l'ordinateur et lui faire effectuer des séquences de calcul. Pour sa simplicité et son ouverture, nous allons utiliser le langage Python. Ensuite, nos allons aborder qulques notions de statistiques utiles pour ce jeu. Si vous pensez posséder ces bases, vous pouvez directement passer à la suite. Programmer en python, c'est auusi simple que de parler en anglais, en voici quelques exemples:
print('Bonjour Lena')
Des opérations mathémtiques de base :
2 * 5
3 / 4
a**b désigne "a puissance b"
2**0 + 2**1 + 4**1.5
créons une liste d'objets en les énumérant entre les symboles [ et ]:
une_liste = [ 1, 4, 5 ]
print(une_liste)
On peut facilement la manipuler en ajoutant un élément:
une_liste.append(6)
print(une_liste)
on peut donc aussi faire une liste pour notre jeu:
une_liste_B = []
une_liste_B.append(0)
une_liste_B.append(1)
une_liste_B.append(0)
une_liste_B.append(0)
une_liste_B
ou de façon plus explicite (pour changer, au lieu de parler de balles rouges ou noires, on va ici parler de ballons de foot='⚽️' ou de basket ='🏀'):
N_ballons = 8
une_liste_C = []
for j in range(N_ballons//2):
une_liste_C.append('🏀')
for j in range(N_ballons//2):
une_liste_C.append('⚽️')
print(une_liste_C)
il y a encore plein d'autres façons d'utiliser des listes:
liste_de_listes = [une_liste, une_liste_B, une_liste_C ]
print(liste_de_listes)
À noter, un autre objet très utile en programmation est un dictionaire:
dico_français_anglais = dict(watch='montre', name='name', age='age')
name = 'watch'
print('La traduction du mot anglais "', name,
'" en français est "', dico_français_anglais[name],'".')
quelque bases de statistiques et de probabilités¶
Pour analyser notre jeu, nous allons avoir besoin de quelques outils mathématiques - si vous pensez posséder ces bases, vous pouvez directement passer à la suite. Une fonction importante pour analyser notre jeu est d'utiliser des générateurs de nombres aléatoires (dans la librairie numpy.random).
import numpy as np
np.set_printoptions(precision=6, suppress=True)
et de fonctions de visualisation pour afficher par exemple des histogrammes avec plt.hist.
import os
%matplotlib inline
#%config InlineBackend.figure_format='retina'
%config InlineBackend.figure_format = 'svg'
import matplotlib.pyplot as plt
on définit la taille des figures selon le nombre d'or:
phi = (np.sqrt(5)+1)/2
fig_width = 10 # en pouces
figsize = (fig_width, fig_width/phi)
print('2 π =', 2 * np.pi)
Explorons direct l'histogramme de $1000000$ tirages d'une variable aléatoire uniforme entre $0$ et $5$:
fig, ax = plt.subplots(figsize=figsize)
ax.hist(5 * np.random.rand(1000000), bins=20);
La même chose avec une variable aléatoire en cloche qui représente bien des statistiques de population:
fig, ax = plt.subplots(figsize=figsize)
ax.hist(.3 * np.random.randn(1000000), bins=20);
En particulier, si on prend un nombre aléatoire entre 0 et 1:
np.random.rand()
il est facile de le transformer en une valeur binaire aléatoire (soit vraie ou fausse, soit True ou False):
np.random.rand() > .5
D'où le tirage d'une variable aléatoire binaire:
fig, ax = plt.subplots(figsize=figsize)
resultats = np.random.rand(100) > .5
ax.hist(resultats)
Si on la considère comme une séquence de tirages d'un dé non pipé, on peut la transformer un un gain poistif ($+1$) ou négatif ($-1$):
plt.step(np.arange(100), 2*resultats-1);
Un intéret pour notre jeu est de considérer le gain accumulé pour des paris, et on "plotte" ici le gain accumulé sur $20$ différentes parties en fonction du temps ($100$ cycles):
resultats = np.random.rand(100, 20) > .5
gains = 2*resultats-1
gains_cumulés = np.cumsum(gains, axis=0)
fig, ax = plt.subplots(figsize=(8, 5))
t = np.arange(100)
std = np.sqrt(t) * gains.std()
ax.fill_between(t, std, -std, color='k', edgecolor='none', lw=0, alpha=0.1);
ax.plot(gains_cumulés, alpha=0.2);
Ces courbes sont importantes: elles montrent que lors d'un jeu non biaisé, les courbes de gain ont en moyenne un gain nul. On montre que leur variance (c'est à dire le carré de la déviation à cette moyenne nulle) augmente proportionnellement et linéairement avec le temps. On donne à ce mouvement le mouvement de mouvement brownien ou de "marche de l'alcoolique" à cause de la forme aléatoire des changements de direction...
application au jeu de l'urne: méthode des tests¶
Une première stratégie pour étudier notre jeu est d'essayer de dénombrer tous les jeux possibles. Dans notre cas particulier, ils consistent en toutes les combinaisons de l'ordre d'occurence des couleurs. Si on les numérote de $0$ à $7$, les occurences de la couleur rouge peuvent par exemple être $[0, 5, 6, 7]$, $[2, 3, 5, 7]$ ou encore $[0, 1, 2, 4]$. Le nombre de façon de tirer $k=4$ nombres parmi $n=8$ est noté $C_n^k$ ou aussi $(^k_n)$ et vaut $\frac{n!}{k! (n-k)!}$ où $n$ est le nombre total de balles et $k$ le nombre de balles rouges et $m!= 1 \times 2 \times \ldots \times m$ est la factorielle de $m$. On va donc pouvoir utiliser la fonction combinations de la librairie itertools (cf https://docs.python.org/3/library/itertools.html#itertools.combinations ) pour former tous ces jeux.
def factorial(n): return np.prod(np.arange(n)+1)
from itertools import combinations
N_ballons = 8
N_basket = N_ballons//2
indices = list(combinations(range(N_ballons), N_basket))
print ('Il y a', len(indices), 'combinaisons. (On avait prédit',
int(factorial(N_ballons)/factorial(N_basket)/factorial(N_ballons-N_basket)), ' 😎). ')
for index in indices:
test = np.zeros(N_ballons, dtype=np.int)
test[list(index)] = 1
print('index = ', index, ' - test = ', test)
Alternativement, nous utiliserons aussi une autre stratégie plus simple de prime abord car elle correspond à la réalité du déroulement d'un jeu réel: réalisons plein de tirages au hasard (c'est la méthode dite de Monte Carlo). d'abord pour un "test":
def generate_test(N_ballons, N_test=1):
assert (N_ballons/2 == N_ballons//2) # on vérifie que c'est pair
tests = np.zeros((N_test, N_ballons), dtype=np.int)
N_basket = N_ballons//2 # on a moitié de ballons de basket
tests[:, N_basket:] = 1.
for i_test in range(N_test):
tests[i_test, :] = np.random.permutation(tests[i_test, :])
return tests
test = generate_test(N_ballons)
print(test)
on peut noter l'utilisation de la fonction np.random.permutation qui permet de ranger de façon aléatoire une liste (ici les $1$ dénotent arbitrairement des ballons de basket 🏀).
Cette fonction permet de générer un grand nombre de tirages:
N_test = 1000
tests = generate_test(N_ballons, N_test)
test = tests[N_test//13, :]
print(test)
On vérifie alors que le nombre moyen de ballons de baskets est bien $N/2$, et ceci exactement:
print('le nombre de valeurs True = ', np.mean(tests.sum(axis=1)), ' +/- ', np.std(tests.sum(axis=1)))
Créons donc une fonction qui puisse faire ces deux types de tests:
N_ballons = 8
N_basket = N_ballons//2 # on a moitié de ballons de basket
N_test = None
def generate_test(N_ballons=N_ballons, N_basket=N_basket, N_test=N_test, verbose=False):
if N_test is None:
indices = list(combinations(range(N_ballons), N_basket))
tests = np.zeros((len(indices), N_ballons), dtype=np.int)
for i_test in range(len(indices)):
tests[i_test, list(indices[i_test])] = 1
if verbose : print('index = ', indices[i_test], ' - test = ', tests[i_test, :])
else:
tests = np.zeros((N_test, N_ballons), dtype=np.int)
tests[:, :N_basket] = 1
for i_test in range(N_test):
tests[i_test, :] = np.random.permutation(tests[i_test, :])
return tests
tests = generate_test(N_ballons=N_ballons, N_basket=N_basket, N_test=N_test, verbose=True)
une première stratégie: choix a priori d'un nombre fixe¶
Adoptons tout d'abord la stratégie d'un agent qui de façon tétue se dirait qu'il allait regarder un nombre fixe de ballons (par exemple 2) puis se décider pour la solution la plus probable:
N_ballons_vus = 3
information = test[:N_ballons_vus]
information
N_ballons_restant = N_ballons - N_ballons_vus
print ('on a vu ', N_ballons_vus, ' ballon(s), il en reste', N_ballons_restant, " dans l'urne")
N_ballons_restant = N_ballons - N_ballons_vus
print ('on en a vu ', sum(information), ' de basket (=True=Droite) donc il reste',
N_ballons//2 - sum(information), " ballons de basket dans l'urne")
proba_True_restant = (N_ballons/2 - sum(information)) / N_ballons_restant
print ('la probabilité de tirer un de basket est ', proba_True_restant*100, '%, ',
'contre ', (1-proba_True_restant)*100, "% pour l'autre choix ")
On prend logiquement la décision de prendre le choix le plus probable, le cas symétrique étant résolu en prenant une décision au hasard:
if proba_True_restant==.5:
choix = proba_True_restant > np.random.rand()
else:
choix = proba_True_restant > .5
print(choix)
et on peut prévoir notre gain
gain_esperé = N_ballons_restant # c'est-à-dire N_ballons - N_ballons_restant - 1
print(gain_esperé)
et maintenant vérifier si ce choix était le bon
réussite = (test[N_ballons_vus] == choix)
réussite, réussite*2 - 1
gain = gain_esperé * (réussite*2 - 1)
#gain = gain_esperé * réussite
gain
à noter, on peut aussi représenter une information vide avec une liste vide:
test[:0]
Maintenant que nous avons suivi notre stratégie pour un ballon et sur un test, généralisons le à plusieurs tests: regardons d'abord un seul ballon:
N_test = None
tests = generate_test(N_ballons=N_ballons, N_basket=N_basket, N_test=N_test)
gains = np.zeros(len(tests))
N_ballons_vus = 1
for i_test in range(len(tests)):
information = tests[i_test, :(N_ballons_vus)]
N_ballons_restant = N_ballons - N_ballons_vus
proba_True_restant = (N_ballons//2 - np.sum(information)) / N_ballons_restant
if proba_True_restant==.5:
choix = np.random.rand() > .5
else:
choix = proba_True_restant > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant
gains[i_test] = gain_esperé * (réussite*2 - 1)
plt.hist(gains);
et maintenant sur tous les tests:
ax = plt.pcolormesh(tests.T);
tests_0 = tests[:, 0]
tests_1 = tests[:, 1]
#print (tests[:, 1:].sum(axis=1), tests[:, 1:].sum(axis=1).std())
print (1. - np.sum(tests_0 == tests_1)/ len(tests_1))
en résumé, on peut calculer le gain moyen sur un certain nombre de tests :
def agent_tetu(tests, N_ballons_vus, penalité=1, aléatoire=False):
gains = np.zeros(len(tests))
for i_test in range(N_test):
information = tests[i_test, :(N_ballons_vus)]
N_ballons_restant = N_ballons - N_ballons_vus
proba_True_restant = (N_ballons//2 - sum(information)) / N_ballons_restant
if aléatoire:
choix = proba_True_restant > np.random.rand()
else:
if proba_True_restant==.5:
choix = np.random.rand() > .5
else:
choix = proba_True_restant > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*(1+penalité) - penalité)
return gains
N_test = 1024
tests = generate_test(N_ballons=N_ballons, N_basket=N_basket, N_test=N_test)
gains = agent_tetu(tests, N_ballons_vus=1, aléatoire=False)
print ('gain = ', gains.mean(), '+/-', gains.std())
N_test = 10000
fig, ax = plt.subplots(figsize=figsize)
for aléatoire, label in zip([True, False], ['aléa', 'max']):
print('Stratégie aléatoire? ', aléatoire)
gains = np.zeros((N_ballons, N_test))
tests = generate_test(N_ballons=N_ballons, N_basket=N_basket, N_test=N_test)
for N_ballons_vus in range(N_ballons):
gains[N_ballons_vus, :] = agent_tetu(tests, N_ballons_vus, aléatoire=aléatoire)
print('Moyenne des gains avec', N_ballons_vus, 'ballons vus =', np.mean(gains[N_ballons_vus, :]) , ' +/- ', np.std(gains[N_ballons_vus, :]) )
ax.errorbar(np.arange(N_ballons)-.1*(aléatoire*1-1), y=np.mean(gains, axis=(1)), yerr=np.std(gains, axis=(1))/10, label=label, alpha=.5, lw=2)
ax.set_xlabel(' # ballons vus ')
ax.set_ylabel(' gain moyen par jeu (+/- SEM / 10 ) ')
ax.legend();
La stratégie optimale est de choisir la gain a priori maximal.
Première conclusion: le gain évolue en fonction du nombre de ballons vus.
- Les gains sont en moyenne toujours positifs, on s'oriente vers un enrichissement infini...
- la variabilité de gain pour chaque jeu individuel est toujours grand et de l'ordre du nombre de points en jeu: on est proche d'un pari de type pile ou face,
- Le comportement d'un agent aléatoire est toujours significativement inférieur,
- La stratégie optimale pour cet agent est de choisir quand on a vu $3$ ballons. On note une oscillation pour des nombres de ballons vus pairs qui est dû au fait que nous ayons deux catégories.
Maintenant on peut imaginer, de régler le paramètre de pénalité pour optimiser le compromis entre précision et gain.
penalités = np.linspace(.5, 1.5, 9)
penalités
N_test = 10000
fig, ax = plt.subplots(figsize=figsize)
for penalité in penalités:
gains = np.zeros((N_ballons, N_test))
tests = generate_test(N_ballons=N_ballons, N_basket=N_basket, N_test=N_test)
for N_ballons_vus in range(N_ballons):
gains[N_ballons_vus, :] = agent_tetu(tests, N_ballons_vus, penalité=penalité)
ax.errorbar(np.arange(N_ballons)-.1*(aléatoire*1-1), y=np.mean(gains, axis=(1)), yerr=np.std(gains, axis=(1))/10, label=str(penalité), alpha=.5, lw=2)
ax.set_xlabel(' # ballons vus ')
ax.set_ylabel(' gain moyen par jeu (+/- SEM / 10 ) ')
ax.legend();
on voit qu'en fonction de la pénalité on peut "encourager" un tel agent tétu à prendre des décisions plus hâtives ou tardives. On restera pour l'instant au cas équilibré avec une pénalité nulle. Clairement, pour un tel agent, la stratégie optimale est de ragarder $3$ ballons puis de se décider.
Note: on remarque que le gain si on a tout observé est bien nul (l'information est totale mais la récompense est nulle):
print ('gains ', gains[-1, :])
N_ballons_vus = 7
print('Moyenne des gains avec', N_ballons_vus, 'ballons vus =', np.mean(gains[N_ballons_vus, :]) , ' +/- ', np.std(gains[N_ballons_vus, :]) )
Pour résumer, nous pouvons "encapsuler" toute la programmation liée à cet agent dans un objet:
class AgentTétu:
def __init__(self, N_test=2**12, N_ballons=8, verbose=True):
self.N_test = N_test
self.N_ballons = N_ballons
self.N_basket = N_ballons//2
self.verbose = verbose
def generate_test(self):
return generate_test(N_ballons=self.N_ballons, N_basket=self.N_basket, N_test=self.N_test)
def agent_tetu(self, tests, N_ballons_vus):
gains = np.zeros(len(tests))
for i_test in range(len(tests)):
information = tests[i_test, :(N_ballons_vus)]
N_ballons_restant = self.N_ballons - N_ballons_vus
proba_True_restant = (self.N_ballons//2 - sum(information)) / N_ballons_restant
if proba_True_restant==.5:
if self.N_test is None:
gains[i_test] = 0.
else:
choix = np.random.rand() > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*2 - 1)
else:
choix = proba_True_restant > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*2 - 1)
return gains
def test(self):
tests = self.generate_test()
gains = np.zeros((self.N_ballons, len(tests)))
for N_ballons_vus in range(self.N_ballons):
gains[N_ballons_vus, :] = self.agent_tetu(tests, N_ballons_vus)
if self.verbose: print('Moyenne des gains avec', N_ballons_vus, 'ballons vus =', np.mean(gains[N_ballons_vus, :]) ,
' +/- ', np.std(gains[N_ballons_vus, :]) )
return gains
def plot(self):
gains = self.test()
fig, ax = plt.subplots(figsize=figsize)
ax.errorbar(np.arange(self.N_ballons), y=np.mean(gains, axis=(1)), yerr=np.std(gains, axis=(1))/10, alpha=.5, lw=2)
ax.set_xlabel(' # ballons vus ')
ax.set_ylabel(' gain moyen par jeu (+/- SEM / 10 ) ')
return fig, ax
agent = AgentTétu()
agent.plot();
Cet objet nous permet de vérifier que ce comportement ne dépend pas significativement du nombre de test (s'il est significativement plus grand que $70$):
%%timeit -n1 -r1
agent = AgentTétu(N_test=2**10)
agent.plot();
%%timeit -n1 -r1
agent = AgentTétu(N_test=2**13)
agent.plot();
Le résultat exact est donné en calculant sur l'ensemble des combinaisons:
%%timeit -n1 -r1
agent = AgentTétu(N_test=None)
agent.plot();
On observe que la stratégie "Monte Carlo" donne des résultats similaires mais est plus longue à simuler. On pourra choisir notre stratégie computationnelle en fonction de notre budget en resources (ordinateurs, CPU, ...).
On observe aussi que le comportement du jeu est similaire avec plus ou moins de ballons:
agent = AgentTétu(N_ballons=16, N_test=None)
agent.plot();
agent = AgentTétu(N_ballons=6, N_test=None)
agent.plot();
On peut aussi montrer en fonction du nombre de ballons vus l'evolution du gain au cours du temps (en fonction du nombre de tests):
agent = AgentTétu()
gains = agent.test()
gains_cumulés = np.cumsum(gains, axis=1)
fig, ax = plt.subplots(figsize=figsize)
for N_ballons_vus in range(agent.N_ballons):
label = '%d ballons vu' % N_ballons_vus
if N_ballons_vus>1: label += 's '
ax.plot(gains_cumulés[N_ballons_vus, :], alpha=0.9, label=label)
ax.set_xlabel(' # essais ')
ax.set_ylabel(' gain cumulé ')
ax.legend();
Les tendances sont nettes et on observe bien que la stratégie optimale est vite payante. Notez toutefois, que par le jeu du hasard, ce n'étatit peut-être pas vrai au tout début.
une deuxième stratégie: choix au fil de l'eau¶
Nous avons qualifié cette stratégie de tétue car elle décidait a priori quel était le nombre optimal de ballons à voir sans examiner ce qui venait d'être observé dans un test particulier. Par exemple, les chances sont complétement différentes si on a observé deux ballons de même type contre deux ballons différents. De la même façon, notre stratégie devrait dépendre en fonction de ce qu'on vient de voir.
Mais ce que nous avons vu au dessus peut nous être utile. Imaginons que nous avons vu un certain nombre de ballons, on peut alors faire assez de tests pour anticiper en moyenne les gains que l'on peut espérer si on attend un tour ou plus. La stratégie consiste alors à parier si le gain présent est supérieur à celui auquel qui est prédit si on attend un tour ou plus.
Il faut juste modifier l'agent ci-dessus en lui donnant la possibilité d'avoir un nombre différent de ballons de baskets ou de ballons de foot:
class AgentTétuAvecInit:
def __init__(self, N_test=2**13, N_basket=4, N_foot=4, verbose=True):
self.verbose = verbose
self.N_test = N_test
self.N_ballons = N_basket + N_foot
self.N_foot = N_foot
self.N_basket = N_basket
def generate_test(self):
return generate_test(N_ballons=self.N_ballons, N_basket=self.N_basket, N_test=self.N_test)
def agent_tetu(self, tests, N_ballons_vus):
gains = np.zeros(tests.shape[0])
for i_test in range(tests.shape[0]):
information = tests[i_test, :(N_ballons_vus)]
N_ballons_restant = self.N_ballons - N_ballons_vus
proba_True_restant = (self.N_basket - sum(information)) / N_ballons_restant
if proba_True_restant==.5:
if self.N_test is None:
gains[i_test] = 0.
else:
choix = np.random.rand() > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*2 - 1)
else:
choix = proba_True_restant > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*2 - 1)
return gains
def test(self):
tests = self.generate_test()
gains = np.zeros((self.N_ballons, tests.shape[0]))
for N_ballons_vus in range(self.N_ballons):
gains[N_ballons_vus, :] = self.agent_tetu(tests, N_ballons_vus)
if self.verbose: print('Moyenne des gains avec', N_ballons_vus, 'ballons vus =', np.mean(gains[N_ballons_vus, :]) ,
' +/- ', np.std(gains[N_ballons_vus, :]) )
return gains
def razor(self):
gains = self.test()
gain_moyen = gains.mean(axis=1)
return gain_moyen[0]>gain_moyen[1:].max()
def plot(self):
gains = self.test()
fig, ax = plt.subplots(figsize=figsize)
ax.errorbar(np.arange(self.N_ballons), y=np.mean(gains, axis=(1)), yerr=np.std(gains, axis=(1))/10, alpha=.5, lw=2)
ax.set_xlabel(' # ballons vus ')
ax.set_ylabel(' gain moyen par jeu (+/- SEM / 10 ) ')
return fig, ax
agent = AgentTétuAvecInit(N_basket=5, N_foot=3)
agent.plot();
On vérifie que l'on retrouve l'agent initial avec un nombre balancé de ballons:
agent = AgentTétuAvecInit(N_basket=4, N_foot=4)
agent.plot();
En particulier, il semble qu'il vaille mieux attendre quand on a tiré un seul ballon car on peut espérer un gain moyen supérieur:
agent = AgentTétuAvecInit(N_basket=4, N_foot=3)
agent.plot();
Notre prédiction donne aussi l'information que le gain espéré sera meilleur dans exactement deux coups! Mais bien sûr, celà dépend de l'occurence suivante.
En particulier, si on tire encore un ballon de basket, il vaut mieux attendre:
agent = AgentTétuAvecInit(N_basket=3, N_foot=3)
agent.plot();
Alors que si on observe un ballon de foot, il vaut mieux parier:
agent = AgentTétuAvecInit(N_basket=4, N_foot=2)
agent.plot();
En bref, notre nouvel agent permet de prendre une décision:
gains = agent.test()
gain_moyen = gains.mean(axis=1)
print('Gain si on parie:', gain_moyen[0], 'Gain moyen max si on attend :', gain_moyen[1:].max(), )
print('Should I stay? ', gain_moyen[0]<gain_moyen[1:].max(), ' or should I go? ', gain_moyen[0]>gain_moyen[1:].max() )
Dans ce cas particulier, il faut donc parier!
On peut obtenir cette décision via l'objet avec la fonction razor:
N_basket = 3
N_foot = 5
décision = AgentTétuAvecInit(N_basket=N_basket, N_foot=N_foot, verbose=False).razor()
print('Pour N_basket=', N_basket, ', N_foot= ', N_foot, ' Parier = ', décision)
Finalement, on obtient une grille des stratégies optimales:
N_ballons = 8
go = np.zeros((N_ballons//2+1, N_ballons//2+1))*np.nan
go[0, :] = 1 # quand il n'y a plus de ballons, l'information est certaine
go[:, 0] = 1
for N_basket in range(1, N_ballons//2 + 1):
for N_foot in range(1, N_ballons//2 + 1):
go[N_basket, N_foot] = AgentTétuAvecInit(N_basket=N_basket, N_foot=N_foot, verbose=False, N_test=None).razor()
go
fig, ax = plt.subplots(figsize=(figsize[0], figsize[0]))
ax.matshow(go)
ax.set_xlabel(' # ballons foot ')
ax.set_ylabel(' # ballons basket ');
La figure se lit comme suit: sur un axe, on a le nombre de foot restant, sur l'autre axe le nombre de ballons de basket restant. Notre jeu commence donc en bas à droite et on peu considérer chaque instance du jeu (toutes les combinaisons possibles) comme des trajectoires partant du point initial et en se déplaçant soit d'un pas vers la gauche, soit d'un pas vers le haut. Notre agent nous a montré une stratégie optimale donnée par la couleur des cases: si elle est bleue, on attend, si on touche une jaune, il faut parier (pour la direction correspondant bien sûr au plus probable, c'est-à-dire pour lequel le nombre de ballons restant est supérieur).
La stratégie de cet agent peut donc se résumer exactement par ce graphe: il faut parier quand l'écart en nombres de ballons est supérieur au quart du nombre total de ballons restant.
En mathématiques, un tel résultat peut être considéré comme un théorème: il permet de donner une stratégie simple (une heuristique) qui a été prouvée sur l'ensemble de tous les cas possibles.
N_ballons = 8
go = np.zeros((N_ballons//2+1, N_ballons//2+1))
go[0, :] = 1 # quand il n'y a plus de ballons, l'information est certaine
go[:, 0] = 1
for N_basket in range(1, N_ballons//2 + 1):
for N_foot in range(1, N_ballons//2 + 1):
if np.abs(N_basket - N_foot) > (N_basket + N_foot)/4:
go[N_basket, N_foot] = 1
go
à noter que le cas $(N_{basket}=3, N_{foot}=2)$ (ou symétriquement $(N_{basket}=2, N_{foot}=3)$) est indécis: on peut aussi bien passer que parier.
AgentTétuAvecInit(N_basket=3, N_foot=2, N_test=None).plot();
on remarque aussi que le choix d'attendre de 2 tours est environ 2 fois moins indécis. C'est un point que l'on a pas pris en compte dans notre critère (gagner le plus en moyenne) mais qui pourrait être pris en compte par exemple si on exprime le désir de pas avoir perdu de l'argent au bout d'un certain temps avec un certain taux de confiance. Mais c'est l'objet d'un étude plus poussée... mais très intéressante quand on sait que l'aversion au risque peut varier d'une personne à l'autre.
C'est une symétrie que nous avons aussi observé pour le jeu avec $N_{ballons}=6$ ou $N_{ballons}=10$ et qu'il serait utile d'étudier si on veut étudier l'aversion au risque d'un joueur.
un "meta-agent"¶
Intéressons-nous plutôt à construire un agent qui va utiliser l'agent tétu (mais simplement sur l'ensemble des combinaisons pour gagner du temps de calcul) pour décider ce qu'il faut faire à chaque tour dans chaque jeu. À noter qu'on aurait pu aussi utiliser notre "théorème", mais cet agent reste plus général:
N_test = 2**13
N_test_agent = None
class MetaAgent:
def __init__(self, N_test=N_test, N_test_agent=N_test_agent, N_basket=4, N_foot=4, verbose=True):
self.N_test = N_test
self.N_test_agent = N_test_agent
self.N_basket = N_basket
self.N_foot = N_foot
self.N_ballons = N_basket + N_foot
self.verbose = verbose
def generate_test(self):
return generate_test(N_ballons=self.N_ballons, N_basket=self.N_basket, N_test=self.N_test)
def meta_agent(self, tests):
gains = np.zeros(tests.shape[0])
for i_test in range(tests.shape[0]):
for N_ballons_vus in range(self.N_ballons):
N_basket = self.N_basket - sum(tests[i_test, :(N_ballons_vus)]==1)
N_foot = self.N_foot - sum(tests[i_test, :(N_ballons_vus)]==0)
N_ballons_restant = self.N_ballons - N_ballons_vus
assert(N_foot+N_basket == N_ballons_restant)
if N_basket==0 or N_foot==0 :
break
elif AgentTétuAvecInit(N_basket=N_basket, N_foot=N_foot, verbose=False, N_test=self.N_test_agent).razor():
break
proba_True_restant = N_basket / N_ballons_restant
if proba_True_restant==.5:
if self.N_test is None:
gains[i_test] = 0.
else:
choix = np.random.rand() > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*2 - 1)
else:
choix = proba_True_restant > .5
réussite = (tests[i_test, N_ballons_vus] == choix)
gain_esperé = N_ballons_restant - 1
gains[i_test] = gain_esperé * (réussite*2 - 1)
return gains
def test(self):
tests = self.generate_test()
gains = self.meta_agent(tests)
if self.verbose: print('Moyenne des gains =', np.mean(gains),
' +/- ', np.std(gains) )
return gains
agent = AgentTétuAvecInit(N_test=N_test, N_basket=4, N_foot=4, verbose=True)
gains = agent.test()
gains_cumulés = np.cumsum(gains, axis=1)
agent = MetaAgent(N_test=N_test, N_basket=4, N_foot=4, verbose=True)
meta_gains = agent.test()
Au final, notre nouvel agent se révèle être plus performant que l'agent naïf...
fig, ax = plt.subplots(figsize=figsize)
for N_ballons_vus in range(agent.N_ballons):
label = '%d ballons vu' % N_ballons_vus
if N_ballons_vus>1: label += 's '
ax.plot(gains_cumulés[N_ballons_vus, :], alpha=0.9, label=label)
ax.plot(np.cumsum(meta_gains), alpha=1., label='meta-agent')
ax.set_xlabel(' # essais ')
ax.set_ylabel(' gain cumulé ')
ax.legend();
... mais est-ce l'agent vraiment optimal? Peut-on créer un meta-meta-agent? La question reste ouverte :-)