Strategia Mastermind

Mogłem znaleźć tylko wyzwania związane z golfem dla Mastermind, więc oto wersja z wyzwaniem dla kodu, którą chciałbym wziąć na siebie.

Optymalną strategię dla normalnej gry Mastermind, MM (4,6), odkryli Koyama i Lai w 1993 r., Mając średnią # domysłów = 5625/1296 ~ 4,34. MM (5,8) jest nadal nierozwiązane, ale szacuje się, że ma średnią # domysłów ~ 5,5.

Twoim zadaniem jest stworzenie strategii MM (5,8), czyli dla 5 dołków i 8 kolorów, obejmującej wszystkie pow(8,5) = 32768możliwe odrębne rozwiązania. Oczywiście nie musi być optymalny. Masz dwie możliwości:

1. Opublikuj program deterministyczny, który generuje strategię. Program musi być kompilowany / uruchamialny w systemie Windows 7, Mac OS X lub Linux bez dodatkowego niewolnego oprogramowania.
2. Opublikuj swoją strategię (wraz z nazwą StackExchange) gdzieś w Internecie i opublikuj adres URL tutaj.

W obu przypadkach wpisz wynik (patrz poniżej) w nagłówku odpowiedzi.

Strategia musi być zakodowana zgodnie z następującą gramatyką:

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'

Algorytm używany do decydowania o liczbie czarnych / białych kołków jest opisany w http://en.wikipedia.org/wiki/Mastermind_(board_game)

Zauważ, że odpowiedź „50” (tj. Prawidłowe odgadnięcie) jest domyślna i nie stanowi części gramatyki.

Punktacja: N = suma liczby domysłów dla każdej z 32768 ścieżek / rozwiązań. Wygrywa strategia z najniższą liczbą N. Pierwszy remis: najniższa maksymalna liczba odgadnięć. Drugi remis: pierwsza opublikowana odpowiedź. Konkurs kończy się 1 sierpnia 2014 r. 0:00 GMT .

Przykład strategii dla MM (2,3) z wynikiem = 21:

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

Korzystając z tej strategii, 9 możliwych gier będzie wyglądać następująco:

• 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

Wkrótce opublikuję dla Twojej wygody weryfikator strategii MM (5,8) oparty na Javie.

Jawa

Mój algorytm dla MM (5,8) ocenia 177902 178006 182798 182697 z maksymalną głębokością 8 9 i potrzebuje tylko kilku sekund (na moim wolnym komputerze).

Przykładowy wynik strategii dla MM (2,3) z wynikiem = 21 znaleziony przez ten algorytm wygląda następująco:

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

Z moim algorytmem nie ma nic ekscytującego. Bez wynalazku. Właśnie śledziłem przepisy znalezione w sieci i skompresowałem je do tego kodu Java. Jedyną optymalizacją, jaką zrobiłem, jest próba zoptymalizowania linii kodu (w pewien sposób). Wygląda to tak:

1. Utwórz początkowy zestaw S0 wszystkich możliwych kodów, aby był bieżącym zestawem S.
2. Codebreaker znajduje (chciwe) dobre domysły dla S. Każde zgadywanie prowadzi do partycji P S, gdzie każdy podzbiór S zbiera wszystkie kody (od S) mające taką samą odpowiedź na domysł. Dobra domysł ma dobrą partycję, ponieważ ta daje najwięcej informacji do zgadnięcia.
3. Odgadnij i zgadnij P. Dla każdego niepustego S 'w P zastosuj rekurencyjny koder (krok 2).

@MrBackend: Chyba napisanie weryfikatora jest trudne. ;-)

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

Kilka uwag:

1. Nie jest wymagana kontrola spójności, ponieważ zestawy S i ich partycje są budowane w (automatycznie) spójny sposób.
2. Wybranie dobrego odgadnięcia z S0 (zamiast S) ma sens. Ale nie stosuję tego podejścia w obecnym kodzie.
3. Moje chciwe poszukiwania są sztucznie przycinane do 200 prób.
4. Wiem, „podanie większości informacji do zgadnięcia” nie jest zbyt precyzyjne. Prostym pomysłem jest wybranie partycji z największą liczbą podzbiorów.
5. Wynik zależy w dużej mierze od sposobu obliczenia odpowiedzi (..). W końcu dostosowałem wyraz twarzy Donalda Knutha.

Strategię MM(5,8) można znaleźć tutaj . GitHub ma pewne problemy z wyświetlaniem długich linii, więc kliknij przycisk Raw .

Rubin

EDYCJA: Dodano pewną logikę, aby wykluczyć niemożliwe domysły. Dlatego strategie są teraz zgodne z danym formatem i są o wiele łatwiejsze do zarządzania.

Oto jedna próba uruchomienia tego. Jest dość naiwny (i mało czytelny - pomaga czytać gałąź if / elsif / else od dołu do góry).

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

Po pierwsze, staram 5 z każdego koloru: AAAAA, BBBBB, itd. Od tego rysunku I na jakie kolory są rzeczywiście używane we wzorcu. A potem po prostu próbuję wszystkich permutacji podanych kolorów, pomijając te, które zostały już wykluczone przez czarne kołki.

Oto MM(2,3)strategia:

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

Strategia MM(5,8)zajmuje 376 KB i można ją znaleźć tutaj . GitHub ma pewne problemy z wyświetlaniem długich linii, więc kliknij przycisk Raw .

Teraz, jeśli otrzymam weryfikator, mogę również powiedzieć, jaki jest mój rzeczywisty wynik. :)