Ajax's Home

Un précédent article porte sur la théorie des jeux. Il nous permet d’obtenir des stratégies optimales pour un grand nombre de jeux.

Je vous propose ici d’autres résultats, concernant des jeux dont le gain dépend directement du moment où le joueur s’arrête.

Le premier jeu présenté sera un lancé de dés. Le principe est le suivant : le joueur lance un premier dé, il peut choisir de s’arrêter. Si il s’arrête, il gagne en euros le score du dé. C’est à dire que si il fait un 6 et qu’il choisi de s’arrêter, il gagne 6 €. Il peut aussi choisir de continuer, donc de lancer un deuxième dé, et de nouveau, il a la possibilité de s’arrêter. Si il le fait, il gagne le score du second dé, et ainsi de suite.
Il a le droit à 6 lancés de dé, sachant qu’au bout du 6ème il est obligé de s’arrêter ( et donc de gagner en euros ce qui est indiqué sur le dé ).

Quelle est la stratégie optimale à ce jeu ?

En effet, il est certain que si j’obtiens un 6 à n’importe quel lancé, je m’arrête ( Je ne pourrais pas obtenir mieux que 6€ de gain ). Mais qu’en est-il si j’obtiens un 4 à mon premier lancer ? ou un 3 à l’avant dernier lancer ?

Eh bien, pour ce genre de situation/jeu , un outil va nous permettre de déterminer la stratégie à adopter ( c’est à dire que faire à chaque lancer si on souhaite une espérance mathématique du gain maximale ). J’ai nommé la récurrence à rebours.

Le principe est le suivant : Nous allons partir du dernier lancé, regarder la stratégie optimale, puis revenir à l’avant-dernier lancé, faire de même, etc .. jusqu’au premier lancé. Et donc en tiré la stratégie à adopter sur tout le jeu. Mais appliquons cette méthode à notre problème de lancé de dé, ce sera plus clair.

Tout d’abord, si nous n’avions qu’un seul dé, l’espérance mathématique serait de 3,5 €  ( 1/6 * 1 + 1/6 * 2 + 1/6 * 3 + 1/6 * 4 + 1/6 * 5 + 1/6 * 6 = 3,5 ). Donc sur le dernier lancé, nous pouvons espéré gagné 3,5€ .

Ainsi, sur l’avant-dernier lancé, nous savons que nous pouvons gagné 3,5€ avec le dernier lancé. Donc si nous faisons moi que 3,5 ( 1, 2 ou 3 ) nous attendrons le dernier lancé ; mais si nous faisons plus, c’est à dire 4, 5 ou 6, nous nous arrêtons, car nous ne pouvons pas espéré théoriquement mieux . On en déduit alors la stratégie optimale pour l’avant-dernier lancé qui est de s’arrêter si on obtient un 4, 5 ou 6 et de continuer sinon.

L’espérance mathématique de l’avant-dernier lancé vaut alors : (3/6 * 3,5 + 1/6 * 4 + 1/6 * 5 + 1/6 * 6 = ) 4,25 . Avec le même raisonnement que ci-dessus, la stratégie optimale au 4ème lancé est de s’arrêter si on obtient un 5 ou un 6, et de continuer sinon.

En remontant ainsi jusqu’au premier lancé ( d’où le terme “rebours” ), la stratégie optimale ( au regard de l’espérance mathématique à chaque lancé ) est :

1,2,3,4 lancé : s’arrêter si 5,6 ; continuer sinon
5 lancé : s’arrêter si 4,5,6 ; continuer sinon
6 lancé : s’arrêter dans tout les cas

Je vais maintenant vous présentez un deuxième problème d’arrêt optimale.

Le jeu est le suivant : Vous avez devant vous 100 papiers avec chacun un numéro, face caché, placés au hasard .Vous ne connaissez pas l’intervalle dans lesquels ont été choisi les numéros. Vous retournez les billets un par un, en vous arrêtant sur celui que vous estimez contenir le nombre le plus élevé. Si vous ne vous arrêtez pas avant, vous êtes obligé de vous arrêter sur le 100ème.

Un exemple avec 10 billets ( au lieu de 100 ) : Vous retournez le premier billet : 55, le deuxième 130, le troisième 20, le quatrième 150. Vous décidez de vous arrêtez. Pas de chance, le 7ème billet était 562 et le 9ème était 2314. Il fallait s’arrêter sur le 9ème.

Il est clair qu’intuitivement, les chances de gagner à ce jeu sont très faibles. En faite, nous allons montrer que finalement, elle ne sont pas si faibles que ça, elles sont même supérieures à 1/3 !

Montrer n’est pas le terme exacte, puisque nous n’introduirons pas ici de démonstration rigoureuse.
Des recherches universitaires ont montrés que le meilleur pourcentage de victoire est de 1/e ( où e = exp(1) , donc 1/e environ égal à 0,3678 ).

La technique utilisée est la suivante : il faut retourner tout d’abord E(N/e) +1 cartes ( partie entière du nombre de cartes totale quotient de exp(1) ,  + 1 ). On regarde alors quelle est le plus grand nombre que l’on connais actuellement. On appelle ce nombre un “record”. Puis on retourne une par une les cartes, jusqu’à obtenir un nombre qui dépasse notre précédent record. On s’arrête alors.

Cette technique est la technique optimale, garantissant 1/e chances de gagner .

J’avoue que lorsque j’ai vu ce résultat, je n’y ai pas trop cru. Et en tout bon lecteur non niais que vous êtes, j’espère que c’est un peu la même chose pour vous. J’ai donc écrit un petit programme, pas très long, qui simule à la fois le jeu ainsi que la méthode décrite ci-dessus, comptant le nombre de fois qu’elle est gagnante. L’expérience étant renouvelé 10000 fois, afin d’avoir des résultats assez correct en terme de statistique ( loi des grands nombres ).

On obtient ( pour 5 lancements ) : 0,3684 ; 0,3700 ; 0,3729 ; 0,3605 ; 0,3747

Des résultats donc relativement ( 10 000 lancés, c’est peu ) très proche de ceux annoncés par la théorie.

Un résultat qui est donc intéressant à connaitre. A noter qu’un officier s’est fait beaucoup d’argent en pariant avec ses collègues sur l’issue d’un tel jeux. 1€ pour tout le monde en cas de perte, 10€ dans sa poche de la part de chacun en cas de victoire, donc une espérance mathématique de 3,038 € / partie ( Évidemment, il ne présentait pas le jeu comme ça à ses collègues ! ).

Pour finir, voici le programme en python utilisé pour simulé le dernier jeu :

from random import *

score,n,k = 0,10000.,0

while(k < n):

    #Simulation d'un seul jeu
    tab,amax = [],1

    for i in range(1,101): # Création des billets et détermination du nombre le plus grand
        a = randint(1,50000)
        if a > amax :
            amax = a
        tab.append(a)

    #application de la méthode
    imax = 0
    for i in range(1,38):
        if tab[i] > tab[imax] :
            imax = i

    j,act = 38,tab[38]

    while(act < tab[imax] and j<99):
        j = j+1
        act = tab[j]

    if(amax == act) : #vérification
        score = score + 1

    k=k+1
print score/n #on affiche le résultat pour n( = 10 000 ) parties jouées
input()

Référence : Pour la Science N°381

Cet article a été publié le Jeudi 6 août 2009 à 15 h 44 min et est classé dans En vrac. Vous pouvez en suivre les commentaires par le biais du flux RSS 2.0. Vous pouvez laisser un commentaire, ou faire un trackback depuis votre propre site.