Mastermind strategy

Question

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.

Answer 1

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.

Answer 2

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. :)