![[ICO]](/icons/blank.gif){kind=icon}
![[PARENTDIR]](/icons/back.gif){kind=icon}
![[ ]](/icons/a.gif){kind=icon}
![[ ]](/icons/layout.gif){kind=icon}
Das Spiel "Mastermind" ist nun schon einige Jahrzehnte alt, es wurde 1970/71 von M. Meirowitz entwickelt. Früher war es im deutschen Sprachraum unter dem Namen "Superhirn" bekannt, eine etwas holprige Übersetzung.
Das Spiel wird zu zweit gespielt: Spieler 1 setzt verdeckt einen Code, bestehend aus 4 Stiften in jeweils einer von 6 Farben (wobei es hier viele Variationen gibt). Spieler 2 muss nun versuchen, mit höchstens 10 Versuchen diesen Code zu erraten.
Da es für den Code insgesamt 1296 verschiedene Möglichkeiten gibt, bekommt er dabei natürlich Hilfe: nach jedem Rateversuch bewertet Spieler 1 diesen, indem er neben den Code bis zu vier schwarze oder weiße Stifte setzt: einen schwarzen für jeden komplett richtigen Stift im Code und einen weißen für jeden Stift, der zwar eine Farbe hat die im geheimen Code vorkommt, jedoch an der falschen Stelle platziert wurde.
Ziel war es in diesem Fall, ein Programm zu schreiben, das einen gegebenen Code möglichst effektiv lösen kann, sowohl in Bezug auf die Anzahl an Rateversuchen, als auch sekundär auf die Rechenzeit.
Darüberhinaus sollte das Programm allgemeiner gehalten sein, als das Spiel "Mastermind", und daher auch Codes mit anderen Anzahlen an Stiften und Farben, und eine andere Zahl an maximalen Rateversuchen unterstützen.
Der optimale Algorithmus, der vor jedem Rateversuch sämtliche Möglichkeiten durchgeht und bewertet, braucht durchschnittlich 4.34 Züge. Da dies aber mit hohem Zeitaufwand verbunden ist, wurde von uns eine performantere Lösung gesucht, ohne die Anzahl an Rateversuchen stark zu beeinträchtigen.
Fündig wurden wir schließlich bei einem Algorithmus, den Peter Swaszek im Artikel "The Mastermind Novice" vorstellt: Die Idee ist, aus sämtlichen noch möglichen Zügen einen zufällig auszuwählen, was zwar nicht besonders überlegt klingt, aber bei guter Umsetzung durchschnittlich nur 0.3 Versuche mehr braucht.
Dies erfordert aber noch immer die Berechnung sämtlicher konsistenter Züge. Daher wurde eine nochmal etwas performantere Lösung gewählt, bei dem der Zug nicht komplett zufällig ausgewählt wird, sondern von einem zufällig ausgewählten willkürlichen Zug solange "hochgezählt" wird, bis ein konsistenter Zug erreicht wird. Auch dieser Algorithmus ist noch annähernd optimal.
Nachdem das Programm in Ghostscript (oder einem vergleichbaren
Programm) geladen wurde, kann man einen beliebigen Code (als Array mit n
Zahlen zwischen 0 und c - 1) auf den Stack legen und das Programm diesen
mit setcode start lösen lassen.
Darüber hinaus kann mit randomguess einen zufälligen
Code erzeugen lassen. Bequemerweise gibt es für das Erstellen und Lösen
eines zufälligen Codes auch eine Abkürzung, r.
Die Zahlen n (Anzahl an Stiften pro Code) und c (Anzahl an Farben), sowie die Anzahl der maximalen Versuche können direkt im Sourcecode geändert werden (ca. Zeilen 35-40, je nach Version).
Knuth, Donald E. The computer as Master Mind. Journal of Recreational Mathematics 9. (1976).
Kenji, Koyama; Lai, Tony W. An optimal Mastermind strategy. Journal of Recreational Mathematics 25. (1993).
Nelson, Toby. Investigations into the Master Mind board game. Break the hidden code. http://www.tnelson.demon.co.uk/mastermind/. (1999).
Swaszek, Peter F. The Mastermind novice. Journal of Recreational Mathematics 30. (1999).
Das Programm wurde geschrieben von Torsten Gerfertz, Christian Pernegger und Thomas Seidl.
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| mastermind-NEW.ps | 2008-01-22 22:59 | 12K | |
| mastermind.ps | 2008-01-22 22:59 | 11K | |
| praesentation1.pdf | 2007-12-03 02:49 | 225K | |
| praesentation2.pdf | 2008-01-08 15:56 | 271K | |