Vorlesung im Wintersemester 2001/02, Dr. J. Waldmann

Kombinatorische Spieltheorie


Teilnehmerkreis:

Vorlesung für Studenten der Informatik oder Mathematik im Hauptstudium, mit Schwerpunkt Praktische oder Theoretische Informatik.

Aktuelles:

Die Vorlesung findet donnerstags 17:00 - 18:30 im Seminarraum SG 3-05 statt.

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


Übersicht:

Die kombinatorische Spieltheorie ist die mathematische Analyse von endlichen, deterministischen Zweipersonen-Nullsummenspielen mit vollständiger Information.

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:

(außer Freude am Spielen und logischen Schließen) keine.

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
best viewed with any browser