Vorlesung: Praxis der Funktionalen Programmierung | Index

Spezielles zu Brettspielen

In den vorgestellten Rahmen passen Go, Gomoku, Hex, Connect.

Hausaufgabe: implementiere Spielbrett und Spieler dafür. Ein Connect-Spielbrett habe ich, siehe unten. Die Gruppe von Prof. Althöfer in Jena beschäftigt sich auch mit Connect, ein Leipziger Programm sollte also demnächst mal gegen ein Jenaer Programm spielen. Interessenten bitte bescheidgeben. Programmierung idealerweise in Haskell, muß aber nicht. Das Jenaer Programm ist es auch nicht. Mein Interface ist darauf vorbereitet, externe Programme aufzurufen.

(Atari-)Go

Go ist ein sehr altes asiatisches Brettspiel, über das man lange Vorträge halten und das man sein Leben lang studieren kann. Ganz kurz gesagt geht es darum, auf dem Spielfeld Gebiet abzugrenzen, und wer die meisten freien Punkte umschlossen hat, gewinnt. Was ist Gebiet? Ein Punkt ist ein Gebietspunkt, wenn sich der Gegner dort nicht mehr zu setzen traut, weil er dann gefangen würde. Wann wird ein Stein (eine Gruppe von Steinen) gefangen? Wenn sie keine freien Nachbarpunkte mehr besitzt.

Einige Links zum Go

Deutscher Go-Bund
Go im Leipziger Hochschulsport
Go spielende Programme
Many Faces of Goeines der besten und umfangreichsten kommerziellen Programme
Igowin, kostenlose Demo-Version davon, sehr empfohlen für Anfänger
Gnu Go, freie Software, d. h. mit Quelltexten zum Studieren und Hacken
CGoban, eine grafische Oberfläche, mit der man (z. B.) die Gnugo-Engine benutzen kann.

Hausaufgabe: im Sinne von Prof. Althöfers Vortrag: das Gnugo so hacken, daß man aus den Top-k Zügen wählen kann.

Go-Programme sind derzeit viel schwächer als etwa Schach-Programme, weil zwar viel Wissen über das Spiel vorhanden ist, dieses aber bis jetzt wenig formalisiert ist.

Mit dem Spiel Atari-Go kann man das Fangen üben (aber nicht das Gebiet-Machen). Das Ziel im Atari-Go ist es, als erster einen Stein (eine Gruppe) des Gegners zu fangen.

Hausaufgabe: ein Spielbrett-Modul für Go schreiben (d. h. mitrechnen, ob jemand gefangen wird und ob ein Ko geschlagen werden darf) und ein Spieler-Modul für Atari-Go.

Gomoku

Hat nichts mit Go zu tun. Heißt manchmal auch Gobang oder Fünf in einer Reihe. Leicht geänderte Regeln sind Renju.

Spielziel: fünf Steine eigener Farbe in einer Reihe anordnen (waagerecht, senkrecht oder diagonal).

Vorsicht: auf kleinen Feldern ist das Spiel vollständig gelöst. Viktor Allis hat den kompletten Suchbaum durchmustert (mit viel Rechenkraft). Das heißt aber noch nicht, daß es ideal spielende Programme gibt (die müßten den Baum aufbewahren, aber der ist zu groß).

Ein recht gut spielendes Programm mit ganz einfachem Algorithmus hat jeder auf seinem Rechner, meist ohne daß er es weiß: emacs anschalten und dann Meta-X gomoku.

Aufgaben:

Gomoku-Schiedsrichter
Gomoku-Spieler von emacs verstehen, evtl. nachimplementieren
einen besseren Spieler programmieren

Hex

Das Spielfeld ist hier zu einem Rhombus verschoben, trotzdem sind die Koordinaten verwendbar. Spielziel: eine Verbindung zwischen gegenüberliegenden Seiten schaffen.

Weitere Erläuterungen

Auch hier gibt es ein sehr gut spielendes Programm, das eine simple Idee verwendet, die schon von Claude Shannon stammt: man betrachtet den Graphen als Widerstandsnetzwerk und rechnen den Knoten/Kante aus, über den der meiste Strom fließt, und setzt dort.

Aufgaben

Hex-Schiedsrichter
die obige Idee implementieren
einen besseren Spieler programmieren

Connect

Auch ein Verbindungs-Spiel, auch recht alt. Bei Hex hatten wir Knoten besetzt, jetzt geht es um Kanten in einem Graphen.

Spielziel: zwei gegenüberliegende Seiten verbinden oder einen geschlossenen Kantenzug erreichen.

Jetzt geht das nicht mehr so einfach mit den Widerständen, denn selbst eine in drei Zügen drohende Oben-Unten-Verbindung kann durch eine Folge von Kleinen-Kreis-Drohungen zunichte gemacht werden. Es ist nicht klar, wie die beiden Gewinnmöglichkeiten bei der Suche berücksichtigt werden sollten.

Aufgaben

(Schiedsrichter habe ich schon)
einen Spieler programmieren, der auch mal gegen Jena antreten kann

Der Connect-Schiedsrichter

Bei allen Verbindungsspielen geht es um Punkte, Punktmengen, Kanten, Kantenzüge usw. Oft werden verbundene Steine als Gruppe weiterbehandelt (die dann eine Verbindung ergibt, oder als Ganzes gefangen wird, usw.) Dazu muß man feststellen, wer zu welcher Gruppe gehört (und umgekehrt die Mitglieder einer Gruppe finden - das aber seltener). D. h. man benötigt eine Struktur für Disjoint Sets. Die muß die Operation Testen (ob zwei Punkte in der gleichen Menge sind) und Vereinigen unterstützen. Man macht das mit Zeigern, also implizit Bäumen, die man beim Vereinigen erzeugt: jeder zeigt auf einen Vorgänger (der schon "früher" in der Menge war), und einer (der erste) hat keine Vorgänger.

Wir benutzen dabei FiniteMaps. Wir sehen hier, wie das benutzt wird, um den Spielzustand zu verwalten, und hier, wie das als Instanz von Brett und Bild verkauft wird.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de