[TZI]  [Computer Science Department]  [University of Bremen] 

General Game Playing Competition

Seminar SS 2009:
Spieltheorie (Game Theory)
Kooperation, Lernen, Entscheiden

Dozenten

Stefan Edelkamp
TAB Raum 2.62
Telefon: +49-421-218-4676
eMail: edelkamp(at)tzi.de
Hagen Langer
TAB Raum 2.55
Telefon: +49-421-218-4676
eMail: hlanger(at)tzi.de
Hartmut Messerschmidt
TAB Raum 2.77
Telefon: +49-421-218-9740
eMail: hartmut.messerschmidt(at)tzi.de 
Thomas Wagner
TAB Raum 2.89
Telefon: +49-421-218-9740
eMail: twagner(at)tzi.de 

Modul

710 (KI)

Treffpunkt

Dienstags, 15-17 Uhr, TAB, Raum 1.51

Thema

Die Spieltheorie ist ein Gebiet der theoretischen Wirtschaftswissenschaften, neuerdings jedoch auch für Künstliche Intelligenz und Informatik von Interesse, wenn es darum geht, dezentrale, heterogene Systeme von egoistischen Agenten zu modellieren. Während Lösungsbegriffe für Spiele bereits bekannt sind, sind noch viele algorithmische Fragen zu behandeln. Das Lösen von Ein-, Zwei- und Mehrpersonenspielen gehört zu den erfolgreichsten Anwendungen der Künstlichen Intelligenz. Auch in der letzten Zeit gibt es immer wieder erstaunliche Entwicklungen. Das Seminar hinterleuchtet Ansätze, die in State-of-the-Art Computerspielern verwendet werden und geht dabei sowohl auf die technischen Rafinessen als auch auf theoretischen Konzepte ein.

Inhalte

Von Ein- und Zwei-Personen-Nullsummenspielen und deren Komplexität ausgehend, werden Spiele mit Kosten, Zufall und mehereren Spielern untersucht. Das Lernen von Evaluationsfunktionen insbesondere in Alpha-Beta wird thematisiert. Aus der Vielzahl von Beschleunigungstechniken werden einige hervorgehoben. Mit UCT finden auch neuere Algorithmen Eingang, die keine vorab definierte Evaluationsfunktion benötigen. Realzeitspiele bilden gänzlich andere Anforderungen als Strategiespiele, und rücken aufgrund ihres Markpotentials in den Fokus von KI-Forschern. Allgemeine Spielprogramme nutzen keine zusätzliche Information als die Spielbeschreibung selbst und sind somit universell einsetzbar. Der Bezug zwischen einer optimalen Spielbeschreibung und eines ebensolchen Reglers wird offenbar, wenn man den Gegenspieler durch die durch die mit Unsicherheit behaftete Umgebung ersetzen kann.

Themen

T.B.A.

Literatur (Auswahl)

  • Anatol Rapoport: Two-Person Game Theory, Dover
  • Cameron Browne: Hex Strategy, AK Peters
  • Ernst A. Heinz: Scalable Search in Computer Chess
  • Werner Krabs: Spieltheorie, Dynamische Behandlung von Spielen, Teubner
  • Martin Müller: Computer Go as the Sum of Local Games, ETH Zürich
  • Andreas Junghanns: Pushing the Limits: New Developments in Single-Agent Search, University of Alberta
  • Bernhard Nebel: Spieltheorie, Vorlesungsskript
  • Ingo Wegener/Thomas Hofmeister: Operations Research, Vorlesungsskript
...sowie aktuelle Veröffentlichung in KI-Konferenzen und Journalen
Spieltheorie

Stefan Edelkamp (edelkamp@tzi.de)