PostScript spielt Mastermind

PostScript spielt Mastermind

Inhalt:

  1. Inhalt
  2. Das Spiel
  3. Aufgabenstellung
  4. Algorithmus
  5. Referenzen
  6. Selbstschulterklopferei

Das Spiel

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.

Aufgabenstellung

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.

Algorithmus

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.

Verwendung

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).

Referenzen

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).

Selbstschulterklopferei

Das Programm wurde geschrieben von Torsten Gerfertz, Christian Pernegger und Thomas Seidl.

[ICO]NameLast modifiedSizeDescription

[DIR]Parent Directory  -  
[   ]praesentation2.pdf08-Jan-2008 15:56 271K 
[   ]praesentation1.pdf03-Dec-2007 02:49 225K 
[   ]mastermind.ps22-Jan-2008 22:59 11K 
[   ]mastermind-NEW.ps22-Jan-2008 22:59 12K 

Apache/2.2.22 (Debian) DAV/2 mod_fcgid/2.3.6 PHP/5.4.36-0+deb7u3 mod_python/3.3.1 Python/2.7.3 mod_ssl/2.2.22 OpenSSL/1.0.1e mod_perl/2.0.7 Perl/v5.14.2 Server at www.complang.tuwien.ac.at Port 80