Stratégie pour un jeu de déduction @ Prise2Tete

scrablor · #1

Voici un type de jeu de société auquel j'ai été confronté récemment. Il se base sur le thème du Cluedo.
Un joueur choisit quatre éléments, à chaque fois parmi cinq possibilités: l'assassin, l'arme, le lieu et le jour du crime. L'autre joueur propose par écrit douze phrases du genre "Le colonel Moutarde a tué avec le poignard dans la cuisine le lundi". L'auteur de l'énigme corrige, notant 0 les phrases 100% fausses et 1 celles où figure au moins l'un des éléments requis. Muni de ces informations, l'enquêteur doit découvrir la réalité.
L'expérience nous a montré que l'enquêteur gagnait le plus souvent, mais avait parfois deux ou trois choix possibles.
Je me pose alors la question : existe-t-il une liste de douze propositions qui permette de gagner à tous les coups ?

gwen27 · #2

En prenant dans l'ordre Coupable, Arme, Lieu et Jour (numérotés de 1 à 5 ),
ces douze propositions marchent, par exemple :

CALJ
1111
2222
3333
4444
1234
2341
3412
4123
5423
1543
1455
3142

enigmatus · #3

Bonjour,
@gwen27 #2 :
Avec tes 12 propositions, je trouve que, par exemple, ces 5 solutions ont la même signature.

Code:

(1, 3, 3, 1)
(1, 3, 3, 5)
(1, 3, 5, 1)
(1, 3, 5, 5)
(1, 5, 3, 1)

Signature commune :
(1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0)

gwen27 · #4

Oups, mal lu... Je ne prenais pas 1 mais le nombre de bons.

enigmatus · #5

@gwen27 #4 :
Effectivement, si on ne se limite pas à 0 et 1, ça marche.
Il est plus facile de vérifier une solution que d'en trouver une…

scrablor · #6

J'avais pensé mais sans le tester à écarter tous les n°5.
1111
2222
3333
4444
1234
2341
3412
4123
1432
2143
3214
4321

Petits calculs :
5^4=625 situations possibles
2^12=4096 listes de résultats au maximum
Il y a un paquet de signatures impossibles !...

enigmatus · #7

@scrablor #6 :

J'ai testé ta solution, et il y a 18 couples quit ont la même signature.
En voici un :

Code:

(2, 4, 5, 5)
(5, 5, 4, 2)]

Signature commune :
(0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0)

Édité :
Le test précédent est erroné (je comptais le nombre de correspondances pour générer la signature). Il n'y a que 301 signatures qui correspondent à une solution unique. Il y a 98 doublons, 8 quadruplets, 8 quintuplets, et 8 heptuplets.

scrablor · #8

Merci enigmatus, je craignais pire.

scrablor · #9

Il faut peut-être intégrer quelques 5 dans le dernier tiers :
1111
2222
3333
4444
1234
2341
3412
4123
1455
5543
3554
5325

enigmatus · #10

J'ai corrigé mon message #7.

@scrablor #9 :
Cette dernière proposition génère 468 signatures à solution unique, 71 doublons et 5 triplets.

Nombrilist · #11

Je propose à tout hasard:

1111
2222
3333
4444
1234
2345
3451
4512
5123
4321
5432
1543

Et je me demande si les matrices des plans expérimentaux factoriels fractionnaires ne pourraient pas aider ici, vu que l'on cherche à maximiser l'indépendance entre les lignes.

Enigmatus, tu pourrais partager ton code python ? Je n'ai pas compris cette dernière phrase:

"Cette dernière proposition génère 468 signatures à solution unique, 71 doublons et 5 triplets."

Une proposition ne génère qu'une seule signature, non ?

scrablor · #12

Il y a 625 situations possibles à découvrir.
Dans ma dernière proposition, enigmatus constate que je n'ai plus qu'un choix dans 468 cas, donc je gagne. Dans 71 cas, j'hésite entre deux possibilités et dans 5 cas, je dois choisir entre 3 solutions.
Vérification : 468+2*71+3*5=625

Nombrilist · #13

Merci Scrablor, ça y est j'ai compris.

enigmatus · #14

Bonjour,

Nombrilist #11 a écrit:
Enigmatus, tu pourrais partager ton code python ?

Bien sûr. J'y ai mis tes données, qui conduisent à 444 solutions uniques, 86 doublons et 3 triplets.

Code:

from itertools import product

choix=(
1111,
2222,
3333,
4444,
1234,
2345,
3451,
4512,
5123,
4321,
5432,
1543,
)
def verif(p):
   ret=[]
   for c in choix:
      c_=tuple(map(int,str(c)))
      dif=0
      for k in range(len(c_)):
         if c_[k]==p[k]: dif=1; break
      ret.append(dif)
   return tuple(ret)

rng=range(1,6)
prod=tuple(product(rng,repeat=4))
def prog():
   dic={}
   for p in prod:
      ver=verif(p)
      if not ver in dic: dic[ver]=[]
      dic[ver].append(p)
   nb_sol={}
   for k in sorted(dic):
      lon=len(dic[k])
      if not lon in nb_sol: nb_sol[lon]=0
      nb_sol[lon]+=1
      if lon>1: print(k, dic[k])
   t1=t2=p=0
   for k in nb_sol:
      t1+=nb_sol[k]
      t2+=k*nb_sol[k]
  #   p+=float(nb_sol[k])/k # À remplacer par p+=float(nb_sol[k])
      print('%3d %3d %3d'%(k,nb_sol[k],k*nb_sol[k]))
   print('Tot %3d %3d'%(t1,t2))
   print('Proba de gain : %7.3f %%'%(100.*t1/t2))
prog()

Il n'y a pas beaucoup de commentaires (c'est un euphémisme). Les signatures menant à une solution unique ne sont pas listées.

Ajouté : Calcul de la probabilité de gain
Édité : Correction du calcul de cette proba

scrablor · #15

Merci ! Joli programme qui me dépasse un peu... Mon dernier programme sérieux était en pascal au XXe siècle...
J'en ai profité pour améliorer ma version :
choix=(
1111,
2222,
3333,
4444,
1234,
2341,
3412,
4123,
3255,
5521,
4552,
5435
)
81,12% de probabilité de gain.

choix=(
1111,
2222,
3333,
4444,
1234,
2341,
3412,
4123,
3255,
5521,
2554,
5435
)
81,307% de probabilité de gain.

Nombrilist · #16

Merci Enigmatus !

choix=(
1111,
2222,
3333,
4444,
1234,
2345,
3451,
4512,
5123,
4155,
5314,
1543,
)
82,800% de probabilité de gain.

Je ne vois pas comment améliorer.

Nombrilist · #17

choix=(
1234,
3241,
4213,
5321,
2354,
4332,
1523,
2542,
3155,
5112,
1415,
5443,
)

83.107% de probabilité de gain.

Nombrilist · #18

Pour obtenir un plan optimal, j'émets les hypothèses que:

1 - chaque colonne doit contenir entre 2 et 3 fois le même chiffre. Pas plus, pas moins.

2 - chaque paire de ligne ne doit pas avoir plus d'un chiffre en commun.

1 3 5 4
1 2 5 3 Incorrect!

3 - il ne doit pas y avoir de transitivité directe

1 4 3 2
2 4 5 1
1 3 5 4 Incorrect!

Le 4 connecte le 1 et le 5. Je bute sur ce problème. Il me reste toujours un cas de transitivité dans mes derniers exemples.

4 - il ne doit pas y avoir, ou il faut limiter la transitivité indirecte

3 1 2 5
4 1 3 2
1 2 3 4
3 5 1 4 Incorrect!

A la quatrième ligne, le 3 et le 4 sont connectés via les 1 et 3 des lignes précédentes.

Si j'ai raison, alors le plan optimal s'écrit:

1 x x x
1 x x x
1 x x x
2 x x x
2 x x x
2 x x x
3 x x x
3 x x x
4 x x x
4 x x x
5 x x x
5 x x x

ça me fait vraiment penser aux plans d'expériences fractionnaires, où il faut maximiser l'orthogonalité. Je suis certain qu'ils donneraient de bons résultats, mais il faut un générateur de plan.

shadock · #19

Quelqu'un peut me dire en quoi "assassin", "jour", "lieu" et "date" du crime ça fait 5 possibilités ?

nobodydy · #20

C'est simple, c'est la seule chose que j'ai compris

Il y a 5 assassins possibles
Exemple :
Mademoiselle Joséphine Rose
Colonel Michael Moutarde
Madame Blanche Leblanc
Révérend John Olive
Madame Patricia Pervenche

5 lieux, 5 dates, 5 armes ...

shadock · #21

Ah d'accord

gwen27 · #22

Je pense que la solution suivante améliore sensiblement le résultat :
1123
1341
2255
2424
3354
3412
3543
4111
4232
5214
5431
5525

Nombrilist · #23

La vache, 89.787% !

Comment t'as fait ?

gwen27 · #24

Sans y passer trop de temps : Une formule sous excell qui renvoie à chaque lot de combinaisons proposées un nombre binaire à 12 bits étendue à chacune des 625 combinaisons possibles.

Une petite formule me donne le nombre de signatures différentes dans la liste obtenue.

Après, c'est bidouille : Je teste 1 2 3 4 5 pour chacun des 48 chiffres et je garde le meilleur.

Là, j'ai fait deux fois la boucle à partir d'une combinaison arbitraire
1111 1111 1111 ... 1111

Un programme testant les 3 133 080 443 665 742 400 738 147 440 000 000 solutions possibles marcherait aussi mais en dehors de toute blague, un programme qui testerait la méthode à partir d'une solution possible pour l'améliorer, oui.

On voit vite que 4432 à la place de 4332 te donnerait 6 signatures de plus dans ta dernière proposition.

godisdead · #25

A quoi correspond le 89.787% de probabilité de gain ?
j'ai essayé également de faire une feuille excel avec une macro d'amélioration, en mettant la proposition de gwen, je n'ai pas le même résultat.

Néanmoins, j'arrive pour le moment à des résultat inférieurs !

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 22-08-2016 19:46:27

Straégie pour un jeu de déduction

#0 Pub

#2 - 23-08-2016 09:35:27