Un problème issu du mastermind

[Patastronch]

Ca m'intéresse tout ça.
Je vais programmer la stratégie naïve que je présente pour voir son taux de réussite. On pourra comparer.

Le programme de mon coté est déjà fait Par contre la modélisation va etre assez penible, va falloir calculer une formule qui renvoie la distribution de proba sur les 9 indications (de type X a la bonne place et Y a la mauvaise place) possible qu'on peut avoir sachant un historique d'indication. Je me pencherais dessus les semaines a venir et si je trouve la formule miracle je la balancerais dans mon programme pour en déduire la meilleure stratégie à prendre et on pourra affronter nos 2 petits robots

[Patastronch]

Ben, une stratégie non gagnante et 100% prévisible n'est pas non plus une très bonne stratégie... Je pense que la stratégie probabiliste a un énorme trou ! Si vous n'utilisez pas le hasard quelque part, alors il y a aura plein des combinaisons que cette stratégie ne trouvera jamais en 3 coups.

Ben en gros utiliser les probas c 'est juste jouer au hasard une combinaison dans une sorte de dichotomie. Sauf qu'on s'arrange pour jouer au hasard dans la partie la plus favorable de cette pseudo dichotomie (c'est a dire jouer au hasard une combinaison appartenant à l'ensemble des combinaisons maximisant notre espérance de gain).

[leon1789]

Le programme de mon coté est déjà fait Par contre la modélisation va etre assez penible, va falloir calculer une formule qui renvoie la distribution de proba sur les 9 indications (de type X a la bonne place et Y a la mauvaise place) possible qu'on peut avoir sachant un historique d'indication. Je me pencherais dessus les semaines a venir et si je trouve la formule miracle je la balancerais dans mon programme pour en déduire la meilleure stratégie à prendre et on pourra affronter nos 2 petits robots

On est d'accord que cela demande un certain effort de préparation.
Mais pour le premier coup, il y a évidemment pleins de propositions possibles qui offrent les mêmes "espoirs". Sur quel critère vas-tu en sélectionner un particulier ?

EDIT : ok, nos messages se croisent, tu as répondu juste au-dessus

[Patastronch]

On est d'accord que cela demande un certain effort de préparation.
Mais pour le premier coup, il y a évidemment pleins de propositions possibles qui offrent les mêmes "espoirs". Sur quel critère vas-tu en sélectionner un particulier ?

Voir plus haut :p

[leon1789]

Voir plus haut :p

vi vi :++:

[leon1789]

Ben en gros utiliser les probas c 'est juste jouer au hasard une combinaison dans une sorte de dichotomie. Sauf qu'on s'arrange pour jouer au hasard dans la partie la plus favorable de cette pseudo dichotomie (c'est a dire jouer au hasard une combinaison appartenant à l'ensemble des combinaisons maximisant notre espérance de gain).

ok, normal.

Maintenant, peut-on imaginer pouvoir choisir un secret tel qu'il ne soit jamais dans le tas le plus favorable ? (au troisième coup, tout au moins)

[Imod]

La technique déterministe ( poussée à son extrème ) proposerait 111 comme solution au premier essai et je crains pour la suite ...

Imod

[leon1789]

La technique déterministe ( poussée à son extrème ) proposerait 111 comme solution au premier essai et je crains pour la suite ...

Imod

pourquoi ? on pourrait commencer le comptage à 123 ...

Qu'entends-tu pas LA technique déterministe ?

[Patastronch]

ok, normal.

Maintenant, peut-on imaginer pouvoir choisir un secret tel qu'il ne soit jamais dans le tas le plus favorable ? (au troisième coup, tout au moins)

Pas a priori, mais a posteriori (cad selon notre première proposition) on a pu tomber dans le pire cas sans le savoir. Mais comme toutes les proposition de départ se valent (1/720 d'être la bonne avec des futurs similaires) et qu'on va jouer notre premier coup au hasard, il est donc pas possible d'anticiper une combinaison perverse avant que la première proposition de combinaison ait été faite.

[leon1789]

Pas a priori, mais a posteriori (cad selon notre première proposition) on a pu tomber dans le pire cas sans le savoir. Mais comme toutes les proposition de départ se valent (1/720 d'être la bonne avec des futurs similaires) et qu'on va jouer notre premier coup au hasard, il est donc pas possible d'anticiper une combinaison perverse avant que la première proposition de combinaison ait été faite.

oui au début, c'est du 1/720 . Mais tu ne comptes pas gagner au premier coup quand même

En fait, sans doublon, tous les secrets ont la même chance d'être trouvés (après autant de coups que l'on veut, fixé à l'avance, comme 3 par exemple) puisque rien ne différencie 123 de 456 ou de 789...

Avec les doublons, ce serait différent.

[Patastronch]

oui au début, c'est du 1/720 . Mais tu ne comptes pas gagner au premier coup quand même

En fait, sans doublon, tous les secrets ont la même chance d'être trouvés puisque rien ne différencie 123 de 456 ou de 789...

Oui c'est exactement la raison pour laquelle il n'y a pas de combinaisons secrètes perverses à priori si notre premier coup est aléatoire.

[leon1789]

Oui c'est exactement la raison pour laquelle il n'y a pas de combinaisons secrètes perverses à priori si notre premier coup est aléatoire.

Mais alors est-ce que les "ensembles dichotomiques" ne seront pas tous de même cardinal la plupart du temps ?

[Patastronch]

Mais alors est-ce que les "ensembles dichotomiques" ne seront pas tous de même cardinal la plupart du temps ?

Non, car selon les indications recues apres notre premiere essai, certaines combinaisons deviennent alors plus "probable" ou vont permettre de rendre tres probable la proposition au troisième coup.

Par exemple si tu en a 2 a la bonne place des le premier coup, on voit tout de suite que certaines stratégies vont dès lors être plus payantes que les autres, chose qu'une stratégie hasardeuse jusqu'au bout ne prendrait pas en compte (voila l'intérêt d'user une heuristique au passage !).

De même le cas ou j'aurais rien a la bonne place et rien a la mauvaise place, je peux des lors jouer avec que 7 couleurs pour la suite. En fait chaque indication va déséquilibrer ces "pseudos dichotomies". (au passage ces pseudos dichotomie ne sont rien d'autre que des classes de distribution de probabilités sur un support fini, l'espérance de ces distribution est l'heuristique la plus intuitive lorsqu'on chercher a maximiser ses chances, mais de grands débats se posent dans les cas de jeux non répétés à l'infini et on préfère alors appliquer d'autres critère de discrimination, je peux te filer un de mes articles si ca t'interesse :p)

[nuage]

Salut,
j'ai l'impression que vous avez considérablement dérivé par rapport à la question de départ :

Bjr,

il y a un client qui m'a appelé pour le problème suivant:


c'est un problème de mastermind posé en concours d'entrée en école d'infirmière:

il y a une solution de mastermind inconnue, exemple le triplet (1,3,5).


on présente la matrice "logique" 3 \times 3, accompagnée des réponses
156 un chiffre à la bonne place,un chiffre à la mauvaise place
234 un chiffre à la bonne place
691 un chiffre à la mauvaise place


la question est:

déterminer un algorithme qui donne la solution (en trois coups donc)
ou des heuristiques qui donnent la réponse dans des cas particuliers.

En fait dans ce type de question on sait qu'il existe une solution unique. Ce qui réduit considérablement l'univers des possibles.

Et il y a des heuristiques qui permettent de trouver assez vite la solution.
Pour réussir les concours d'entré en IFSI il vaut mieux que la solution soit trouvé en moins d'une minute.
C'est très diffèrent du problème que vous semblez chercher à résoudre.

Pour l'heuristique de résolution, on cherche ce qui implique le maximum de contrainte.
Sur l'exemple ça donne :
Entre les lignes 1 et 3 on a le 5 dans la combinaison.
Il ne peut pas être bien placé, sinon 1 ou 6 serais bien place en ligne 1 ou 3.
Et je crois que l'on peut s'arrêter là.
Il ne s'agit pas d'un pb posé aux concours.

[leon1789]

Avec la stratégie probabiliste, le dernier coup est aléatoire parmi les combinaisons compatibles avec les deux réponses précédentes.

Si on joue sans doublon, il y a équivalence entre tous les premiers coups, donc on peut commencer au hasard.

Finalement, tout se joue sur le second coup : c'est peu pour faire la différence entre plusieurs stratégies !!

Non, car selon les indications recues apres notre premiere essai, certaines combinaisons deviennent alors plus "probable" ou vont permettre de rendre tres probable la proposition au troisième coup.

>, tu es optimiste :id:
Bon, certes, on va pouvoir augmenter le pourcentage de gain, mais de combien ? ...

Par exemple si tu en a 2 a la bonne place des le premier coup,

ok.
(mais là, la situation est peu probable)

De même le cas ou j'aurais rien a la bonne place et rien a la mauvaise place, je peux des lors jouer avec que 7 couleurs pour la suite.

là, toujours sans doublons, jouer au hasard un second coup compatible avec les 7 couleurs est pareil que tout (cf le premier coup). Donc là, au final, aucune différence avec ma stratégie naïve.

[Patastronch]

là, toujours sans doublons, jouer au hasard un second coup compatible avec les 7 couleurs est pareil que tout (cf le premier coup). Donc là, au final, aucune différence avec ma stratégie naïve.

Tu n'applique donc deja plus une stratégie naive, jouer uniquement avec les couleurs possible est deja une heuristique ! Mais je pense sincerement que maximiser l'espérance de victoire est la meilleure si on joue un grand nombre de parties.

Et puisque tu sembles convaincu que la stratégie aléatoire semble etre tres bonne, je te propose de faire jouer 10000 parties a nos petits robots et de parier sur leurs victoire :p

Sinon en effet on dévie du sujet initial. La on traite un cas général, mais l'énnoncé c 'est sachant les 3 premieres propositions que l'on nous donne avec leurs indication quelle stratégie appliquer pour trouver en 3 coups sur (donc en 6) la solution finales Ce qui est pas bien sorcier :

On a :
156 un chiffre à la bonne place,un chiffre à la mauvaise place
234 un chiffre à la bonne place
691 un chiffre à la mauvaise place

On déduit deja qu'on a un 6 ou un 1 dans la combinaison, un 5 et un parmi {2,3,4}.
En fait (sauf erreur) on a que 4 possiblités : 135,251, 536 et 654

On propose 536.
4 cas possible donc (N pour le nombre de bien placés et B pour le nombre de présent dans la combinaison gagnante mais mal placé):

1/ indications : (1N;1B). La solution gagnante est donc 135
2/ indications : (0N;1B). La solution gagnante est donc 251
3/ indications : (3N;0B). On a gagné !
4/ indications : (0N;2B). La solution gagnante est donc 654

[busard_des_roseaux]

Salut,
j'ai l'impression que vous avez considérablement dérivé par rapport à la question de départ :

oui. La question était sérieuse (concours d'infirmière). Il ne s'agit pas de programmer un automate qui joue au mastermind.
c plus simple. La matrice est imposée ,avec les réponses et il faut déterminer alors la solution unique.

Il s'agit plutôt d'analyser une partie qui se termine avec succès en trois coup.

[leon1789]

Tu n'applique donc deja plus une stratégie naive, jouer uniquement avec les couleurs possible est deja une heuristique !

Je n'ai jamais dit que je jouais totalement au hasard !

une bonne logique ? ben, proposer des triplets aléatoires mais conformes aux réponses précédentes ...

Mais je pense sincerement que maximiser l'espérance de victoire est la meilleure si on joue un grand nombre de parties.

Certes cela ne peut pas être moins bon (sauf au niveau du nombre de calculs), mais de combien est-ce meilleur ? Dans quels cas est-ce nettement meilleur ? Deux chiffres bien placés dès le début ?...

Et puisque tu sembles convaincu que la stratégie aléatoire semble etre tres bonne, je te propose de faire jouer 10000 parties a nos petits robots et de parier sur leurs victoire :p

Il est clair qu'une stratégie sans aléatoire est nulle.

La stratégie probabiliste que tu proposes ne se différencie que sur la seconde
proposition par rapport à la mienne. Il me paraît intéressant de mesurer l'impact d'un choix "réfléchi" (avec les probas) par rapport à la stratégie "naïve".

Pour cela, il faut faire plusieurs genres de test (10000 ne me paraissent pas suffisant, mais c'est pas grave, on peut augmenter, c'est l'ordi qui calcule ) :
-- tirer des secrets au hasard
-- partir d'une première réponse fixée : il y a 9 réponses possibles
On pourra ainsi constater où la stratégie probabiliste apporte le plus par rapport à la stratégie naïve.
Je crois que sera intéressant/amusant, non ?

Sinon en effet on dévie du sujet initial. La on traite un cas général, mais l'énoncé c 'est sachant les 3 premieres propositions que l'on nous donne avec leurs indication quelle stratégie appliquer pour trouver en 3 coups sur (donc en 6) la solution finales Ce qui est pas bien sorcier :

Je n'avais pas compris ça.
Maintenant, ça ressemble au vrai mastermind avec un gain peut-être quasi-assuré en moins de 3+3 coups, même avec la stratégie naïve...

Avec 3 coups fixés, la meilleure stratégie est sans aléatoire.

Je me penche sur le petit programme qui pourra jouer avec/sans doublons, avec N coups imposés initialement... Dès que j'ai des stats, je les donne, ça donnera une idée du minimum. (qui à mon avis, ne sera pas loin d'être le maximum dans le cas sans doublon avec N=0 )

[leon1789]

oui. La question était sérieuse (concours d'infirmière). Il ne s'agit pas de programmer un automate qui joue au mastermind.

ha... :triste:

c plus simple. La matrice est imposée ,avec les réponses et il faut déterminer alors la solution unique.

Il s'agit plutôt d'analyser une partie qui se termine avec succès en trois coup.

Je ne comprends toujours pas : pour deviner le secret, on a le droit de poser des questions ou pas ?

[busard_des_roseaux]

ha... :triste:


Je ne comprends toujours pas : pour deviner le secret, on a le droit de poser des questions ou pas ?

ben non. Il y a trois questions imposées, sous forme d'une matrice donnée en hypothèse, avec les réponses.

Il faut trouver la solution.

par exemple, je donne la matrice

123
324
435

avec les réponses et il faut trouver la solution. Est-ce qu'il y a une méthode ? ça doit être de l'algèbre de Boole,non ? je ne vois pas ce que viennent faire les probas içi.