Strategia Mastermind

19

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.

MrBackend
źródło
Trudno mi zrozumieć, w jaki sposób stosowana jest przykładowa strategia MM (2,3). Czy możesz opublikować przykładową grę wyjaśniającą strategię?
@tolos Dodałem wszystkie 9 :)
MrBackend
Byłoby wspaniale, gdyby twój weryfikator mógł również wygenerować wynik!
Nie to, że Charles
@Charles zrobi!
MrBackend
2
Czy chciałbyś zmienić gramatykę, aby umożliwić taką samą odpowiedź na wiele kombinacji kluczowych klawiszy? Jak {AB:{10|01:BB}}? Mam odpowiedź, ale jest dość naiwna, a ze względu na strukturę drzewa gramatyki wcale nie skaluje się dobrze (4 dziury, 3 kolory, generuje strategię 147 MB, którą mogłem znacznie zmniejszyć , łącząc części drzewo).
Martin Ender

Odpowiedzi:

6

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 .

Bob Genom
źródło
cześć, jak ładnie wydrukować tekst github, aby wyniki można było przekształcić w przewodnik wyszukiwania .. od pierwszego punktu początkowego „HHCAA”… i następnego kroku w zależności od odpowiedzi… i do następnego itd. Obecny format tekstu surowego nie jest łatwiejszy do ręcznego skanowania. Technika, którą szukam, to jak analizować zagnieżdżone nawiasy i uzyskać ładny układ tabeli, który jest łatwiejszy do końca, podobnie jak wypunktowana lista w pytaniu dla MM (2,3). Dziękuję Ci. Mam nadzieję, że zrozumiesz, o co mi chodzi. (wolę pytona niż
parsować
2

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

Martin Ender
źródło
Źle się czuje, że weryfikator nie został jeszcze opublikowany, ale jest na dobrej drodze ... Coś jest nie tak z twoją (pierwszą) strategią MM (2,3), na przykład, jeśli rozwiązaniem jest AB: Zgadnij = AA; odpowiedź = 10; zgadnij = BB; odpowiedz = 10, dla której nie ma strategii. Przyjrzę się twojej sugestii grupowania odpowiedzi, ale nie powinno to być konieczne dla dobrych strategii, ponieważ zestaw możliwych rozwiązań jest rozłączny dla różnych odpowiedzi.
MrBackend
@MrBackend Dobry połów, pominąłem tam sprawę. Teraz powinno to zostać naprawione. Jeśli chodzi o gramatykę, oczywiście nie jest to konieczne dla dobrych strategii, ale pomyślałem, że możesz chcieć nieco obniżyć poprzeczkę. ;) Jeśli ludzie mogą przesyłać prostsze wpisy (takie jak moje), możesz mieć więcej szczęścia, otrzymując ciekawe zgłoszenia, które stopniowo się poprawiają, zamiast konieczności dołączania wszystkich kombinatoryki od samego początku.
Martin Ender
Oto oferta: skończę obecnego weryfikatora i opublikuję go (jako aplikacja internetowa - jest on zbyt duży, aby go wkleić). Niestety może być zbyt surowe, ponieważ uważa niemożliwe odpowiedzi za błąd. Następnie dostosuję go do obsługi wielu odpowiedzi i po prostu wyemituję ostrzeżenia o niemożliwych odpowiedziach. Powiedziawszy to, twoja strategia 1.3G MM (4,4) musi zawierać wiele niemożliwych odpowiedzi i / lub nieredukujących domysłów, ponieważ szacowany rozmiar przyzwoitej strategii MM (5,8) to garstka megamiast.
MrBackend
@MrBackend Oczywiście moje strategie zawierają mnóstwo niemożliwych odpowiedzi. To właśnie miałem na myśli przez „nie używam kombinatoryki”. ;) Jeśli jest to dla ciebie zbyt trudnym zadaniem, abyś mógł to wspierać i grupować odpowiedzi, nie martw się, to spróbuję pominąć niemożliwe domysły.
Martin Ender
@MrBackend Dobra wiadomość, naprawiłem to. :) Mam nadzieję, że strategia jest teraz aktualna. Daj mi znać, jeśli nadal będą z tym jakieś problemy.
Martin Ender