Drahtzieher

„Mastermind“ ist ein Spiel zum Entschlüsseln von Codes, bei dem ein Spieler (oder der Computer) einen geheimen Code festlegt – eine Reihenfolge farbiger Stifte – und der andere Spieler versucht, diesen innerhalb einer begrenzten Anzahl von Versuchen zu erraten. Nach jedem Versuch gibt der Code-Ersteller eine Rückmeldung, wie viele Stäbchen die richtige Farbe an der richtigen Position haben (schwarze Stäbchen) und wie viele die richtige Farbe, aber an der falschen Position haben (weiße Stäbchen). Die klassische Version verwendet 4 Positionen und 6 Farben, was 10 bis 12 Versuche ermöglicht.

Regeln

1. Der Codemacher erstellt einen geheimen Code aus 4 farbigen Stäbchen, die aus 6 möglichen Farben ausgewählt werden. Gleiche Farben sind zulässig.
2. Der Codeknacker macht einen Versuch, indem er 4 farbige Stäbchen in einer Reihe platziert.
3. Der Codemacher gibt Feedback anhand der Stäbchen:

• Schwarzer Stecker: Ein Stecker hat die richtige Farbe an der richtigen Position.
• Weißer Stecker: Ein Stecker hat die richtige Farbe, befindet sich jedoch an der falschen Position.

1. Jede Farbe im Tipp darf höchstens einmal vorkommen: Exakte Übereinstimmungen (schwarz) haben Vorrang vor Farbübereinstimmungen (weiß).
2. Der Codeknacker nutzt das Feedback, um nachfolgende Vermutungen zu verfeinern.
3. Das Spiel endet, wenn der Code richtig erraten wurde oder die maximale Anzahl an Versuchen ausgeschöpft ist.

Strategien

• Knuths Algorithmus: Im Jahr 1977 bewies Donald Knuth, dass das klassische „Mastermind“-Spiel mit 4 Stiften und 6 Farben immer in höchstens 5 Versuchen gelöst werden kann. Sein Minimax-Algorithmus beginnt mit dem Versuch (1, 1, 2, 3) und wählt jeden nachfolgenden Versuch so aus, dass die Anzahl der verbleibenden Möglichkeiten im schlimmsten Fall minimiert wird.
• Optimierung des ersten Versuchs: Beginne mit einer Vermutung, die zwei Farbpaare enthält (z. B. AABB). Dies liefert maximale Informationen darüber, welche Farben vorhanden sind.
• Ausgeschlossene Codes im Blick behalten: Schließe nach jeder Rückmeldung gedanklich oder physisch alle Codes aus, die mit der bisher erhaltenen Rückmeldung unvereinbar sind. Dein nächster Tipp sollte mit allen bisherigen Rückmeldungen übereinstimmen.
• Informationsmaximierung: Wähle Tipps, die die verbleibenden Möglichkeiten in möglichst gleich große Gruppen aufteilen. Der Tipp, der die gleichmäßigste Aufteilung ergibt, liefert unabhängig von der Rückmeldung die meisten Informationen.
• Farben zählen: Nutzen Sie frühe Vermutungen, um festzustellen, welche Farben im Code vorkommen und wie oft. Sobald Sie die Farbzusammensetzung kennen, konzentrieren Sie sich darauf, die richtige Anordnung zu finden.
• Ausschlussverfahren: Erhält eine Vermutung das Feedback „0 Schwarz, 0 Weiß“, kommt keine dieser Farben im Code vor. Dies kann den Suchraum drastisch einschränken.

Mastermind wurde 1970 von Mordecai Meirowitz, einem israelischen Postmeister und Telekommunikationsexperten, erfunden. Nachdem mehrere Spielzeughersteller das Spiel abgelehnt hatten, wurde es schließlich von Invicta Plastics, einem kleinen britischen Unternehmen mit Sitz in Leicester, England, hergestellt und vertrieben. Das Spiel kam 1971 auf den Markt und wurde zu einem internationalen Sensationserfolg, der sich in den ersten zehn Jahren über 50 Millionen Mal verkaufte.

Das Design des Spiels wurde von einem älteren Bleistift-und-Papier-Spiel namens „Bulls and Cows“ (auch bekannt als „Moo“) beeinflusst, dessen Ursprünge mindestens bis ins frühe 20. Jahrhundert zurückreichen. Bei „Bulls and Cows“ erraten die Spieler eine geheime Zahl und erhalten Rückmeldung über richtige Ziffern an der richtigen Stelle („Bulls“) und richtige Ziffern an der falschen Stelle („Cows“). Meirowitz’ Innovation bestand darin, dieses abstrakte Zahlenspiel in ein visuell ansprechendes Brettspiel mit farbigen Spielsteinen zu verwandeln und es so einem breiteren Publikum zugänglich zu machen.

„Mastermind“ erregte große Aufmerksamkeit bei Mathematikern und Informatikern. Im Jahr 1977 veröffentlichte Donald Knuth eine bahnbrechende Abhandlung, in der er nachwies, dass der Codeknacker den Code mithilfe einer Minimax-Strategie stets in höchstens fünf Versuchen ermitteln kann. Diese Analyse verband das Spiel mit der Informationstheorie, der Kombinatorik und dem Algorithmusdesign. Das Problem der optimalen Mastermind-Strategie wurde seitdem intensiv untersucht, wobei Varianten mit unterschiedlicher Anzahl von Stiften und Farben hinsichtlich ihrer rechnerischen Komplexität analysiert wurden – tatsächlich wurde 2005 nachgewiesen, dass Mastermind mit einer beliebigen Anzahl von Stiften und Farben NP-vollständig ist.

Das Spiel hat zahlreiche Varianten hervorgebracht, darunter „Super Mastermind“ (5 Stifte, 8 Farben), „Grand Mastermind“ (5 Stifte mit Musterformen) und elektronische Versionen. Es hat auch das Spieldesign im weiteren Sinne beeinflusst, wobei die Mastermind-Mechanik in Videospielen wie „Fallout“ (Terminal-Hacking) und dem Handyspiel „Wordle“ (das einen ähnlichen Feedback-Mechanismus beim Wortraten anwendet) auftaucht. Mastermind ist nach wie vor ein fester Bestandteil von Logikspiel-Sammlungen und ein beliebter Einstieg in das kombinatorische Denken.