Mastermind-Strategie

19

Ich konnte nur Code-Golf-Herausforderungen für Mastermind finden, daher hier eine Code-Challenge-Version, die ich gerne selbst angenommen hätte.

Eine optimale Strategie für das normale Mastermind-Spiel, MM (4,6), wurde 1993 von Koyama und Lai mit einer durchschnittlichen Rate von 5625/1296 ~ 4,34 gefunden. MM (5,8) ist immer noch ungelöst, hat aber schätzungsweise eine durchschnittliche Anzahl von Vermutungen von ~ 5,5.

Ihre Aufgabe ist es, eine MM (5,8) -Strategie für 5 Löcher und 8 Farben zu erstellen, die alle pow(8,5) = 32768möglichen unterschiedlichen Lösungen abdeckt . Natürlich muss es nicht optimal sein. Sie haben zwei Möglichkeiten:

  1. Veröffentlichen Sie ein deterministisches Programm, das die Strategie generiert. Das Programm muss unter Windows 7, Mac OS X oder Linux ohne zusätzliche nicht-freie Software kompilierbar / lauffähig sein.
  2. Veröffentlichen Sie Ihre Strategie (zusammen mit Ihrem StackExchange-Namen) irgendwo im Internet und geben Sie die URL hier ein.

Geben Sie in beiden Fällen die Punktzahl (siehe unten) in der Kopfzeile der Antwort an.

Die Strategie muss gemäß der folgenden Grammatik codiert werden:

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'

Der Algorithmus zur Bestimmung der Anzahl der schwarzen / weißen Tastenstifte ist in http://en.wikipedia.org/wiki/Mastermind_(board_game) beschrieben.

Beachten Sie, dass die Antwort "50" (dh die richtige Schätzung) impliziert ist und nicht Teil der Grammatik ist.

Wertung: N = die Summe der Anzahl der Vermutungen für jeden der 32768 Pfade / Lösungen. Die Strategie mit den niedrigsten N gewinnt. Erster Gleichstand: Die niedrigste maximale Anzahl von Vermutungen. Zweiter Gleichstand: Die erste gesendete Antwort. Der Wettbewerb endet am 1. August 2014 um 0:00 Uhr GMT .


Ein Beispiel für eine Strategie für MM (2,3) mit score = 21:

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

Mit dieser Strategie werden die 9 möglichen Spiele so ablaufen:

  • 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

Ich werde demnächst einen Java-basierten MM (5,8) -Strategieprüfer veröffentlichen.

MrBackend
quelle
Es fällt mir schwer zu verstehen, wie die Beispielstrategie von MM (2,3) angewendet wird. Können Sie ein Beispielspiel veröffentlichen, in dem die Strategie erklärt wird?
@ Tolos Ich fügte alle 9 :)
MrBackend
Es wäre großartig, wenn Ihr Prüfer auch eine Punktzahl ausgeben könnte!
Nicht dass Charles
@ Charles wird es tun!
MrBackend
2
Wären Sie bereit, Ihre Grammatik zu ändern, um die gleiche Reaktion auf mehrere Tastenkombinationen zu ermöglichen? Wie {AB:{10|01:BB}}? Ich habe eine Antwort, aber es ist ziemlich naiv und aufgrund der Baumstruktur der Grammatik überhaupt nicht gut skalierbar (4 Löcher, 3 Farben, 147 MB ​​Strategie, die ich durch die Kombination von Teilen von deutlich reduzieren könnte) der Baum).
Martin Ender

Antworten:

6

Java

Mein Algorithmus für MM (5,8) punktet mit 177902 178006 182798 182697 mit einer maximalen Tiefe von 8 9 und benötigt nur wenige Sekunden (auf meinem langsamen Computer).

Eine Beispielausgabe einer Strategie für MM (2,3) mit score = 21, die von diesem Algorithmus gefunden wurde, sieht folgendermaßen aus:

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

Es gibt nichts Aufregendes an meinem Algorithmus. Keine Erfindung. Ich habe gerade die im Netz gefundenen Rezepte befolgt und in diesen Java-Code komprimiert. Die einzige Optimierung, die ich vorgenommen habe, ist der Versuch, die Codezeilen (in gewisser Weise) zu optimieren. Es geht so:

  1. Erstellen Sie die erste Menge S0 aller möglichen Codes, um die aktuelle Menge S zu sein.
  2. Der Codebrecher findet eine (gierige) gute Vermutung für S. Jede Vermutung führt zu einer Partition P von S, in der jede Teilmenge S 'alle Codes (von S) sammelt, die dieselbe Antwort auf die Vermutung haben. Eine gute Vermutung hat eine gute Partition, da diese die meisten Informationen für die Vermutung liefert.
  3. Nehmen Sie die gute Vermutung und sein P. Für jedes nicht leere S 'in P wenden Sie Codebreaker rekursiv an (Schritt 2).

@ MrBackend: Einen Prüfer zu schreiben ist schwierig, denke ich. ;-)

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

Einige Bemerkungen:

  1. Es ist keine Konsistenzprüfung erforderlich, da Sets S und ihre Partitionen (automatisch) konsistent erstellt werden.
  2. Es ist sinnvoll, eine gute Vermutung aus S0 (anstelle von S) zu ziehen. Aber ich verfolge diesen Ansatz im aktuellen Code nicht.
  3. Meine gierige Suche ist künstlich auf 200 Versuche beschränkt.
  4. Ich weiß, "die meisten Informationen für die Vermutung zu geben" ist nicht sehr genau. Die einfache Idee besteht darin, die Partition mit der meisten Anzahl von Teilmengen auszuwählen.
  5. Das Ergebnis hängt stark davon ab, wie Sie die Antwort berechnen (..). Schließlich habe ich Donald Knuths Gesichtsausdruck angepasst.

Die Strategie für MM(5,8) finden Sie hier . GitHub hat einige Probleme mit der Anzeige langer Zeilen. Klicken Sie daher auf die Schaltfläche Raw .

Bob Genom
quelle
Hi, wie man den Github- Text hübsch druckt, damit die Ergebnisse in eine Suchanleitung umgewandelt werden können. Ab dem ersten Startpunkt 'HHCAA' und dem nächsten Schritt, abhängig von der Antwort ... und bis zum nächsten und so weiter. Das aktuelle Rohtextformat ist nicht einfacher für das manuelle Scannen. Die Technik, die ich suche, ist, wie man die geschachtelten Klammern parst und ein schönes Tabellenlayout erhält, das bis zum Ende einfacher zu befolgen ist, ähnlich der Liste mit Aufzählungszeichen in der Frage für MM (2,3). Vielen Dank. Hoffe du kannst verstehen, wonach ich suche. (
Bevorzugen Sie
2

Rubin

BEARBEITEN: Es wurde eine Logik hinzugefügt, um unmögliche Vermutungen auszuschließen. Daher entsprechen die Strategien jetzt dem vorgegebenen Format und sind viel leichter zu handhaben.

Hier ist ein Versuch, dies in Gang zu bringen. Es ist ziemlich naiv (und nicht gut lesbar - es hilft, den if / elsif / else-Zweig von unten nach oben zu lesen).

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

Zuerst versuche ich 5 jede Farbe: AAAAA, BBBBBusw. Von diesem ich herausfinden , welche Farben tatsächlich in dem Muster verwendet werden. Und dann probiere ich einfach alle Permutationen der angegebenen Farben aus und lasse diejenigen weg, die von den schwarzen Stiften bereits ausgeschlossen wurden.

Hier ist die MM(2,3)Strategie:

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

Die Strategie für MM(5,8)dauert 376 KB und kann hier gefunden werden . GitHub hat einige Probleme mit der Anzeige langer Zeilen. Klicken Sie daher auf die Schaltfläche Raw .

Wenn ich jetzt einen Prüfer bekomme, kann ich Ihnen auch sagen, wie hoch meine tatsächliche Punktzahl ist. :)

Martin Ender
quelle
Es tut mir leid, dass der Prüfer noch nicht veröffentlicht wurde, aber er ist auf dem Weg ... Ihre (erste) MM (2,3) -Strategie ist nicht in Ordnung, zum Beispiel, wenn die Lösung AB lautet: Guess = AA; reply = 10; rate = BB; reply = 10, für die es keine Strategie gibt. Ich werde Ihren Vorschlag prüfen, Antworten zu gruppieren, aber dies sollte für gute Strategien nicht erforderlich sein, da die Menge der möglichen Lösungen für verschiedene Antworten nicht zusammenfällt.
MrBackend
@ MrBackend Guter Fang, ich habe dort einen Fall übersprungen. Es sollte jetzt behoben sein. Was die Grammatik angeht, ist es natürlich nicht notwendig für gute Strategien, aber ich dachte, Sie wären vielleicht bereit, die Messlatte ein wenig zu senken. ;) Wenn Leute einfachere Einsendungen einreichen können (wie meine), haben Sie vielleicht mehr Glück, wenn Sie interessante Einsendungen erhalten, die sich allmählich verbessern, anstatt alle kombinatorischen Elemente von Anfang an einzubeziehen.
Martin Ender
Hier ist der Deal: Ich beende den aktuellen Prüfer und veröffentliche ihn (als Web-App - es ist zu groß, um ihn hier einzufügen). Leider könnte es zu streng sein, da es unmögliche Antworten für einen Fehler hält. Danach passe ich es an, um mehrere Antworten zu unterstützen, und sende nur Warnungen für unmögliche Antworten aus. Allerdings muss Ihre 1,3-G-MM (4,4) -Strategie viele unmögliche Antworten und / oder nicht reduzierende Vermutungen enthalten, da die geschätzte Größe einer anständigen MM (5,8) -Strategie eine Handvoll Megabyte beträgt.
MrBackend
@ MrBackend Natürlich enthalten meine Strategien eine Menge unmöglicher Antworten. Das habe ich mit "Ich mache keine Kombinatorik" gemeint. ;) Wenn es zu mühsam ist, das zu unterstützen und Antworten zu gruppieren, mach dir keine Sorgen, dann werde ich versuchen, unmögliche Vermutungen auszulassen.
Martin Ender
@ MrBackend Gute Nachricht, ich habe es behoben. :) Ich hoffe die Strategie ist jetzt gültig. Lassen Sie mich wissen, wenn es noch Probleme gibt.
Martin Ender