19
\$\begingroup\$

I could only find code-golf challenges for Mastermind, so here's a code-challenge version that I would have liked to take on myself.

An optimal strategy for the normal Mastermind game, MM(4,6), was found by Koyama and Lai in 1993, having an average # of guesses = 5625/1296 ~ 4.34. MM(5,8) is still unsolved, but is estimated to have an average # of guesses ~ 5.5.

Your task is to create an MM(5,8) strategy, that is for 5 holes and 8 colors, covering all pow(8,5) = 32768 possible distinct solutions. Obviously, it doesn't have to be an optimal one. You have two choices:

  1. Post a deterministic program that generates the strategy. The program must be compileable/runnable on Windows 7, Mac OS X or Linux without any extra non-free software.
  2. Publish your strategy (along with your StackExchange name) somewhere on the Internet and post the URL here.

In both cases, state the score (see below) in the answer's header.

The strategy must be encoded according to the following grammar:

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'

The algorithm used to decide the number of black/white key pegs is described in http://en.wikipedia.org/wiki/Mastermind_(board_game)

Note that the reply "50" (i.e. correct guess) is implied and not part of the grammar.

Scoring: N = the sum of the number of guesses for each of the 32768 paths/solutions. The strategy with the lowest N wins. First tie-break: The lowest maximum number of guesses. Second tie-break: The first posted answer. The competition ends August 1, 2014 0:00 GMT.


An example of a strategy for MM(2,3) with score = 21:

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

Using this strategy, the 9 possible games will go like this:

  • 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

I will soon post a Java-based MM(5,8) strategy verifier for your convenience.

\$\endgroup\$
  • \$\begingroup\$ I'm having a difficult time understanding how the example strategy of MM(2,3) is applied. Can you post a sample game explaining the strategy? \$\endgroup\$ – user21677 Jun 18 '14 at 22:15
  • \$\begingroup\$ @tolos I added all 9 :) \$\endgroup\$ – MrBackend Jun 18 '14 at 22:58
  • \$\begingroup\$ It would be great if your verifier could output a score, too! \$\endgroup\$ – Not that Charles Jun 24 '14 at 11:06
  • \$\begingroup\$ @Charles Will do! \$\endgroup\$ – MrBackend Jun 24 '14 at 12:01
  • 2
    \$\begingroup\$ Would you be willing to change your grammar to allow the same response to multiple key peg combinations? Like {AB:{10|01:BB}}? I do have an answer, but it's pretty naive and due to the tree-structure of the grammar it doesn't scale well at all (4 holes, 3 colours, generates a 147MB strategy, which I could cut down significantly by combining parts of the tree). \$\endgroup\$ – Martin Ender Jul 19 '14 at 14:44
6
\$\begingroup\$

Java

My algorithm for MM(5,8) scores with 177902 178006 182798 182697 with a maximum depth of 8 9 and needs only a few seconds (on my slow computer).

An example output of a strategy for MM(2,3) with score = 21 found by this algorithm looks like this:

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

There is nothing exciting with my algorithm. No invention. I just followed recipes found in the net and compressed them into this Java code. The only optimization I did is trying to optimize the lines of code (in a way). It goes like this:

  1. Create the initial set S0 of all possible codes to be the current set S.
  2. Codebreaker finds a (greedy) good guess for S. Each guess leads to a partition P of S, where each subset S' collects all codes (from S) having the same reply on the guess. A good guess has a good partition, as the one giving most information for the guess.
  3. Take the good guess and its P. For each nonempty S' in P apply codebreaker recursive (step 2).

@MrBackend: Writing a verifier is hard, I guess. ;-)

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)+"}");
    }
}

Some remarks:

  1. No consistency check is needed because sets S and their partitions are build in a (auto-)consistent way.
  2. Picking a good guess out of S0 (instead of S) makes sense. But I don't follow this approach in the current code.
  3. My greedy search is artificially pruned to 200 tries.
  4. I know, "giving most information for the guess" is not very precise. The simple idea is to pick the partition with the most number of subsets.
  5. The result heavily depends on how you calculate the reply(..). Finally I adapted Donald Knuth's expression.

The strategy for MM(5,8) can be found here. GitHub has some issues displaying lines that long, so click on the Raw button.

\$\endgroup\$
  • \$\begingroup\$ hi how to pretty print the github text so that the results can be turned into a lookup guide.. from the first starting point 'HHCAA'.. and next step depending on the reply... and to next and so on. The current raw text format it is not easier for manual scanning.. the technique i am after is how to parse the nested brackets and get a nice table layout that is easier to follow through till the end, similar to the bulleted list in the question for MM(2,3). Thank you. Hope you can understand what I am after. (prefer python to parse str) \$\endgroup\$ – ihightower Dec 30 '17 at 16:04
2
\$\begingroup\$

Ruby

EDIT: Added some logic to exclude impossible guesses. Hence, the strategies now comply with the given format and are much more manageable.

So here is one attempt to get this going. It's pretty naive (and not very legible - it helps to read the if/elsif/else branch from bottom to top).

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 '}'

First, I try 5 of each colour: AAAAA, BBBBB, etc. From that I figure out which colours are actually used in the pattern. And then I simply try all permutations of the given colours, omitting those which have been ruled out by the black pegs already.

Here is the MM(2,3) strategy:

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

The strategy for MM(5,8) takes 376KB and can be found here. GitHub has some issues displaying lines that long, so click on the Raw button.

Now if I get a verifier, I can also tell you what my actual score is. :)

\$\endgroup\$
  • \$\begingroup\$ Feeling bad about the verifier not published yet, but it´s on its way... There is something wrong with your (first) MM(2,3) strategy, for example if the solution is AB: Guess=AA; reply=10; guess=BB; reply=10, for which there is no strategy. I´ll look into your suggestion of grouping replies, but it should not be necessary for good strategies, since the set of possible solutions are disjoint for different replies. \$\endgroup\$ – MrBackend Jul 20 '14 at 9:51
  • \$\begingroup\$ @MrBackend Good catch, I skipped a case there. It should be fixed now. As for the grammar, of course it's not necessary for good strategies, but I thought you might be willing to lower the bar a bit. ;) If people can submit simpler entries (like mine) you might have a bit more luck getting interesting submissions that gradually improve, instead of having to include all of the combinatorics right from the start. \$\endgroup\$ – Martin Ender Jul 20 '14 at 10:43
  • \$\begingroup\$ Here's the deal: I'll finish the current verifier and publish it (as a web app - it is too large to paste here). Unfortunately, it might be too strict, as it considers impossible replies an error. Afterwards, I'll adapt it to support multiple replies and just emit warnings for impossible replies. Having said that, your 1.3G MM(4,4) strategy has to contain a lot of impossible replies and/or non-reducing guesses, as the estimated size of a decent MM(5,8) strategy is a handful of megs. \$\endgroup\$ – MrBackend Jul 21 '14 at 7:11
  • \$\begingroup\$ @MrBackend Of course my strategies contain a ton of impossible replies. That's what I meant by "I'm not doing the combinatorics". ;) If it's too much of a hassle for you to support that and grouping replies, don't worry, then I'll have a look into omitting impossible guesses. \$\endgroup\$ – Martin Ender Jul 21 '14 at 13:31
  • \$\begingroup\$ @MrBackend Good news, I fixed it. :) I hope the strategy is valid now. Let me know if there are still any problems with it. \$\endgroup\$ – Martin Ender Jul 28 '14 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.