Computer-Othello

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die Artikel Computer Othello und Computer-Othello überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. 46.115.157.79 00:10, 10. Mär. 2014 (CET)

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

Verfügbarkeit[Bearbeiten]

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[Bearbeiten]

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.

Strategien zur Bewertung von möglichen Zügen[Bearbeiten]

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[Bearbeiten]

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 10 unterschiedliche Feldtypen auf dem Brett, die sich durch Spiegelsymmetrie auf das ganze Brett abbilden lassen.

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

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:

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:

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 f_4^4) bereits durch die Grundstellung bei Spielbeginn belegt.)

Für 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 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: 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.

Mobilität[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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 Bayesisches 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[Bearbeiten]

  1. Saio (Saio) von Benedetto Romano
  2. Edax (Edax) von Richard Delorme
  3. Cassio (Cassio) von Stéphane Nicolet
  4. NTest (Ntest) von Chris Welty
  5. WZebra (WZebra) von Gunnar Andersson
  6. Pointy Stone (Pointy Stone) von Jonathan Kreuzer
  7. Herakles (Herakles) von Kostas Tournavitis - das stärkste 10x10-Othelloprogramm
  8. Iagno (Iagno) GNOME-Version von Reversi (Open-Source-Programm)
  9. Tothello (Tothello) von F. Pittner - das stärkste 4x4- und 6x6-Othelloprogramm
  10. Cyrano (Cyrano java applet) von Bruno Causse

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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. C# Othello, bei Sourceforge.
  5. How Ntest Works March 02, 2005
  6. The History of Computer Games (PDF; 216 kB)
  7. Othello Indonesia

Weblinks[Bearbeiten]