Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Valeurs cachées

Amis des probabilités et des espérances de gain, bonjour.

Un joueur a devant lui une grille $n\times n$ contenant des valeurs entières de 1 à $n^2$, aléatoirement disposées et toutes cachées. Il a le droit de révéler de 1 à $n$ cases, étant entendu que son gain correspondra à la valeur de la dernière case qu’il aura dévoilée. Y a-t-il des stratégies particulières et si oui, que permettent-elles en terme de gain ?

Pour $n$ = 5 (valeurs de 1 à 25 et cinq cases à ouvrir au maximum) j’arrive à une espérance de gain de 20,192 mais est-ce l’optimum ?

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Valeurs cachées

Bonjour

Le joueur regarde-t-il le numéro tiré après chaque tirage?

Merci

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Valeurs cachées

Hello,

Oui, chaque fois qu’il dévoile une case il sait la valeur de celle-ci. Il peut décider de s’arrêter là et d’empocher, ou au contraire de continuer, sachant qu’à la $n$-ième il n’aura plus le choix et devra se contenter de la valeur de cette dernière.

Pour $n=2$ ce n’est pas très difficile. Au moment où il dévoile la première case, il sait. Si part exemple il tombe sur un $4$, c’est la plus grande valeur du panel (puisqu’il sait que ce sont les valeurs de $1$ à $n^{2}$ qui sont cachées) et donc il s’arrête. S’il tombe sur un $1$ il continue bien sûr, il sait qu’il fera toujours mieux. La stratégie qu’il adopte fait qu’avec un $2$ il continue puisqu’il reste $1$, $3$ et $4$ et donc qu’il a deux chances sur trois de faire mieux (espérance $\dfrac{\left( 1+3+4\right) }{3}=\dfrac{8}{3}>2$), alors qu’avec un $3$ il reste puisque cette fois son espérance est inférieure, à savoir $\dfrac{\left( 1+2+4\right) }{3}=\dfrac{7}{3}<3$.

Avec cette stratégie, l’espérance de gain du jeu $n=2$ est égale à $\dfrac{\left( \dfrac{\left( 2+3+4\right) }{3}+\dfrac{\left( 1+3+4\right) }{3}+3+4\right)}{4}=\dfrac{19}{6}$.

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 801

Re : Valeurs cachées

Bonjour,

Je n'ai pas fait les calculs précis mais, avec $n=5$, j'aurai envie de dire qu'après la première case, on s'arrête si celle-ci est supérieure à 20, sinon on continue. Dans ce cas, on s'arrête après la seconde case si cette dernière est supérieure à 15, puis après la troisième si elle est supérieure à 10, et enfin après la quatrième si elle est supérieure à 5.

Ainsi, je pense qu'on est proche de la valeur annoncée par Ernst :

j’arrive à une espérance de gain de 20,192

mais je n'ai aucune idée de la question de l'optimalité...

Ma question : est ce plus ou moins ce que tu as suivi comme idée Ernst ?

Roro.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Valeurs cachées

Bonjour,

Pour n=5 je trouve qu'on peut s'arrêter au premier tirage à partir de 13.
A partir d'arbres ( noeud racine = premier tirage pour chacun etc ) on doit s'en sortir informatiquement, en stoppant pour un arbre donné et une branche donnée lorsque la valeur obtenue dépasse toutes les espérances de gains ultérieures.
La somme la plus extérieure pour calculer l'espérance de gain est celle sur tous les arbres concernés.
Avec n=3 ça fait déjà pas mal de calculs si on fait à la main.

Bonne soirée
A.

Dernière modification par bridgslam (30-06-2025 17:20:51)

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Valeurs cachées

Bonjour,

Je n'ai pas fait les calculs précis mais, avec $n=5$, j'aurai envie de dire qu'après la première case, on s'arrête si celle-ci est supérieure à 20, sinon on continue. Dans ce cas, on s'arrête après la seconde case si cette dernière est supérieure à 15, puis après la troisième si elle est supérieure à 10, et enfin après la quatrième si elle est supérieure à 5.

Ainsi, je pense qu'on est proche de la valeur annoncée par Ernst :

j’arrive à une espérance de gain de 20,192

mais je n'ai aucune idée de la question de l'optimalité...

Ma question : est ce plus ou moins ce que tu as suivi comme idée Ernst ?

Roro.

Hello,

Oui, c'est bien ça, et effectivement ta stratégie est très proche avec 19.33… Pour l’idée que je m’en fais, au début on garde l’espoir de tomber sur des valeurs hautes et donc on laisse passer les basses et les moyennes, et plus on avance plus il faut réduire ses exigences. (les seuils que j'ai retenus sont 19, 18, 17 et 14)

Pour déduire ces seuils d’une part je fais des tirages aléatoires (je mélange les n² valeurs et je prends les n premières), d’autre part je détermine une stratégie en choisissant la valeur de ces seuils au hasard. J’applique cette stratégie à un tirage précis, et le gain obtenu est ensuite attribué aux seuils s’il est plus important. Comme cela va très vite, je teste des milliers et des milliers de stratégies différentes avec ce même tirage, puis je change de tirage et je recommence, encore et encore. Avec 100 000 tirages et 10 000 stratégies par tirage, j’obtiens un milliard de simulations en moins de dix secondes, et les valeurs stabilisées restent ensuite les mêmes.

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Valeurs cachées

Avec n=3 ça fait déjà pas mal de calculs si on fait à la main.

Oui, cela devient tellement touffu avec de grands $n$ que j’ai préféré estimer à partir de tirages aléatoires - une forme de sélection darwinienne si on veut - plutôt que me lancer dans le calcul.

Le problème, c’est que chaque branche de l’arborescence a des espérances de gain différentes au fil des cases découvertes. Perso j’établis des seuils pour chaque étape, à telle valeur je continue et à telle autre je conserve, mais c’est assez bourrin vu que ces seuils sont préfixés et ne tiennent pas compte de l’obtention des cases précédentes. Logique de penser qu’un 7, 3 et 2 déjà découverts laissent bien plus de valeurs hautes à la quatrième étape qu’un 13, 15 et 12 par exemple. Faudrait donc le faire en temps réel à la volée.

En fait à force d’y penser, je me rends compte que c’est un peu comme le black jack au casino, la banque applique un algorithme public qui garde un avantage sur n’importe quelle méthode pré-calculée, mais reste inférieur à des mises tenant compte des cartes restant dans le talon. Ici même chose, ma stratégie au doigt mouillé est sans doute satisfaisante comme base, mais peut très certainement être améliorée de façon dynamique.

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Valeurs cachées

Amis des probabilités et des espérances de gain, bonjour.

C'est bon, problème résolu. D'une part en pratique j'ai fait un programme qui détaille toute l'arborescence, j'ai donc l'espérance de gain exacte (pour $n=5$ c'est 20,2056) et d'autre part j'ai trouvé la formule théorique, suffit de l'appliquer aux $n^2$ pour se rapprocher de plus en plus de ces valeurs.

Tirage d’un nombre aléatoire entre [0..1], espérance de gain 0,5.
Seuil $x$ à 0,5 et deuxième tirage si inférieur, moyenne de l’espérance [0,5..1] et de l’espérance [0..1] égale à 0,625.
Ici seuil $x$ = 0,5 optimum puisque la moyenne des espérances est le polynôme $E(x) = \frac{1 - x^2 + x}{2}$ et que sa dérivée s’annule en 0,5.
Formule récursive complète :
\[ \left\{ \begin{array}{l} E_1 = \dfrac{1}{2} \\[2ex] E_n = E_{n-1}^2 + \dfrac{1}{2}(1 - E_{n-1}^2) \end{array} \right. \]
On notera que pour $n$ tirages, l'espérance est donnée par $E_n$ et le seuil par $E_{n-1}$