Programm

Das Betriebsprogramm für den Mastermind-Taschenrechner erledigt die Kalkulation der nächsten Kombination als Vermutung und die Ansteuerung von Tastatur und Display. Es ist in einer Mischung aus PicBasic und Assembler geschrieben.

Wer keinen PicBasic-Compiler zur Verfügung hat, kann sich auch einer in die Standard-Microchip-Assemblersprache übersetzten Fassung bedienen. Damit ließen sich kleinere Veränderungen vornehmen; die MPLAB-IDE ist von Microchip frei erhältlich und enthält auch den Assembler.

Wer lediglich das Gadget nachbauen und dafür einen 16F84 brennen möchte, benötigt lediglich das Binärprogramm (im Intel-Hex-Format, wie vom Assembler produziert) und einen Brenner.

Historie des Programms

Dies ist inzwischen die fünfte oder sechste Implementierung eines Mastermind-Solvers, die ich im Laufe der Jahre realisiert habe. Die erste, leider nicht mehr vorhandene Fassung entstand auf einem 4-MHz-Singleboardcomputer namens Nascom II, in Z80-Assemblersprache, einige Jahre, nachdem das Spiel unter dem Namen Mastermind vermarktet worden war. Die zweite Version war eine Portierung auf den CP/M-2.2-Computer, in den ich den besagten Nascom II in der Zwischenzeit ungebaut hatte. Eine weitere Fassung entstand als Portierung desselben Algorithmus,  diesmal aber in einem G-Level PL/1, auf der selben, zuhause zusammengelöteten CP/M-Kiste.

Die Codebrecherstrategie ist ein nettes algorithmisches Problem, mit dem man gut neue Sprachen oder neue Architekturen erkunden kann, nicht so trivial wie der allgegenwärtige Primzahlengenerator, aber doch simpel genug, um eine einfache Implementierung aus dem Ärmel schütteln zu können.  Knuth [1] fand und publizierte eine optimale Strategie, kurz nachdem Invicta Plastics das Spiel unter dem Namen Mastermind popularisiert hatte. Dennoch bleibt es unter starken Beschränkungen bezüglich Speicherplatz oder CPU-Geschwindigkeit oder als Fingerübung interessant.

Der hier verwendete Prozessor, ein 16F84, hat gerade einmal genügend RAM, um alle Antworten zu speichern, insofern kam eine Implementation meines ursprünglichen Algorithmus, der aus den noch möglichen Kombinationen diejenige auswählt, welche im nächsten Schritt den Suchraum am stärksten reduziert, nicht infrage. Auf einem Midrange-PIC wie diesem ist nicht einmal das Verfahren, aus einer Menge noch unbekannter Größe ein Element zufällig auszuwählen, von vorneherein auf der Hand liegend. Jedenfalls habe ich hier die simple Zufallstrategie verwendet, welche aus den verbleibenden möglichen Kombinationen eine zufällig als nächste Frage auswählt. Laut Mike Wiener [2] ist diese Strategie fast so gut wie die optimale Strategie und ebenfalls in der Lage, die richtige Antwort (bei 4x6) mit etwa fünf Fragen zu finden.

Von den 68 verfügbaren Bytes des 16F84 habe ich 18 Bytes für das Abspeichern von maximal sechs Antworten verwendet. Weitere 16 Bytes werden  für das unkomprimierte Abspeichern von vier Kombinationen verwendet, ein paar weitere Bytes für temporäre Variable.

Ein Kombinationsvergleich benötigt 150 Instruktionen resp. 150 µs bei Verwendung einer 4MHz-Clock. Das ergibt einen Zeitbedarf von 150*µs*2401 == 1/3 Sekunde für die Betrachtung aller möglichen Kombinationen nach der ersten Frage. Mit einem 8MHz-Resonator, wie hier verwendet (wenn man nicht den vollen Temperatur/Vdd-Range braucht, läuft ein PIC16F84-04/P auch mit 10 MHz problemlos), ist die nächste Frage in maximal einer halben Sekunde errechnet.

Fortsetzung

• ein paar Anmerkungen zum Algorithmus.

[1] Donald E. Knuth, The Computer as Master Mind. J. Recreational Mathematics, Vol. 9(1) (1976-77), 1-6.

[2] Kenji Koyama, Tony W. Lai. An Optimal Mastermind Strategy, J. Recreational Mathematics, VOl. 25(4), 251-256,1993 (my copy says 1993, not 1994)

[3] http://www.math.niu.edu/~rusin/uses-math/games/mastermind/mastermind