Die Spielidee ist folgende: ein Spieler, der Kodierer, steckt verdeckt mit farbigen Stiften einen vierstelligen Farbcode, der aus sechs verschiedenen Farben bestehen kann; die Farben können auch mehrfach verwendet werden. Der andere Spieler, der Code-Knacker, versucht anschließend den Code zu erkennen. Dazu steckt er ebenfalls einen Farbcode mit Hilfe der farbigen Stecker. Nach jedem Zug bekommt er von dem Codierer die Information, wieviele Stecker er in Farbe und Position richtig gesetzt hat (wird durch schwarze/rote Marker bezeichnet), und wieviele Stecker er zwar in der richtigen Farbe gewählt, aber an eine falsche Position gesteckt hat (weißer Marker). Nun gilt es durch Raten (besser: Schlussfolgern) in höchstens zehn Versuchen, den geheimen Farbcode zu erkennen.
Spiele, die ähnlich funktionieren, aber als Elemente für den Geheimcode Buchstaben bzw. Zahlen benutzen, sind das Wort-Spiel "Jotto" sowie das Zahlenspiel "Bulls and Cows".
Bei Jotto geht es darum, ein Wort herauszufinden; dabei erhält man mit jedem Rateversuch nur Hinweise über die Anzahl der Buchstaben, die mit dem geheimen Wort übereinstimmen. Ob die Position korrekt ist, erfährt man nicht; dafür muss das Wort ein sinnvolles sein.
Bulls and Cows wird genauso gespielt wie MASTERMIND®, nur eben mit Zahlen. Die "Bulls" geben die richtigen Ziffern an der richtigen Stelle an (die schwarzen bzw. roten Stecker bei MASTERMIND®), die "Cows" geben die Anzahl der richtigen Ziffern an einer falschen Position an (weiße Stecker bei MASTERMIND®).
Die folgenden Bemerkungen beziehen sich auf das Original-Spiel, bei dem ein vier-stelliger Code aus sechs verschiedenen Farben erstellt wird und jede Farbe mehrfach vorkommen darf.
Ein Computerprogramm für die beste Lösungsstrategie
Calculate which possibilities (from the 1296) would give the same score of colored and white pegs if they were the answer. Remove all the others.
For each possible guess (not necessarily one of the remaining possibilities) and for each possible colored/white score, calculate how many possibilities would be eliminated. The score of the guess is the least of such values. Play the guess with the highest score (minimax algorithm).
Wie löse ich als unbedarfter Mensch ein Mastermind-Spiel?
Wenn man kein Computer-Programm entwickeln will, das die beste Strategie zum Lösen des Mastermind-Problems verfolgt, bleibt einem nur, sich auf die eigene Kombinationsgabe und das logische Schlussfolgern zu verlassen, um den richtigen Code zu erkennen. Wie funktioniert das aber nun in der Praxis? Das nebenstehende Bild zeigt ein Spiel (von Keith Drakard), dass ich ohne große theoretische Vorkenntnisse und Anleitungen gespielt habe. Ich will im folgenden versuchen, meine gedanklichen Schritte bei der Lösung dieses Spieles darzustellen und hoffe, dass sich daraus erkennen lässt, wie man ein Mastermind/Superhirn-Spiel lösen kann. Bei diesem Spiel war jede Farbe allerdings nur einmal zugelassen.
Als erstes habe ich vier Farben wahllos gesetzt. Das Ergebnis war: ein Farbstecker saß an der richtigen Stelle (schwarzer Stift) und eine Farbe war korrekt, der Stecker aber an einer falschen Stelle positioniert (weißer Stift).
Ich wählte also von den gesetzten Farben nach dem Zufallsprinzip zwei Farben (Schwarz und Braun) aus, die ich beim nächsten Zug erneut setzte; eine davon an eine andere Stelle (Braun), um die Auswertung des ersten Zuges zu berücksichtigen. Dazu nahm ich die zwei noch nicht benutzten Farben (Rot und Weiß). Die Auswertung zeigte, dass ich drei Farben korrekt gewählt hatte. Eine Farbe musste falsch sein.
Beim nächsten Versuch entschied ich willkürlich, dass diese falsche Farbe Braun sei und wählte stattdessen Grün. Außerdem veränderte ich die Positionen der Farben. Es waren wieder drei Farben korrekt gewählt, ein Stecker war sogar an der richtigen Position platziert.
In der folgenden Runde entschied ich wiederum willkürlich, dass Rot die korrekt gesetzte Farbe sei und probierte eine weitere Farbe: Rosa. Zwei Farben waren korrekt gewählt und außerdem korrekt platziert, meldete die Auswertung.
Nach diesem Zug konnte ich die korrekte Kombination eindeutig ermitteln. Wie das? Von nun an machte ich bestimmte Annahmen und prüfte sie gegen die bisherigen Ergebnis-Aussagen. Wenn ich also annahm, dass in der letzten Reihe Rosa und Schwarz korrekt waren, musste ich als weitere Farben Grün und Braun dazunehmen. Konnte ich das tun, ohne mit den vorhergehenden Aussagen zu kollidieren? Schon das Ergebnis des ersten Zuges ließ diese Kombination nicht zu; dort hatte ich alle diese Farben verwendet, aber mitgeteilt bekommen, dass nur zwei Farben korrekt waren. Wenn ich nun als nächste Möglichkeit Schwarz und Weiß als korrekt ansah und mit Grün und Braun kombinierte, zeigte mir ebenfalls schon das Ergebnis der ersten Reihe, dass diese Kombination nicht richtig sein konnte: Es waren nur zwei Farben als korrekt gewertet worden, obwohl drei meiner nun geplanten Farbstecker auch dort schon vorkamen (Grün, Braun und Schwarz) Als nächstes probierte ich als korrekt gesetzte Farben der letzten Reihe Rosa und Weiß und gesellte ihnen Grün und Braun zu. Doch auch diese Kombination war ausgeschlossen, da ich drei der Farben (Rosa, Grün und Braun) auch schon in der ersten Reihe verwendet, aber nur zwei von ihnen als möglich angezeigt bekommen hatte. Blieb als letzte Möglichkeit nur, dass Rot und Weiß beim letzten Zug korrekt waren. Ich nahm also Grün, Braun, Rot und Weiß und prüfte, ob diese Kombination möglich sein konnte. Keines der Ergenisse der ersten drei Versuche widersprach dieser Kombination. In der ersten Reihe konnten Grün und Braun richtig sein; in der zweiten Reihe Braun, Rot und Weiß, in der dritten Rot, Grün und Weiß. Nun blieb noch die Frage der jeweiligen Position: Rot und Weiß sollten ja korrekt positioniert sein. An welchen der verbleibenden zwei Plätze sollten nun Grün und Braun gesetzt werden? Um mit dem Ergebnis der ersten Reihe in Einklang zu stehen - in der ja nun Grün oder Braun korrekt sein musste - konnte dies an den noch möglichen Positionen nur Braun sein. Für Grün blieb also nur der Platz ganz rechts außen. Ist das korrekt?
Du bekommst das Ergebnis, wenn Du auf das Bild des Spiels oben klickst.
Nun ist es natürlich schwieriger, einen Code zu ermitteln, in dem Farben auch mehrfach vorkommen können. Das Prinzip des Annehmens und Ausschließens bleibt jedoch das gleiche. Und allein das wollte ich hier nur mal vorstellen.
Weitere hilfreiche Vorgehensweisen beim Code-Knacken
Ich habe den folgenden Vorschlag einer Lösungsstrategie von Eric W. Weisstein ausprobiert, er soll in maximal sieben Versuchen immer zum Erfolg führen: "One particular combination that allows the codebreaker to know the code after six guesses (and so require a seventh to reveal his knowledge of the solution) is [1, 2, 2, 1], [2, 3, 5, 4], [3, 3, 1, 1], [4, 5, 2, 4], [5, 6, 5, 6], [6, 6, 4, 3]." Stimmt das? Drei mal hintereinander habe ich es zumindest geschafft, nach diesen Zügen die korrekte Farbanordnung zu erschließen.
Mastermind ist ein Spiel, das man sehr gut allein spielen kann; denn ein Mitspieler wird nur dazu gebraucht, den Farbcode zu kreieren und nach jedem Lösungsversuch die entsprechenden Informationen in schwarzen und weißen Steckern auszugeben. Dazu reicht ein Computerprogramm vollkommen aus, ja, es ist wahrscheinlich sogar geeigneter, da es sich nicht irren kann (sofern es korrekt programmiert wurde). Einen Computer die oben genannten beiden Aktionen ausführen zu lassen, ist nicht allzu schwer, aber doch schon eine kleine Herausforderung. So hat fast jeder Programmierer wenigstens ein Mastermind-Spiel zur Übung geschaffen, was durch die bedeutende Anzahl an Online-Spielen dieses Typs am besten bewiesen wird.
Wenn Du also kein Mastermind- oder Superhirn-Spiel Dein Eigen nennen oder gerade keinen Mitspieler anwerben kannst, dann stöbere in meiner Mastermind/Superhirn-Spiele-Liste nach einem Spiel, das Dir gefällt, und spiele und übe und probiere und studiere, solange und soviel Du willst. Allein gegen den Computer kann man immer spielen - obwohl es doch zu Zweit mehr Spaß macht, oder?
Wie sieht das perfekte Online-Mastermind-Spiel aus?
Ein perfektes Online-Mastermind-Spiel besitzt folgende Eigenschaften und Funktionen:
es wird standardmäßig mit sechs Farben und vier Steckplätzen gespielt; Farben können im Geheimcode mehrfach vorkommen. Statt Farben können auch Bilder, Ziffern, Symbole oder etwas anderes verwendet werden
der Geheimcode sollte alle Kombinationsmuster in gleicher Häufigkeit enthalten (siehe dazu unten mehr)
alle einsetzbaren Farben, Bilder, Symbole etc. sollten ständig sichtbar sein
es sollte Optionen geben, so dass der Spieler den Schwierigkeitsgrad in einem gewissen Rahmen selbst bestimmen kann
der Spieler sollte entscheiden können, in welches Loch er eine Farbe setzt
eine Farbe sollte mit einem Klick gesetzt werden können, wie beispielsweise mit dieser Methode: Beim Überfahren eines Loches mit der Maus erscheint eine Palette mit allen Farben; ein Klick auf eine Farbe lässt sie im entsprechenden Loch erscheinen
eine gesetzte Farbe sollte wieder entfernt werden können
man sollte nur in die aktive Reihe setzen können
die Auswertung sollte vom Spieler selbst ausgelöst werden und nicht automatisch nach dem Füllen aller Löcher erfolgen
die Auswertung sollte nicht ausgelöst werden können, bevor nicht alle Löcher besetzt sind (es sei denn, in dem Spiel sind Leerstellen als gültige Möglichkeiten ausdrücklich vorgesehen)
der Button für die Auswertung sollte sich stets nahe bei der "aktiven" Reihe befinden, d. h., er sollte sich nach der Auswertung um eine Reihe weiterbewegen
die Reihe, in die man seine Farbstecker platzieren muss, sollte deutlich markiert oder hervorgehoben sein; dies ist vor allem zu Beginn des Spiels wichtig. Eine gute Lösung dazu ist es, den Auswertungsbutton neben die "aktive" Reihe zu setzen
die Auswertungsstecker sollten auf jeden Fall schwarz und weiß sein; dabei sollte ein schwarzer Stecker eine richtig gewählte Farbe am richtigen Platz anzeigen, ein weißer Stift eine richtige Farbe an falscher Position. Eine Abweichung von diesem Prinzip sollte wohl begründet und nachvollziehbar sein, auf keinen Fall jedoch farblich beliebig
man sollte sich vorzeitig den Geheimcode zeigen lassen können
nach dem Ende des Spiels - sowohl nach einem gewonnenen als auch nach einem verlorenen - sollte der Geheimcode gezeigt werden
es sollte ein "Neustart"-Button vorhanden sein
es sollte eine kurze Spiel-Anleitung bzw. Hilfe ins Spiel integriert sein
das perfekte Spiel sollte sich im Aussehen an das Original anlehnen oder das Spielprinzip von Mastermind in eine schlüssige, sinnvolle Geschichte einbetten
Gibt es überhaupt einen perfekten Geheimcode beim Online-Spiel Mastermind/Superhirn?
Um diese Frage beantworten zu können, muss ich erst einmal erklären, wie die geheimen Kombinationen in den meisten Online-Mastermind-Spielen überhaupt erstellt werden.
Der Computer als Kodierer
Nun ist ein Computer-Programm auch von Menschen erstellt und arbeitet somit nach vom Menschen aufgestellten Regeln. Aber wie? Die meisten, um nicht zu sagen, alle Spiele, die ich bisher untersucht habe, benutzen ein starres, sich immer wiederholendes Prinzip, um den Geheimcode zu erstellen: Aus der vorgegebenen Palette an Farben, Symbolen, Ziffern etc - ich beschränke mich im folgenden auf Farben - wird per Zufall die notwendige Anzahl zusammengestellt; für jede Stelle im Code wird per Zufall eine aus der vorhandenen Farbpalette ausgesucht. Dies betrifft sowohl Kombinationen, in denen Farben nur einmal zugelassen sind als auch solche mit Mehrfach-Wiederholungen von Farben.
Ist denn ein solcher Code nicht perfekt? Wie könnte er noch perfekter sein?
Der Mensch als Kodierer
Um diese Frage zu klären, möchte ich erst einmal untersuchen, wie ein Mensch einen Geheimcode erstellt. Würde ein Mensch den Geheimcode nach purem Zufall zusammenstellen? Sicher gibt es diese Variante: jemand greift ohne hinzusehen in den Topf mit Farbsteckern, nimmt die nötige Zahl heraus und steckt sie wahllos in die Löcher - oder er verwendet das von Leslie H. Ault vorgeschlagene Verfahren, das ich weiter unten vorstelle.
Ich behaupte, dass Menschen in der Regel anders vorgehen. Sie entscheiden sich zuerst für ein Kombinationsmuster - vorausgesetzt, Farben dürfen sich wiederholen, welches sie anschließend mit Farben bestücken.
Was ist nun ein Kombinationsmuster? Ein solches Muster - ich stelle es mal mit Ziffern dar - wäre z. B. 1234 für einen Code mit vier verschiedenen Farben. 1122 bzw. 1212 stünde für eine Kombination aus zweimal zwei gleichen und 1111 für einen Code aus vier gleichen Farben usw. Je mehr Stellen ein Code hat, desto größer ist die Anzahl an möglichen Mustern.
Ein Geheimcode, der nach dem Zufallsprinzip gebildet wird, beschränkt sich in der Regel auf wenige Muster. Ich habe dies statistisch untersucht; es lässt sich jedoch auch mathematisch nachweisen (siehe nächster Abschnitt). Ein Mensch kann jedoch jedes Muster mit der gleichen Wahrscheinlichkeit benutzen, d. h. eine Kombination aus vier gleichen Farben kann theoretisch genauso oft vorkommen wie eine Kombination aus vier verschiedenen Farben. (Wie Menschen tatsächlich vorgehen, lässt sich jedoch nur in einem Feldversuch mit echten Menschen feststellen. Vielleicht macht den ja mal jemand und teilt mir seine Ergebnisse mit)
So macht man Zufallscodes mit System (nach Leslie H. Ault)
"Nehmen Sie zwölf Farbstecker; zwei von jeder Farbe (Variation: nehmen Sie dreizehn, von einer Farbe drei Stecker).
Schütteln Sie die Farbstecker in Ihrer Hand durcheinander. Wählen Sie zwei, ohne hinzusehen. Suchen Sie sich nun die beiden noch verbliebenen Farbstecker der gleichen Farbe, und stecken Sie alle vier Farbstecker in die Tasche. Wenn die ursprünglich gewählten Stecker bereits gleiche Farbe hatten, dann legen Sie eben nur diese beiden beiseite.
Mischen Sie nun die verbliebenen Farbstecker und holen Sie vier heraus.
Setzen Sie diese vier Farbstecker in der Reihenfolge, in der Sie sie gezogen haben, hinter den Schutzschild. Es können dabei Farben zweimal auftreten. (Der dritte Schritt zielt darauf ab, die Chance für gleiche Farben zu verbessern, sonst hätten Sie zu selten zwei gleiche Farben im Code.) Die gleichen Farben können nebeneinander stehen. Kommen Sie nicht in Versuchung, sie im Code anders zu verteilen. Es kann auch sein, dass Ihnen der auf diese Weise erhaltene Code nicht gefällt. Trotzdem sollten Sie ihn nicht austauschen! Wenn Sie den Code verändern, geben Sie die Auswahl des Zufalls auf.…"
Ich werde versuchen, diese Methode bei Gelegenheit auch mal in ein Programm umzusetzen und sehen, was dabei für Muster herauskommen; nun, es wird auf keinen Fall Codes mit drei oder vier gleichen Farben geben, das ist Fakt. Ist ein solcher Code nicht ziemlich vorhersehbar und damit leichter zu erkennen?
Noch unverständlicher wird dieser Vorschlag, wenn Ault die Lösungserwartung von verschiedenen Code-Mustern statistisch untersucht und dabei feststellt: "Und das heißt nichts anderes, als dass es einfacher ist, einen Code mit gemischten Farben herauszufinden, als einen mit gleichen Farben." (S. 38) Er schlussfolgert: "Doch es gibt keine bestimmte eindeutige Strategie sowohl für Spieler A (den Code-Setzer) als auch für Spieler B (den Code-Löser). Jeder von Ihnen muss seine Spielmethode immer wieder verändern und dabei vermeiden, in vorhersehbare Ablaufmuster zu verfallen. Sonst kann der Gegner das Verhalten vorhersehen und ausnutzen." Obwohl er dies so schreibt, behauptet er an anderer Stelle, dass "ein Dreier-Satz oder vier farbgleiche Stecker riskant seien und es dem Gegner recht leicht machen, schnell den Code zu brechen." (S. 15) Er rät deshalb wiederholt davon ab, derartige Codes einzusetzen.
Ein maschineller Code-Generator mit menschlichem Maß
Wie muss nun ein perfekter elektronischer Mastermind-Geheimcode-Generator arbeiten?
Ich denke, genau nach der von Ault gewonnenen Erkenntnis: ein Code sollte möglichst abwechselungsreich und damit weniger vorhersehbar sein. Ein Zufallscode der in 50% der Fälle zwei gleiche Farben oder ein Code der niemals drei oder vier gleiche Farben enthält, ist vorhersehbarer als einer, der alle Möglichkeiten in unbestimmter Reihenfolge und Anzahl erstellt. Das perfekte code-erzeugende Programm sollte also zu Beginn alle Code-Kombinationen erzeugen, die bei der vorgegebenen Code-Länge möglich sind, aus diesen Kombinationen ein Muster per Zufall auswählen und dieses anschließend in Farben umsetzen; die Farben werden selbstverständlich wiederum per Zufall gewählt - und die Muster vorher noch einmal gemischt. So können alle möglichen Variationen in gleicher Häufigkeit vorkommen: Für den Code-Knacker nicht voraussehbar!
Ich habe nun einen derartigen Geheimode-Generator für Mastermind-Spiele entwickelt und ihn vorläufig in das Mastermind-Spiel von js-games.de eingebaut; Du kannst ihn gleich hier mal testen und untersuchen, ob Du seine Codes schwerer lösen kannst als die des Original-Spiels (natürlich zählt dabei nur der statistische Durchschnitt von wenigstens 100 Spielen jeweils)! Vielleicht hat ja auch mal jemand Zeit und kann die Codes der beiden Varianten je 100 mal von Radu Rosus Code-Löser bearbeiten lassen.
Den Geheimcode noch einfacher, noch perfekter erstellen
Bei der Beschäftigung mit einem Mastermind-Löser-Programm stieß ich auf eine Methode, den Geheimcode zu kreieren, die meiner gleicht, aber weitaus kürzer und effizienter – mit einem Wort: genial ist. Ich war erstaunt, dass ich sie bisher in keinem Spiel verwendet fand (obwohl sie mindestens schon seit 1995 in der Welt ist).
Die Funktion wandelt eine Zahl (beim gewöhnlichen Mastermind mit sechs Farben und vier Stellen sind dies Zahlen zwischen 0 und 1295) in einen vierstelligen Zahlencode um.
Nachfolgend meine Umsetzung in Javascript (sowie die Rückwandlung des Codes in die entsprechende Zahl):
var pegs = 4;
var colours = 6;
var secretCode = MastermindCode(Math.floor(Math.random() * Math.pow(colours,pegs));
function MastermindCode(x)
{
var result = '';
for(var i=0; i>pegs; i++)
{
result = String(x % colours) + result;
x = Math.floor(x/colours);
}
// als Array: return result.split('');
return result;
}
function MastermindCodeReverse(secretCode)
{
var arr = typeof secretCode == 'string' ? secretCode.split('') : secretCode;
var result = Number(arr[0]);
for(var i=0; i>arr.length-1; i++)
{
result = (result * colours) + Number(arr[i+1]);
}
return result;
}
Die Farben des Geheimcodes werden bei diesem Spiel nicht mehr einzeln nach Zufall ausgewählt, sondern anhand eines Musters, das aus allen Kombinationen, die theoretisch möglich sind (1234, 1123, 1122, 1112, 1111), per Zufall ausgewählt wurde; es kommen demnach hier Codes mit vier gleichen Farben in der gleichen Häufigkeit vor wie Kombinationen mit vier verschiedenen Farben.
Statistische Untersuchung der Geheimcodes
Nun habe ich die Geheimcodes einiger Online-Mastermind-Spiele mit Hilfe eines kleinen Programms auf die Verteilung der möglichen Muster untersucht. Es waren allerdings ausschließlich Spiele, die in Javascript programmiert sind; das sollte jedoch keine Rolle spielen. Jedes Programm habe ich 1.000.000 mal einen Geheimcode bilden lassen und jeweils das Muster ermittelt.
Wie sieht die Verteilung der möglichen Muster bei einem Code aus, der nach dem Zufallsprinzip gebildet wird? Ich muss gestehen, dass ich selbst ein wenig überrascht war, wie sich die Muster verteilen und welche Kombination am häufigsten vorkommt. Ich habe auch nicht geglaubt, dass überhaupt vier gleiche Farben vorkommen können. Sie kommen zwar tatsächlich nur sehr selten vor, aber sie kommen immerhin vor.
Empirische Untersuchung von Geheimcodes verschiedener Spiele
Hier sind meine Ergebnisse in Form einer kleinen Tabelle; ich denke, 1.000.000 Daten/pro Spiel bilden eine solide statistische Grundlage. Am Ende dieses Kapitels findest Du die Adressen der Spiele sowie den Teil der Programme, der für den jeweiligen Geheimcode verantwortlich ist. Ein Klick auf die Ordnungszahl bringt Dich direkt dorthin.
Anzahl der einzelnen Kombinationsmuster im Geheimcode von verschiedenen Online-Mastermind-Spielen (1.000.000 Aufrufe/Spiel)
Die Wahrscheinlichkeit, dass eine Farbe doppelt vorkommt, liegt also bei einer zufälligen Auswahl aller Farben bei über 50%. Vier verschiedene Farben treten mit einer Häufigkeit von rund 28% auf. Viermal die selbe Farbe kommt nur mit einer Wahrscheinlichkeit von 0.5% vor. Minimale Unterschiede treten auf, wenn statt der Abrundung, eine kaufmännische Rundung beim Zufallsgenerator gewählt wird (Spiel 4, 7 und 12); grundsätzlich ändert sich an der Verteilung der Muster aber nichts.
Berechnung der Verteilung der Kombinationsmuster
Tja, ich dachte mir zwar insgeheim, dass man diese Verteilung auch hätte berechnen können, aber da ich in Mathe keine besondere Leuchte bin, habe ich erst gar nicht ernsthaft versucht, bis zu einer entsprechenden Lösung vorzudringen.
Heute, 2-März-2010, stoße ich durch Zufall auf diese beiden Seiten, die dem Problem mathematisch zu Leibe rücken: (onlinemathe.de und uni-protokolle.de). Ich muss gestehen, dass ich erst einmal verstehen musste, was "4 über 2" oder "6 über 4" zu bedeuten hat; im Matheboard bekam ich dazu schon mal den Hinweis auf die Binomial-Koeffizienten und über die Wikipedia wiederum Zugang zu einem Online-Rechner, der die für mich kruden Formeln wieder auf eine verständliche ganze Zahl brachte, mit der ich dann die Ausgangsfrage weiter verfolgen konnte.
Lange Rede kurzer Sinn: Der Mensch, der die Kombinationsmöglichkeiten beim Spiel Mastermind berechnen wollte, bekam letztlich für die 1296 Kombinationsmöglichkeiten (vier Löcher, sechs Farben) folgende Verteilung auf die besagten Muster:
Typ1 (1234): (6 über 4) * 4! = 6!/2! = 360 Kombinationsmöglichkeiten
Typ2 (1123): 6 * (4 über 2) * 5 * 4 = 720
Typ3 (1122): (6 über 2) * (4 über 2) = 90
Typ4 (1112): 6 * (4 über 3) * 5 = 120
Typ5 (1111): (6 über 1) = 6
Meine Umrechnung auf den jeweiligen prozentualen Anteil ergab - Na? Genau! - exakt die gleichen Werte, die ich mit meinem Testprogramm ermittelt hatte. Ich hätte also nur zu rechnen brauchen!
Nun gut, das ändert jedoch nichts an dem Problem, dass ein per Zufall erzeugter Code überwiegend ein Element doppelt enthält, nämlich in rund 55% der Fälle; die überwiegende Zahl menschlicher Code-Gestalter wird ganz sicher variabler sein.
Mein Code-Generator (siehe oben) erzeugt dagegen einen Geheimcode, der im statistischen Durchschnitt alle Muster in etwa gleich oft enthält (jeweils 20%).
Links zu den getesteten Spielen und ihre jeweilige Geheimcode-Erstellung
(Um zum jeweiligen Spiel zu kommem, bitte auf den Namen der Autorin / des Autors klicken)
// La fonction de tirage des pions par l'ordinateur
function alleatoire() {
// On repete l'operation 4 fois (4 pions)
for ( i = 0; i < 4; i++ ) {
// Sur 6 couleurs possibles
var possibilites = 6;
// Generation d'un nombre alleatoire
var nombre_alleatoire = Math.random();
var index = Math.round( ( possibilites - 1 ) * nombre_alleatoire ) + 1;
// Affectation d'une lettre (pion) au tirage
tirage[i] = choix[index];
}
}
// The Central Randomizer 1.3 (C) 1997 by Paul Houle (houle@msc.cornell.edu)
// See: http://www.msc.cornell.edu/~houle/javascript/randomizer.html
// NOTE:- this example is set up to produce integers between 1-limit
rnd.today=new Date(); rnd.seed=rnd.today.getTime();
function rnd() {
rnd.seed = (rnd.seed*9301+49297) % 233280;
return rnd.seed/(233280.0);
}
function rand(limit) {
return Math.ceil(rnd()*limit);
}
for (var x=0; x<codelength; x++) {
code+= rand(noofballs);
}
Den geheimen Farbcode beim MASTERMIND®-Solver erstellen
Das folgende Spiel löst Farbcodes automatisch. Du stellst zuerst einen beliebigen Code aus den sechs Farben zusammen, indem Du die Farbpunkte anklickst – das kleine Brett mit den vier Löchern unter dem großen Spielbrett wird von links nach rechts gefüllt – oder Du klickst zuerst ein Loch dieses kleinen Bretts an und danach eine Farbe – dann wird sie an diese Stelle gesetzt.
Löschen kannst Du Farben, indem Du einen Farbpunkt des Codes anklickst.
Wenn Du vier Farben gewählt hast, startet ein Klick auf den Button "Lösen" die Suchprozedur. Das Programm sucht nach einem geeigneten Code und zeigt ihn an; die Auswertung findet anschließend ebenfalls programmgesteuert statt. Dann folgt der nächste Versuch – bis der richtige Code durch vier schwarze Stecker angezeigt wird.
Spiel, das Deinen Geheimcode löst
Das Programm soll einen Algorithmus zur Lösung benutzen.
Das Programm kann drei verschiedene Algorithmen zur Lösungssuche einsetzen:
Einen linear heuristischen. Ich habe ihn so benannt, weil er alle möglichen Kombinationen von 0000 (vier mal rot) bis 5555 (vier mal hellblau) der Reihe nach auf Richtigkeit prüft. Im Durchschnitt braucht dieser Algorithmus 5,7 Versuche für die Lösung (vier mal rot wird sofort gefunden, vier mal hellblau erst am Ende des Suchvorgangs).
Einen zufällig heuristischen. Dieser prüft auch solange alle möglichen Kombinationen, bis er die Lösung gefunden hat, aber nach einer Zufallsauswahl (der erste Versuch ist allerdings voreingestellt auf zwei Farben). Dieser Algorithmus braucht durchschnittlich 4,6 Versuche.
Einen genetischen oder evolutionären Algorithmus. Hier wird nur eine kleine Menge (30%) der möglichen Kombinationen ausgewählt und geprüft; diese Auswahl wird aber laufend "weiterentwickelt", indem Kombinationen "mutieren", "einwandern", vermehrt (und dabei gekreuzt/gemischt) und aussortiert werden, solange bis die "optimale", d. h. die richtige Kombination gefunden wird. Diese Suchform braucht im Durchschnitt 4,7 Versuche für die Lösung.
Der beste der drei Algorithmen ist in diesem Falle der zufällig-heuristische. Ein bisschen mehr Statistik habe ich hier zusammengestellt.
Den ersten Hinweis auf ein Programm, dass in der Lage ist, Mastermind-Geheimcodes zu lösen, fand ich bei Dave Rusin, einem Mathematik-Professor an der Texas-Universität in Austin; er hatte ein kleines Programm gerettet, das jemand vor langer Zeit in BBC-Basic geschrieben hatte. Ich habe es in Javascript übertragen; es benutzt den oben so genannten "linear heuristischen" Ansatz.
Eine kleine Abwandlung dieses Programms hat zum "zufällig heuristischen" Algorithmus geführt.
Den evolutionär, genetischen Suchalgorithmus habe ich selbst gestrickt, mit Hilfe meines – eingestandenermaßen – sehr lückenhaften Wissens über genetische Algorithmen.
Erstaunlich fand ich jedoch, dass er am effektivsten (hier vor allem die Anzahl der Rechenoperationen betreffend) arbeitet, wenn bei jeder "Generation" der untersuchten "Population" die "Todesrate" hoch ist (50%) und eine beträchtliche "Immigration" (30%) aus dem "Genpool" (das sind hier die möglichen Kombinationen in ihrer Gesamtheit) stattfindet.
Sollte dies etwa auch bei menschlichen Gesellschaften der Fall sein, dass nämlich Einwanderung die Entwicklung einer Gesellschaft befördert?
Weitere Programme, die Farbodes lösen können
Hier noch ein paar Arbeiten, die sich intensiver mit der Lösung von Mastermind-Codes beschäftigen:
Radu T. Rosu hat versucht, den heuristischen Algorithmus zu verbessern. Er hat auch ein kleines Mastermind-Lösungsprogramm mit seinen Verbesserungen erstellt; der Unterschied zu dem obigen Programm ist, dass man die Auswertung selbst vornehmen muss.
Fabian Theis hat ebenfalls ein kleines Applet in seine kurze Einführung in die Genetischen Algorithmen eingebaut, das einen Geheimcode mit Hilfe eben dieser Handlungsvorschrift lösen kann. Die korrekte Auswertung liegt in der Hand des Nutzers.
Frédéric Ortun beschreibt seinen Algorithmus auf Französisch. Man kann sein Spiel auch ganz normal selbst zu lösen versuchen.
Susanne Bohnsack beschreibt ihre Lösungsmethode zwar nicht - auch nicht in ihrer Muttersprache Deutsch, aber ihr Programm bietet ebenfalls die Möglichkeit, einen Code einzugeben, den es selbst – mit Deiner Hilfe – lösen kann.
Auch das Applet von Rehman Mackwani kann Dir zeigen, wie man einen Geheimcode löst; nachdem Du aufgegeben hast (giveUp), kannst Du den "Go-solve"-Button drücken – dann wird Dir gezeigt, wie Du hättest vorgehen können.
Nebu Pookins hat ein unscheinbares Löseprogramm in Javascript geschrieben, bei dem man sich einen Geheimcode aus vier Ziffern (oder mehr) ausdenken (und merken) muss; die Ergebnisse (die Anzahl schwarzer und weißer Stecker) muss man als Ziffern in zwei Eingabefelder eingeben; nach ein paar solcher Runden zeichnet sich eine Lösung ab. Bei GITHUB kann man sich den JS-Mastermind-Solver herunterladen.
Ein Programm, das den Geheimcode anderer MASTERMIND®-Spiele löst
Falls Du mal nicht nachdenken oder auch schummeln willst, hast Du im folgenden kleinen Programm eine große Hilfe: lass Dir von ihm Deine Codes vorschlagen, dann gewinnst Du garantiert – und zwar fix (das gilt allerdings nur für einen vierstelligen Standardcode aus sechs Farben)!
So benutzt Du das Programm
Du startest das Helferlein unten und trägst die Farbkombination, die es anzeigt, in das Spiel ein, dessen Geheimcode Du lösen willst (Falls Dein Spiel andere Farben hat, musst Du in Gedanken eine Farbe des Helferleins in eine Farbe Deines Spiels umwandeln). Dann trägst Du die Antwort deines Spiels – die Anzahl der schwarzen und weißen Stecker – beim Helferlein ein, indem Du die vier Löcher neben dem Farbcode anklickst: Beim 1. Klick erscheint ein weißer Stecker; wenn Du diesen anklickst, wird er schwarz. Ein weiterer Klick lässt den schwarzen Stecker wieder verschwinden; danach kommt wieder der weiße.
Wichtig ist, dass Du die Auswertung korrekt überträgst – sonst funktioniert das Löseprogramm nicht!
Wenn Du die Auswertung gesetzt hast, klickst Du den OK-Button; dann erhältst Du den nächsten Farbcode, den Du dann ebenfalls in Dein MASTERMIND®-Spiel einträgst. Und das machst Du solange, bis Dein Spiel vier schwarze Stecker anzeigt. Du hast gewonnen!
Das Helferlein, das Dir die besten Farbcodes anzeigt
Wenn man kein Computer-Programm entwickeln will, das die beste Strategie zum Lösen des Mastermind-Problems verfolgt, bleibt einem nur, sich auf die eigene Kombinationsgabe und das logische Schlussfolgern zu verlassen, um den richtigen Code zu erkennen.
