Un problème issu du mastermind

[busard_des_roseaux]

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" , 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.


merçi d'avance.

[Doraki]

Il n'y a pas de stratégie pour toujours déterminer en 3 coups ne serait-ce que l'ensemble des chiffres présents dans la solution.
=/
Quant à une heuristique qui donne la réponse dans des cas particulier, je suis pas sur de comprendre ce qu'ils veulent.

[Imod]

Curieux ce 9 ! Les chiffres à deviner figurent parmi 1;2;3;4;5;6;7;8;9 ? Tolère-t-on les doublons du style 1123 ?

Imod

[leon1789]

Obtenir la solution en 3 coups, à coup sûr ! ...c'est impossible.
123 : aucun chiffre
456 : aucun chiffre
et maintenant, il reste plusieurs (dizaines de) possibilités.

[leon1789]

Curieux ce 9 ! Les chiffres à deviner figurent parmi 1;2;3;4;5;6;7;8;9 ? Tolère-t-on les doublons du style 1123 ?
Imod

en plus tu triches... non pas à cause du doublon, mais parce que toi, tu veux cacher 4 chiffres ! :ptdr:

[Imod]

Un simple décompte montre que c'est impossible :

Nombre de possibilités à 3 chiffres :
Nombre de triplets pour le codage des 3 essais :

Ca ne colle pas !

Imod

[busard_des_roseaux]

je précise si ce qui est demandé à l'examen:

1) le motif caché est un arrangement de 3 parmi 10.

2) ils proposent des exercices choisis pour avoir une solution et une seule.

3) les candidats doivent apprendre des heuristiques (c'est à dire des méthodes de résolution) qui marchent dans certains cas particuliers.

La question est:

pourriez vous m'en trouver ? (des heuristiques)

je vais essayer de transformer ces "booléens" en entiers naturels.
pour l'instant, c juste une vague idée, ou plutôt en calculs dans Z/2Z

merçi d'avance.

[Imod]

Les valeurs que j'ai fournies ne correspondent pas à grand-chose mais si j'ai bien compris les nouvelles données , le problème n'est pas là . Il s'agit plus de résoudre un exercice façon problème d'échec ou de bridge : la solution est unique , comment l'obtenir ? Il me semble qu'on attend pas un algorithme mais plutôt une bonne logique .

Imod

[leon1789]

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

[Imod]

Pour avoir travaillé sur le problème il y a quelques années je peux t'affirmer que ce n'est pas la meilleure stratégie .

Imod

[Patastronch]

Une bonne maximisation de l'espérance ca devrait faire une heuristique pas trop mal :)
Quand on propose une combinaison on peut mettre une loi de proba sur les indications qu'on va recevoir (bonne place ou pas, l'indication gagnante étant 3 a la bonne places), ainsi après des indication on va refaire une combinaison qui va nous donner une nouvelle distribution de probabilité et ainsi de suite jusqu'à qu'on trouve la bonne combinaison . Ainsi on peut évaluer la puissance d'un coup par son espérance de gains (cad proba de gagner en 1 coup * M-1 + proba de gagner en 2 coups * M-2 + ... ou M est le nombre de coup maximale pour gagner dans le pire cas, cette espérance renvoie donc le nombre M-a où a est la moyenne du nombre de coups nécessaire pour trouver la solution,, donc plus a est petit plus on a de chances de trouver vite) et il suffit alors de faire la combinaison maximisant cette espérance future à chaque fois qu'on doit proposer une combinaison.

P.S: En gros je propose d'appliquer l'éspérance d'utilité célèbre chez les économistes où la fonction d'utilité serait u(x)=M-x pour ce cas

[leon1789]

Pour avoir travaillé sur le problème il y a quelques années je peux t'affirmer que ce n'est pas la meilleure stratégie .
Imod

En tout cas, elle est simple à programmer, rapide, pas "anticipable",
et vu le faible taux de réussite auquel on s'attend quelle que soit la stratégie adoptée sur 3 coups, je ne suis pas certain qu'on voit une différence nette avec une stratégie basée sur des calculs probabilistes.

Il faudrait pour cela réaliser des milliers de parties pour comparer les scores de différentes stratégies... Moi, je veux bien m'occuper de celle que j'ai donnée !

P.S: En gros je propose d'appliquer l'éspérance d'utilité célèbre chez les économistes où la fonction d'utilité serait u(x)=M-x pour ce cas

Es-tu partant pour la programmer ?

[leon1789]

P.S: En gros je propose d'appliquer l'éspérance d'utilité célèbre chez les économistes où la fonction d'utilité serait u(x)=M-x pour ce cas

Es-tu partant pour la programmer ?

[leon1789]

1) le motif caché est un arrangement de 3 parmi 10.

Donc pas de doublon dans le secret, ok.

[Patastronch]

En tout cas, elle est simple à programmer, rapide, pas "anticipable",
et vu le faible taux de réussite auquel on s'attend quelle que soit la stratégie adoptée sur 3 coups, je ne suis pas certain qu'on voit une différence nette avec une stratégie basée sur des calculs probabilistes.

Il faudrait pour cela réaliser des milliers de parties pour comparer les scores de différentes stratégies... Moi, je veux bien m'occuper de celle que j'ai donnée !


Es-tu partant pour la programmer ?

Oui c'est justement une partie de ma thèse de travailler sur l'espérance d'utilité et j'étais en train de me dire que le mastermind était une bonne application !

[leon1789]

Oui c'est justement une partie de ma thèse de travailler sur l'espérance d'utilité et j'étais en train de me dire que le mastermind était une bonne application !

le mastermind classique, celui où on sait qu'on va finir par trouver, ok,
mais là ?

[Patastronch]

le mastermind classique, celui où on sait qu'on va finir par trouver, ok,
mais là ?

Le but d'une heuristique est de guider le choix attention, on est tous d'accord qu'en 3 coups c 'est pas possible mais l'énoncé demande de proposer une bonne heuristique le cas échéant si je ne m'abuse, et donc de maximiser la probabilité de gagner. Si on veut juste maximiser la proba de gagner en 3 coups il suffit de prendre M=3 et non au max du nombre de coups nécessaire pour gagner.

Apres on peut extraire de cette heuristique des cas particuliers favorable (donc des indications particuliere au 1er et 2 eme coup) qui permetrait de gagner à coup sur.

[Imod]

En tout cas, elle est simple à programmer, rapide, pas "anticipable",et vu le faible taux de réussite auquel on s'attend quelle que soit la stratégie adoptée sur 3 coups, je ne suis pas certain qu'on voit une différence nette avec une stratégie basée sur des calculs probabilistes.

Le programme que tu proposes je l'ai fait il y a 30 ans quand je hantais les couloirs de la fac de sciences de Tours , j'avais poussé l'exploit jusqu'à le faire fonctionner sur ma calculatrice ( à l'époque on comptait en octets ) . Un "robot" qui propose une solution "au pif" ce n'est pas ce que j'appelle
une stratégie :--:

Imod

[leon1789]

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.

[leon1789]

Un "robot" qui propose une solution "au pif" ce n'est pas ce que j'appelle une stratégie :--:

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.