Kombinatorische Spieltheorie

Teilnehmerkreis:

Aktuelles:

Hörer und Interessenten tragen sich bitte in die Mailingliste ein. (Neue Subskribenten lesen bitte zunächst das Archiv.)

Übersicht:

Der einfachste Fall sind ungeteilte Spiele (impartial games), bei denen beiden Spielern stets die gleichen Zugmöglichkeiten zur Verfügung stehen. (Klassische, und gleichzeitig typische Vertreter sind Nim-Spiele.) Wir werden diese Spiele nach der Theorie von Sprague und Grundy durch Zahlen beschreiben.

Auch im Falle von geteilten Spielen (partizan games, die Spieler haben verschiedene Optionen) suchen wir nach mathematischen Objekten, die den Wert einer Spielsituation beschreiben. Wir wollen mit diesen Objekten rechnen, d. h. insbesondere sie vergleichen und addieren. Wir stellen jedoch schnell fest, daß ganze Zahlen für geteilte Spiele nicht ausreichen.

Die Lösung ist Conways Konstruktion, eine Verallgemeinerung sowohl der Cantorschen Ordinalzahlen, als auch des Dedekindschen Schnittes. Wir erhalten nicht nur ganze und reelle, sondern auch infinitesimal kleine und große, sowie andere surreale Zahlen.

Wir lernen diese Objekte sowohl axiomatisch als auch praktisch kennen, und werden damit verschiedene Spiele analysieren, beginnend bei einfachen, über nur scheinbar einfache (Käsekästchen) hin zu Go-Endspielen.

An einigen Stellen ziehen wir Verbindungen zur Komplexitätstheorie und endlichen Modelltheorie: kombinatorische Spiele könnte man im Prinzip durch vollständiges Absuchen aller Möglichkeiten entscheiden, das ist aber impraktikabel, denn viele sind vollständig für hohe Komplexitätsklassen (PSPACE). Das liegt daran, daß das abwechselnde Setzen im Spiel einer Folge von Quantorenwechseln in einer logischen Formel entspricht.

Bei Interesse können die Hörer gern Spielstrategien implementieren und gegeneinander spielen lassen. (Empfohlen wird dazu der Besuch des Blockpraktikums Haskell compact zu Semesterbeginn.) Gegen Ende der Vorlesung werden wir das Spiel für den nächsten Programmierwettbewerb im Sommersemester 2002 festlegen.

Vorkenntnisse:

Literatur:

E. R. Berlekamp, J. H. Conway, R. K. Guy, Gewinnen, Vieweg, 1985.

(Englisches Orginal: Winning Ways, Academic Press, 1982; A K Peters, 2001)

John H. Conway, Über Zahlen und Spiele, Vieweg, 1983.

(Englisches Orginal: On Numbers and Games, Academic Press, 1976; A K Peters, 2001)

Donald E. Knuth: Surreal Numbers,

Addison Wesley, 1974

Richard J. Nowakowski (Ed.), Games of No Chance,

Cambridge University Press, 1996.

Online-Literatur

Richard J. Nowakowski (Ed.): Games of No Chance

http://www.msri.org/publications/books/Book29/contents.htm

David Eppstein: Combinatorial Game Theory (Link-Sammlung)

http://www.ics.uci.edu/~eppstein/cgt/

6. Computer-Olympiade (Maastricht, 2001)

http://www.cs.unimaas.nl/olympiad/

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