Index

Überblick

Algorithmen

Anhang

Teil 3 von 4


10. Die Board-Klassen

Die Aufgabe der ersten Teilgruppe war die Implementierung einer Klasse, in der das Reversi-Spielbrett abgelegt werden konnte. Aus Gründen des Speicherplatzbedarfs und der Vereinfachung beschlossen wir, den Datentyp Board, der ein Spielfeld und die Grundlegenden Zugriffsfunktionen enthalten sollte, nicht an den in ´GameStatus´ angebotenen Datentyp anzulehnen, sondern für unsere Zwecke eine eigene Klasse zu implementieren. Dies schien uns den Vorteil zu haben, daß wir in der Ausarbeitung an keiner Stelle durch von anderen getroffene Konventionen eingeschränkt wären.

Die Klasse SmartBoard sollte das Board, welches nur die grundlegendsten Funktionen wie Steine setzen und umdrehen erfüllte, um andere Funktionen erweitern, wie das Errechnen der legalen Züge oder zum Beispiel das Ausführen eines Zuges. Dies erfordert außer dem trivialen Setzen eines Spielsteins noch das Umdrehen der eingeschlossenen Steine. Diese Funktionen wurden zuerst ohne Beachtung der Dauer auf einfache, aber zeitaufwendige Arten implementiert.

Die zweite Erweiterung des Boards (also in Wirklichkeit eine Erweiterung der Klasse Smartboard) trägt den Namen EvalBoard und liefert vor allem die statische Bewertungsfunktion für Spielbretter, auf deren genaue Funktionalität weiter unten eingegangen werden soll. Außerdem enthält eine Instanz der Klasse EvalBoard noch einige Instanzenvariablen wie eine Variable, in der die Bewertung abgelegt werden kann, und einen Verweis auf ein nächstes EvalBoard, um die Evalboards als Liste behandeln zu können.

Aus dem zu den Spielfeldern schon genannten Gründen haben wir auch eine Klasse MoveNode geschrieben, die einen Zug enthält; und außerdem eine Klasse MoveList (eine Liste von Zügen als Movenodes). Dieselbe Klasse List, die zur Erzeugung der MoveList herangezogen wurde, sollte dann, leicht abgewandelt, auch die EvalBoardList (eine Liste von EvalBoards) realisieren. Als letzte zu unserem Bereich zu erwähnende Klassen sind noch HashTable und HashTree zu erwähnen, durch welche die während eines Spiels ermittelten statischen Bewertungen jedes schon aufgetretenen Spielbrettes zwischengespeichert werden, um die Zeit, die ein nochmaliges Berechnen brauchen würde, einzusparen.

Die grundlegende Implementierung der drei 'Board'-Klassen konnte sehr zügig abgeschlossen werden, doch die Diskussion kam auf, ob man das Spielfeld in einem 8x8 Felder großen Byte-Array speichern sollte, oder doch besser in bitweise beispielsweise in zwei 64-Bit Variablen, wobei die erste Variable Einser für besetzte und Nuller für unbesetzte Felder enthält und die zweite ebenso die Farbe der besetzten Felder angibt. Vorteil der ersten Variante ist da ganz klar die Übersichtlichkeit und dadurch auch später die erleichterte Fehlersuche, wobei die zweite Variante uns durch die zu erwartenden Geschwindigkeitsgewinne und den geringeren Speicherbedarf bei eventueller Speicherung von Spielständen und auch bei Aufbau des Spielbaumes als die bessere erschien. Wir mußten jedoch wider Erwarten feststellen, daß (zumindest in Java) bei den durchgeführten Geschwindigkeitsvergleichen die Bit-Variante nicht annähernd an die kurzen Zeiten der Feld-Implementierung heranreichte. Bitweise Operationen sind in Java scheinbar sehr umständlich eingebunden, was dann später bestätigt wurde, als ein Test ergab, daß eine Multiplikation mit 8 deutlich schneller geht als dreimal linksshift.(..?) Das haben wir zwar so nicht ganz verstehen können, aber wir haben das Spielfeld dann doch als Byte-Feld implementiert. (Henrik Stürzebecher)

 

11. Der Bewertungsalgorithmus

Aus der einschlägigen Fachliteratur haben wir ein Verfahren entnommen, das bei der Ermittlung der legalen Züge Geschwindigkeitsvorteile bringen soll und ausserdem gute Bewertungsmöglichkeiten bieten soll. Unser bisheriges Verfahren geht der Reihe nach alle 64 Felder durch und überprüft, ob dort ein legaler Zug gesetzt werden kann (in alle 8 Richtungen). Das neue Verfahren basiert auf Betrachtung der 'Strahlen' des Spielfeldes. Diese Strahlen sind alle Spalten, Reihen und Diagonalen des Spielfeldes von mindestens Länge drei. Ein Zug kann nur dann legal sein, wenn er auch isoliert betrachtet in einem der Strahlen ein legaler Zug ist. Die Strahlen mit einer Länge kürzer als drei sind hier uninteressant, da innerhalb dieser Strahlen keine Zugmöglichkeit entstehen kann. Es werden bei diesem Verfahren jetzt nur noch die 38 Strahlen überprüft. (acht Spalten + acht Reihen + zweimal elf Diagonalen ergibt 38 Strahlen) Dabei kann jeder Zug bis zu viermal auftreten, man muß also dafür sorgen, dass jeder Zug nur einmal in die Liste der legalen Züge eingefügt wird. Da der Strahl mit einem sehr einfachen Algorithmus durchlaufen werden kann, ist es in der Tat die schnellere Variante, die 38 Strahlen mit maximal acht Feldern zu überprüfen als An allen 64 Feldern in die acht Richtungen zu schauen. Die Vorteile der Strahlenmethode für die Bewertung werde ich später noch ansprechen.

Eine weitere Chance zur Steigerung der Geschwindigkeit bei der Berechnung der legalen Züge bietet die Möglichkeit, eine Tabelle aufzustellen, in der man nachschauen kann, bei welcher Belegung der Felder an welchen Stellen legale Züge möglich sind. Daran ist für das gesamte Spielbrett (drei hoch 64 Permutationen!) sicher nicht zu denken, doch für die Strahlen mit maximaler Länge von acht Feldern (also nur drei hoch acht = 6561 Möglichkeiten) ist das kein Problem. Dieser Tabellenzugriff spart sicher gegenüber der Berechnung der legalen Züge Zeit, und somit haben wir diese Möglichkeit implementiert.

Unsere Bewertungsfunktion basiert auf 7 verschiedenen Merkmalen: Mobilität, also die Differenz der Zugmöglichkeiten beider Spieler, und potentielle Mobilität, also die Differenz von an gegnerische Steine angrenzenden Feldern, sind die beiden wichtigsten Merkmale. Diese Merkmale können durch die schon zur Ermittlung der legalen Züge verwendeten Strahlenmethode approximiert werden, ohne das Nachteile für die Qualität der Bewertungsfunktion entstehen. Zur Ermittlung der Werte für Mobilität und potentielle Mobilität waren auf diese Weise auch nur ein paar Tabellenzugriffe notwendig.

Die weiteren Merkmale sind die Reihen und Spalten, wobei die vier Randreihen ein Merkmal ergeben, die vier mit einem Feld Abstand zum Rand, die mit zwei Feldern Abstand zum Rand und die in der Mitte. Da das Feld symmetrisch ist, ist es nicht nötig hier Reihen und Spalten zu unterscheiden. Als letztes Merkmal wurden diejenigen zwei mal vier Felder großen Feldabschnitte benutzt, die ein Eckfeld enthalten. Um zu Bewerten, welche Stellungen auf den Strahlen und Feldabschnitten wie zu bewerten sind, haben wir einhunderttausend im Internet verfügbare Othellospiele ausgewertet, indem wir abzählen ließen, wie oft jede beliebige Stellung in welcher Spielphase (acht gleich lange Spielabschnitte) vorkam und ob sie dann zu einem Sieg führte oder nicht.

Die relative Gewichtung der Merkmale haben wir angelehnt an die Ausführungen von Dr. Michael Buro durchgeführt. Dies sieht so aus, daß zu Beginn vor allem die potentielle Mobilität einen hohen Stellenwert einnimmt (was dazu führt, daß zu Spielbeginn nur sehr wenige Steine der eigenen Farbe auf dem Brett sind, mit Vorliebe aber innere), im Mittelspiel eher die Mobilität, die dann gegen Ende von einer sehr starken Gewichtung der zwei mal vier Eckenmuster abgelöst wird. (Henrik Stürzebecher)

12. Spielbaum

Als Implementation des Spielbaums entschieden wir uns für den aus der Vorlesung bekannten alpha-beta-Algorithmus. In weiteren Ausbaustufen sollte dann noch Last-Window-Improvement und Nullfenstersuche implementiert werden. Da die Nullfenstersuche eine Erweiterung des Last-Window-Verfahren ist, entschlossen wir uns nur die Nullfenstersuche zu verwenden. Da wir bereits eine durch die Bewertungsfunktion vorsortierte Zugliste erhalten, sollte sowohl der Alpha-Beta-Algorithmus als auch die Nullfenstersuche eine sehr gute Verbesserung erzielen.

Durch einige Verständnisprobleme des Alpha-Beta-Alogrithmus mußten wir diesen insgesamt zwei mal programmieren. Eines der Probleme war zum Beispiel, ob die Bewertungen der Bretter im aus Sicht eines Spielers, oder des gerade anspielenden Spielers zu sehen ist. Anfangs wurden zwei Methoden für Min. und Max. verwendet, da jedoch dauerende Änderungen des Source-Codes, die dann an beiden Stellen ausgeführt werden mussten, die Verwaltung unnötig vergrößerten, entschlossen wir uns, den NegaMax-Alg. zu verwenden. Nachdem dieser nach einigen Korrekturen funktionierte, erweiterten wir ihn um die Nullfenstersuche, nur um zu erkennen, daß diese allem Anschein nach absolut keinen Geschwindigkeitsgewin brachte (eher das Gegenteil).

Da in den Spezifikationen die Rückgabe vorläufiger Züge vorgesehen, bot es sich an, die Berechnungtiefe des Spielbaums iterativ nach oben zu setzen. D.h. es wird zuerst nur eine Ebene berechnet und dieser Wert vorläufig zurückzugeben. Durch die unten beschriebene Hashing-Funktion würden dann bereits errechnete Evaluationswerte schnell wieder zur Verfügung stehen. Leider ließ sich diese Idee nicht vollständig in die Realität umsetzen, da vorläufige Züge leider aufgrund nicht funktionsfähiger Netzwerkroutinen nicht zur Verfügung standen, mußten wir diese Zwischenwerte intern speichern, was auch die Timing-Routinen wesentlich komplizierter machten (siehe unten). Wegen diversen Problemen mit der Hashing-Funktion konnten wir dessen Funktionalität leider auch nicht nutzen.

Die zuerst angedachte Vorgehensweise könnte man zusammenfassend nocheinmal so beschreiben: Eine übergeordnete Routine holt das zu bearbeitenden Spielbrett ab, und übergibt es der Baumroutine (doTree), diese Berechnung zuerst 1 Ebene tief einen möglichst guten Zug. Dieser wird als vorläufiger Zug zurückgeschickt, gleichzeitig wird überprüft, ob dieser Zug aktzeptiert wird, oder ob bereits ein neues Spielbrett anliegt, in beiden Fällen wird die DoTree-Routine abgebrochen, ansonsten wird die bis Ebene 2 gerechnet, durch die Hashing-Funktion erhält man die aus Ebene 1 bereits errechneten Werte schneller. Um Timing muss man sich dabei also fast keine Gedanken machen.

Da sich allerdings wie bereits erwähnt, dieses Verfahren nicht durchsetzen liess, implementierten wir ein Thread-Mechanismus, der auf die Multihreading-Fähigkeit von Java aufbaut, was sich leider ebenfalls als nicht vollständig funktionsfähig bzw. geeignet erwieß. So kamen wir letztendlich zur der einfachsten Implementation mit einer Routine, die regenmässig aufgerufen wird, und kurz vor überschreiten der Zeit ein Flag setzt, welches die doTree-Routine zur Abbrechen zwingt. (Martin Girschick)

 

13. Hashing

Da vor Berechnug eines Spielbaumes zuvor schon der nächstkleinere Baum berechnet worden ist, wollten wir Rechenzeit einsparen, indem wir die Spielbretter, die in diesem Baum schon einmal vorkamen, nicht neu bewerten, sondern die schon erfolgte Bewertung abrufen. Dazu müssen diese Bewertungen ohne grossen Zeitaufwand zwischgengespeichert werden.

Dies haben wir realisiert, indem wir jeweils einen Binärbaum für alle Spielstände mit derselben Anzahl von gesetzten Steinen aufbauen. Um die Spielstände zu sortieren, muß ihnen ein relativ kurzer Schlüssel zugewiesen werden, nach dem jedoch eine möglichst eindeutige Zuordnung erfolgen sollte. (Eine eindeutige Zuordnung würde einen definitiv ineffektiv langen Schlüssel erfordern.)

Zur Implementierung gibt es folgendes zu sagen. Die Hashtable sollte als eigenständiges Objekt existieren. Da es auch nur ein Objekt davon zur Laufzeit geben sollte wurden alle Methoden und Attribute statisch deklariert. Als öffentliche Schnittstelle gab es nur drei Methoden:

cutOf()

zum Löschen nicht mehr benötigter Einträge, um Speicher freizugeben.

haveCached()

ist 'true', wenn schon ein Spielstand mit diesem Schlüssel existiert.

cache()

fügte einen Spielstand ein.

Hashing war zwar eine einleuchtende Idee, jedoch war die Zeitersparnis eher minimal. Nachdem es zuerst so schien, daß durch Hashing der Zeitaufwand vergrößert würde, ließ sich nach weiteren Optimierungen eine Zeitersparnis von (nur) ungefähr zehn Prozent erzielen. Diese Ersparnis sollte sich dadurch erhöhen, daß während des gegnerischen Zuges der Hashtable soweit möglich gefüllt werden sollte. Leider gibt es in Java kein Möglichkeit, festzustellen ob noch ausreichend freier Speicher zur Erstellung dieser Tabelleneinträge zur Verfügung steht. Deshalb konnten wir nicht verhindern, daß auf den überlasteten Rechnern immer wieder ein 'OutOfMemoryError' erzeugt wurde, was uns zwang, den Hashtable wieder aus dem Programm zu entfernen.

 

next...