Computer-Othello

Der Disk-Square-Ansatz ist, verglichen mit dem Erfolg der beiden anderen Strategien, eher naiv und wird von menschlichen Spielern als ausschließliche Strategie nur im Anfängerbereich gespielt. Hierbei wird jedem Feld auf dem Spielbrett eine bestimmte Wertigkeit zugeordnet. Insgesamt gibt es zehn unterschiedliche Feldtypen auf dem Brett, die sich durch Spiegelsymmetrie auf das ganze Brett abbilden lassen.

• 
  DefaultDiskSquare

Die Abbildung oben stellt einen solchen Disk-Square-Ansatz dar, mit den kleinstmöglichen Faktoren. Der Algorithmus funktioniert trivial: Addiere die Werte aller gegnerischen Steine, die der Zug umdreht, und den Wert des Steines, den du setzt. Ausgegangen von folgender Spielsituation mit Weiß am Zug

• 
  SampleSetting

und dem oben gezeigten Ansatz würde sich also Zug A zu 1 + 3 + 5 = 9 und Zug B zu 2 + 8 = 10 ergeben. Somit wäre Zug B der bessere. Nun gelten die Felder, die im ersten Diagramm mit 7 und vor allem mit 8 bezeichnet worden sind, als besonders „schlecht“ für den eigenen Zug. Daher gewichten Disk-Square-Ansätze solche Felder meist anders[4], sodass insbesondere die Eck-Felder als besonders wertvoll gelten, die direkt daran grenzenden als besonders vermeidenswert, etwa so:

• 
  OtherAdjustment

Dann wäre Zug A: 1 + 1 + 5 = 7, und Zug B wäre: 1 + (−30) = −29. Und nun wäre Zug A besser. Für Entwickler von Othello-Programmen ist es eine besondere Herausforderung, diese Gewichtungen zu justieren. Ein Ansatz besteht darin, die Gewichtung mit dem Fortgang des Spiels neu zu berechnen. Hier belässt man es pro Feld nicht bei einem festen Wert, also einer konstanten Funktion, sondern berechnet entlang eines Parameters oder sogar mehrerer den Wert mit jedem Halbzug neu. In der einfachen Version ist der einzige Parameter der Halbzug-Zähler. So kann man etwa festlegen, dass in der Eröffnungsphase die Randfelder möglichst zu vermeiden sind, im späteren Verlauf des Spiels aber anzustreben.

Wenn man sich das Othello-Bord als Matrix vorstellt und alle Symmetrien berücksichtigt, lässt sich der entsprechende Algorithmus anschaulich darstellen:

${\displaystyle M(i)={\begin{pmatrix}f_{1}^{1}(i)&f_{2}^{1}(i)&f_{3}^{1}(i)&f_{4}^{1}(i)\\0&f_{2}^{2}(i)&f_{3}^{2}(i)&f_{4}^{2}(i)\\0&0&f_{3}^{3}(i)&f_{4}^{3}(i)\\0&0&0&0\end{pmatrix}}}$

(Die mit Nullen besetzten Komponenten der Matrix sind entweder über Symmetrien abgedeckt oder (wie ${\displaystyle f_{4}^{4}}$) bereits durch die Grundstellung bei Spielbeginn belegt.)

Für ${\displaystyle f_{k}^{j}}$ können nun passende Funktionen festgelegt werden. Da die Eckfelder besonders erstrebenswert sind, reicht in einem ersten Entwurf eine konstante Funktion, etwa ${\displaystyle f_{1}^{1}(i)=1}$. Für ein Randfeld, das wie oben gesagt zu Beginn des Spiels zu vermeiden, im Verlauf jedoch anzustreben ist, könnte eine passende Funktion lauten: ${\displaystyle f_{3}^{1}(i)={\frac {(i-32)^{3}}{32^{3}}}}$.

Komplexere Varianten übergeben weitere Parameter, etwa die Besetzung der umgebenden Felder mit eigenen und gegnerischen Steinen. Sehr ausgeklügelte Algorithmen dieser Art sind fast gleichwertig mit solchen, die andere Strategien anwenden, jedoch benötigen sie wesentlich mehr Rechenaufwand.

Dass vor allem Online-Implementierungen von Othello häufig auf dem Disk-Square-Algorithmus beruhen, liegt daran, dass er sich, wie gezeigt, mit sehr geringem Aufwand programmieren lässt.

Die meisten menschlichen Spieler streben danach, ihre eigene Mobilität (Anzahl der möglichen, erlaubten Züge) zu maximieren und zugleich die des Gegners zu minimieren. Darüber hinaus achten sie darauf, Grenzsteine (Steine, die an leere Felder grenzen) zu vermeiden. Gute menschliche Spieler erreichen, je nach Fähigkeit, auf diese Weise sehr schnell einen Vorteil. Mobilitäts-Algorithmen verfolgen dieselbe Strategie[5] und sind dabei im Vergleich zum Disk-Square-Ansatz wesentlich schneller. Viele Othello-Programme verfügen über Kenntnisse von Rand- und Eck-Spielstellungen, auf deren Basis sie sich darum bemühen, die eigene Anzahl von Spielsteinen während der Eröffnung und des frühen Mittelspiels so klein wie möglich zu halten. Einige Programme wie etwa NTest oder WZebra verfügen über eine so starke Mobilitätsbewertung, dass sie, selbst wenn sie ihren nächsten Halbzug einzig auf dieser Basis ermitteln und den Spielbaum völlig außer Acht lassen, auch für geübte Spieler nur schwer zu schlagen sind.

Einige Programme enthalten Algorithmen, die typische Spielsituationen erkennen. Othello ist ein Spiel, das wesentlich mehr Symmetrien enthält als etwa Schach, sodass es ausreicht, kleine Bereiche des Bretts zu analysieren. Es gibt beispielsweise typische „Fallen“ an den Rändern der Spielfelder, die (gedreht, gespiegelt) achtmal auftauchen können und die nach fünf Halbzügen zwangsläufig zur Besetzung eines Eckfeldes führen, sodass der Spielbaum hier gar nicht weiter durchsucht werden müsste. Wenigstens lässt sich einer solchen Konstellation ein bestimmter Wert zuordnen, der mit den weiteren Auswertungen verglichen werden kann. Gerade mit dem Aufkommen von Mehrkern-Prozessoren und der stetig wachsenden Verfügbarkeit von Hilfsmitteln innerhalb von Software-Entwicklungs-Werkzeugen, die diese Fähigkeiten unterstützen, kommt diesem Aspekt immer größere Bedeutung zu. Typischerweise kombinieren erfolgreiche Othello-Programme alle diese drei Methoden, wobei „Disk-Square“ und „Mustererkennung“ meist zum Ausschluss bestimmter Zweige im Spielbaum dienen, und „Mobilität“ die übrig bleibenden Zweige bewertet.