Go-Programmierung

Vorwort

Nachdem ich des öfteren nach der Funktionsweise von Augos gefragt worden bin, möchte nun einige Techniken erläutern. Bei Augos ging es nicht um ein kommerzielles Produkt, sondern um eine Drosophila zur Untersuchung einiger Methoden der Künstlichen Intelligenz.

Veröffentlichungsform: hier soll immer mal wieder einige Kapitel eingefügt werden, je nachdem, wieviel Zeit mir zur Verfügung steht.

Inhalt

Einleitung   
  Definitionen 
  Repräsentation eines Spielfelds in einem Computerprogramm
  Ko-Regel 
Basisfunktionen eines Go-Programms   
  Innerhalb eines Spielfelds 
  Gebietsberechnung 
  Freiheitenberechnung 
  Test, ob ein Zug legal ist 
  Einen Zug ausführen 
Der Denkprozeß
  Kurze Einführung in die Spieltheorie
  Lokale Muster 
  Der letzte Zug des Gegners 
  Ziele in der Go-Programmierung 
  Ziele haben 
  Gewinnung von strategischen Zielen 
Diverse Aufgabenstellungen   
  Partien laden und speichern 
Anhang
  Weiterführende Literatur

Einleitung

Definitionen

Eine Kette ist eine Menge zusammenhängender Steine derselben Farbe. Auch ein einzelner Stein falle hier unter diese Kategorie. Merke: es ist einfach, Ketten zu erkennen.

Hier hat Weiß vier Ketten, Schwarz zwei

Eine Gruppe ist eine Menge von Ketten, die sich in räumlicher Nähe befinden und die üblicherweise das gleiche Schicksal teilen, also entweder alle gemeinsam leben oder sterben. Auch eine einzelne Kette falle hier unter diese Kategorie.

Hier hat Weiß eine Gruppe links oben, eine weitere Gruppe oben am Rand und Schwarz hat eine Gruppe rechts oben. Jede Gruppe besteht aus zwei Steinen.

Nun könnte man einwenden, Weiß besitze am oberen Rand nur eine einzige Gruppe, bestehend aus vier Steinen. Schwarz kann aber auf G17 invadieren und so die beiden Weißen Gruppen getrennt halten. Um dies zu erkennen, muß man bereits eine gewisse Spielstärke besitzen - man muß bereits Go spielen können. Das sieht nach einem Zirkelschluß aus, denn man kann diese Spielstärke ja nicht voraussetzen, sondern will sie aus einfacheren Elementen aufbauen.

Eine Heuristik bzw. heuristische Regel ist eine Aussage oder eine Anweisung die in den meisten Fällen korrekt ist, aber nicht unbedingt in allen Fällen. Beispielsweise gibt es beim Go die Aussage: "Dreidrei lebt immer". Damit ist gemeint, daß man, wenn man irgendwo im Eck ein neues Leben beginnen will, möglichst auf dem Punkt (3,3) anfangen soll. Beim Go gibt es eine Fülle solcher Strategeme oder Tips, die man teilweise sehr leicht einem Computer beibringen kann. Oft genügt dazu lokale Mustererkennung. Diese wird später erläutert.

Repräsentation eines Spielfelds in einem Computerprogramm

Bei Augos ist das Spielfeld ein zweidimensionales Array [0..18,0..18] von Integerzahlen. Empfehlung: besser ist es, einen dynamisch allozierten linearen Speicherbereich zu verwenden (malloc(),free()) und den Ort vermöge des Terms y * Breite + x umzurechnen, wobei x die Werte 0 bis Breite-1 und y die Werte 0 bis Hoehe-1 annehmen darf.

Spielsteine des Computers werden durch den Wert +1, Spielsteine des Gegners durch -1 repräsentiert. Leere Punkte werden durch 0 dargestellt. In einem Go-Programm wird man nicht mit einem einzigen Feld auskommen, sondern für die verschiedensten Zwecke weitere Felder halten, so z.B., um den Einfluß von Steinen auszudrücken oder den Wert von alternativen Zügen zu speichern.

Ko-Regel

Die Ko-Regel soll Endlospartien vermeiden. Die chinesischen Regeln sagen, daß eine Gesamtstellung nicht wiederholt werden darf. Um dies per Programm sicherzustellen, kann man eine Liste der bisherigen Stellungen in einer Datei speichern. Alternativ kann man angesichts heutiger Speichergrößen auch alle bisher gespielten Stellungen im Hauptspeicher halten oder man merkt sich nur die Züge und rekonstruiert ggf. die Stellung.

Aus Gründen der Effizienz hält man sich einen Fingerabdruck (z.B. CRC oder nur Anzahl der schwarzen und weißen Steine) jeder bisherigen Stellung im Hauptspeicher und liest die komplette Stellung aus der Datei nur dann für einen Vergleich ein, wenn ein in Frage kommender Zug zu einer Stellung mit einem Fingerabdruck führen würde, der schon einmal da war.

Bei Augos wurden die japanischen Regeln verwendet. Diese sagen, daß ein einzelner schlagender Stein nicht gleich wieder geschlagen werden darf.

Empfehlung: die chinesische Ko-Regel ist zu bevorzugen, besonders auf kleinen Brettern. Die chinesischen Regeln erlauben größere Variantenvielfalt.

Basisfunktionen eines Go-Programms

Innerhalb eines Spielfelds

Bei Augos bis einschließlich Version 6 ist die Brettgröße fest als 19*19 vorgegeben. Dem Leser sei aber empfohlen, die Brettgröße variabel zu gestalten. Das Brett habe die Größe Breite * Höhe. Somit ergibt sich eine Funktion für den Test, ob ein Zug innerhalb des Spielfelds liegt, zu

Definition Innerhalb(x,y): boolean
Falls (x >= 0) und (x < Breite) und (y >= 0) und (y < Hoehe) 
  return true
sonst
  return false

Gebietsberechnung

Die Funktion Gebiet() hat einen Punkt (x,y) als Parameter sowie ein Feld F. Sie liefert eine Liste von Punkten zurück. Hierzu wird ein Hilfsfeld M für Markierungen sowie ein Stapel (auch Stack oder Keller genannt) von Punkten verwendet. f ist eine Variable für die betrachtete "Farbe".

Definition Gebiet(x,y,F): Liste
- result := []
- f := F[x,y]
- Leere den Stapel
- Leere Feld M
- M[x,y] := 1     
- Staple (x,y)
- Solange der Stapel nicht leer ist
   - Nimm einen Punkt (a,b) vom Stapel
   - Addiere (a,b) zu result
   - Für alle (c,d) aus {(a+1,b),(a-1,b),(a,b+1),(a,b-1)}
      - Falls Innerhalb(c,d) und M[c,d] = 0 und F[c,d] = f
        - M[c,d] := 1
        - Staple(c,d)
- return result

Freiheitenberechnung

Um die Freiheiten einer Kette zu berechnen, kann man auf die bereits vorhandene Funktion Gebiet() zurückgreifen.

Definition Freiheiten(x,y,F): Liste
- result := []
- L := Gebiet(x,y,F)
- Leere Feld M
- Für alle (a,b) aus L
   - Für alle (c,d) aus {(a+1,b),(a-1,b),(a,b+1),(a,b-1)}
     - Falls Innerhalb(c,d) und M[c,d] = 0 und F[c,d] = 0
       - Addiere (c,d) zu result
       - M[c,d] := 1
- return result

Test, ob ein Zug legal ist

Dieser Test ist zweiteilig. Zuerst wird auf ein Hilfsfeld G gesetzt. Etwaige geschlagene gegnerische Steine werden von G entfernt und in einer Liste gesammelt. Der gesetzte Stein muß nun mindestens eine Freiheit haben.

Der zweite Teil, KoBehandlung(...), besteht in der Untersuchung in Bezug auf die Ko-Regel. Die japanischen Regeln besagen, daß ein einzelner schlagender Stein nicht sofort wieder geschlagen werden darf. In diesem Falle besteht KoInfo nur in der Nennung des letzten einzelnen Schlagsteines, und der Test auf Verletzung der Ko-Regel besteht darin, zu prüfen, ob die Liste Geschlagen nur in diesem einen Stein besteht.

Definition Legal(x,y,f,F,KoInfo):
- Kopiere das Spielfeld F nach G
- Geschlagen := []
- Falls G[x,y] != 0,
    - return false
- G[x,y] := f
- Für alle (a,b) aus {(x+1,y),(x-1,y),(x,y+1),(x,y-1)}
    - Falls Innerhalb(a,b) und G[a,b] = -f und Freiheiten(a,b,G) = []
      - l := Gebiet(a,b,G)
      - Für alle (c,d) aus l 
        - G[c,d] := 0
        - Addiere (c,d) zu Geschlagen
- Falls Freiheiten(x,y,G) = 0
  - return false
- return KoBehandlung(G,Geschlagen,KoInfo)

Einen Zug ausführen

Diese Funktion ähnelt dem Test, ob ein Zug legal ist, wo auf ein Hilfsfeld gesetzt wird. Hier aber wird auf das 'richtige' Feld F gesetzt, und Tests auf Legalität finden hier nicht statt.

Definition Ausfuehren(x,y,f,Feld,KoInfo):
- Geschlagen := []
- F[x,y] := f
- Für alle (a,b) aus {(x+1,y),(x-1,y),(x,y+1),(x,y-1)}
    - Falls Innerhalb(a,b) und F[a,b] = -f und Freiheiten(a,b,F) = []
      - l := Gebiet(a,b,F)
      - Für alle (c,d) aus l 
        - F[c,d] := 0
        - Addiere (c,d) zu Geschlagen
- UpdateKoInfo(F,Geschlagen,KoInfo)

Der Denkprozeß

Kurze Einführung in die Spieltheorie

In diesem Kapitel geht es um eine der Möglichkeiten, ein Computerprogramm in die Lage zu versetzen, sich für eine von mehreren Alternativen zu entscheiden. Genauer gesagt, es geht um Zweipersonen-Nullsummen-Strategiespiele mit vollständiger Information. Es wird erläutert, was es mit Suchbäumen auf sich hat.

Der Zustand des Spiels besteht üblicherweise im Inhalt eines Spielfeldes, der Stellung. Für die weitere Betrachtungsweise nehmen wir an, daß eine schnelle Bewertung existiert, die einer Stellung eine Zahl zuordnet. Für Schach bietet sich an, z.B. den Materialwert in Bauerneinheiten aufzusummieren und dabei eigene Figuren als positiv, gegnerische Figuren als negativ zu werten.

Beim Go ist es schwieriger, eine Stellung zu beurteilen, denn die Aussage, daß z.B. 41 schwarze und 50 weiße Steine auf dem Brett stehen, sagt wenig darüber aus, wer besser steht. Gelingt es aber, eine Teil-Stellung zu extrahieren, so kann der Materialwert sehr wohl aussagekräftig sein, Beispielsweise bei Treppen, Geta oder Tsumego.

Wenn man durch einen Zug eine Stellung in eine Folgestellung überführen muß, so erscheint es sinnvoll, eine mit einer möglichst großen Bewertung zu wählen (Im Rahmen dieser Überlegungen möge es stets eine Zugmöglichkeit geben. Den Fall, daß man auch passen darf, kann man dadurch behandeln, daß man eine Folgestellung vorsieht, die denselben Wert wie die Ausgangsstellung besitzt).

Hier sollte man den Zug ausführen, der zur Stellung mit der Bewertung 23 führt.

Anders sieht die Sache aus, wenn man noch die Antwort des Gegners auf den eigenen Zug berücksichtigen muß. Unser Gegner wird stets bestrebt sein, unseren Gewinn möglichst klein zu halten.

Hier ist eine Stellung, die uns 50 Punkte bringt, die beste Zukunft. Um diese zu erreichen, muß man den Zug b ausführen. Der Gegner wird aber nicht so liebenswürdig sein, dann den Zug g zu machen, sondern wird dann f wählen, was uns nur 7 Punkte einbringt. Wenn man den besten Zug c aus dem Beispiel zuvor mit der Ein-Zug-Vorausschau ausführt, wird der Gegner mit h antworten, was uns nicht 23 Punkte, sondern letztlich nur 15 Punkte bringt. Der beste Zug ist d, worauf der Gegner dann mit j anworten wird, so daß d 18 Punkte wert ist.

Man sieht, daß man bei dieser Betrachtungsweise von Strategiespielen an den Blättern den Spielbaums beginnen muß, um eine Stellung zu beurteilen. Der Gegner wird stets darum bemüht sein, unseren Gewinn zu minimieren, während wir ihn maximieren wollen.

N(s,i) sei eine Funktion, die zu einer Stellung s die i-te Nachfolgestellung liefert.

Definition Bewerte(s): integer
- Falls IstBlatt(s)
    - return eb(s)
- Falls GegnerIstAmZug(s)
    - return Minimum(Bewerte(N(s,i))) über alle i
- Falls man in S selbst am Zug ist,
    - return Maximum(Bewerte(N(s,i))) über alle i

Anders als bei Schach, Mühle oder beispielsweise Dame kann Minimax nicht für globale Entscheidungen eingesetzt werden, weil der Spielbaum zu groß ist, ausgenommen bei sehr kleinen Brettern, sagen wir, höchstens der Größe 5*5. Sinnvolle Anwendungen für Baumberechnungen beim Computer-Go sind jedoch Funktionen zum Entscheiden lokaler Situationen, z.B. Treppen und Tsumego.

Lokale Muster

Das menschliche Auge sieht nur in einem winzigen Ausschnitt des Sichtfeldes scharf, mit Hilfe der Makula. Der Mensch muß deswegen ein Schriftstück oder eine Go-Stellung abtasten, indem er seinen Blick schweifen läßt.

Dieses zu modellieren ist auch bei einem Go-Programm sinnvoll. Mit einem Endlichen Automaten (bisweilen auch Zustandsautomat genannt) ist das leicht zu realisieren. Ein Endlicher Automat ist ein primitives informationsverarbeitendes Gerät. Er besitzt eine endliche Anzahl von Zuständen. In einem Zeittakt liest er genau ein Zeichen aus einem seriellen Eingabekanal und geht in einen Folgezustand, der eindeutig aus der Kombination Ausgangszustand + Eingabezeichen bestimmt ist. Beim Erreichen des Zielzustands wird dann eine Ausgabe ausgelöst (Genauer gesagt, es handelt sich hierbei um einen Moore-Automaten. Nur der Vollständigkeit halber sei erwähnt, daß es noch das Modell der Mealy-Automaten gibt, deren Ausgabe nicht vom Zielzustand abhängt sondern von der Kombination Ausgangszustand + Eingabezeichen).

Ausgabe bedeutet hier, daß der Endliche Automat bescheid sagt, daß ein bestimmtes Muster erkannt worden ist, wenn ein bestimmter Zustand erreicht worden ist.

Bei Augos wird die Mustererkennung durch eine Baum-Datenstruktur realisiert. Jeder Knoten hat 4 Nachfolgeknoten, für die Eingabezeichen s (schwarz), w (weiß), l (leer) und a (außerhalb).

Der Eingabestrom wird durch durch spiralförmiges Abtasten des Spielfelds in der Umgebung eines Punktes bereitgestellt. Kommt man beim Abtasten auf einen Punkt außerhalb des Spielfelds, wird das Eingabezeichen a (wie außerhalb) angenommen.

Dieses Muster wird durch die Zeichenfolge [..x.o......................x.....o..aaaaaaaaaaaaaa.............a] repräsentiert.

Muster beim Go haben eine achtzählige Symmetrie. Es gibt vier Rotationen und davon jeweils zwei spiegelbildliche Varianten.

Der letzte Zug des Gegners

Oft liest man in Problembüchern "Weiß hat gerade den markierten Stein gesetzt. Wie sollte Schwarz antworten?". Hier wird der Eindruck erweckt, der beste Zug von Schwarz wäre ein anderer, wenn ein anderer Stein markiert wäre. Eine einfache Technik für Go-Programme ist es, in lokalen Mustern den letzten Zug des Gegners und einen Vorschlag für einen eigenen Zug anzugeben. So erreicht man schnell spektakuläre Erfolge. Dies funktioniert aber nur eine zeitlang gut und läßt Initiative vermissen. Außerdem gibt es im Go oft genug Situationen, wo man einen Zug des Gegners ganz woanders beantworten muß.

Ein Go-Programm sollte sich in eine vorgegebene Gesamtstellung eindenken können, ohne Rücksicht auf den bisherigen Spielverlauf.

Ziele in der Go-Programmierung

Ziele haben

Ziele im Sinne von Augos sind Listen, bestehend aus einem Verb und einer Reihe von beliebig vielen Objekten. Mit Objekt ist hier meist der Name einer Kette oder ein Punkt auf dem Spielfeld gemeint.

Beispiele:

VERTEIDIGEN 100
ANGREIFEN 53
NEUES-LEBEN-BEGINNEN
VERBINDEN 41 43
BESETZEN 234
VERZICHTEN

Es gibt eine Ziel-Hierarchie, auf deren unterster Ebene stets Wünsche / Anweisungen / Befehle zum Besetzen einzelner Punkte stehen. Auf oberster Ebene könnte man Ziel GEWINNEN nennen, aber dieses Oberziel ist trivialerweise immer vorhanden.

Bei Augos sind die Ziele höchster Stufe stets die Namen von Ketten. Handelt es sich um eine eigene Kette, so ist diese Kette zu retten. Mögliche Unterziele: sich ausdehnen, an andere Kette anbinden, zwei Augen machen, einen Fluchtsprung machen usw. Handelt es sich um eine gegnerische Kette, so ist diese zu töten, und mögliche Unterziele sind: diese Kette umzingeln, eine Freiheit wegnehmen usw.

In der Praxis wird man zur rechnerinternen Repräsentation von Zielen nicht Strings nehmen, sondern Klassen von einer allgemeineren Klasse TGoal oder so ableiten. Sinnvoll ist eine Methode ToString(), mit der man ein Ziel textuell ausgeben kann.

Gewinnung von strategischen Zielen

Wie die Klassifikation der Gruppen bzw. Ketten geschehen soll, ist nicht Gegenstand dieses Kapitels. Jedem Programmierer ist selbst überlassen, Methoden der Klassifikation zu finden. Es ist sogar so, daß die Ermittlung des Status einer Gruppe / Kette so schwierig ist wie Gospielen selber. In der Praxis sollte man also nach Näherungslösungen suchen.

- Baue einen Graphen auf, dessen Knoten die Ketten, und dessen Kanten räumliche Nähe repräsentieren.

- Berechne die taktischen Werte aller Ketten.

Sichere und tote Ketten bekommen den taktischen Wert 0, angreifbare und rettbare Ketten bekommen den Wert Anzahl Steine * 2 + Anzahl Freiheiten.

Rechtfertigung: man muß beim Go eine gegnerische Kette nicht herausschlagen, sondern kann sie großräumig umzingeln, so daß noch das nichtbesetzte Gebiet einverleibt wird. Man gewinnt also die Steine der Kette, die Felder, wo sich die Kette drauf befindet und noch das Gebiet drumherum, das hier grob abgeschätzt wird als die Anzahl der Freiheiten der Kette.

- Berechne die strategischen Werte einer Gruppe

Der strategische Wert einer Gruppe ist die Summe aus dem taktischen Wert der Gruppe + Summe der taktischen Werte der gegnerischen Nachbargruppen.

- Ableitung von Zielen

Ermittle die Kette mit dem höchsten strategischen Wert. Falls es eine Kette der eigenen Farbe ist, tue etwas für die Kette: erhöhe die Freiheiten, entferne eine Nachbarkette, binde die Kette an, mache zwei Augen ... Falls es eine Kette der gegnerischen Farbe ist, unternimm etwas gegen die Kette: umzingle die Kette, nimm eine Freiheit weg, schlage die Kette raus, ...

Diverse Aufgabenstellungen

Partien laden und speichern

Das Dateiformat SGF (Smart Game Format) ist ein Quasi-Standard für die Speicherung von Go-Partien. Es ist sehr leicht, eine Partie im SGF-Format abzuspeichern, aber es ist aufwendig, SGF zu lesen und Partien darzustellen. Denn SGF unterstützt diverse Markierungen von Punkten, Varianten und sogar Partie-Sammlungen in einer einzigen Datei.

Augos unterstützt sowohl das Schreiben als auch das Lesen von SGF-Dateien. Der SGF-Parser wurde als eine Delphi-Komponente realisiert. Wer ein Go-Programm mit Delphi entwickelt, kann diese Komponente verwenden, um Go-Partien, die im SGF-Format vorliegen, in einem TreeView (Steuerelement zur Anzeige von Baum-Strukturen) darzustellen.

Empfohlen sei dem Leser, zumindest eine zusätzliche Möglichkeit der Speicherung von Partien im SGF-Format anzubieten, dann aber ein eigenes Format zu verwenden, das leicht zu programmieren ist. Für das Nachspielen von Partien gibt es bereits sehr schöne freie SGF-Editoren, die mitunter eben nicht selber Go spielen können, so daß man sich nicht mehr mit diesem Thema beschäftigen muß.

Anhang

Weiterführende Literatur