Master Mind

Bemerkung zur HTML-Version: Um die Fussnoten zu sehen, klicken Sie bitte auf die jeweilige hochgestellte, markierte Nummer. Im untenstehenden Fenster sollte die gewünschte Fussnote erscheinen.

Einleitung

Dieses Projekt liegt zum grösseren Teil in Form von html-Dateien vor. Von diesen Dokumenten aus lässt sich das Ergebnis der Arbeit an diesem Projekt, das Programm "Master Mind Player", das als Java-Applet laufen kann, starten. Das Gedruckte ist lediglich ein Teil des Projekts und beschränkt sich auf dessen blosse Beschreibung. Ich möchte Sie deshalb bitten, sich das Projekt auch (und vor allem) in der Form der html-Dateien anzuschauen.

Das Programm, um das es sich handelt, spielt das weitverbreitete Denkspiel "Master Mind", bei dem es darum geht, eine bestimmte Farbenkombination durch wiederholtes Fragen herauszufinden. Das Programm sucht die Kombination nach der kleinstmöglichen Anzahl Fragen zu erraten. Zu diesem Zwecke untersucht es alle möglichen Fragen und wählt die informativste 1 .

Da das Programm in Java geschrieben ist, kann es einerseits auf allen Plattformen 2 als Applikation laufen 3 , andererseits kann es auch als Java-Applet über das Internet in einem der gängigen Java-fähigen Browser betrachtet werden. Auf das Programm kann ¨ber diesen Link zugegriffen werden.

Regeln von Master Mind

Das Spiel Master Mind besteht daraus, dass ein Spieler an eine gewisse Farbkombination denkt und der andere Spieler versucht, diese Farbkombination zu erraten. Die Darstellung einer Farbkombination im Spiel sieht folgendermassen aus:

[rot][weiss][grün][leer]

Es sind vier Löcher vorhanden, in jedes kann ein Stäbchen von beliebiger Farbe gesteckt werden oder es kann leergelassen werden. Eine Farbe kann auch mehrfach vorkommen. Es gibt 7 Farben, wenn man "leer" (das Leerlassen eines Loches) mitrechnet. Bei einer Farbkombination ist auch die Reihenfolge relevant. Ein Spielzug besteht nun daraus, dass der eine Spieler, Spieler A, rät, indem er auf dem Spielbrett eine Farbkombination setzt, z.B.

[rot][rot][rot][grün]

Der andere Spieler, Spieler B, der an eine bestimmte Farbkombination gedacht hat, muss jetzt auf das Geratene ([rot][rot][rot][grün]), also auf die Frage antworten, indem er es mit dem Gedachten vergleicht. Dabei ist die Antwort auf jede Farbe, die in beiden Farbenkombinationen vorkommt und die gleiche Position hat, ein schwarzes Stäbchen. Wenn hingegen die geratene Farbe zwar auch im Gedachten vorkommt, sich aber an einem anderen Ort befindet, wird mit einem weissen Stäbchen geantwortet. Zur Antwort wird also eine bestimmte Anzahl schwarzer und weisser Stäbchen gesetzt. Um es an einem Beispiel zu veranschaulichen, nehmen wir an, dass Spieler B an die Kombination [rot][weiss][grün][leer] denkt. Spieler A rät, im Beispiel zuvor [rot][rot][rot][grün]. Es ist ersichtlich, dass in beiden Kombinationen an der ersten Stelle [rot] steht, dafür gibt es ein schwarzes Stäbchen. [Rot] kommt zwar auch an zweiter und dritter Position im Geratenen vor, aber für eine Position (die erste Position im Gedachten) kann nicht mehr als ein Stäbchen gesetzt werden. Im vom Spieler A geratenen kommt an vierter Stelle [grün] vor, was mit der Farbe an der dritten Stelle vom gedachten übereinstimmt. (Gedachtes von B: [rot][weiss][GRÜN][leer], Geratenes von A: [rot][rot][rot][GRÜN]) Dafür wird ein weisses Stäbchen gesetzt. Auf dem Spielbrett sieht das nun folgendermassen aus:

Geratenes: [rot][rot][rot][grün] ,

Anwort [schwarz][weiss][leer][leer]

Für die stehen vier Löcher rechts von den Löchern für die Frage zur Verfügung, in diese werden schwarze und/oder weisse Stäbchen (oder gar keine) gesetzt. Die Reihenfolge spielt dabei keine Rolle, folgende Antworten sind also mit der vorherigen völlig gleichbedeutend:

[leer][schwarz][leer][weiss]

[weiss][leer][leer][schwarz]

usw.

Aus der erhaltenen Antwort kann der Ratende, Spieler A, seine Schlüsse ziehen. Anschliessend rät Spieler A ein weiterers Mal und bekommt wiederum eine Anwort von Spieler B. Dies wird solange wiederholt, bis Spieler A die Kombination erraten hat, also bis das Gedachte und das Geratene gleich sind (im vorherigen Beispiel: bis [rot][weiss][grün][leer] geraten wurde)5. In diesem Falle lautet die Antwort natürlich [schwarz][schwarz][schwarz][schwarz].

Benutzung des Programms

Das Programm kann am leichtesten als Java-Applet benutzt werden. Auf der beiliegenden Diskette befindet sich eine Datei Namens Mind.html 6  . Eine Alternative dazu ist, wie schon zuvor angesprochen, diese Datei auf dem World Wide Web. Zum Starten muss die Datei lediglich in den Browser geladen werden.

Im Dokument erscheinen zwei Knöpfe: "Guess Yourself", "Let Computer Guess". Die Variante "Guess Yourself" ist lediglich ein Spiel, bei dem man selber versuchen sollte, eine Kombination zu erraten (dies tut man, indem man mit der Maus auf die linksstehenden Kreise klickt).

Das Programm das ich beschreiben werde, lässt sich mit dem Knopf "Let Computer Guess" starten. Ein Fenster wird geöffnet und an dessen linkem Rand erscheint eine aus vier farbigen Kreisen bestehende Farbkombination, diese ist das Erste, was das Programm rät. Sie müssen sich nun eine Kombination denken und sie mit dem geratenen vergleichen und die Antwort angeben. Dafür befinden sich am rechten Rand vier leere Kreise, durch mehrmaliges Klicken mit der Maus lassen sie sich in die Positionen [leer], [weiss], [schwarz] bringen. Drücken Sie bitte danach auf den Knopf "Enter". Danach sollte das Programm einige Zeit lang7 rechnen. (Der Stillstand ist also vorgesehen, obwohl es vielleicht den Anschein eines Absturzes machen könnte.) Danach rät das Programm wieder, es bietet sich wieder die Möglichkeit einer Antwort. Um ein neues Spiel anzufangen, kann man den Knopf "New" drücken. Falls Sie des Programms überdrüssig sein sollten, drücken Sie bitte "Quit".

Zum Algorithmus des Master Mind Programms

Zuerst wird die Menge der von den bisher bekannten Fakten erlaubten Farbkombinationen erstellt. Mit einem Faktum meine ich eine Abfolge einer Frage und der dazugehörigen Antwort. Es sei m die momentane Zahl erlaubter Kombinationen.

Fernerhin definiere man eine Variable i, die durch alle verschiedenen möglichen Antworten läuft. (Bei 4 Plätzen gibt es n = 14 verschiedene Antworten.)

Nun werde eine beliebige Frage F, die nicht unbedingt eine erlaubte Kombination sein muss, in Erwägung gezogen. Man vergleiche diese Frage mit jeder einzelnen erlaubten Kombination und bestimme die resultierenden Antworten. Der Wert mi bezeichne, wie oft die Antwort Nummer i unter den resultierenden Antworten vorgekommen sei,

Summa(i=1...n) mi = m.

Jetzt definiert man die relative Häufigkeit pi einer bestimmten Antwort als pi = mi / m,

Summa(i=1...n) pi = 1.

Nun kann man der Frage F einen Informationsgehaltswert mit Hilfe folgender Formel zuordnen:

InfoValue(F) = - Summa(i=1...n) pi ln(pi) .

Je höher der Wert InfoValue(F) ist, desto schlechter lässt sich die Antwort vorhersagen. Damit ist auch die Antwort auf die Frage F informativer. Wenn hingegen InfoValue(F) gleich 0 ist8, weiss man die Antwort schon im voraus. Deshalb liefert eine solche Antwort keine neue Information.

Es ist also ersichtlich, dass man die Frage Fmax mit dem grössten Wert InfoValue(Fmax) suchen muss, um die informativste Frage zu finden.

Bei diesen Ausführungen habe ich die implizite Annahme gemacht, dass die relative Häufigkeit pi einer Antwort gleich ihrer Wahrscheinlichkeit ist, denn die obige Formel bezieht sich eigentlich auf Wahrscheinlichkeitswerte. Es ist natürlich möglich, dass diese Annahme nicht absolut richtig ist, da Menschen möglicherweise dazu neigen, bestimmte Farbkombinationen mit grösserer Vorliebe zu setzen, doch dieses Problem ist nicht mehr Sachgebiet der reinen Mathematik oder Informatik, also klammere ich es aus meinen Betrachtungen aus.

Der Algorithmus, der zur kleinsten Anzahl von Fragen führt (im Durchschnitt), besteht nun daraus, dass man für die Frage F alle möglichen Farbkombinationen einzeln einsetzt, und dann die entsprechenden Berechnungen dafür durchführt. Dies kann aber unter Umständen zeitaufwendig sein9 , da Java oft (aber nicht immer) als Interpretersprache verwendet wird. Um Rücksicht auf den Benutzer zu nehmen und ihn weniger lang warten zu lassen, habe ich neben einigen programmiertechnischen Optimierungen auch die Auswahl der Fragen, die für F eingesetzt werden (in der oben beschriebenen Formel) geändert. Es werden nicht alle Kombinationen durchgenommen, sondern es werden Stichprobenartig nach dem Zufallsprinzip einige ausgewählt und für die Berechnungen herangezogen. Damit lässt sich die Berechnungszeit auf ein Bruchteil der ursprünglichen verringern. Ich habe das Programm mit der Option ausgebaut, dass die Berechnungszeit vom Benutzer eingestellt werden kann. Der Nachteil einer zu stark verkürzten Berechnungszeit ist natürlich, dass das Ergebnis weniger gut sein wird und das Programm somit nicht die absolut beste Frage stellt, sondern nur die beste, die unter einem betimmt starken Zeitdruck gefunden werden kann.

Zu der Einstellung der maximalen Berechnungszeit

Bei der Einstellung der Berechnungszeit durch den Benutzer stellt sich das Problem, dass das Programm mit ganz verschiedenen Voraussetzungen und unterschiedlichen Plattformen laufen kann. Aus diesem Grunde kann man nicht im Voraus wissen, wie schnell ein bestimmter Berechnungsschritt durchgeführt wird.10

Um diesem Problem aus dem Wege zu gehen, ist im Programm nicht die maximale Berechnungszeit, sondern die maximale Zahl der Berechnungsschritte11 einstellbar.

Die Voreinstellung ist 50000 Schritte. Die Durchführung der 50000 Schritte hat beim Test auf meinem Rechner (486DX, 66MHz, Just-in-Time-Compiler von Netscape Navigator 3.0) 15 Sekunden gedauert, aber die Zeit kann natürlich je nach Umständen stark variieren.

Eine Kurzbeschreibung des Aufbaus des Programms

Alle Elemente des Programms sind in Klassen untergebracht. Der Übersichtlichkeit halber habe ich die Klassen in drei Kategorien unterteilt: in diejenigen für die algorithmischen Berechnung der idealen Frage, in diejenigen der graphischen Darstellung der Ergebnissen und diejenigen, die einen Zusatz für die Kommunikation mit dem Benutzer bieten und nicht Ergebnisse direkt darstellen.

Klassen der algorithmischen Berechnung

Guess Eine Instanz von Guess ist eine Farbkombination, sowohl die zu erratende Farbkombination als auch die Frage sind Guesses.
Answer Ein Answer-Objekt enthält die Antwort auf den Vergleich einer Farbkombination mit einer Frage.
Fact Ein Fact ist die Verbindung von einem Guess und einem Answer.
FreqL (Frequency List) Liste der Häufigkeiten verschiedener Antworten. Aus ihr wird der Informationsgehalt InfoValue(F) einer Frage berechnet.
Thinker Der "Denker". Diese Klasse ist für die Suche nach der idealen Antwort zuständig.
GuessEnumerator Diese Klasse numeriert alle möglichen Kombinationen durch und gibt sie alle einzeln nacheinander aus.
randomEnumerator Ein randomEnumerator gibt eine zufällige Stichprobe von Elementen aus einer grösseren Menge aus.
GuessColors definiert die Anzahl möglicher Farben, zudem wird jeder möglichen Zahl eine bestimmte Farbe zugeordnet.

Klassen der graphischen Darstellung der Ergebnisse

CircleColorButton Abstrakte Klasse, die einen runden, farbigen Knopf und seine Darstellung auf dem Bildschirm definiert. Diese Klasse enthält das gemeinsame von GuessButton und AnswerButton.
GuessButton stammt von CircleColorButton ab. durch klicken mit der Maus kann die Farbe des Knopfes verändert werden.
AnswerButton Platz für ein Element der Antwort auf eine Frage. die möglichen Postionen sind "leer", "schwarz" und "weiss". Durch anklicken wird die Position umgeschaltet.
GuessPanel Enthält 4 GuessButtons.12 Ein GuessPanel dient zur graphischen Darstellung von einer Farbenkombination, also einem Guess.
AnswerPanel Enthält 4 AnswerButtons13. Ein AnswerPanel dient zur graphischen Darstellung einer Antwort, also eines Answers.
FactPanel Verbindung von GuessPanel und AnswerPanel, stellt dem Namen entsprechend ein Fact dar.
allFactsPanel Stellt alle bisher vorhandenen Fakten eines Spiels graphisch dar. Beim Anfangen eines neuen Spiels kann der Inhalt gelöscht werden.

Klassen zur Kommunikation mit dem Benutzer

Warning

youVeGotIt

Klassen für das Bilden verschiedener Dialogboxen
simplePlayer einfachere (für den Computer) Version des Master Mind Spiels, bei der der Benutzer eine Kombination erraten muss, an die der Computer gedacht hat. (Die Kombination wird mit einem Zufallsgenerator erstellt.)
Player für den Computer (und vor allem für den Programmierer) schwierigere Version des Spiels, bei der der Benutzer an eine Kombination denkt. Der Computer versucht diese Kombination in möglichst wenigen Schritten zu erraten.
Mind Diese Klasse ist als Applet implementiert. Das Applet enthält die Knöpfe "Guess Yourself" und "Let Computer Guess", je nach gedrücktem Knopf wird simplePlayer oder Player konstruiert und gestartet.

C++ Version des Programms

Für den Fall, dass das Java-Programm nicht gestartet werden konnte oder dass es als zu langsam erscheinen sollte, habe ich eine frühere Version davon, die ich in C++ geschrieben hatte und die auf Graphik verzichtet, auch auf die Diskette kopiert. Sie befindet sich im Verzeichnis a:\old_ver. In diesem Verzeichnis sind die nichtkompilierten Quelldateien. Das Programm auf der Diskette heisst a:\old_ver\mind.exe. Wenn man es startet, erscheint die Liste der möglichen Farben der Abkürzungsbuchstabe jeder einzelnen Farbe. Danach können Sie sich eine Farbkombination ausdenken, anschliessend muss man eine beliebige Taste drücken. Es werden drei Zeilen ausgegeben: Die benötigte Zeit zum Rechnen. Die Anzahl noch vorhandener Möglichkeiten für eine gedachte Farbkombination. Das vom Programm Geratene. (Die Farben werden durch einzelne Buchstaben bezeichnet.) Danach wird nach der Antwort gefragt. Nun kann man die Anzahl schwarzer und die Anzahl weisser Stäbchen angeben.

Autor:
Andras Niedermayer
1997