Prof. Franz Schweiggert Abteilung Angewandte
Informationsverarbeitung 23. November 2004
Christian Ehrhardt Blatt 5
Allgemeine Informatik 3 (WS 2004/2005)
Abgabetermin 30.11.2004
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ß
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 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 implementiert. Dort könnt Ihr Euch auch Anregungen
holen, wie das Spielfeld mit Hilfe von Ascii-Zeichen dargestellt werden
kann.
Christian Ehrhardt
2004-11-23