Je sais que j'arrive après la bataille, mais je me suis penché sur la question et j'ai eu l'approche suivante:
Créer la liste de toutes les combinaisons possibles (après tout il n'y en a que 84 = 4096). Pour chaque combinaison, compter le nombre de combinaisons qui rapportent chaque score (donc parcourir 4096*4096 = 16 millions de combinaisons au premier coup, c'est faisable). Ensuite, calculer l'espérance d'élimination associée à chaque coup jouable. Jouer le coup qui va éliminer le plus de combinaisons.
On peut alors recommencer en ne considérant que les combinaisons qui n'ont pas été éliminées.
Au final, le premier coup est assez lent, tout ça pour sortir 4 chiffres différents, on peut donc le hard-coder pour aller plus vite.
Le résultat est:
- 3 essais dans 22% des cas
- 4 essais dans 68% des cas
- 5 essais dans 10% des cas
À noter que ce n'est peut être pas l'approche optimale. On joue le coup qui a la meilleure espérance, mais il peut aboutir à une situation où tous les coups suivants sont mauvais alors qu'un autre coup légèrement moins bon peut aboutir à une situation ou un coup suivant est suffisamment bon pour compenser. En pratique, je pense que c'est assez proche de l'optimal quand même (au moins pour 4 pions choisis parmi 8 couleurs).
Petit bonus, avec 8 couleurs et 4 pions, la probabilité d'avoir 2 pions de la même couleur est étonnamment élevée si on choisit la combinaison aléatoirement:
# Un peu à la bourre
Posté par Colin Pitrat (site web personnel) . En réponse au journal Yes Master. Évalué à 3.
Je sais que j'arrive après la bataille, mais je me suis penché sur la question et j'ai eu l'approche suivante:
Créer la liste de toutes les combinaisons possibles (après tout il n'y en a que 84 = 4096). Pour chaque combinaison, compter le nombre de combinaisons qui rapportent chaque score (donc parcourir 4096*4096 = 16 millions de combinaisons au premier coup, c'est faisable). Ensuite, calculer l'espérance d'élimination associée à chaque coup jouable. Jouer le coup qui va éliminer le plus de combinaisons.
On peut alors recommencer en ne considérant que les combinaisons qui n'ont pas été éliminées.
Au final, le premier coup est assez lent, tout ça pour sortir 4 chiffres différents, on peut donc le hard-coder pour aller plus vite.
Le résultat est:
- 3 essais dans 22% des cas
- 4 essais dans 68% des cas
- 5 essais dans 10% des cas
À noter que ce n'est peut être pas l'approche optimale. On joue le coup qui a la meilleure espérance, mais il peut aboutir à une situation où tous les coups suivants sont mauvais alors qu'un autre coup légèrement moins bon peut aboutir à une situation ou un coup suivant est suffisamment bon pour compenser. En pratique, je pense que c'est assez proche de l'optimal quand même (au moins pour 4 pions choisis parmi 8 couleurs).
Petit bonus, avec 8 couleurs et 4 pions, la probabilité d'avoir 2 pions de la même couleur est étonnamment élevée si on choisit la combinaison aléatoirement:
4 couleurs différentes: 1680 / 4096 = 41%
3 couleurs différentes: 2016 / 4096 = 49%
2 couleurs différentes, 2 pions chaque: 168 / 4096 = 4%
2 couleurs différentes, 3 pions d'une couleur: 224 / 4096 = 5%
1 seule couleur: 8 / 4096 = 0.2%