# Mastermind (Spiel)

Mastermind, auch SuperHirn, in der DDR auch als Super Code, Variablo und LogikTrainer bekannt, ist ein Logikspiel für zwei Personen, bei dem eine Farbreihenfolge durch sukzessive Vermutungen ermittelt werden soll. Das Spiel wurde 1970 von Mordechai Meirovitz erfunden und entwickelte sich zu einem der erfolgreichsten Spiele der 1970er. Bis 2000 wurden über 55 Millionen Spiele in 80 Ländern verkauft.

## Geschichte

Mastermind wurde 1970 von Mordechai (Marco) Meirovitz, einem in Paris lebenden israelischen Telekommunikationsexperten, erfunden. Nachdem mehrere Spielefirmen das Spiel ablehnten, stellte er das Spiel 1971 auf der Nürnberger Spielwarenmesse vor. Die von Edward Jones-Fenleigh 1946 gegründete kleine englische Firma Invicta Plastics aus Leicester kaufte alle Rechte. Jones-Fenleigh verfeinerte das Spiel und veröffentlichte es dann 1971/72 als Mastermind. Es war sofort sehr erfolgreich und wurde im Vereinigten Königreich als erstes Game of the Year 1973 von der British Association of Toy Retailers ausgezeichnet; bis dahin hatte die British Association of Toy Retailers seit 1965 jedes Jahr ein Spielzeug (Toy of the Year) prämiert.
Das Spiel erschien 1973 bei Parker Brothers, 1981 bei Pressman Toy und bei vielen anderen Verlagen. Es erschienen auch mehrere Varianten bei verschiedenen Verlagen.
Mastermind für vier Spieler wurde 1980 patentiert.
Im deutschsprachigen Raum wurde es anfangs unter Namen SuperHirn und später auch als Mastermind vertrieben. In der DDR wurde es unter Logik Trainer oder Super Code (VEB Plasticart) verkauft und im englischsprachigen Raum hauptsächlich als Mastermind vertrieben. Eine Variante mit zwei mal drei Stiften, bei der zwei Spieler gegenseitig raten, wurde unter der Bezeichnung Variablo in der DDR hergestellt (VEB Plastspielwaren Berlin).
Mit Stand des Jahres 2000 hat Invicta das Spiel an Hasbro, Pressman Toy und Orda Industries lizenziert.

## Spielbrett und Spielprinzip

Als Spielbrett dient eine Lochplatte mit hintereinander angeordneten Viererreihen Rundlöcher zur Aufnahme pilzförmiger Farbsteine und parallel daneben jeweils vier kleinere Löcher in quadratischer Anordnung zur Aufnahme nagelförmiger Stifte.
Ein Spieler (der Codierer) legt zu Beginn verdeckt einen vierstelligen geordneten Farbcode fest, der aus sechs Farben ausgewählt wird; jede Farbe kann auch mehrmals verwendet werden. Der andere Spieler (der Rater) versucht, den Code herauszufinden. Dazu setzt er einen gleichartigen Farbcode als Frage; beim ersten Zug blind geraten, bei den weiteren Zügen mit Hilfe der Antworten zu den vorangegangenen Zügen.
Auf jeden Zug hin bekommt der Rater die Information, wie viele Stifte er in Farbe und Position richtig gesetzt hat und wie viele der übrigen Stifte zwar die richtige Farbe haben, aber an einer falschen Position stehen. Ein Treffer in Farbe und Position wird durch einen schwarzen Stift angezeigt, ein farblich richtiger Stift an falscher Stelle durch einen weißen Stift.
Genauer: Wenn das Tupel $(c_{i})=(c_{1},\cdots ,c_{4})$ der zu bestimmende Code ist und $(r_{i})$ vom Rater gesetzt wurde, dann ist die Zahl der schwarzen Stifte
    $s=|\{i\,|\,r_{i}=c_{i}\}|$,
also die Zahl der Positionen $i$, an denen der Rater einen richtigen Stift gesetzt hat. Die Zahl $w$ der weißen Stifte ergibt sich so, dass die Summe $s+w$ der Stifte die maximale Zahl an Übereinstimmungen ist, die man durch Permutieren von $(r_{i})$ erhalten kann:
    $s+w=\max _{k}\,|\{i\,|\,r_{\pi _{k}(i)}=c_{i}\}|$.
Ziel des Raters ist es, den Farbcode mit möglichst wenigen Fragen zu erraten. Der Codierer darf seine Farbreihe nicht verändern und muss zu jeder Frage die zutreffende Anzahl schwarzer und weißer Stifte setzen. Alle Fragen und Antworten bleiben bis zum Ende des Spiels gesteckt.
Es gibt auch Varianten mit zwei Spielbrettern, wo jeder zugleich auf einem Brett Rater und auf dem anderen Brett Codierer ist und beide abwechselnd fragen.

## Beispiel

Gesucht ist der Farbcode:
grün – rot – blau – grün
1. Rateversuch: rot – gelb – rot – grün
Antwort: Einmal schwarz (weil an der vierten Position grün richtig ist), einmal weiß (weil rot im gesuchten Code einmal vorkommt, aber nicht an der ersten oder dritten Stelle).
2. Rateversuch: grün – grün – orange – rot
Antwort: Einmal schwarz (weil grün diesmal an der ersten Position richtig ist), zweimal weiß (weil 1. grün im gesuchten Code ein zweites Mal vorkommt, aber nicht an der zweiten Position und 2. rot im gesuchten Code vorkommt, aber nicht an der vierten Position).
Wenn der richtige Farbcode gefunden wurde, lautet die Antwort viermal schwarz. Der ratende Spieler hat normalerweise zwölf Versuche, um die richtige Lösung zu finden. Je nach Ausführung des Spiels kann diese Anzahl variieren; die kleinere Reise-Ausführung bietet nur Platz für sechs Versuche.

## Ergebnisraum
### Mastermind

Die Anzahl der möglichen Codes beträgt $6^{4}=1296$. Bei 6 Farbcodes besitzen alle 4 Stifte die gleiche Farbe, bei 210 gibt es genau 2 Farben (davon 90 mal 2+2 Stifte und 120 mal 3+1 Stifte), bei 720 gibt es genau 3 Farben (2+1+1 Stifte), und bei 360 Farbcodes haben alle 4 Stifte unterschiedliche Farben. Bei einer Mastermind-Variante mit 8 Farbcodes für die vier Steckplätze beträgt die Anzahl der möglichen Codes 4096.

### Super Mastermind

Bei der 1975 erschienenen Super Mastermind Version sind 5 Löcher und 8 Farben vorhanden. Die Anzahl der möglichen Codes beträgt dort: $8^{5}=32768$.
Wie beim originalen Mastermind stehen dem Spieler 12 Versuche zu, die Aufgabe zu lösen.

### Variante mit Lücken als zusätzliche Farbe

Häufig wird vereinbart, dass Steckplätze freigelassen werden dürfen. Diese Lücken gelten wie eine zusätzliche (gedachte) Farbe. Dadurch erhöht sich die Anzahl der möglichen Codes beim Standard-Mastermind auf $7^{4}=2401$ und beim Super-Mastermind auf $9^{5}=59049$.

## Strategien

Ein guter Mastermind-Spieler benötigt Kombinationsgabe und logisches Denkvermögen.
Im Rahmen mathematischer Untersuchungen kann die Suchstrategie im Mastermind-Spiel unter verschiedenen Gesichtspunkten optimiert werden. Als Kriterium wird dabei entweder der schlechtest mögliche Fall (Worst Case), der wahrscheinlichkeitstheoretische Durchschnitt (Average Case) oder der spieltheoretische Minimax-Wert zugrunde gelegt:

### Worst-Case-Optimierung

Donald E. Knuth hat 1976 gezeigt, dass es möglich ist, jeden möglichen Farbcode des Spiels (4 Stellen, 6 Farben) in maximal fünf Zügen zu ermitteln. Dazu beginnt der Ratende mit einem Farbcode, der zwei Farben jeweils doppelt enthält. Diese Verfahrensweise, aber auch jeder nachfolgend geratene Farbcode, kann nach einem einheitlichen Verfahren mit Minimax-Charakter abgeleitet werden: Rate stets einen solchen Farbcode, bei dem das Maximum der Anzahlen von Farbcodes, die nach den diversen Antwortmöglichkeiten auf den aktuellen Rateversuch noch denkbar sind, möglichst klein ist.

### Average-Case-Optimierung

Kenji Koyama und Tony W. Lai fanden 1994 eine Mastermind-Strategie, die im Durchschnitt nur 5625/1296 = 4,340 Versuche benötigt, sofern man annimmt, dass die zu suchende Kombination gleich wahrscheinlich unter den 1296 Möglichkeiten zufällig ausgelost wird. Diese Strategie – und jede andere, die im Durchschnitt genauso schnell ist – benötigt im schlechtesten Fall sechs Versuche. Sie bewiesen außerdem, dass es in Bezug auf den Durchschnitt keine schnellere Strategie geben kann.
Kenji Koyama und Tony W. Lai fanden ihre Strategie durch eine Bruteforce-Berechnung aller nur möglichen Strategien. Durch einen Trick ist es ihnen gelungen, den Suchraum so zu verkleinern, dass eine vollständige Bruteforce-Suche mit der 1994 zur Verfügung stehenden Hardware möglich war.

### Minimax-Strategie

Berücksichtigt man auch den strategischen Einfluss des Codierers, so ergibt sich für die Suchlänge ein spieltheoretischer Minimax-Wert von 5600/1290 = 4,341. Dabei wählt der Codierer seinen Code unter allen 1290 Codes mit mindestens zwei Farben gleich wahrscheinlich aus. Die Berechnungen dazu wurden unabhängig voneinander erstmals von Tom Nestor (1985) und einige Jahre später von Mike Wiener durchgeführt.

## Varianten

Neben diesem klassischen Mastermind gibt es die erweiterte Variante Super Mastermind mit fünf Steckplätzen und acht Farben. Im deutschsprachigen Raum heißt sie SuperHirn professional (Parker).
Darüber hinaus gibt es auch ein „Grand Mastermind“. Bei dieser Variante muss der Spieler ebenfalls einen Code aus vier Elementen knacken, wobei diese Elemente jedoch aus einer Kombination einer Farbe mit einer Form gebildet werden. Es gibt fünf verschiedene Farben und fünf verschiedene Formen. Darüber hinaus gibt es drei „Antwortstifte“. Schwarz steht für eine vollständig richtige Antwort (Kombination und Stelle korrekt), blau für eine teilweise richtige Antwort, und weiß für ein richtiges Farbe/Form-Paar an der falschen Stelle.
Word Mastermind nennt sich eine Variante, in dem der Codierer statt eines Farbcodes ein vierbuchstabiges sinntragendes Wort legt. Der Ratende muss versuchen, das gelegte Wort durch ebenfalls sinntragende Wörter zu erraten.