Spezialvorlesung Handlungsplanung und Allgemeines Spiel (WS 2010/11)

Dozenten



Termine

Raum 1.50 (TZI, TAB, Am Fallturm 1)



Thema

Die Vorlesung gibt einen Einblick in den aktuellen Forschungsstand und neue Forschungsrichtungen in der Handlungsplanung und im Allgemeinen Spiel.

Handlungsplanung

Dieser Teil wird komplett von Stefan Edelkamp gehalten. Alle Informationen (Skript, Folien, etc.) dazu sind auf seiner Webseite zu finden.

Allgemeines Spiel (engl. General Game Playing, GGP)

Forschungszweig, in dem Spiele in einer problemunabhägigen Beschreibungssprache formuliert werden und dazu aufgerufen wird, Spieler zu konzipieren, die über eine geeignete Schnittstelle gegen einen Menschen oder gegeneinander antreten.
Die Spiele sind endlich und terminale Zustände werden über Auszahlungsvektoren mit Werten im Bereich {0,. . . ,100} beschriftet. Algorithmen propagieren diese Werte innerhalb des Suchbaumes möglicher Abspiele zu dem aktuellen Spielzustand, um daraus eine gewinnversprechende Nachfolgerwahl zu ermöglichen.
Der heute wohl am weitesten verbreitete Beschreibungsformalismus GDL (Game Description Language) ist eine logikbasierte Beschreibungssprache, die - im Gegensatz zu PDDL, das häufig in der Handlungsplanung zum Einsatz kommt - auf dem Situationskalkül beruht und statische Definitionsblöcke, welche in Datalog beschrieben werden, besitzt. Es gibt nationale und internationale Wettbewerbe, von denen jener auf der amerikanischen KI-Konferenz AAAI am höchsten dotiert ist letzterer ist sicherlich auch ein Grund für den Erfolg dieses Formalismus.
Das allgemeine Spiel wurde ursprünglich von der Logik-Gruppe der Universität Stanford initiiert und gefördert; in Deutschland war in den letzten Jahren die Gruppe um Michael Thielscher an der gebend - dort findet sich auch ein Server, auf dem Spieler gegeneinander antreten können.
Neben einfachen Klassikern wie Nimm oder Tic-Tac-Toe liegen bereits Spiele wie Schach, Dame oder Halma teils in vereinfachter, teils in vollständiger Spezifikation vor, wobei es sich alich um deterministische, endliche Spiele mit vollständiger Information handelt. Die Endlichkeit wird häufig über einen Zugzähler sichergestellt und ein Spiel endet, wenn eine bestimmte Anzahl an Zügen durchgeführt wurde.
Erste erfolgreiche Implementierungen von Spielern wie etwa CLUNEPLAYER und FLUXPLAYER verwenden Heuristiken basierend auf αβ-Pruning. Dabei können Mehrpersonenspiele beispielsweise als Varianten des Zweipersonenspiels aufgefasst werden, indem die Spieler in zwei Mannschaften unterteilt werden: Diejenigen, die mit dem eigenen Spieler kooperieren (was sich etwa darin zeigt, dass sie die gleiche Bewertung in sämtlichen Zielzuständen bekommen), und diejenigen, die gegen ihn spielen.
Ein weiterer aktueller Trend im allgemeinen Spiel ist der UCT Algorithmus (Upper Confidence Bounds Applied to Trees), bei dem nur ein Teil des Spielgraphen im Speicher gehalten wird und eine Einschätzung üer die Qualität einer Position durch zufällige Abspiele ermittelt wird. Die Sieger der letzten drei internationalen Meisterschaften haben diesen Ansatz verfolgt und ihn für Mehrpersonenspiele erweitert.

Übung

Anstatt einer traditionellen Übung mit zu bearbeitenden Zetteln wird von den Studierenden begleitend durch die Vorlesung schrittweise ein Allgemeiner Spieler in Gruppenarbeit programmiert. Am Ende der Vorlesung findet eine Präsentation / Wettbewerb statt.