Computer-Othello

Computer-Othello ist die Umsetzung des Spiels Othello für Computer durch Algorithmen.

Es gibt zahlreiche Othello-Programme, beispielsweise NTest, Saio, Edax, Caissio, Herakles, WZebra und Logistello. Diese können kostenlos aus dem Internet heruntergeladen werden. Die genannten Programme sind in der Lage, die besten menschlichen Spieler zu schlagen, wenn sie auf aktueller Hardware ausgeführt werden. Darüber hinaus existieren zahlreiche Implementierungen, die, etwa per Java-Applet, direkt online gespielt werden können. Diese sind jedoch in der Regel weit weniger spielstark als die o. g. Programme. Weiterhin existieren Programme, die sich an ambitionierte Spieler wenden und bestimmte Spielsituationen trainieren helfen sollen. Ein bekannter Vertreter ist Happy End, der dabei hilft, in einer nicht eindeutigen Endspiel-Situation die richtigen Züge zu erkennen, um am Ende mehr Spielsteine als der Gegner zu besitzen. Andere Programme dienen dem „Pauken“ von Spieleröffnungen, deren Kenntnis für Turnierspieler essenziell ist, ganz ähnlich wie beim Schach.

Othello-Programme suchen mögliche erlaubte Züge i. d. R. mittels eines Suchbaums. Sie untersuchen alle Positionen (Knoten des Baums), also jeden Halbzug (engl.: ply), solange bis der Baum vollständig durchlaufen wurde, eine gewisse Suchtiefe erreicht wurde oder eine gewisse Zeit ablief. Triviale Algorithmen wie Minimax oder Negamax können den Baum innerhalb einer akzeptablen Zeit nur bis zu einer geringen Tiefe durchsuchen. Daher wurden mit der Zeit effizientere Algorithmen gesucht und formuliert. Diese basieren meist auf Alpha-Beta-Suche, Negascout, MTD-f, NegaC*^[1]. Neuere Hardware erlaubt die Nutzung mehrerer Prozessorkerne. ABDADA^[2] und APHID^[3] sind bekanntere Beispiele hierfür. Diverse auf Pseudozufallszahlen basierende Ansätze mit erfolgreichen Algorithmen wie Monte-Carlo Tree Search (MCTS), Upper Confidence Bounds (UCB) oder UCB applied to Tree Search (UCT) werden ebenfalls alternativ verwendet.

Othello ist, genau wie das bekannte Schulpausen-Spiel Tic-Tac-Toe, ein endliches Spiel. Somit gibt es eine endliche Anzahl von möglichen Spielverläufen. Die Anzahl der Knoten und Blätter eines vollständigen Spielbaums beträgt etwa 10⁵⁴, und die Anzahl der möglichen, erlaubten Züge, beträgt etwa 10²⁸. Diese Zahl stellt jedoch auch für die heutzutage stärksten Computer eine so große Herausforderung dar, dass es, insbesondere auf Personal Computern, unmöglich ist, das gesamte Spiel zu berechnen und auf Basis des Ergebnisses einen Zug auszuwählen. Deswegen sind verschiedene Ansätze entwickelt worden, um Züge zu bewerten. Die wichtigsten drei lauten:

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.

Zwar ist Othello ein endliches Spiel, jedoch reicht die heutige Rechenleistung nicht aus, um ein Spiel innerhalb eines Zeitraums, der etwa für ein Turnier angemessen ist, komplett auszurechnen. Um Programmen im Eröffnungs- und im Endspiel einen Vorteil zu geben, verfügen diese deswegen über eine Eröffnungs- und teilweise auch über eine Endspiel-Bibliothek. Diese haben im Allgemeinen keine festgelegte Zugtiefe, sondern sind derart gestaltet, dass Spielkonstellationen, die schnell eine eindeutige Bewertung gestatten, nur mit geringer Tiefe enthalten sind, und solche, die knapp sind, mit weit größerer Tiefe gespeichert verfügbar sind. Die meisten spielstarken Othello-Programme verfügen über eine Eröffnungsbibliothek, etwa die Thor-Datenbank, die auf zahlreichen Spielen besonders starker Spieler, insbesondere auch allen Spielen der Weltmeisterschaften basiert. Einige Programme enthalten auch Endspiel-Bibliotheken, die so ähnlich funktionieren wie das o. g. Trainingsprogramm Happy End. Zur Minimierung des Datenbestands werden auch hier die zahlreichen Symmetrien von Othello ausgenutzt.

1978: Nintendo veröffentlichte das Arcade-Spiel Computer Othello.

1980: Das Programm Moor (von Mike Reeve und David Levy) gewann eins von sechs Spielen gegen den Weltmeister Hiroshi Inoue.

Frühe 1980er: Paul Rosenbloom entwickelte das Othello-Programm IAGO. IAGO zeigte sich in Spielen gegen Moor überlegen darin, die gegnerische Mobilität zu minimieren.

1984: Das von Robert Woodhead programmierte Computer-Othello wird unter dem Namen Reversi dem Mac OS-Betriebssystem für den Apple Macintosh 128k beigefügt.^[6][7]

1985: Unter Namen Reversi wurde es bei Microsoft Windows 1.0 mitgeliefert^[8][9] und bleibt bis 1998 Microsoft Windows 98 als Spiel im Betriebssystem enthalten. Bei Windows ME und Windows XP war es nur noch als Onlinespiel enthalten.^[10][11]

Späte 1980er: Kai-Fu Lee und Sanjoy Mahajan schrieben BILL, ein Programm, das IAGO ähnelt, jedoch bayessches Lernen implementierte. BILL konnte IAGO regelmäßig schlagen.

1992: Michael Buro begann mit seiner Arbeit am Programm Logistello. Logistellos Algorithmen zur Berechnung von Zügen und die Implementierung von Mustererkennungen machten das Programm überlegen im Vergleich zu älteren Programmen. Außergewöhnlich war, dass Logistello über 100.000 Spiele gegen sich selbst bestritt, um seine Fähigkeiten zu verbessern.

1997: Logistello gewann alle von sechs Spielen gegen den Weltmeister Takeshi Murakami. Auch wenn die Fachwelt sich sicher war, dass Othello-Programme früher oder später stärker spielen würden als menschliche Spieler, war es 17 Jahre her, seit ein Programm gegen einen amtierenden Weltmeister gespielt hatte. Nach diesem Turnier gab es jedoch keinen Zweifel mehr: Logistello war jedem menschlichen Spieler weit überlegen.^[12]

2004: Ntest rang den Titel des stärksten Othello-Programms von Logistello ab.^[13]

2005: Ntest, Saio, Edax, Cyrano und WZebra wurden in ihren aktuellen Versionen wesentlich spielstärker als Logistello. Ntest und WZebra wurden seitdem nicht mehr weiterentwickelt, sind jedoch auch heute noch für ambitionierte Spieler, gerade wegen ihrer historischen Bedeutung, beliebte Herausforderungen.

2011: Saio, Edax und Cyrano zeigten, etwa im Vergleich zur Referenz Logistello, wie sehr sich Othello-Programme optimieren lassen.

• Saio von Benedetto Romano
• Edax von Richard Delorme
• Cassio von Stéphane Nicolet
• NTest von Chris Welty
• WZebra von Gunnar Andersson
• Pointy Stone von Jonathan Kreuzer
• Herakles von Kostas Tournavitis – das stärkste 10×10-Othelloprogramm
• Iagno GNOME-Version von Reversi (Open-Source-Programm)
• Tothello von F. Pittner – das stärkste 4×4- und 6×6-Othelloprogramm
• Cyrano von Bruno Causse
• Phönix Othello-Klon im Duell spielbar von Sunnygames
• Othellox Othello-Klon gegen eine KI oder einen Mitspieler (von gameus!de)
• Ai Othello Othello gegen KI (von Joachim Feltkamp)

1. ↑ Jean-Christophe Weill (1992). The NegaC* Search. ICCA Journal, Vol. 15, No. 1, pp. 3-7
2. ↑ Jean-Christophe Weill (1996). The ABDADA Distributed Minimax Search Algorithm. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted ICCA Journal Vol. 19, No. 1
3. ↑ Mark Brockington (1997). KEYANO Unplugged – The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta.
4. ↑ Projektübersicht zu C# Othello bei SourceForge.
5. ↑ How Ntest Works (Memento vom 9. November 2011 im Internet Archive)
6. ↑ Apple Macintosh Longplay - Reversi (1984) Robert J. Woodhead auf YouTube
7. ↑ Early Macintosh Games from 1984, macgui.com, 5. August 2020: „Robert Woodhead, co-author of the Wizardry RPG series for Apple II, wrote Reversi in mid-1984. This is an electronic version of an ancient board game popularly known as "Othello.“
8. ↑ Windows 1.01 Longplay - Reversi (1985) Microsoft auf YouTube
9. ↑ Windows 1.0 to 10: The changing face of Microsoft's landmark OS, zdnet.com, 19. November 2015: „Windows 1.0: There was even a game, Reversi.“
10. ↑ Microsoft Windows ME (included games), mobygames.com: „Microsoft Internet Reversi“
11. ↑ Microsoft Windows XP (included games), mobygames.com: „Microsoft Internet Reversi“
12. ↑ The History of Computer Games (Memento vom 24. Januar 2011 im Internet Archive) (PDF; 216 kB)
13. ↑ Othello Indonesia