Sommaire
Incipit
Je lui donnai les explications les plus claires possibles sur les nombreuses combinaisons, quatre couleurs différentes, une couleur doublée ou triplée, les pions blancs et rouges.
Elle écoutait attentivement, questionnait sans cesse et se pénétrait de mes réponses.
— Et est-il possible de trouver la bonne combinaison du premier coup ? Rose a crié tout à l’heure :« En un coup », et a levé les bras. Qu’est-ce que ça signifie ?
— En un coup, Margaux, c'est exceptionnel; Cela n'arrive presque jamais.
— En combien de coups alors ?
— En général, si on joue bien, on y arrive en 6 coups.
— Et cela arrive souvent ? Pourquoi y-a-t'il 9 lignes ? C'est pour les imbéciles ?
— Parce que l'on peut manquer de chance et mettre un peu plus de coups pour réussir.
— Quelle bêtise ! Là, est-ce que j'ai réussi du premier coup ?
— Margaux, le un coup vient d'être fait; c’est un mauvais moment pour penser réussir en un coup. Un blanc.
— Qu’est-ce que tu racontes! Et là ?
— Au deuxième coup, c'est rare aussi. Un blanc, un rouge.
— Des bêtises! Quand on craint le loup on ne va pas au bois. C’est perdu ?
Margaux ne tenait pas en place. Elle semblait vouloir fasciner les petits pions. Le troisième coup donna deux blancs, un rouge. Margaux était hors d'elle. Elle donna un coup de poing sur la table quand j'indiquai encore deux blancs et un rouge.
— Canaille! s’écria-t-elle. Ce maudit 4 rouges ne veut donc pas sortir ? Je veux rester jusqu’à ce qu’il sorte! C’est toi scélérat qui l'empêche de sortir!... Et là ?
— 4 rouges !
— Tu vois! Tu vois! dit vivement Margaux toute rayonnante. C’est Dieu lui-même qui m’a donné l’idée de mettre cette combinaison...
Intuition
Ces derniers jours, j'ai recommencé à jouer à Mastermind avec mes filles.
Pour rappel ou pour ceux qui ne connaîtrait pas ce classique, il faut découvrir un code de 4 couleurs parmi 8 (on peut mettre plusieurs fois une couleur). A chaque tentative, il est indiqué le nombre de pions de la bonne couleur bien placé (avec un indicateur rouge ou noir suivant les versions) et le nombre de pions de la bonne couleur mal placé (avec un indicateur blanc).
Dans nos parties, on trouve le code en 6 coups. Parfois 5 quand on a de la chance, parfois 7 quand on en manque.
Au début, après un premier coup au hasard avec 4 couleurs différentes, on ne faisait que des coups compatibles avec les indications. Ensuite, intuitivement, on s'est mis à faire un deuxième coup avec les 4 couleurs que l'on avait pas encore mis au premier coup quite à ce que ce coup ne soit pas compatible avec le premier. Je me suis demandé quelle était la meilleure stratégie et surtout si nos 6 coups étaient dans la moyenne.
Code
J'ai donc sorti mon éditeur de code favori et utilisé le langage le plus élégant au monde pour écrire un petit programme qui me permettrait de vérifier tout ça. Tout d'abord les bases, un petit programme qui me permettait de jouer seul. Programme trivial, il a fallu juste que je trouve un moyen de vérifier la combinaison et de déterminer les blancs et rouges.
Pour les rouges, c'est trivial, pour les blancs un petit peu moins. La méthode qui m'est venu a été de compter dans les deux codes (celui à trouver et celui de la tentative) le nombre de fois que chaque couleur était jouée. Pour chaque couleur, je prends la valeur minimale. J'additionne toutes ces valeurs minimales, ce qui me donne le nombre total de bonnes couleurs (bien ou mal placé). Je n'ai plus qu'à soustraire à ce total, le nombre de rouges et j'obtiens le nombre de blancs. Voir def verify
Bien mais ce n'était pas l'objectif. J'ai mis en place la partie auto avec un premier algo qui tire au hasard des combinaisons jusqu'à ce qu'il trouve la bonne solution (il est tellement crétin qu'il peut tirer plusieurs fois la même combinaison). Résultat après quelques milliers de parties, le nombre de coups moyens converge gentiment vers 4000-4100 coups (ce qui correspond bien à 84 = 4096, arrangement de 4 couleurs parmi 8 avec remise). Ça permet de vérifier la loi des grands nombres qui est bien souvent faussement invoqué pour jouer à Mme Irma.
Deuxième algo, le même mais cette fois-ci il ne tire plus deux fois la même combinaison. Résultat : on semble converger cette fois-ci vers 2048 coups. Je suis bien incapable de le prouver. Afin d'améliorer les performances, j'ai dû stocker les combinaisons déjà faites sous forme d'arbre. Voir def make_tree
Bon, on passe maintenant à des algos un peu plus intéressant. Le troisième algo joue un coup au hasard en premier puis des coups compatibles (coups qui ne sont pas incompatibles au vu des résultats des tentatives précédentes).
Puis, un quatrième algo implémente notre intuition : sur les deux premiers coups, on joue les 8 couleurs puis des coups compatibles.
Enfin, un cinquième algo ressemble beaucoup au troisième en obligeant le premier coup à jouer avec 4 couleurs différentes puis des coups compatibles.
Résultats
Je ne reviens pas sur les deux premiers algo.
Le 3ème donne, après 10000 parties:
- 5,42 coups en moyenne
- 9 coups maximum
Le 4ème donne, après 10000 parties:
- 5,52 coups en moyenne
- 9 coups maximum
Le 5ème donne, après 10000 parties:
- 5,40 coups en moyenne
- 9 coups maximum
Avec nos 6 coups, on est dans la moyenne. De façon étonnante, on a jamais été au-delà de 7 coups alors que l'algo "compatible" monte à 9. Enfin notre intuition n'est pas bonne même si elle permet d'avoir des infos faciles à intégrer au début du jeu. Enfin, il vaut mieux jouer 4 couleurs différentes en premier.
Je me pose quand même la question de savoir si 10000 parties suffisent pour bien converger sur la deuxième décimale. D'après mes tests, c'est un peu juste.
Épilogue
Chères lectrices, chers lecteurs, pour aller plus loin je te propose deux défis :
- Sauras-tu retrouver l'oeuvre originale, tombée dans le domaine public, dont est très largement inspiré l'incipit ?
- Sauras-tu trouver un algorithme qui permettra de descendre sous les 5,4 coups de moyenne (avec 10000 parties) tout en maintenant les parties à 9 coups maximum ? Voir le README.md pour qu'il s'intègre harmonieusement avec le reste du code.
# 4096 vs 2048
Posté par gUI (Mastodon) . Évalué à 2.
Moi c'est plutôt le 4096 que je ne comprends pas, le 2048 étant plus facile à expliquer : tu as une chance sur 4096 de trouver la bonne formule. Des fois tu la trouvera en un coup (comme Rose), des fois en 4096 (comme le mec qui a le moins de chance du monde), en moyenne c'est donc 2048.
Par contre, pour l'algo qui fait au hasard quitte à refaire plusieurs fois la combinaison, je ne saurais expliquer le 4096.
En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
[^] # Re: 4096 vs 2048
Posté par bobo38 . Évalué à 7.
bah si: à chaque combinaison aléatoire (sans se souvenir des combinaisons déjà testées), il y a 1 chance sur 4096…
[^] # Re: 4096 vs 2048
Posté par gUI (Mastodon) . Évalué à 2.
ah oui :)
En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
[^] # Re: 4096 vs 2048
Posté par SChauveau . Évalué à 3.
En effet, il n'y a pas de mémoire donc il ne faut oublier les cas ou le nombre d'essais est supérieur à 4096.
Et pour le fun, voici une petite commande bash simulant un tel tirage au sort. Chaque ligne indique le nombre d'essais pour trouver une valeur entre 0 et N-1 (donc avec une probabilité de 1/N) ainsi que la moyenne depuis le début.
# Le grand Donald Knuth
Posté par Serge Julien . Évalué à 8.
Le grand Donald Knuth (The Art of Computer Programming, tout ça) s'y est collé dès 1977
[^] # Re: Le grand Donald Knuth
Posté par Paul POULAIN (site web personnel, Mastodon) . Évalué à 7.
Je suis le seul à avoir presque lu "Donald Trump" ? :\
[^] # Re: Le grand Donald Knuth
Posté par Maclag . Évalué à 10.
Le grand Donald Trump n'a pas besoin d'algorithme: il gagne toujours du premier coup grâce à son génie, mais ses adversaires persistent à tricher en ne mettant pas les vrais pions dans le compartiment caché.
[^] # Re: Le grand Donald Knuth
Posté par matteli . Évalué à 2.
Belle trouvaille !
Par contre dans l'édition étudiée par Knuth, il n' y a que 6 couleurs.
Dans celle que j'étudie, il y en 8.
[^] # Re: Le grand Donald Knuth
Posté par Benoît Sibaud (site web personnel) . Évalué à 5. Dernière modification le 23 novembre 2020 à 13:03.
https://fr.wikipedia.org/wiki/Mastermind#Pr%C3%A9sentation
Le nombre de pions de couleurs différentes est de 6 et les couleurs sont dans la version originale2 : jaune, bleu, rouge, vert, blanc, noir.
Il existe de nombreuses variantes suivant le nombre de couleurs, de rangées ou de trous et les couleurs utilisés pour les pions. Le jeu peut par exemple contenir 8 couleurs (rouge, jaune, bleu, orange, vert, blanc, violet, rose) et les pions indicatifs peuvent être jaunes et rouges. Il y a aussi une version qui propose de découvrir un code de 5 couleurs en 12 rangées : le "Super" Master Mind.
Et encore plus de détails et d'algos dans https://en.wikipedia.org/wiki/Mastermind_(board_game)#Algorithms_and_strategies
# Domaine public
Posté par Mimoza . Évalué à 5.
De la même manière que les politiques manipules la novlangue, ont peux faire de même pour de plus nobles raisons.
«Élever» est préférable à «tomber» quand ont parle du domaine public. Ça permet de se faire une autre représentation que sont les bien commun, ils ont une promotion au lieu d'être rétrogradé.
[^] # Re: Domaine public
Posté par Ysabeau 🧶 (site web personnel, Mastodon) . Évalué à 5.
En fait je trouve que le verbe « élever » n’est pas le plus pertinent. On pourrait opter pour « arriver », « entrer », « être », « figurer », « intégrer », « faire partie ». Bref, ce ne sont pas les termes qui manquent.
« Tak ne veut pas quʼon pense à lui, il veut quʼon pense », Terry Pratchett, Déraillé.
[^] # Re: Domaine public
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 2.
L'idée était tout de même de substituer un terme à connotation positive, à un terme flirtant avec le péjoratif — sauf, pour ceux dont c'est la spécialité comme Uke, ou l'ayant droit (non auteur) à qui tomber évoque les espèces sonnantes et surtout trébuchantes qui viennent choir dans l'escarcelle sans le travail honnie auquel le reste de l'espèce est astreinte pour assurer sa pitance.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Domaine public
Posté par Ysabeau 🧶 (site web personnel, Mastodon) . Évalué à 10.
Je ne vois pas en quoi "élever" est si positif. En fait ça fait mauvaise traduction. Dire "entrer" dans le domaine public est plus conforme à la réalité et signifie que c'est sa place légitime. Comme on entre au Panthéon.
Et puis, j'en ai un peu assez de ces expressions qui doivent jouer avec un sentiment.
« Tak ne veut pas quʼon pense à lui, il veut quʼon pense », Terry Pratchett, Déraillé.
[^] # Re: Domaine public
Posté par windu.2b . Évalué à 4.
Tomber amoureux/amoureuse, c'est péjoratif ? Et s'élever c'est forcément positif ? Même quand on parle d'Icare ?
[^] # Re: Domaine public
Posté par Ysabeau 🧶 (site web personnel, Mastodon) . Évalué à 2. Dernière modification le 25 novembre 2020 à 10:24.
Et aussi, je trouve dommage de se limiter à un seul mot pour des considérations assez vaseuses, quand on peut en utiliser plusieurs en fonction des contextes. On a une langue riche, pourquoi vouloir l’appauvrir en réduisant le vocabulaire utilisé ? Déjà que l’adjectif « beau » utilisé à la place de « bon » me sort par les trous de nez, idem pour « large » à la place de grand, vaste ou étendu par exemple.
« Tak ne veut pas quʼon pense à lui, il veut quʼon pense », Terry Pratchett, Déraillé.
[^] # Re: Domaine public
Posté par fearan . Évalué à 4.
L'amour, rendant aveugle et con, j'aurais tendance a penser que oui :P
De même il est mal venu de 'tomber enceinte';
si tu regardes les définition pour tomber
https://www.larousse.fr/dictionnaires/francais/tomber/78343
tu noteras quand même dans les exemples qu'a part celui que tu as donnée tous sont neutre ou négatif
avec notamment :
Passer d'un état neutre ou valorisant à un état dévalorisant, affligeant, etc. : Une œuvre qui tombe dans l'oubli.
Il ne faut pas décorner les boeufs avant d'avoir semé le vent
[^] # Re: Domaine public
Posté par Gil Cot ✔ (site web personnel, Mastodon) . Évalué à 0.
Toi t'es factuelle <3 Mais à l'heure des discours qui titillent le sentimentalisme et l'émotion, il faut tomber (bas) ou s'élever (haut) etc. Ah oui, la langue des poètes et des diplomates, bref la vente de rêves/mensonges/idéaux qui se disent plus blancs que neige et plus nationaux que jeanne.
“It is seldom that liberty of any kind is lost all at once.” ― David Hume
# coups incompatibles
Posté par mahikeulbody . Évalué à 2.
Si on veut minimiser le nombre de coups en moyenne (i.e. sur un grand nombre de parties) sans compter sur le hasard, il me semble qu'il ne faut pas exclure de jouer des coups incompatibles mais qui apportent plus d'information. J'ai programmé ce jeu il y a quelques décennies (avec un algorithme de parcours d'arbre classique et min-max) et il me semble bien que le programme sortait aussi des coups incompatibles avec la connaissance disponible au tour concerné.
[^] # Re: coups incompatibles
Posté par matteli . Évalué à 1.
oui sans doute. Je suis parti sur ma façon de jouer mais ce n'est pas optimale.
[^] # Re: coups incompatibles
Posté par ploum (site web personnel, Mastodon) . Évalué à 2. Dernière modification le 23 novembre 2020 à 20:43.
J'ai fait un truc dans le genre il y'a 20 ans pour m'amuser. Dans mes souvenirs, je faisais du constraint programming mais je jouais beaucoup sur les premiers coups qui étaient quasiment « hardcodés ». Du type : 3 de la même couleur puis un autre. Ne changer qu'un seul pion du tour précédent.
Si je me souviens bien, cela me permettait de jouer à chaque fois maximum 5 coups (avec le défaut que c'était quasi à tous les coups 5 coups).
Mais, punaise, c'est loin, je peux me tromper.
Mes livres CC By-SA : https://ploum.net/livres.html
# humm
Posté par fearan . Évalué à 2.
J'ai lu un peu vite mais sur le 2e coup du deuxième algo tu fais forcément les 4 couleurs qui n'ont pas été présente au premier.
Il faudrait faire un cas où les 4 couleurs matches, car dans ce cas ce coup est totalement inutile, et n'apporte strictement rien.
Il ne faut pas décorner les boeufs avant d'avoir semé le vent
[^] # Re: humm
Posté par matteli . Évalué à 1.
Tu dois parler du 4ème algo.
Tu as raison. Si ça se trouve, c'est le 0,1 coup d'écart.
[^] # Re: humm
Posté par fearan . Évalué à 2. Dernière modification le 23 novembre 2020 à 16:48.
oui pardon j'ai zappé les autres :)
Pour l'écart, il faudrait savoir combien de fois on est tombé dans ce cas là, car un coup pour rien lorsque l'on est à 4 ou 5 coup, ça commence à chiffrer :)
mais bon faut 4 couleurs différentes et qu'on teste ces 4 la ;) donc c'est pas méga fréquent.
Il ne faut pas décorner les boeufs avant d'avoir semé le vent
[^] # Re: humm
Posté par matteli . Évalué à 1.
5,49 en enlevant le cas des 4 couleurs matchés au 1er coup.
0,03 en moins mais encore une fois la convergence de la deuxième décimale n'est pas totalement obtenue.
# Orthographe
Posté par matteli . Évalué à 1.
Je me suis sans doute basé sur une traduction bien mauvaise de l’œuvre car c'est bourré de fautes. Dans la 1ère phrase de l'incipit :
Je lui donnai les explications le*s* plus claires possible*s*
Margaux était hors de soi me parait aussi pas bon :
Margaux était hors d'elle.
[^] # Re: Orthographe
Posté par gUI (Mastodon) . Évalué à 2.
Corrigé, merci.
En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.
[^] # Re: Orthographe
Posté par matteli . Évalué à 1.
Merci à toi
# Incipit
Posté par Mika Cousin (site web personnel) . Évalué à 3.
Trouvé ! :-)
ROT13 pour ceux qui veulent chercher : Yr wbhrhe qr Qbfgbïrifxv
[^] # Re: Incipit
Posté par ploum (site web personnel, Mastodon) . Évalué à 3.
Je ne l'ai pas lu mais j'ai adoré d'autres du même auteur. Celui-ci en vaut-il la peine ?
(merci pour la réponse)
Mes livres CC By-SA : https://ploum.net/livres.html
[^] # Re: Incipit
Posté par sebas . Évalué à 2.
Sans être une œuvre maîtresse de cet auteur, comme [ah, zut, je ne peux pas les citer, ou alors en rot13 :-)], c'est un court roman, bien écrit, intéressant, surtout quand on sait que l'auteur était lui-même victime de ce vice. Oui, selon moi, ça vaut tout à fait le coup d'être lu.
[^] # Re: Incipit
Posté par Mika Cousin (site web personnel) . Évalué à 1.
Je confirme. Si tu apprécies l'auteur, c'est à lire.
[^] # Re: Incipit
Posté par matteli . Évalué à 1.
Bien vu !
# Un peu à la bourre
Posté par Colin Pitrat (site web personnel) . É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%
[^] # Re: Un peu à la bourre
Posté par matteli . Évalué à 1.
Et, tu me fais un petit pull request ?
[^] # Re: Un peu à la bourre
Posté par Colin Pitrat (site web personnel) . Évalué à 2.
Alors j'ai tout recodé moi même, mais je vais jeter un coup d’œil, ça devrait être faisable :-)
[^] # Re: Un peu à la bourre
Posté par Colin Pitrat (site web personnel) . Évalué à 2.
J'ai regardé pour te faire ça et du coup je suis tombé sur un os.
Tu retournes le nombre de pions bien placés, mais pas le nombre de pions de la bonne couleur mais mal placés:
Par exemple:
En essayant les huit lettres sur les deux premiers essais, j'ai 0 good et 4 bad à chaque fois. Pourtant le premier à aucune lettre bonne. Le deuxième à les 4 bonnes lettres mais aucune au bon endroit.
Du coup, https://github.com/matteli/yesmaster/issues/1
[^] # Re: Un peu à la bourre
Posté par matteli . Évalué à 1.
Oui j'avais mal regardé ton exemple mais il y avait bien une erreur et j'ai bien intégré ta modification.
C'est la première fois que j'ai une contribution extérieure sur un de mes codes.
Ça me fait un bon exercice pour l'utilisation de git github.
Donc même si ça reste un petit programme, je tâtonne un peu et j'essaye de faire ça correctement.
[^] # Re: Un peu à la bourre
Posté par Colin Pitrat (site web personnel) . Évalué à 2. Dernière modification le 07 décembre 2020 à 11:49.
En fait, les chiffres ci-dessus sont faux.
Mon code avait un bug: je comptais le nombre de coups nécessaires pour être sûr de la combinaison (je m'arrêtais quand les combinaison possibles étaient réduites à 1). Mais pour gagner, il faut jouer cette combinaison. Donc dans certains cas, il fallait un coup de plus pour gagner.
Cette stratégie est du "one-step ahead" et comme dit précédemment, n'est pas nécessairement la meilleure. C'est celle décrite par Knuth dans son papier (mais pour 6 couleurs).
Un papier de 2013, "An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case" par Geoffroy Ville recherche une solution optimale pour le Mastermind à 7 couleurs (6 couleurs plus trous autorisés) et donne des résultats:
https://arxiv.org/pdf/1305.1010.pdf
Je continue de creuser et documente mes trouvailles et mon code à http://colin.pitrat.free.fr/?p=539
# Commentaire supprimé
Posté par mobuysellram . Évalué à 0. Dernière modification le 09 décembre 2020 à 19:24.
Ce commentaire a été supprimé par l’équipe de modération.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.