¶ Mastermind
Mastermind, auch als SuperHirn oder Supercode bekannt, ist ein Logikspiel für zwei Spieler:innen mit dem Ziel, einen Farbcode sukzessive zu erraten. Es ist eines der beliebtesten Spiele der 1970er Jahre.
¶ Geschichte
Mastermind wurde 1970 bis 1971 vom israelischen Ingenieur Mordecai Meirowitz entwickelt. Obwohl viele Spielehersteller das Spiel zunächst nicht vertreiben wollten, entwickelte es sich nach dem Kauf durch das Unternehmen Invicta Plastics zu einem der erfolgreichsten Spiele der 70er und zu einem der bekanntesten Denkspiele weltweit.[1] Da es sich bei Mastermind eher um ein passives Spiel handelt, bei dem ein Spielender (der Codemaker) lediglich Feedback gibt, kann es eher als Puzzle denn als klassisches Spiel verstanden werden.
¶ Vorgänger und verwandte Spiele
Mastermind ist nicht das einzige Codebreaking-Spiel seiner Art; es ist eine Sonderform des Bulls and Cow-Spiels. Bereits Ende der 60er Jahre wurde am MIT von J. M. Grochow ein Programm namens MOO mit ähnlichen Spielprinzip entwickelt, das für Computer verfügbar war. Statt eines Farbcodes muss bei MOO ein vierstelliger numerischer Code erraten werden. Sobald eine Zahl vollständig richtig (also die richtige Zahl am richtigen Ort) platziert wurde, erhält der ratende Spielende einen "Bull"; wenn die Zahl zwar im Code vorkommt, aber an anderer Stelle, erhält die spielende Person als Feebdack eine "Cow".
Auch nach der Hochphase von Mastermind in den 70er Jahren reißt das Interesse an Bulls and Cow-Spielen nicht ab. Das populäre Online-Spiel Wordle ist im Wesentlichen nichts weiter als eine wörterbasierte Version des Spiels, bei der Spieler:innen für jede Stelle des fünfbuchstabigen Wortes insgesamt 26 Möglichkeiten haben.
¶ Spielprinzip und Regeln
Mastermind wird von zwei Spieler:innen über eine gerade Anzahl von Runden gespielt. In jeder Runde ist einer der beiden Spielenden abwechselnd der codierende Spielende, der im Vorhinein den zu erratenden Farbcode festlegt und dessen Aufgabe es ist, die Vorschläge seines Mitspielenden nach jedem Raten zu bewerten. Sobald der geheime Farbcode erraten wurde oder die Anzahl an Rateversuchen überschritten ist, endet die Spielrunde und die Spieler:innen tauschen die Rollen. Die Person, die zum Ende des Spiels die meisten Runden gewonnen hat, gewinnt.
¶ Ablauf einer Runde
- Der codierende Spielende wählt einen geheimen, vierstelligen Farbcode aus sechs Farben aus und platziert diesen im dafür vorgesehenen Spielbereich.
- Der ratende Spielende versucht, den geheimen Code herauszufinden, indem eine Kombination von Farben in einer bestimmten Reihenfolge vorgeschlagen und auf dem Spielbrett pkatziert wird.
- Nach jedem Raten gibt der Codierende Feedback in Form eines farbigen Pins.
- Weißer Pin: Eine Farbe wurde korrekt geraten, ist aber an einer anderen Position.
- Roter Pin: Eine Farbe und deren Position wurden korrekt geraten.
Feedback und Analyse:
- Der Ratende nutzt das Feedback, um seine Versuche zu optimieren und den geheimen Code schnellstmöglich zu knacken. Wenn eine zuvor festgelegte Anzahl an Rateversuchen (zumeist zwölf) überschritten ist, verliert der Ratende. Anderenfalls verliert der codierende Spielende.
Ein Beispiel für eine fertiggestellte Runde ist auf folgender Abbildung zu sehen:
¶ Varianten
Es gibt verschiedene Varianten von Mastermind, die sich nicht hinsichtlich der Regeln, sondern vor allem hinsichtlich des möglichen Ergebnisraumes unterscheiden. Die algorithmischen Ansätze zur Lösung der verschiedenen Mastermind-Varianten unterscheiden sich im Großen und Ganzen nicht, die Laufzeit verschiedener Algorithmen kann durch die Größe des Suchraumes allerdings beeinflusst werden.
¶ Traditionelle Variante
In der traditionellen Variante von Mastermind gibt es mögliche Farbcodes, da ein vierstelliger Code bestehend aus sechs möglichen Farben ausgewählt werden muss. Für die Farbverteilung innerhalb der möglichen Codes gilt:
| Anzahl an Farben im Code | Anzahl der Codes |
|---|---|
| Einfarbiger Code | 6 |
| Zweifarbiger Code | 210 |
| Dreifarbiger Code | 720 |
| Vierfabiger Code | 360 |
¶ Supermastermind
In einer anderen Variante des Spiels, die auch als Supermastermind[2] bekannt ist, vergrößert sich der Ergebnisraum. Der gesuchte Farbcode ist nun fünfstellig und es gibt insgesamt acht Farben zur Auswahl, sodass es mögliche Codes gibt.
¶ Lücken als Farbe
Eine Abwandlung des Spiels stellt es dar, wenn Lücken als zusätzliche Farbe[3] gewertet werden können. Auf diese Weise gibt es in der traditionellen Variante von Mastermind Möglichkeiten für die Auswahl eines Farbcodes. Zentraler Vorteil dieser Variante ist es, dass sie kein verändertes Spielfeld bedarf.
¶ Lösungsansätze
Mastermind kann mithilfe verschiedener Algorithmen gelöst werden.
¶ Donald E. Knuths Algorithmus
Der wohl bekannteste Algorithmus zur Lösung von Mastermind ist der Five-Guess-Algorithmus von Donald E. Knuth aus dem Jahre 1977. Er findet eine Lösung im traditionelle Mastermind-Spiel mit sechs Farben und einem vierstelligen Farbcode in maximal fünf Zügen (durchschnittlich beträgt die benötigte Zugzahl Züge). Die zugrundeliegende Idee ist, dass der ratende Spieler in jedem Zug den Guess wählt, der die Anzahl an maximal verbleibenden gültigen Farbcodes minimiert.
Die möglichen Codes werde als vierstellige Zahlen mit Ziffern von 1 bis 6 repräsentiert und die möglichen Resultate sind numerisch dargestellte Kombinationen von roten und weißen Pins: die erste Zahl steht für die Anzahl an roten und die zweite Zahl für die Anzahl an weißen Pins.
¶ Pseudocode
Der Pseudocode für den Algorithmus sieht wie folgt aus:
possible_codes = [1111, 1112, ..., 6666];
secret_code = select random code out of possible_codes;
results = [00, 01, 02, ..., 40]
guess = 1122;
res = getResult(secret_code, guess);
while res != 40:
remove guess from possible_codes;
for code in possible_code:
cmp_res = getResult(guess, code);
if cmp_res != res:
remove code from possible_codes;
minmax(possible_codes);
Zunächst werden alle Möglichkeiten für den Farbcode in einem Set gespeichert. Der geheime Code ist ein zufälliger, aus diesem Set ausgewählter Code. Das Zielergebnis ist kodiert als 40, was vier rote Pins repräsentiert.
In Zeile 5 wird als initialer Guess 1122 gewählt. Anschließend wird mithilfe der getResult()-Funktion überprüft, zu welchem Ergebnis der Guess führen würde. Solange dieses Ergebnis nicht 40 (also vier rote Pins) ist, wird die Menge der möglichen Codes auf folgende Weise reduziert: Betrachte den aktuellen Guess als Geheimcode und schaue, zu welchem Ergebnis jeder mögliche Code aus dem initial aufgestellten Set führen würde. Wenn das Ergebnis sich vom im Zeile 6 erhaltenen Resultat unterscheidet, wird der untersuchte Code aus dem Set entfernt. Das liegt daran, dass alle Codes, die nicht zum selben Ergebnis führen wie dem ursprünglich erhaltenen Ergebnis, als Ergebnis nicht infrage kommen können.
In Zeile 12 wird der näcchste Guess ausgewählt. Hierfür wird eine Minmax-Strategie mit dem Ziel, den Code zu wählen, der zu einer größtmöglichen Verringerung der Ratemöglichkeiten führt, verfolgt. Der Minmax-Algorithmus agiert wie in folgendem Pseudocode beschrieben:
S = possible_codes;
guesses = [];
for guess in S:
solutions = {};
for try in S:
res = getResult(try, guess);
solutions[res].append(try);
guesses.append(min(solutions));
return min(guesses);
Die zwei verschachtelten Schleifen iterieren über alle Codes, die noch im Set vorhanden sind. Für jede Komboniation von Codes aus dem Set wird das Resultat berechnet und der Versuch wird in einem Dictionary an der dem Ergebnis entsprechenden Stelle hinzugefügt. Beispiel: Wenn der Guess 1122 gegen den Versuch 1143 getestet wird, wird ist das Resultat 20 und am Key 20 im Dictionary solutions wird der Versuch 1143 in einer Liste abgespeichert.
Auf diese Weise entsteht einsteht eine Art Tabelle mit den möglichen Ergebnissen zu jedem Guess. In Zeile 8 fügen wir den Guesses die Liste aus dem Dictionary mit den wenigsten Einträgen hinzu. Nachdem alle Kombinationen ausgetestet wurden, gibt die Funktion die Liste von Guesses zurück, die die wenigsten Einträge enthält. Aus dieser Liste wird nach Donald Knuth[4] der Eintrag als nächster Guess gewählt, der chronologisch zuerst dran ist.
¶ Die Wahl des initialen Guesses
Die Wahl des initialen Guesses ist ausschlaggebend für den Erfolg des Algorithmus; andere initiale Codevorschläge wie 1234 führen zu keinem Erfolg in fünf Zügen[4:1]. Auch hier wird die bereits beschriebene Minmax-Strategie angewendet. Exemplarisch sei hier die Auswahl des ersten Zuges mit konkreten Zahlenwerten dargestellt:
Zu Beginn eines Spiels können fünf verschiedene Arten von intialen Guesses gespielt werden:
- A: vier Mal dieselbe Farbe (z.B. 1111)
- B: drei Mal dieselbe Farbe und eine weitere (z.B. 1112)
- C: zwei Mal zwei geiche Farben (z.B. 1122)
- D: zwei Mal dieselbe Farbe und je ein Mal eine weitere (z.B. 1123)
- E: vier verschiedene Farben (z.B. 1234)
Es stellt sich nun die Frage, welcher initiale Guess zu einer größten Verringerung der Ratemöglichkeiten führt. Folgende Tabelle[5] listet die initialen Ratemöglichkeiten auf und zeigt, wie viele Ratemöglichkeiten in Abhängigkeit vom Feedback verbleiben.
| Antwort | A | B | C | D | E |
|---|---|---|---|---|---|
| 00 | 625 | 256 | 256 | 81 | 16 |
| 01 | unmöglich | 308 | 256 | 276 | 162 |
| 02 | unmöglich | 61 | 96 | 222 | 312 |
| 03 | unmöglich | unmöglich | 16 | 44 | 136 |
| 04 | unmöglich | unmöglich | 1 | 2 | 9 |
| 10 | 500 | 317 | 256 | 182 | 108 |
| 11 | unmöglich | 156 | 208 | 230 | 252 |
| 12 | unmöglich | 27 | 36 | 84 | 132 |
| 13 | unmöglich | unmöglich | unmöglich | 4 | 8 |
| 20 | 150 | 123 | 114 | 105 | 96 |
| 21 | unmöglich | 24 | 32 | 40 | 48 |
| 22 | unmöglich | 3 | 4 | 5 | 6 |
| 30 | 20 | 20 | 20 | 20 | 20 |
| 40 | 1 | 1 | 1 | 1 | 1 |
Wir betrachten nun die größte Zahl in jeder Spalte und wählen die Spalte aus, bei der diese Zahl am kleinsten ist. Dies ist offensichtlich die Spalte C, die die Ratemöglichkeit "Zwei Mal dieselbe Farbe" repräsentiert.
Anmerkung: Natürlich kommt nicht nur der initale Guess 1122 infrage, auch andere initale Ratemöglichkeiten wie 2233 führen selbstverständlich zum selben Ergebnis.
¶ Optimierungsmöglichkeiten
Der obige Algorithmus kann noch verbessert werden, indem als infrage kommende nächste Guesses nicht nur die im Set verbleibenden Codes betrachtet werden. Stattdessen kann ein Set mit allen Codes außer der bereits gespielten herangezogen werden[6]. Dies hat den Vorteil, dass unter Umständen ein Zug gewählt wird, der zu einer optimaleren (größeren) Verringerung von Ratemöglichkeiten führt.
¶ Genetische Algorithmen
Neben Knuths Algorithmus werden zur Lösung von Mastermind sogenannte Genetische Algorithmen eingesetzt. Diese sind besonders vielversprechend bei Problemen, die aufgrund ihrer Komplexität vielfach nur ineffizient gelöst werden können. Im Durchschnitt brauchen sie zum Teil zwar weniger Züge als der Algorithmus von Knuth; der Worst-Case liegt aber darüber[7]. Die meisten genetischen Algorithmen spielen einen Zug, sobald er machbar ist. Berghman et al. erzielen interessante Verbesserungen, indem sie auch die Vorhersagekraft eines Guesses in ihre Heuristik einfließen lassen.
¶ Komplexität
Mastermind ist NP-vollständig. Stuckman und Zhang[8] zeigen dies über das Mastermind Satisfiability Problem.
Definition Mastermind Satisfiability Problem (MSP)
Erhalte als Input , eine Teilmenge aller möglichen Farbcodes, und für jedes einen Mastermind-Score. Die Frage, die das Entscheidungsproblem stellt, ist dann folgende: Gibt es einen Guess , der das Rätsel löst, oder nicht?
Dieses Entscheidungsproblem ist NP-vollständig. Offensichtlich gilt, dass eine Lösung in Polynomialzeit überprüft werden kann, denn es ist möglich, die Farbe und Position der Pins in Polynomialzeit zu überprüfen. Stuckman und Zhang beweisen die NP-Vollständigkeit durch eine Reduktion vom Vertex-Cover-Problem, indem sie Instanzen von Vertex-Cover in MSP-Instanzen übersetzen.
Auch für eine andere Version von Mastermind, bei der das Feedback lediglich durch rote Pins erfolgt, bekannt als "single-count" Version, wurde die NP-Vollständigkeit von Goodrich nachgewiesen.[9]
¶ Referenzen
Toby Nelson. A Brief History of the Master Mind Board Game. https://web.archive.org/web/20070812112301/http://www.tnelson.demon.co.uk/mastermind/history.html ↩︎
Jumbo. Mastermind Spielanleitung. https://www.spiele4us.de/wp-content/uploads/2022/10/super-mastermind-5-loecher-8-farben-gebraucht-g002301770.pdf ↩︎
Wikipedia. Mastermind Ergebnisaum. https://de.wikipedia.org/wiki/Mastermind_(Spiel)#Ergebnisraum ↩︎
Knuth, Donald E. (1976-1977): The Computer as Mastermind, in: J. Recreational Mathematics Vol. 9(1). pdf ↩︎ ↩︎
Meinstein.ch. Mathematische Strategie bei Mastermind. https://meinstein.ch/math/mathematische-strategie-bei-mastermind/ ↩︎
NathanDuran, Five-Guess-Algorithmus auf GitHub, https://github.com/NathanDuran/Mastermind-Five-Guess-Algorithm ↩︎
Berghman, Lotte, Goossens, Dries and Leus, Roel (2009): Efficient solutions for Mastermind using genetic algorithms, in: Computers & Operations Research 36, p. 1880-1885. pdf. ↩︎
Stuckman, Jeff and Zhang, Guo-Qiang (2005): Mastermind is NP-Complete. pdf ↩︎
Goodrich, Michael T. (2009): On the algorithmic complexity of the Mastermind game with black-peg results, in: Information Processing Letters 109, p. 675–678. pdf. ↩︎