Journal Yes Master

Posté par  . Licence CC By‑SA.
Étiquettes :
21
23
nov.
2020

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  . Évalué à 2 (+1/-1).

    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  . Évalué à 7 (+6/-0).

      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  . Évalué à 2 (+0/-0).

        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  . Évalué à 3 (+3/-1).

      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.

      N=4096;  s=0; for ((i=1;;i++)) ; do cpt=1 ; while true ; do let "A=(RANDOM+(RANDOM<<15))%N" ; [ $A == "0" ] && break ; let cpt=cpt+1 ; done ;  let s=s+cpt ; printf "essais = %6d  moy = %6d\n" "$cpt" "$((s/i))" ; done
  • # Le grand Donald Knuth

    Posté par  . Évalué à 8 (+6/-0).

    Le grand Donald Knuth (The Art of Computer Programming, tout ça) s'y est collé dès 1977

  • # Domaine public

    Posté par  . Évalué à 5 (+7/-4).

    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  (site Web personnel) . Évalué à 5 (+6/-3).

      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.

      Designeuse de masques pour sphéniscidés.

      • [^] # Re: Domaine public

        Posté par  (site Web personnel) . Évalué à 2 (+2/-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  (site Web personnel) . Évalué à 10 (+11/-1).

          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.

          Designeuse de masques pour sphéniscidés.

        • [^] # Re: Domaine public

          Posté par  . Évalué à 4 (+2/-0).

          L'idée était tout de même de substituer un terme à connotation positive, à un terme flirtant avec le péjoratif

          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  (site Web personnel) . Évalué à 2 (+0/-0). Dernière modification le 25/11/20 à 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.

            Designeuse de masques pour sphéniscidés.

          • [^] # Re: Domaine public

            Posté par  . Évalué à 4 (+2/-0).

            Tomber amoureux/amoureuse, c'est péjoratif ?

            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  . Évalué à 0 (+0/-1).

        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.

  • # coups incompatibles

    Posté par  . Évalué à 2 (+0/-0).

    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  . Évalué à 1 (+0/-0).

      oui sans doute. Je suis parti sur ma façon de jouer mais ce n'est pas optimale.

      • [^] # Re: coups incompatibles

        Posté par  (site Web personnel) . Évalué à 2 (+0/-0). Dernière modification le 23/11/20 à 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.

  • # humm

    Posté par  . Évalué à 2 (+0/-0).

    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  . Évalué à 1 (+0/-0).

      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  . Évalué à 2 (+0/-0). Dernière modification le 23/11/20 à 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  . Évalué à 1 (+0/-0).

          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  . Évalué à 1 (+0/-0).

    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.

  • # Incipit

    Posté par  (site Web personnel) . Évalué à 3 (+3/-0).

    Trouvé ! :-)

    ROT13 pour ceux qui veulent chercher : Yr wbhrhe qr Qbfgbïrifxv

    • [^] # Re: Incipit

      Posté par  (site Web personnel) . Évalué à 3 (+1/-0).

      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)

      • [^] # Re: Incipit

        Posté par  . Évalué à 2 (+1/-0).

        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  . Évalué à 1 (+0/-0).

      Bien vu !

  • # Un peu à la bourre

    Posté par  (site Web personnel) . Évalué à 3 (+1/-0).

    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  . Évalué à 1 (+0/-0).

      Et, tu me fais un petit pull request ?

      • [^] # Re: Un peu à la bourre

        Posté par  (site Web personnel) . Évalué à 2 (+0/-0).

        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  (site Web personnel) . Évalué à 2 (+0/-0).

        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:

        Test (4 letters among ROGBYAPW):
        OBAW
        0 good 4 bad
        
        Test (4 letters among ROGBYAPW):
        PGRY
        0 good 4 bad
        
        Test (4 letters among ROGBYAPW):
        YRPG
        4 good 0 bad
        
        Bravo 3 attempts
        

        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  . Évalué à 1 (+0/-0).

          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  (site Web personnel) . Évalué à 2 (+0/-0). Dernière modification le 07/12/20 à 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  . Évalué à 0 (+0/-0). Dernière modification le 09/12/20 à 19:24.

    Ce commentaire a été supprimé par l’équipe de modération.

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.