[Chair]  [Computer Science Department (FBI)]  [Technical University Dortmund] 

Vorlesungsfolien

General Game Playing Competition

Spezialvorlesung
SS 2008: Spieltheorie - Algorithmen zur Lösung von Spielen

Dozent/Betreuung

PD Dr. Stefan Edelkamp

Dipl. Inform. Peter Kissmann

Mittwochs, 10-12 Uhr, Otto-Hahn-Str. 14, Raum 105 Achtung: Wegen des großen Andrangs: Übergangsweise Verlegung auf 202

Zuordnung Schwerpunktgebiete

4. Algorithmen, Komplexität und formale Modelle, 7. Intelligente Systeme

Thema

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. Die Problem-orientierte Vorlesung hinterleuchtet Ansätze, die in State-of-the-Art Computerspielern verwendet werden und geht dabei weniger auf die technischen Rafinessen, denn vor allem auf theoretischen Konzepte ein.

Inhalt

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. Letztendlich ist die Spieltheorie 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.

Struktur

  • Einleitung/Übersicht
  • Einpersonenspiel
  • Spielbaumsuche Zweipersonenspiel
  • Minimax-Theorem
  • Nicht-kooperative Spiele
  • Kooperative Spiele
  • Koalitionen
  • Spielbaumsuche Mehrpersonenspiel
  • Evaluationsfunktionen
  • Kombinatorische Spieltheorie
  • Spiele mit Zufall
  • Allgemeine Spiele
  • Realzeitspiele
  • Spiele und Model-Checking

Highlights

  • Schach: Von "Null-Move Pruning" zu "Interior-Node Recognition". Highlight: Das PC-Computerprogramm Fritz schlägt Wladimir Kramnik
  • Schiebepuzzle: Musterdatenbanken und Externe Suche. Highlight: Vollständige Exploration des 15-Puzzles
  • Sokoban: Das Lernen von Sackgassen und Symbolisches Planen. Highlight: Lösung von Microban-Problemen mit einem Planungssystem
  • Checkers: Die Macht von Endspieldatenbanken. Highlight: Lösung des American Checkers Problem.
  • Hex: Lernen von Evaluationsfunktionen in Alpha-Beta. Highlight: Virtuelle Verbindungen motiviert aus der E-Technik.
  • Go: Kombinatorische Spieltheorie. Highlight: Suchfreie Lösung von Nimm.
  • Backgammon: Temporal Difference Learning bei Zwei-Personen-Spielen. Highlight: TD-Gammon spielt so gut wie der Mensch.
  • Skat: Doppelter Dummy. Highlight: Auswertung eines Blatts in Sekundenschnelle.
  • StarCraft: Strategische Realzeitspiele. Highlight: Programmier-Wettbewerb.
  • General Game Playing: Monte-Carlo Sampling und UCT Highlight: Vollständige Erreichbarkeitsanalyse von 4-Gewinnt.
  • Das Paritätsspiel: Synthese von Kontrollern. Highlight: Lösung von mu-calculus Modellprüfungsproblemen.
  • Matching-Pennies, Gefangendilemma und Auktionen: Highlight: Nash-Gleichgewichtstheorie.
  • Wumpus, RaceTrack u.ä.: Markov'sche Entscheidungstheorie. Highlight: Externe Wertiteration.
  • Poker: Modellierung des Gegners. Highlight: Aktuelle Ergebnisse der Competition.

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 (stefan.edelkamp@cs.uni-dortmund.de)