Implementation

Das wichtigste ist, dass ihr korrekten Code schreibt. Ein Spieler der einen super schnellen Algorithmus implementiert, eine passende Bewertungsfunktion hat und das Spiel sehr früh ganz lösen kann, aber alle zehn Züge einen falschen Zug macht, eine NullPointerException wirft oder sonstige Fehler macht, wird das Turnier nicht gewinnen. Hier deshalb einige Tipps für eine korrekte Implementation und Debugging bevor Performance Tipps folgen.

Design by Contract

Design by Contract bedeutet grob gesagt, dass man erst definiert was für Parameter die Funktion bekommt, was der Rückgabewert ist und welche Bedingungen diese Werte erfüllen.
Für den Alpha-Beta-Algorithmus und Reversi sollte beispielsweise gelten, dass

• alpha kleiner ist als beta
• Das Steindifferenz immer zwischen -64 und 64 liegt
• Das die Anzahl leerer Felder nach einem gemachten Zug um 1 kleiner ist als vor diesem Zug

Es lassen sich noch weitere solcher Bedingungen aufstellen, die helfen können das Programm zu debuggen.
Hierfür sind sogenannte Assertions sehr nützlich. Diese können ins Programm eingefügt werden und werden nur überprüft wenn man der JVM das entsprechende Flag ("-ea") übergibt.

Sonderfälle im Spiel

Die unter der Algorithmus-Seite beschriebenen Algorithmen decken zwei Fälle nicht ab:

1. Ein Spieler muss passen
2. Die Zeit ist abgelaufen

Ersteres ist daran erkennbar, dass ein Spieler keine Züge zur Verfügung hat. Zweiteres muss über das Timeout und System.currentTimeMillis() überprüft werden, am Besten bei jedem rekursiven Aufruf.

Performance Tipps

Um die Performance seines Spielers zu verbessern gibt es einerseits algorithmische Optimierungen, wovon einige auf der MiniMax-Seite beschrieben sind.
Andererseits gibt es auch Tipps um einfach mehr Positionen pro Zeit zu untersuchen. Beide Schritte sind wichtig um einen guten Spieler zu schreiben.

Statische Zugvorsortierung

Eine einfache Möglichkeit seine Züge zu sortieren, ist zu Beginn (beispielsweise in initialise eine geordnete verlinkte Liste mit allen Koordinaten zu erstellen, mit welcher man dann während der Spielbaumsuche die Züge überprüft. Diese Ordnung basiert dann auf einer statischen Einschätzung jedes Spielfeldes. Dies kann helfen, die Anzahl Knoten pro Tiefe zu minimieren.
Noch etwas effizienter, wäre es wenn man die Liste jeweils nach einem Zug anpasst, so dass nur leere Felder in der Liste sind. Wenn man auf die Sortierung nicht verzichten will, reicht hier aber eine einfach-verlinkte Liste nicht...

Dynamische Zugsortierung

Falls man die Züge vorgeneriert, bevor sie nacheinander überprüft werden, kann man jeden Zug anhand von Metriken einen Wert geben. Beispiele hierfür können der Bewertungsseite entnommen werden. Falls eine Position beim Blatt gut ist, kann sich schon mitten im Baum abzeichnen. Aus Zeitgründen sollte aber nur einfache Heuristiken verwendet werden (Beispielsweise nur Ecksteine plus Nachbarn anstatt alle stabilen Steine) oder nur eine viel kleinere Baumsuche verwendet werden.

Spielfeld

Die GameBoard-Klasse die im Reversi-Framework implementiert ist, ist zwar korrekt, aber nicht sehr performant.
Da man gezwungen ist, checkMove vor makeMove aufzurufen, muss man entweder doppelte Arbeit verrichten oder man ist auf statische Zugvorsortierung beschränkt. Zudem muss nach einem Zug immer eine neues Board vom alten kopiert werden, da Züge nicht rückgängig gemacht werden können. Speicher allozieren braucht Zeit, und den ganzen Zustand wiederherstellen auch.
Effizienter geht das mit einer eigenen Klasse, welche das Spielfeld repräsentiert: Beispielsweise mit einem langen Array (dazu braucht es nicht ganz 100 Felder, da beim nebeneinander legen, der rechte und linke Rand dasselbe ist) oder als BitBoards. Vor allem letztere erlauben es sehr schnell alle gültigen Züge zu finden, was vor allem im Endspiel ein grosser Vorteil ist.

Zeit-Management

Die meiste Zeit bei der Spielbaumsuche wird in der Nähe der Blätter verbracht. Zudem ist einer Spielbaumsuche auf Tiefe 1, 2 und 3 sehr schnell. Da der Aufruf von System.currentTimeMillis() sehr viel Zeit braucht (kann getestet werden mit einer einfachen while-loop und einem Counter, einmal mit, einmal ohne den Aufruf, einmal nur alle 100 Iterationen und das ganze 5000 Iterationen laufen lassen), kann man sich überlegen bei Tiefen {x <= X | X < 4} den Zeit-Check wegzulassen. Dies kann in diesen Performance-kritischen Momenten Zeit sparen, was es erlaubt mehr Positionen pro Zeit zu analysieren. Man sollte dabei bedenken, dass ein unerwarteter Aufruf des GarbageCollectors eventuell dazu führt, dass man die Zeitlimite überschreitet.

Endspiel

Um möglichst früh das Endresultat zu wissen, so dass man nicht mehr schätzen muss ob der Zug gut ist oder nicht, lohnt es sich nicht alle Tiefen durchzurechnen. Macht man beispielsweise einen Sprung auf die exakte Tiefe sobald die Tiefe d + 3 >= leereFelder kann man vielleicht seinen Gegner übertrumpfen. Je nachdem wie schnell ein Algorithmus kann die konstante auch durch 5, 7 oder sogar 10 ersetzt werden.

Steindifferenz berechnen

Wenn ein Spiel zu Ende ist, also wenn beide Spieler keinen Zug mehr machen können, sollten die Anzahl leere Felder dem Spieler mit mehr Steinen angerechnet werden. Sonst ist beispielsweise ein 15:0 Sieg aus Sicht des Spielers schlechter als ein 40:24 Sieg.