Computer-Othello
Computer-Othello ist die Umsetzung des Spiels Othello für Computer durch Algorithmen.
Verfügbarkeit
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.
Suchtechniken zum Erkennen möglicher Züge
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.
Strategien zur Bewertung von möglichen Zügen
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 1054, und die Anzahl der möglichen, erlaubten Züge, beträgt etwa 1028. 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:
Disk-Square
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:
(Die mit Nullen besetzten Komponenten der Matrix sind entweder über Symmetrien abgedeckt oder (wie ) bereits durch die Grundstellung bei Spielbeginn belegt.)
Für können nun passende Funktionen festgelegt werden. Da die Eckfelder besonders erstrebenswert sind, reicht in einem ersten Entwurf eine konstante Funktion, etwa . 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: .
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.
Mobilität
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.
Mustererkennung
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.
Eröffnungs- und Endspiel-Bibliotheken
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.
Meilensteine in Computer Othello
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.
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.[6]
2004: Ntest errang den Titel des stärksten Othello-Programms von Logistello.[7]
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.
Bekannte Othello-Programme
- Saio (Saio) von Benedetto Romano
- Edax (Edax) von Richard Delorme
- Cassio (Cassio) von Stéphane Nicolet
- NTest (Ntest) von Chris Welty
- WZebra (WZebra) von Gunnar Andersson
- Pointy Stone (Pointy Stone) von Jonathan Kreuzer
- Herakles (Herakles) von Kostas Tournavitis – das stärkste 10×10-Othelloprogramm
- Iagno (Iagno) GNOME-Version von Reversi (Open-Source-Programm)
- Tothello (Tothello) von F. Pittner – das stärkste 4×4- und 6×6-Othelloprogramm
- Cyrano (Cyrano java applet) von Bruno Causse
- Phönix (Phönix flash game) Othello-Klon im Duell spielbar von Sunnygames
- Othellox (Othellox HTML5 game) Othello-Klon gegen eine KI oder einen Mitspieler (von gameus!de)
- Ai Othello (Ai Othello) Othello gegen KI (von Joachim Feltkamp)
Siehe auch
Einzelnachweise
- Jean-Christophe Weill (1992). The NegaC* Search. ICCA Journal, Vol. 15, No. 1, pp. 3-7
- 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
- Mark Brockington (1997). KEYANO Unplugged – The Construction of an Othello Program. Technical Report TR-97-05, Department of Computing Science, University of Alberta.
- C# Othello, bei Sourceforge.
- How Ntest Works (Memento des Originals vom 9. November 2011 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. March 02, 2005
- The History of Computer Games (Memento des Originals vom 24. Januar 2011 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. (PDF; 216 kB)
- Othello Indonesia
