Stratégie Mastermind

19

Je ne pouvais trouver que des défis de code-golf pour Mastermind, alors voici une version de défi de code que j'aurais aimé relever moi-même.

Une stratégie optimale pour le jeu Mastermind normal, MM (4,6), a été trouvée par Koyama et Lai en 1993, avec un nombre moyen de suppositions = 5625/1296 ~ 4,34. MM (5,8) n'est toujours pas résolu, mais on estime qu'il a un nombre moyen de suppositions ~ 5,5.

Votre tâche consiste à créer une stratégie MM (5,8), c'est-à-dire pour 5 trous et 8 couleurs, couvrant toutes pow(8,5) = 32768les solutions distinctes possibles. De toute évidence, il ne doit pas être optimal. Vous avez deux choix:

  1. Publiez un programme déterministe qui génère la stratégie. Le programme doit être compilable / exécutable sur Windows 7, Mac OS X ou Linux sans logiciel supplémentaire non libre.
  2. Publiez votre stratégie (avec votre nom StackExchange) quelque part sur Internet et publiez l'URL ici.

Dans les deux cas, indiquez le score (voir ci-dessous) dans l'en-tête de la réponse.

La stratégie doit être codée selon la grammaire suivante:

strategy : guessing-strategy | known-solution-strategy
guessing-strategy : '{' guess ':' branches '}'
known-solution-strategy : guess
guess : color color color color color
color : 'A'..'H'
branches : '{' branch (',' branch)* '}'
branch : reply ':' strategy
reply : number-of-blacks number-of-whites
number-of-blacks : number-of-key-pegs
number-of-whites : number-of-key-pegs
number-of-key-pegs : '0'..'5'

L'algorithme utilisé pour décider du nombre de chevilles de touches noir / blanc est décrit dans http://en.wikipedia.org/wiki/Mastermind_(board_game)

Notez que la réponse "50" (c'est-à-dire une supposition correcte) est implicite et ne fait pas partie de la grammaire.

Notation: N = la somme du nombre de suppositions pour chacun des 32768 chemins / solutions. La stratégie avec le N le plus bas gagne. Premier tie-break: le plus petit nombre maximum de suppositions. Deuxième bris d'égalité: la première réponse publiée. Le concours se termine le 1er août 2014 à 0h00 GMT .


Un exemple de stratégie pour MM (2,3) avec score = 21:

{AB:{10:{AC:{10:AA,01:CB,00:BB}},02:BA,01:{BC:{01:CA}},00:CC}}

En utilisant cette stratégie, les 9 jeux possibles se dérouleront comme suit:

  • AB 20
  • AB 10, AC 20
  • AB 10, AC 10, AA 20
  • AB 10, AC 01, CB 20
  • AB 10, AC 00, BB 20
  • AB 02, BA 20
  • AB 01, BC 20
  • AB 01, BC 01, CA 20
  • AB 00, CC 20

Je publierai bientôt un vérificateur de stratégie MM (5,8) basé sur Java pour votre commodité.

MrBackend
la source
J'ai du mal à comprendre comment l'exemple de stratégie de MM (2,3) est appliqué. Pouvez-vous publier un exemple de jeu expliquant la stratégie?
@tolos J'ai ajouté tous les 9 :)
MrBackend
Ce serait formidable si votre vérificateur pouvait également produire un score!
Pas que Charles
@Charles fera l'affaire!
MrBackend
2
Seriez-vous prêt à changer votre grammaire pour permettre la même réponse à plusieurs combinaisons de chevilles clés? Comme {AB:{10|01:BB}}? J'ai une réponse, mais elle est assez naïve et en raison de la structure arborescente de la grammaire, elle ne s'adapte pas bien du tout (4 trous, 3 couleurs, génère une stratégie de 147 Mo, que je pourrais réduire considérablement en combinant des parties de l'arbre).
Martin Ender

Réponses:

6

Java

Mon algorithme pour MM (5,8) marque avec 177902 178006 182798 182697 avec une profondeur maximale de 8 9 et n'a besoin que de quelques secondes (sur mon ordinateur lent).

Un exemple de sortie d'une stratégie pour MM (2,3) avec un score = 21 trouvé par cet algorithme ressemble à ceci:

{BC:{00:AA,01:AB:{01:CA},02:CB,10:AC:{00:BB,01:BA,10:CC}}}

Il n'y a rien d'excitant avec mon algorithme. Aucune invention. Je viens de suivre les recettes trouvées sur le net et de les compresser dans ce code Java. La seule optimisation que j'ai faite est d'essayer d'optimiser les lignes de code (en quelque sorte). Ça va comme ça:

  1. Créez l'ensemble initial S0 de tous les codes possibles pour être l'ensemble actuel S.
  2. Codebreaker trouve une bonne supposition (gourmande) pour S. Chaque supposition conduit à une partition P de S, où chaque sous-ensemble S 'recueille tous les codes (de S) ayant la même réponse sur la supposition. Une bonne supposition a une bonne partition, comme celle qui donne le plus d'informations pour la supposition.
  3. Prenez la bonne estimation et son P. Pour chaque S non vide dans P, appliquez le codebreaker récursif (étape 2).

@MrBackend: Écrire un vérificateur est difficile, je suppose. ;-)

import java.util.TreeMap;
import java.util.Vector;

public class MM {
    Vector<String> codeset = new Vector<String>();
    String guess;
    TreeMap<Integer, MM> strategy = new TreeMap<Integer, MM>();

    public String toString() {
        String list="";
        for (Integer reply: strategy.keySet()) {
            if (strategy.get(reply)!=null) list+=(list.length()>0?",":"")+(reply<10?"0":"")+reply+":"+strategy.get(reply);
        }
        if (list.length()>0) return guess+":{"+list+"}"; else return guess;
    }

    MM() { }

    MM(int h, int c) {
        for (int i = 0; i < Math.pow(c, h); i++) {
            String code = "";
            for (int j = 0, p=i; j < h; j++) {
                code+="ABCDEFGH".charAt(p%c);
                p/=c;
            }
            codeset.add(code);
        }
    }

    int replyAccordingToDonaldKnuth(String secret, String guess) {
        int black=0;
        int totalHitsBlackAndWhite=0;
        for (char n = 'A'; n <= 'H'; n++) {
            int a=0, b=0;
            for (int i = 0; i < secret.length(); i++) {
                if (secret.charAt(i)==n) a++;
                if ( guess.charAt(i)==n) b++;
            }
            totalHitsBlackAndWhite+=Math.min(a, b);
        }
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) black++;
        }
        return 10 * black + (totalHitsBlackAndWhite-black);
    }

    int reply(String secret, String guess) {
        return replyAccordingToDonaldKnuth(secret, guess);
    }

    MM codebreaker(Vector<String> permuts) {
        int fitness=0;
        MM protostrategy=null;
        for (int greedy = 0; greedy < Math.min(permuts.size(), 200); greedy++) {
            MM tmp=partition(permuts, permuts.get(greedy));
            int value=tmp.strategy.size();
            if (fitness<=value) {
                fitness=value;
                protostrategy=tmp;
                protostrategy.guess=permuts.get(greedy);
            }
        }
        if (protostrategy!=null) {
            for (Integer reply: protostrategy.strategy.keySet()) {
                protostrategy.strategy.put(reply, codebreaker(protostrategy.strategy.get(reply).codeset));
            }
        }
        return protostrategy;
    }

    MM partition(Vector<String> permuts, String code) {
        MM protostrategy=new MM();
        for (int c = 0; c < permuts.size(); c++) {
            int reply=reply(permuts.get(c), code);
            if (!protostrategy.strategy.containsKey(reply)) protostrategy.strategy.put(reply, new MM());
            if (permuts.get(c)!=code) protostrategy.strategy.get(reply).codeset.add(permuts.get(c));
        }
        return protostrategy;
    }

    public static void main(String[] args) {
        MM mm = new MM(5,8);
        System.out.println("{"+mm.codebreaker(mm.codeset)+"}");
    }
}

Quelques remarques:

  1. Aucun contrôle de cohérence n'est nécessaire car les ensembles S et leurs partitions sont construits de manière (auto-) cohérente.
  2. Choisir une bonne estimation de S0 (au lieu de S) est logique. Mais je ne respecte pas cette approche dans le code actuel.
  3. Ma recherche gourmande est élaguée artificiellement à 200 essais.
  4. Je sais, "donner la plupart des informations à deviner" n'est pas très précis. L'idée simple est de choisir la partition avec le plus grand nombre de sous-ensembles.
  5. Le résultat dépend fortement de la façon dont vous calculez la réponse (..). Enfin, j'ai adapté l'expression de Donald Knuth.

La stratégie pour MM(5,8) peut être trouvée ici . GitHub a quelques problèmes pour afficher des lignes aussi longues, alors cliquez sur le bouton Raw .

Bob Genom
la source
salut comment imprimer le texte github pour que les résultats puissent être transformés en un guide de recherche .. à partir du premier point de départ 'HHCAA' .. et à l'étape suivante en fonction de la réponse ... et au suivant et ainsi de suite. Le format de texte brut actuel n'est pas plus facile pour la numérisation manuelle. La technique que je recherche est de savoir comment analyser les crochets imbriqués et obtenir une belle disposition de tableau qui est plus facile à suivre jusqu'à la fin, similaire à la liste à puces de la question pour MM (2,3). Je vous remercie. J'espère que vous pourrez comprendre ce que je recherche. (préférez python à analyser str)
ihightower
2

Rubis

EDIT: Ajout d'une logique pour exclure les suppositions impossibles. Par conséquent, les stratégies sont désormais conformes au format donné et sont beaucoup plus faciles à gérer.

Voici donc une tentative pour faire avancer les choses. C'est assez naïf (et pas très lisible - cela aide à lire la branche if / elsif / else de bas en haut).

Holes, Colors = ARGV.map &:to_i

ColorChars = ('A'..'H').to_a

def is_possible(guess, blacks, result)
    blacks == guess.chars.zip(result.chars).count {|chars| chars[0] == chars[1]}
end

def print_strategy(known_colors, remaining_permutations, next_color)
    char = ColorChars[next_color]
    if remaining_permutations
        guess = remaining_permutations[0]
        print guess
        if remaining_permutations.length > 1
            print ':{'
            (Holes-1).times do |i|
                new_permutations = (remaining_permutations - [guess]).select { |perm| is_possible(guess, i, perm) }
                next if new_permutations.empty?
                print "#{i}#{Holes-i}:"                
                print '{' if new_permutations.length > 1
                print_strategy(known_colors, new_permutations, next_color)
                print '}' if new_permutations.length > 1
                print ',' if i < Holes-2
            end
            print '}'
        end
    elsif known_colors.length == Holes
        print_strategy(known_colors, known_colors.chars.permutation.map(&:join).uniq, next_color)
    elsif next_color == Colors-1
        print_strategy(known_colors+char*(Holes - known_colors.length), remaining_permutations, next_color+1)
    else
        print char*Holes, ':{'

        (Holes - known_colors.length + 1).times do |i|
            break if i == Holes
            print "#{i}0:"
            print '{' if next_color < Colors-2 || i > 0 || known_colors.length > 0
            print_strategy(
                known_colors+char*i,
                remaining_permutations,
                next_color+1
            )
            print '}' if next_color < Colors-2 || i > 0 || known_colors.length > 0
            print ',' if i < (Holes - known_colors.length) && i < Holes-1
        end
        print '}'
    end
end

print '{'
print_strategy('', nil, 0)
puts '}'

Tout d' abord, j'essaie 5 de chaque couleur: AAAAA, BBBBB, etc. A partir de ce chiffre , je les couleurs qui sont effectivement utilisées dans le modèle. Et puis j'essaye simplement toutes les permutations des couleurs données, en omettant celles qui ont déjà été exclues par les chevilles noires.

Voici la MM(2,3)stratégie:

{AA:{00:{BB:{00:CC,10:{BC:{02:CB}}}},10:{BB:{00:{AC:{02:CA}},10:{AB:{02:BA}}}}}}

La stratégie pour MM(5,8)prend 376 Ko et peut être trouvée ici . GitHub a quelques problèmes pour afficher des lignes aussi longues, alors cliquez sur le bouton Raw .

Maintenant, si je reçois un vérificateur, je peux également vous dire quel est mon score réel. :)

Martin Ender
la source
Se sentir mal à propos du vérificateur pas encore publié, mais il est en route ... Il y a un problème avec votre (première) stratégie MM (2,3), par exemple si la solution est AB: Guess = AA; réponse = 10; suppose = BB; réponse = 10, pour laquelle il n'y a pas de stratégie. J'examinerai votre suggestion de regrouper les réponses, mais cela ne devrait pas être nécessaire pour de bonnes stratégies, car l'ensemble des solutions possibles est disjoint pour différentes réponses.
MrBackend
@MrBackend Bonne prise, j'ai sauté un cas là-bas. Il devrait être corrigé maintenant. En ce qui concerne la grammaire, bien sûr, ce n'est pas nécessaire pour de bonnes stratégies, mais je pensais que vous pourriez vouloir abaisser un peu la barre. ;) Si les gens peuvent soumettre des entrées plus simples (comme la mienne), vous pourriez avoir un peu plus de chance d'obtenir des soumissions intéressantes qui s'améliorent progressivement, au lieu d'avoir à inclure toutes les combinatoires dès le début.
Martin Ender
Voici l'affaire: je vais terminer le vérificateur actuel et le publier (en tant qu'application Web - il est trop volumineux pour être collé ici). Malheureusement, elle peut être trop stricte, car elle considère les réponses impossibles comme une erreur. Ensuite, je l'adapterai pour prendre en charge plusieurs réponses et émettrai simplement des avertissements pour les réponses impossibles. Cela dit, votre stratégie 1.3G MM (4,4) doit contenir beaucoup de réponses impossibles et / ou de suppositions non réductrices, car la taille estimée d'une stratégie décente MM (5,8) est une poignée de megs.
MrBackend
@MrBackend Bien sûr, mes stratégies contiennent une tonne de réponses impossibles. C'est ce que je voulais dire par "je ne fais pas la combinatoire". ;) Si c'est trop compliqué pour vous de supporter cela et de regrouper les réponses, ne vous inquiétez pas, alors je vais essayer d'omettre les suppositions impossibles.
Martin Ender
@MrBackend Bonne nouvelle, je l'ai corrigée. :) J'espère que la stratégie est valide maintenant. Faites-moi savoir s'il y a encore des problèmes.
Martin Ender