Der 5-Züge-Code: Warum Donald Knuth jedes Mastermind-Rätsel knackte

Ein verdeckter vierstelliger Code, sechs oder acht Farben und der gegnerische Kopf, der nach jedem Versuch nur stumme Rückmeldungen gibt: Ein schwarzer Stift für richtige Farbe am richtigen Platz, ein weißer für richtige Farbe am falschen Platz. Mastermind – im deutschsprachigen Raum als „Superhirn“ bekannt – gilt seit den 1970er Jahren als Maßstab für logisches Denken.

Für Gelegenheitsspieler ist es ein Ratespiel, bei dem man hofft, vor dem zehnten Versuch den richtigen Riecher zu haben. Für Mathematiker war es ein gefundenes Fressen.

Donald Knuths 5-Züge-Beweis

Im Jahr 1977 nahm sich kein Geringerer als Informatik-Legende Donald Knuth (Stanford University) das Spiel vor. Bei vier Steckplätzen und sechs Farben gibt es exakt 1.296 mögliche Kombinationen (bei acht Farben sogar 4.096).

Knuth bewies mit seinem Minimax-Algorithmus etwas Erstaunliches: Völlig egal, welchen geheimen Code der Gegner gewählt hat – jedes einzelne Mastermind-Rätsel lässt sich in maximal fünf Zügen mit hundertprozentiger Sicherheit lösen.

Der Schlüssel liegt darin, nicht zu versuchen, die richtige Lösung zu erraten. Stattdessen setzt man in jedem Schritt genau die Farbkombination, die im schlechtestmöglichen Fall („Worst Case“) den verbleibenden Suchraum am stärksten schrumpfen lässt.

Der perfekte Eröffnungszug

Fast alle Anfänger beginnen mit vier verschiedenen Farben (etwa Rot-Blau-Grün-Gelb), um möglichst viele Farben auf einmal abzutesten.

Knuth bewies, dass genau das suboptimal ist. Der mathematisch perfekte Startzug ist fast immer ein Doppelpaar (etwa Rot-Rot-Blau-Blau oder 1-1-2-2):

• Steckt man vier verschiedene Farben und erhält die Antwort „Null Treffer“, schließt man zwar vier Farben aus – aber bei einem Treffer weiß man nicht, welche der vier Farben gemeint ist.
• Steckt man zwei Paare, spaltet die Antwort der Stifte die 1.296 Möglichkeiten in viel gleichmäßigere Teilmengen auf. Der Informationsgewinn ist messbar höher.

Denken wie ein Tresorknacker

Wer Mastermind beherrschen will, trennt sich von vagen Vermutungen. Jeder weiße und schwarze Stift ist ein mathematischer Filter. An unserem Tisch Tresorknacker geht es nicht um bunte Plastikstifte, sondern um die schwere Mechanik eines Mafia-Panzerschranks der 1920er Jahre: Dreh das Schloss, lies die Bolzen – und knack die Kombination, bevor die Wachleute die Treppe herunterkommen.