Le jeu du plus ou moins est un jeu consistant à choisir un nombre entre 1 et 100 et à le faire deviner à une tierce personne. Penchons-nous sur son implémentation en Python.

Jeu du plus ou moins: les règles

Les règles

Le maître du jeu choisit un nombre entier compris entre 1 et 100: c’est le nombre mystère. Il y a donc 100 nombres possibles.

Le joueur propose un nombre: si le nombre mystère est plus grand que la proposition, le maître du jeu répond : « plus », sinon, il répond « moins ».

Le but du jeu est de deviner le nombre mystère en un minimum de coups.

Un exemple d’implémentation en Python

Voici une proposition de programme:

from random import randint

def jeu():
    x = randint(1,100)
    n = 0
    coups = 0
    while x != n:
        n = int( input('Votre proposition: ') )
        coups += 1
        if x < n: print("\033[92m C'est moins.\033[0m")
        elif x > n: print("\033[93m C'est plus.\033[0m")
        else: print(f"\033[91m Gagné en {coups} coups.\033[0m")

Jeu du plus ou moins: une stratégie mathématique

La stratégie: la dichotomie

Il existe une manière de minimiser le nombres de propositions quand on joue à ce jeu.

En effet, si on propose au hasard, sans stratégie, n’importe quels nombres, cela risque d’être long. C’est pourquoi avoir une stratégie s’impose. Ici, nous allons raisonner par dichotomie.

Cela consiste, à chaque étape, à choisir le milieu de l’intervalle où se trouve le nombre.

Un exemple

Supposons que le maître du jeu choisisse le nombre 23.

• On commence par le milieu de l’intervalle [1;100] : 50. Le maître du jeu répond alors : « moins » car 23 < 50.
• On sait maintenant que le nombre mystère est dans l’intervalle [1 ; 50[; on choisit donc son milieu: 25. Le maître du jeu réponds « moins ».
• Le nombre doit donc être dans [1 ; 25[; on choisit le « milieu », tout du moins la partie entière du milieu, soit 12. Le maître du jeu réponds: « plus ».
• Maintenant, on sait que le nombre à deviner est dans ]12 ; 25[; on choisit la partie entière du milieu, soit \(E\left(\frac{12+25}{2}\right)=18\) . Le maître du jeu répond alors : « plus ».
• On choisit alors la partie entière du milieu de ]18;25[, à savoir \(E\left(\frac{18+25}{2}\right)=21\). « c’est plus ».
• Le nombre mystère est donc dans ]21;25[; on propose alors 23, le milieu de cet intervalle… et on gagne!

Implémentation en Python

Nous allons demander à l’ordinateur de choisir un nombre compris entre 1 et 100; nous allons le stocker dans la variable x et nous allons créer une variable « coups » pour compter le nombre de propositions.

from random import randint
x = randint(1,100)
coups = 0

Nous allons maintenant demander à l’ordinateur de simuler les propositions.

n = 0
a, b = 1, 100
while n != x:
    coups += 1
    n = (a+b)//2
    if x > n: a = n
    if x < n: b = n
    print( n )

Cette proposition n’est pas encore optimale car si x = 100, le programme bloque sur « 99 »… et pour cause: \( E\left(\frac{99+100}{2}\right)=99.\)

Il faut donc distinguer le cas où n = a et celui où n est différent de a.

n = 0
a, b = 1, 100
while n != x:
    coups += 1
    n = (a+b)//2
    if x > n:
        if n != a: a = n
        else: n = b
    elif x < n: b = n
    print( f'a={a}, b={b}, n={n}, coups = {coups}' )

a=1, b=50, n=50, coups = 1
a=1, b=25, n=25, coups = 2
a=1, b=13, n=13, coups = 3
a=7, b=13, n=7, coups = 4
a=10, b=13, n=10, coups = 5
a=10, b=13, n=11, coups = 6

Aller plus loin

J’ai implémenter une fonction game(a,b) qui retourne le nombre de coups nécessaires pour trouver le nombre aléatoirement choisi entre deux entiers a et b en utilisant la dichotomie. Ensuite, j’ai effectué 10000 simulations, puis ai calculé la moyenne des coups nécessaires. J’ai fait cela pour a = 1 et pour \(b = 10^n\), avec n variant de 1 à 10. Voici les résultats:

Une belle corrélation linéaire s’offre à nous.

from random import randint
from matplotlib.pyplot import axes, scatter, show, plot, legend, xlabel, ylabel, title

def jeu():
    x = randint(1,100)
    n = 0
    coups = 0
    while x != n:
        n = int( input('Votre proposition: ') )
        coups += 1
        if x < n: print("\033[92m C'est moins.\033[0m")
        elif x > n: print("\033[93m C'est plus.\033[0m")
        else: print(f"\033[91m Gagné en {coups} coups.\033[0m")


def game(a,b):
    x = randint(a,b)
    coups = 0
    n = 0

    while n != x:
        coups += 1
        n = (a+b)//2
        if x > n:
            if n != a: a = n
            else: n = b
        elif x < n: b = n
        
    return coups

x, y = [],[]

for e in range(1,11):
    S = 0
    for _ in range(10000):
        S += game(1,10**e)
    x.append(e)
    y.append(S/10000)
    print( f'e = {e} , moyenne = {S / 10000}' )
    

repere = axes()
repere.grid() # dessiner une grille pour une meilleur lisibilité du graphe
scatter(x,y)
show()

Calculs mathématiques

Notons X la variable aléatoire représentant le nombre de coups nécessaires pour gagner avec la stratégie de la dichotomie.

Alors, X = {1;2;3;4;5;6;7;8}.

• \( P(X = 1) = \frac{1}{100}\) : c’est le cas où le nombre mystère est 50; il y a bien 1 chance sur 100 de le choisir.
• \( P(X = 2) = \frac{2}{100}\) : c’est le cas où le nombre mystère est 25 ou 75.
• \( P(X = 3) = \frac{4}{100}\) : c’est le cas si x = 12 ou 37 ou 62 ou 87.
• \( P(X = 4) = \frac{8}{100}\): c’est le cas si x = 6, 18, 31, 43, 56, 68, 81 ou 93.
• \( P(X = 5) = \frac{16}{100}: c’est le cas pour x = 3, 9, 15, 21, 28, 34, 40, 46, 53, 59, 65, 71, 78, 84, 90, 96.
• \( P(X = 6) = \frac{32}{100}\): c’est le cas pour x = 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 85, 88, 91, 94, 98.
• \( P(X = 7) = \frac{36}{100} \): c’est le cas pour x = 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 86, 89, 92, 95, 97, 99.
• \(P(X = 8) = \frac{1}{100}\) pour x = 100.

On peut donc établir la loi de probabilité de X:

L’espérance mathématique de X est donc:$$E(X)=0,01+2\times0,02+3\times0,04+\cdots+8\times0,01=5,81.$$Cette valeur correspond bien à notre simulation.