Einleitung

Gomoku, auch als Fünf in einer Reihe geläufig, ist ein strategisches Brettspiel für zwei Spieler, das sich durch sein einfaches Spielziel – fünf Spielsteine in einer Reihe zu platzieren – auszeichnet. Das Brettspiel hat seinen Ursprung im antiken China ^[1], von wo es seinen Weg nach Japan fand ^[2] und sich dort großer Beliebtheit erfreut.
So kam es, dass bereits 1981 professionelle Gomoku-Spieler (Sakata und Ikawa) behaupteten, dass der erste Spieler bei perfektem Spiel einen gesicherten Sieg hat. Dies wurde jedoch erst 1993 im Paper „Gomoku and Threat-Space Search“ ^[3] bewiesen. Im Verlauf der Zeit haben sich mehrere Variationen des Spiels entwickelt, die im Abschnitt Spielregeln genauer betrachtet werden.

In diesem Artikel wird zunächst ein grundlegendes Wissen über Gomoku aufgebaut. Darauf aufbauend wird erklärt, wie ein Solver anhand evolutionärer Prinzipien Gomoku spielen bzw. lernen kann.

Spielregeln

Es gibt eine Vielzahl von Varianten oder Abwandlungen von Gomoku, die sich hauptsächlich in den Parametern Brettgröße, Siegbedingungen oder Ausgleichsmechanismen unterscheiden ^[1:1][4][5].
Am Ende dieses Abschnitts finden sich Tabellen, die einige klassische Varianten und Eröffnungsregeln, Gomoku mit mechanischen Abwandlungen und von Gomoku inspirierte Spiele auflisten.

Spielregeln: Freestyle Gomoku

Bei den klassischen Varianten bleibt der grundlegende Spielablauf unverändert; Unterschiede bestehen meist nur in zusätzlichen Eröffnungsregeln, abweichenden Spielzielen (z. B. Overlap – mehr als fünf Steine zählen auch als Sieg) oder verändertem Spielmaterial.

Spielmaterial

Freestyle Gomoku wird auf einem quadratischen Gitter, in der Regel mit 15×15 Schnittpunkten, gespielt. Dabei ist jeder Schnittpunkt eine mögliche Position für einen Spielstein. Die Spielsteine bestehen aus zwei Sets farblich unterschiedlicher Steine – meist schwarz und weiß, da gerne Go-Steine verwendet werden.

Spielziel

Gomoku ist ein zugbasiertes Spiel, das von zwei Spieler:innen ausgetragen wird. Ein Zug besteht aus dem Legen eines Spielsteins der jeweiligen Spieler:in auf einen freien Schnittpunkt des Gitters.
Die Spieler:in, die als Erste:r eine ununterbrochene Folge von fünf oder mehr gleichfarbigen Steinen in horizontaler, vertikaler oder diagonaler Richtung bildet, hat gewonnen und das Spiel endet sofort.

Spielablauf

Das Spiel beginnt mit Schwarz, die bzw. der einen einzelnen Spielstein auf eine Position im Gitter setzt. Anschließend ist Weiß am Zug und setzt einen Spielstein auf einen der noch freien Schnittpunkte.
In jedem Zug darf die bzw. der Spieler:in genau einen Stein setzen.
Des Weiteren gibt es keine weiteren Aktionen (z. B. Verschieben oder Entfernen eines Spielsteins), die während des Zuges ausgeführt werden können.
Die Spieler:innen wechseln sich mit den Zügen ab, bis das Spielende erreicht ist.

Spielende

Freestyle Gomoku endet, sobald eine:r der Spieler:innen den in Spielziel beschriebenen Zustand erreicht.
Das Spiel kann jedoch auch unentschieden enden. Dies ist der Fall, wenn
(1) alle Schnittpunkte belegt sind, ohne dass eine Fünfer-Reihe entstanden ist, oder
(2) beide Spieler:innen die Gewinnversuche der Gegenseite vollständig blockiert haben und keine weitere Fünfer-Bildung möglich ist.

Tabelle: Gomoku klassische Varianten & Eröffnungsregeln

Tabelle: Gomoku mechanische Abwandlungen

Tabelle: Gomoku-inspirierte oder verwandte Spiele

Solver für Gomoku basierend auf genetischen Algorithmen ^[6]

Um den folgenden Inhalt ohne Vorwissen zu genetischen Algorithmen besser einordnen zu können, bietet sich dieser Wiki-Artikel an: Genetische Algorithmen.

Diese Implementierung generiert für jeden Zug eine Startpopulation von Individuen, welche dann anhand ihrer Fitness bewertet und mit Rekombination und Selektion „verbessert“ werden. Dieser Prozess wird iterativ wiederholt, und das Produkt dieses Prozesses – das bestbewertete Individuum – wird dann als tatsächlicher Zug ausgewählt.

\

Gomoku-Kodierung

Eine Spielsequenz wird durch die Angabe des Spielers (B = Solver und A = Gegenspieler) und die Brettkoordinaten (x,y) des gelegten Steins kodiert:

Sequenz: B(7,5) A(9,4) B(7,6) A(6,4) B(7,7) A(8,4) B(7,4) A(7,8)

Ein Individuum besteht aus einer Sequenz von sieben Spielzügen, wobei die Spielerbezeichnung weggelassen werden kann – da sie implizit gegeben ist, denn der Solver startet immer mit einem eigenen Zug:

Individuum: \{(9,4), (7,6), (6,4), (7,7), (8,4), (7,4), (7,8)\}

Die Startpopulation wird dabei zufällig, jedoch mit gewissen Einschränkungen erzeugt: Die Zugpositionen müssen auf einem freien Feld und in einem erweiterten Bereich um alle bereits gesetzten Steine liegen. Der erweiterte Bereich berechnet sich aus allen bereits gesetzten Steinen.
Angenommen, auf dem Spielbrett liegen bereits die folgenden Steine auf den Feldern: (6,6), (7,7), (7,6), (8,7). Dann würde der erweiterte Bereich wie folgt berechnet:

1. Nimm den maximalen und minimalen x- und y-Wert.
2. Addiere 1 zum maximalen Wert und subtrahiere 1 vom minimalen Wert.

Somit gilt für x: x_{min} = 6 und x_{max} = 8, und für y: y_{min} = 6 und y_{max} = 7.
Der erweiterte Bereich ist somit: x_{min}-1 = 5, x_{max}+1 = 9, y_{min}-1 = 5 und y_{max}+1 = 8.
Erweiterter Bereich formal definiert: (x_{min} -1, x_{max} + 1) und (y_{min} - 1, y_{max} + 1).

Fitness-Funktion

"Actually, GA can be regarded as the optimization process of the fitness function." ^[6:1]

Die Fitness-Funktion ist das Herzstück eines jeden genetischen Algorithmus (GA), denn die jeweilige Implementierung hat einen enormen Einfluss auf die Effizienz und Laufzeit eines jeden GAs.

Diese Fitness-Funktion besteht aus fünf Teilen: Der Angriffs- und Verteidigungsbewertung, einer Belohnung für frühe Siege, der Berücksichtigung von nahen Siegsituationen und einer Tendenzbewertung.

Um eine Spielsituation bewerten zu können, muss es ein Mapping von Spielsituation auf einen Wert geben. In diesem Fall werden zwölf wesentliche Brettmuster nach ihrer Gewinnwahrscheinlichkeit klassifiziert. Die Gewinnwahrscheinlichkeit wird stufenweise nach der Formel berechnet:

v(p_n) = 2v(p_{n-1}) + 1

Dabei erhalten Muster 9–11 denselben Maximalwert, da sie einen Zug vor dem Sieg liegen. Positionen, die nicht mit einem Muster klassifiziert werden können, erhalten den Wert 0.

\

\

Angriffs- und Verteidigungsbewertung

Für jeden der sieben Züge einer Lösung wird ermittelt, wie viel dieser Zug zum eigenen Angriff (Angriffswert) und zur Abwehr des Gegners (Verteidigungswert) beiträgt. Der Gesamtwert einer Zugaktion ist die Summe aus Angriffswert und Verteidigungswert.

f(c) = \sum_{i=1}^{7} \left( atk(p_i) + def(p_i) \right)

Dadurch werden Züge höher gewichtet, die einerseits den Sieg vorantreiben und andererseits gegnerische Drohungen entschärfen.

Berechnung Angriffswert

Der Angriffswert ist der Wert der erzeugten Spielsituation unter der Annahme, dass der GA-Löser einen Stein auf Position P legt.

Berechnung Verteidigungswert

Der Verteidigungswert ist der Wert der erzeugten Spielsituation unter der Annahme, dass der Gegner einen Stein auf Position P legt.

Beispiel

Angenommen die Spielsituation ist wie in Abb. 5 dargestellt und der GA-Solver (schwarz) nimmt eine Bewertung der drei markierten Positionen (1, 2 und 3) vor. Dabei wird jede dieser drei Positionen unter zwei Bedingungen ausgewertet: 1. Bedingung ist der Wert des Muster, wenn der eigene Stein an der Position liegt und die 2. Bedingung ist der Wert des Musters, wenn der Stein des Gegeners an dieser Position liegt. Dies würde zu folgenden Bewertungen führen:

Fazit: Position 1 ist die beste Wahl, da sie sowohl eine eigene Gewinnchance aufbaut als auch eine gegnerische verhindert.

Belohnung für nahe Siegsituationen

Liegt ein sofortiger Sieg in einem Zug vor (Mustertypen 9–11), werden ebenfalls alle nachfolgenden Züge maximal bewertet. So werden Nahsiegs-Szenarien besonders forciert.

Berücksichtigung von nahen Siegsituationen

Bei Spielsituationen wie Muster 9, 10, 11 hat der Spieler mit den weißen Steinen einen garantierten Sieg, unabhängig davon, wohin der schwarze Spieler den Stein platziert. Deshalb werden die darauffolgenden Züge mit dem Maximalwert bewertet, um diesen Umstand zu modellieren.

Tendenzbewertung

Dieser Schritt ist essenziell, denn f(c) hat bei der Bewertung nicht zwischen dem GA-Solver und dem Gegenspieler differenziert. Darum wird die Situationsbewertung eines Individuums in jedem Zug mit einem Vorzeichen versehen:

t(c) = \sum_{i=1}^{7} l(i) \cdot \left[ atk(p_i) + def(p_i) \right]

Dabei wertet l(i) wie folgt aus:

• 1: Zug vom GA-Solver
• -1: Zug vom Gegenspieler

Diese Tendenz bewertet Individuen, die für den Gegner vorteilhaft sind und mit der Bewertungsfunktion f(x) einen hohen Wert erhalten hätten, niedriger – und modelliert so die Spielerperspektive.

Selektion ^[7]

In dieser Implementierung wird das Verfahren der Roulette-Rad-Selektion verwendet. Dieses Verfahren trifft die Auswahl von Individuen anhand ihrer Fitnesswerte.
Jedes Individuum hat eine Wahrscheinlichkeit ausgewählt zu werden – diese Wahrscheinlichkeit ist jedoch proportional zum Fitnesswert.
Je höher der Fitnesswert eines Individuums, desto wahrscheinlicher wird es ausgewählt. Allerdings wird die mehrfache Selektion identischer Individuen dabei nicht ausgeschlossen, was den Vorteil der Bevorzugung hoher Fitnesswerte bringt, jedoch das Risiko der vorzeitigen Konvergenz durch die dominante Überrepräsentation von „suboptimalen“ (lokalen Optima) Individuen erhöht.

Rekombination

Elternindividuen werden per Roulette-Auswahl ausgewählt. Die Chromosomen eines ausgewählten Elternpaares werden an einem zufälligen Schnittpunkt geteilt. Die daraus resultierenden Teilstücke werden vertauscht, sodass zwei neue Kinder entstehen.

Beispiel: Crossover bei zwei Individuen

Angenommen, wir haben zwei Eltern-Individuen, die jeweils eine Zugfolge von sieben Spielzügen enthalten. Ein zufälliger Crossover-Punkt wird gewählt, z. B. nach dem dritten Zug:

Elternteil 1:
(7,6) (5,5) (5,4) (2,2) (6,5) (7,7) (4,4)

Elternteil 2:
(5,7) (5,5) (2,4) (7,7) (3,5) (4,4) (3,3)

Kind 1:
(7,6) (5,5) (5,4) (7,7) (3,5) (4,4) (3,3)

Kind 2:
(5,7) (5,5) (2,4) (2,2) (6,5) (7,7) (4,4)

Diese neuen Individuen enthalten jeweils einen Mix der Zugsequenzen ihrer Eltern.

Mutation

In jeder Generation wird ein kleiner Prozentsatz (kleiner als 1 %) der Individuen mutiert. Dabei wird an einer zufälligen Genposition eine Veränderung vorgenommen. Es können dabei ungültige Lösungen (z. B. doppelte Züge auf demselben Feld) entstehen – diese werden jedoch später durch die Fitnessbewertung verworfen.

\

Bildquellen

Abb. 1: Screenshot von TicTacToeFree.com (o. D.).
Abb. 2: Gomoku-Brettspiel Foto. (o. D.). Abgerufen von https://i.ebayimg.com/images/g/ifcAAOSwOZNcrLru/s-l960.webp
Abb. 3–5: Entnommen aus Wang, J., & Huang, L. (2014). Evolving Gomoku Solver by Genetic Algorithm Konferenzbeitrag. Proceedings of IEEE International Conference on Computer and Information Technology, Yangtze University. https://ieeexplore.ieee.org/document/6976460

Literatur