Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 23. November 2004
Christian Ehrhardt Blatt 5






Allgemeine Informatik 3 (WS 2004/2005)


Abgabetermin 30.11.2004

Go

Go ist ein Strategiespiel, das vor allem in Japan und China sehr beliebt ist. Ziel des Spiels ist es, möglichst viel Gebiet auf dem Spielbrett mit Steinen der eigenen Farbe zu umschließen. Dabei können gegnerische Steine gefangen (geschlagen) werden, ein gefangener Stein zählt genau so viel, wie ein einzelner Gebietspunkt.
Die folgende historische Regelvariante entspricht nicht in allen Einzelheiten den modernen Regeln, ist dafür aber besonders einfach zu formulieren und zu verstehen:

• Gespielt wird von 2 Spielern auf einem N kreuz N Spielbrett bestehend aus N senkrechten und N waagrechten Linien, so daß $N^2$ Kreuzungspunkte entstehen.
• Jeder Spieler bekommt eine ausreichende Anzahl an Spielsteinen der eigen Farbe der eine Spieler schwarz, der andere weiß. Der Spieler mit den schwarzen Steinen beginnt!
• Die beiden Spieler plazieren abwechselnd einen Spielstein der eigenen Farbe auf einem der $N^2$ Kreuzungspunkte (nicht wie beim Schach in eines der Felder).
• Die Spielsteine, die sich zu einem bestimmten Zeitpunkt auf dem Spielbrett befinden, werden in zusammenhängende Gruppen aus Steinen der gleichen Farbe eingeteilt. Dabei hängen Steine nur senkrecht und waagrecht zusammen.
  Zwei Steine gehören also zur selben Gruppe, wenn folgende Bedingungen erfüllt sind:
  • Sie haben die selbe Farbe und
  • es gibt einen Weg entlang der Gitterlinien zwischen den beiden Steinen, so daß jeder Kreuzungspunkt auf diesem Weg mit einem Stein der selben Farbe besetzt ist.
• Eine Freiheit einer Gruppe ist ein unbesetzter Kreuzungspunkt, der zu der Gruppe direkt entlang der Gitterlinien (also nur senkrecht oder waagrecht) benachbart ist (Ein unbesetzter Kreuzungspunkt kann gleichzeitig Freiheit von mehreren Gruppen sein). Ein einzelner Spielstein in der Mitte des Spielfelds hat also 4 Freiheiten, nämlich die vier nach links, rechts oben und unten benachbarten freien Felder. Ein Spielstein in der linken unteren Ecke hat dagegen nur 2 Freiheiten, das es zwar nach oben und nach rechts benachbarte freie Kreuzungspunkte gibt, nicht jedoch nach unten und nach links, da dort das Spielfeld endet.
• Für den Zug eines Spielers gelten die folgenden Einschränkungen:
  • Nach dem plazieren eines Steins der eigenen Farbe auf einem freien Kreuzungspunkt werden alle Gruppen des Gegners vom Spielfeld genommen, die jetzt keine Freiheit mehr haben.
  • Die vom Brett genommenen (gefangenen) Steine behält der Spieler bei sich.
  • Der Zug ist nicht legal, wenn nach dem Entfernen der gegnerischen Steine eine (eigene) Gruppe auf dem Brett keine Freiheit mehr hat.
  • Wenn das plazieren eines Steins nicht legal möglich ist, oder wenn der Spieler darin keinen Vorteil sieht, dann kann er statt dessen einen in einem früheren Spielzug gefangenen Stein des Gegners abgeben. Der abgegebene Stein nimmt nicht weiter am Spiel teil.
• Ko-Regel: Ein Zug, der nach den bisherigen Regeln legal wäre ist nicht erlaubt, wenn er den unmittelbar vorangehenden Zug des Gegners vollständig rückgängig macht.
• Der Spieler, der zuerst nicht mehr ziehen kann oder will, verliert das Spiel.

Eure Aufgabe ist es, dieses Spiel zu implementieren. Auf die Implementierung der Ko-Regel darf dabei verzichtet werden. Auf der thales ist unser /usr/local/bin/go ein Programm installiert, das das Spiel für den Fall $N=9$ implementiert. Dort könnt Ihr Euch auch Anregungen holen, wie das Spielfeld mit Hilfe von Ascii-Zeichen dargestellt werden kann.