| Suchoptimierung und Evaluation bei Zwei-Personen-Nullsummen-Spielen am Beispiel von Mühle |  |
## Bedienungsanleitung ### Installation Unser Mühleprogramm verwendet die Programmiersprache JAVA. Zum Ausführen des Programms wird somit eine JAVA Runtime Enviroment ab Version 1.4 benötigt. Diese lässt sich zum Beispiel auf der Webeseite "http://java.sun.com" herunterladen und muss zuerst installiert werden. Nähere Instruktionen zur Installation von JAVA finden sich ebenfalls auf dieser Seite. Die Mühle-Software selbst liegt gepackt in Form einer .zip-Datei vor. Zur Installation muss diese Datei lediglich an einem beliebigen Platz auf der Festplatte entpackt werden. Das entpackte Archiv sollte dann die Dateien "muehle.exe" und "muehle.jar" enthalten, sowie vier weitere Ordner mit der Endspieldatenbank (falls heruntergeladen), den Heuristiken, einen für gespeicherte Spiele sowie einen für weitere Ressourcen. ### Programmstart Zum Start des Mühlespiels bieten sich mehrere Möglichkeiten. Unter dem Betriebssystem Windows lässt sich das Programm durch öffnen der Datei "muehle.exe" starten. Bei anderen Betriebssystemen (wie zum Beispiel Linux) muss das Spiel wie folgt aus einer bash per Kommandozeile gestartet werden: bash:/> java -jar muehle.jar Bei einem derartigen Aufruf per Kommandozeile hat man noch die Option, den "Verbose-Mode" einzuschalten, der die aktuelle Spieleinschätzung eines aktiven Computer-Spielers, der sich am Zug befindet, zurückgibt. Dieser Modus lässt sich mit dem Parameter "-v" aktivieren: bash:/> java -jar muehle.jar -v Die Bedienung des Spiels wird weiter unten beschrieben. Neben dem eigentlichen Spiel ist es auch möglich eine Lern- und Testumgebung aufzurufen, die zwei oder mehrere (selbst erstellte) Heuristiken lernen und testen lassen kann. Diese wird ausschließlich per Kommandozeile aufgerufen. bash:/> java -cp muehle.jar muehle.LernUmgebung [-options] heuristic_1 [-options] heuristic_2 ... Folgende Optionen können hierzu verwendet werden:
-v | setzt den Verbose-Mode, der die Spieleinschätzung des lernenden oder zu testenden Spielers ausgibt
-test | folgende Heuristiken werden nur getestet und lernen nicht
-d=xx | setzt die Denktiefe auf den festen Wert xx. Bis zu dieser Ebene wird unabhängig von der Zeit gedacht. Standard ist d=6
-t=xxxx | setzt die Denkzeit auf xx Millisekunden, die dem Computer-Spieler für einen Zug gegeben wird. Standard ist t=0
-r=x.xx | setzt einen Random-Radius, bis zu dem der eigentliche Spielwert zufällig verändert werden kann. Dies dient dazu, dass nicht immer wieder ein komplett identisches Spiel entsteht. Standard ist r=0.05
-l=x.xx | setzt den Lernparameter lambda. Wie dieser Parameter zu wählen ist, wird im Kapitel "Lernen beim Mühlespiel" beschrieben.
-q=xx | setzt die zusätzliche Denktiefe der Ruhesuchesuche auf den Wert xx. Standard ist q=0
Folgender Beispielaufruf lässt einen Computerspieler mit der Heuristik "max.xml" im Heuristikordner Partien gegen einen Computerspieler mit der Heuristik "joe.xml" im Heuristikordner spielen. Die Denkzeit des ersten Spielers darf 5 Sekunden betragen, der zweite Spieler soll immer 6 Ebenen weit denken. Beide Heuristiken werden nach jedem Spiel mit dem Lernparameter lambda=0.7 gelernt. Die Quiescent Search ist ausgeschaltet und als Random Radius wird r=0.1 verwendet. bash:/> java -cp muehle.jar muehle.LernUmgebung -r=0.1 -l=0.7 -q=0 -t=5000 max -d=6 joe Ein Aufruf für das Testen dieser zwei Heuristiken nach der Lernphase könnte dann so aussehen: bash:/> java -cp muehle.jar muehle.LernUmgebung -test -r=0 -t=5000 max joe Der Output der Lernumgebung umfasst jeweils die Gewinne, die Verluste und die Unentschieden pro Spieler in folgender Form: ... ************************************ max: Won: 153 Lost: 228 Remis: 133 joe: Won: 228 Lost: 153 Remis: 133 ************************************ max: Won: 154 Lost: 228 Remis: 133 joe: Won: 228 Lost: 154 Remis: 133 ************************************ Der Output beim Einschalten des Verbose-Mode sieht folgendermaßen aus: **************************************************************** Ebenen: 10 Maximal: 10 Zeit: 3484 ms Anzahl beste: 1 Knoten durchsucht: 149057 Spieleinschätzung: 0.047893886778407 NetworkOutput: [0.6130141761393355], [0.6318124177361016], [0.5] **************************************************************** Abzulesen sind die Anzahl der gedachten Ebenen, die Anzahl der maximalen Ebenen, die durch Verwendung der Ruhesuche erreicht wurden, und die Denkzeit für den letzten Zug. Außerdem wird die Anzahl der als gleichstark berechneten besten Züge ausgegeben. Bei mehreren besten Zügen wird ein zufälliger gewählt. Eine weitere Information ist die Anzahl der durchsuchten Knoten im Spielbaum. Schließlich wird die Spieleinschätzung der Partie nach einer Minmaxsuche mit der angegebenen Anzahl an Ebenen und die direkte Heuristische Einschätzung der aktuellen Spielsituation durch das Neuronale Netzwerk ohne Minmax-Suche ausgegeben. ### Spielbedienung Nach dem Starten des Mühle-Programms sieht man im Programmfenster drei Bereiche: Der Spielbereich mit dem Mühlebrett, der Status-Bereich (unten). Hier werden die vergangenen Züge angezeigt, Systemmeldungen ausgegeben und bei Netzwerkspielen Nachrichten des Partners angezeigt. Der Bereich rechts am Rand gibt Auskunft, welcher Spieler an der Reihe ist und wieviele Steine die Spieler noch setzen können beziehungsweise auf dem Spielfeld haben. Folgender Screenshot zeigt das Programmfenster nach dem Start. Nach Programmstart beginnt automatisch ein Standard-Spiel gegen einen voreingestellten Computer-Spieler. Man kann nun also entweder ein Standardspiel beginnen oder aber vor dem Spiel noch einige Einstellungen festlegen, wie zum Beispiel den eigenen Namen, die Denkzeit und Heuristik des Gegners und weitere Einstellungen. Hierzu wählt man aus dem Menü-Eintrag "Einstellungen" und den Menüpunkt "Spieler". In dem erscheinenden Dialog hat man nun zahlreiche Möglichkeiten das Spiel zu konfigurieren. Der Dialog ist unterteilt in zwei Bereiche, den linken für den ersten Spieler, den rechten für den zweiten Spieler. Der erste Spieler besitzt die weißen Steine und beginnt das Spiel. Für jeden Spieler kann man einen Namen eingeben und wählen, ob ein Mensch, ein gewöhnlicher Computerspieler oder ein lernender Computerspieler spielen soll. Im Falle eines (lernenden) Computerspielers lässt sich desweiteren entweder eine feste Denktiefe oder eine feste Denkzeit festlegen, die der Computer für einen Zug verwenden darf. Auch die Tiefe der Ruhesuche lässt sich hier einstellen, wobei "0" die Ruhesuche ausschaltet. Für Computer-Spieler lässt sich dazu optional eine Heuristik auswählen, die anstatt der Standard-Heuristik verwendet werden soll. Im Falle eines lernenden Computerspielers ist die Angabe einer Heuristik obligatorisch. Existiert eine angegebene Heuristik nicht, wird eine zufällige neue Heuristik mit entsprechendem Namen erstellt. Ein Screenshot dieses Dialogs ist in folgender Abbildung dargestellt. Für den zweiten Spieler ist zusätzlich die Option "Netzwerkspieler" möglich. Diese kann verwendet werden, um im Netzwerk oder über Internet Partien gegen einen anderen Menschen, der sich nicht am selben Computer befindet, zu spielen. In diesem Fall muss man sich entscheiden, ob man für das Spiel die Funktion des Servers übernehmen will, zu dem sich ein Spielgast (Client) verbinden kann, oder man sich selbst als Client zu einem anderen Server verbinden möchte. Im Falle des Serverbetriebs muss man noch einen beliebigen Port wählen, auf dem die Verbindung aufgebaut werden soll. Der Standard-Port liegt auf 9000. Im Clientbetrieb muss zu der Portnummer noch die Host-Adresse (IP-Adresse oder DNS-Name) des Servers eingetragen werden. Folgende Abbildung zeigt diesen Zusammenhang. Durch einen Klick auf den Button "Spiel starten" wird ein neues Spiel mit den hier getroffenen Einstellungen gestartet. Die Spielstäre eines Computer-Spielers, welche natürlich auch schon von der festegelegten Denkzeit abhängt, lässt sich unabhängig davon unter dem Menüpunkt "Einstellungen / Spielstärke" noch auf drei Stufen einstellen: Anfänger, Fortgeschrittener und Profi. Der Spielablauf selbst ist intuitiv. Wenn man an der Reihe ist, wird durch das Klicken mit der linken Maustaste auf ein freies Spielfeld ein eigener Stein dorthin gesetzt. Wenn durch das Setzen eines eigenen Steines eine Mühle geschlossen wird, kann durch Klicken auf einen Stein des Gegeners dieser aus dem Spiel genommen werden. Die jeweils letzte Aktion wird zur besseren Orientierung auf dem Spielbrett farbig markiert. Diese Einstellung lässt sich unter dem Menüpunkt "Einstellungen" ändern. Wenn die Setzphase vorüber ist, kann kein Stein mehr gesetzt werden. Nun wird per Drag&Drop ein eigener Stein auf ein benachbartes Feld geschoben. Das Schmeißen eines gegnerischen Steines geschieht weiterhin so wie oben beschrieben. Im Endspiel (nur noch drei eigene Steine) kann ein eigener Stein entsprechend den Regeln per Drag&Drop auf ein beliebiges freies Feld gezogen werden. Während der Partie besteht außerdem die Möglichkeit sich einen Zugvorschlag einzuholen. Dieser wird auf Basis derselben Heuristik erstellt, die der entsprechende Gegner verwendet, und bekommt maximal 5 Sekunden Zeit zur Berechnung. Beim Spiel Mensch gegen Mensch und im Netzwerkspiel ist ein Zugvorschlag nicht möglich. Schließlich besteht noch die Möglichkeit dem Mitspieler ein Remis anzubieten oder die Partie aufzugeben. Beide Optionen befinden sich unter dem Menüpunkt "Spiel". Dort befindet sich auch die Option "Neues Spiel", die eine neue Partie mit denselben Einstellungen beginnt. Bei Netzwerkspielen darf so lange kein neues Spiel begonnen werden, bis das aktuelle Spiel beendet ist, sei es durch reguläres Ende der Partie oder durch Aufgabe eines Spielers. Folgende Abbildung zeigt einen Screenshot mitten aus einem Spiel. Die grüne Markierung bedeutet, dass der schwarze Spieler von Feld a1 auf Feld a4 gezogen ist. Durch das Schließen der Mühle darf schwarz also einen weißen Stein aus dem Feld nehmen. Die rote Markierung zeigt, dass sich der Spieler für den Stein auf Feld b6 entschieden hat. Diesen Sachverhalt gibt auch die Ausgabe im Statusbereich zurück: "Zug von Spieler2: a1-a4 xb6". Unser Mühleprogramm erlaubt auch das Speichern und Laden von Partien, sowie das Drucken des aktuellen Spielbretts mit den Aktionen, die zu diesem geführt haben, zu jedem Zeitpunkt der Partie. Diese Optionen sind ebenfalls unter dem Menüpunkt "Spiel" aufzurufen. Ein Beispielausdruck einer Partie ist in folgender Abbildung zu sehen. Zu guter Letzt lassen sich mit dem Dialog "Heuristik erstellen" unter dem Menüpunkt "Einstellungen" eigene Heuristiken anlegen, die dann im Mühlespiel oder mit der Lernumgebung trainiert werden können. Folgende Einstellungen sind hier möglich: Layer bezeichnet die Anzahl der Layer aus denen das Neuronale Netzwerk bestehen soll. Dabei bezeichnet ein Layer ein Single-Layer-Netzwerk. Bei mehr als einem Layer wird ein Multi-Layer-Netzwerk mit entsprechender Anzhahl an Hidden-Layern erstellt. Unter Features kann man das Feature-Set wählen, das zu heuristischen Einschätzung herangezogen werden soll. Die Beschreibung der verschieden Feature-Sets sind in der Ausarbeitung unter dem Kapitel "Heuristiken im Spielbaum" nachzulesen. Für jeden Layer lässt sich nun noch die Anzahl der Knoten und der Typ der Aktiverungsfunktion festlegen. Für den ersten Layer gibt es allerdings stets drei Knoten, da sie den Output des Neuronalen Netzwerkes, also Gewinn-, Verlust- und Remis-Anteil bei der Einschätzung einer Spielsituation, darstellen. Darüber hinaus können hier auch die weiteren Parameter für den Lernvorgang im Neuronalen Netzwerk (siehe Kapitel "Lernen im Multilayer Neural Networks") gesetzt werden. Folgende Abbildung zeigt diesen Dialog.
Letzte Aktualisierung: 04.03.2005 - Bastian Späth