General Game Playing - Universelle Spielprogramme

• Applicant: Professor Dr. Michael Thielscher
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2007 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 59840140

• Final Report Year: 2012

Final Report Abstract

Im Unterschied zur klassischen Spielprogrammierung, die auf vorgegebenen Suchstrategien, Bewertungsfunktionen und umfangreichen Bibliotheken für spezielle Spiele beruht, befasst sich das General Game Playing (kurz: GGP) mit der Konstruktion von universellen Spielprogrammen. Diese sind in der Lage, die Beschreibung eines beliebigen Spiels zu verstehen und ohne menschliches Zutun zu lernen, sich in diesem Spiel erfolgreich zu schlagen. Strategien, Suchheuristiken und Bewertungsfunktionen muss sich das System selbstständig anhand der Spielregeln erarbeiten. Die im Rahmen des Projekts erzielten Hauptergebnisse sind: 1. die Entwicklung der mathematisch-logischen Grundlagen für universelle Spielprogramme; 2. die Generalisierung einer Reihe von Methoden aus der KI-Planung zur Steigerung der Spielstärke von universellen Spielprogrammen; 3. die Entwicklung von Methoden zum automatischen Erlernen spezifischen Wissens allein auf Grundlage der Spielregeln; 4. die Entwicklung von Methoden zur Verwendung dieses Wissens zur Steigerung der Spielstärke; 5. die Weiterentwicklung unseres GGP-Systems Fluxplayer, mit dem wir 2006 den Weltmeistertitel errangen und seitdem an allen internationalen Wettbewerben erfolgreich teilgenommen haben. Die Forschungsinhalte des Projekts finden sich auch als Zusammenfassung auf Grundlage eines ausführlichen Interviews mit dem Projektleiter im DFG-Jahresbericht 2007 als Highlight in den Ingenieurwissenschaften. In einem "Know-how“ der populären Computerzeitschrift c’t haben wir das über das Forschungsgebiet des General Game Playing berichtet und die grundlegenden Verfahren einem breiteren Publikum näher gebracht. Im Zusammenhang mit dem Projekt haben wir die Webseite www.general-game-playing.de aufgebaut. Sie bietet umfassende Informationen über zurückliegende und aktuelle Meisterschaften sowie Workshops im General Game Playing und verweist auf einschlägige Publikationen im Forschungsfeld. Eine umfangreiche Sammlung von Lehrmaterialen erlaubt die Ausgestaltung kompletter Kurse, darüber hinaus stehen Quellcode für einfache Spieler in Java, C++ und Prolog sowie weitere Programme zum automatisierten Parsen, Überprüfen und Schlussfolgern auf Basis von Spielbeschreibungen zur Verfügung. Reger Benutzung durch Gruppen aus aller Welt erfreut sich unser Spieleserver ggpserver.general-game-playing.de. Basierend auf einer umfangreiche Sammlung aktuell in der Spielbeschreibungssprache formulierter Spiele organisiert er Partien zwischen angemeldeten Agenten zu deren Erprobung vollautomatisch. Das Interface erlaubt die Visualisierung gespielter Partien sowie die Abfrage weiterer Informationen über umfangreiche Filtermechanismen. Neben der zusätzlichen Möglichkeit des Antretens eines Menschens gegen einen automatischen Spieler wird auch die komplette Erstellung und Durchführung von Turnieren angeboten. In den letzten Jahren wurden neben den klassischen Suchverfahren mit Bewertungsfunktionen mit simulationsbasierten Verfahren sehr gute Ergebnisse erzielt. Wir wollen untersuchen inwieweit sich diese beiden Ansätze vorteilhaft kombinieren lassen. Des weiteren verfolgen wir die Effektivierung unseres Verfahrens zum automatisierten Beweisen von Spieleigenschaften sowie dessen Erweiterung auf eine größere Klasse von Eigenschaften. Neben der gezielten Nutzung durch automatisierte Spieleagenten ist eine Anwendung unseres Verfahrens für die Korrektheitsanalyse von Spielbeschreibungen in der Designphase interessant. Eine höchst interessante und vielversprechende Anwendung der Ergebnisse aus dem Projekt über die Spielprogrammierung hinaus besteht in ihrer Übertragung auf andere Gebiete der künstlichen Intelligenz. Dem Konzept eines universellen Spielprogramms liegt das Prinzip eines intelligenten Systems zugrunde, das eine Beschreibung eines Problems verstehen kann und das sich dann selbstständig eine Strategie zur Problemlösung erarbeitet und diese anwendet, ohne dass dem Programmierer des Systems die jeweils konkreten Aufgabenstellungen vorher bekannt sind. Bei der Übertragung dieses Grundprinzips von der KI-Spielprogrammierung auf andere Gebiete dürften die in dem Projekt erzielten Ergebnisse von großem Nutzen sein.

Publications

• A multiagent semantics for the Game Description Language. In J. Filipe, A. Fred, and B. Sharp, editors, Agents and Artificial Intelligence, volume 67 of Communications in Computer and Information Science, pages 44–55. Springer, 2009
  Stephan Schiffel and Michael Thielscher
  
• Answer set programming for single-player games in general game playing. In P. Hill and D. Warren, editors, Proceedings of the International Conference on Logic Programming (ICLP), volume 5649 of LNCS, pages 327–341, Pasadena, July 2009. Springer
  Michael Thielscher
  
• Automated theorem proving for general game playing. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 911–916, Pasadena, July 2009
  Stephan Schiffel and Michael Thielscher
  
• Decomposition of multi-player games. In A. Nicholson and X. Li, editors, Proceedings of the Australasian Joint Conference on Artificial Intelligence, volume 5866 of LNCS, pages 475–484, Melbourne, December 2009. Springer
  Dengji Zhao, Stephan Schiffel, and Michael Thielscher
  
• Factoring general games. In Yngvi Björnsson, Peter Stone, and Michael Thielscher, editors, Proceedings of the IJCAI-09 Workshop on General Game Playing (GIGA’09), pages 27–34, Pasadena, California, USA, July 2009
  Martin Günther, Stephan Schiffel, and Michael Thielscher
  
• Matt bei “Vier gewinnt”. c’t, 1:174–181, January 2009
  Daniel Michulke and Stephan Schiffel
  
• Neural networks for state evaluation in general game playing. In W. Buntine, M. Grobelnik, D. Mladenic, and J. Shawe-Taylor, editors, Proceedings of the European Conference on Machine Learning (ECML), volume 5782 of LNCS, pages 95–110, Bled, Slovenia, August 2009. Springer
  Daniel Michulke and Michael Thielscher
  
• A general game description language for incomplete information games. In M. Fox and D. Poole, editors, Proceedings of the AAAI Conference on Artificial Intelligence, pages 994–999, Atlanta, July 2010
  Michael Thielscher
  
• A temporal proof system for general game playing. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1000–1005, Atlanta, July 2010. AAAI Press
  Michael Thielscher and Sebastian Voigt
  
• From general game descriptions to a market specification language for general trading agents. In E. David, E. Gerding, D. Sarne, and O. Shehory, editors, Agent-Mediated Electronic Commerce: Designing Trading Strategies and Mechanisms for Electronic Markets, volume 59 of LNBIP, pages 259–274. Springer, 2010
  Michael Thielscher and Dongmo Zhang
  
• Pushing the envelope: General game players prove theorems. In J. Li, editor, Proceedings of the Australasian Joint Conference on Artificial Intelligence, volume 6464 of LNCS, pages 1–10, Adelaide, December 2010. Springer
  Sebastian Haufe and Michael Thielscher
  
• Symmetry detection in general game playing. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 980–985, Atlanta, July 2010. AAAI Press
  Stephan Schiffel
  
• Knowledge-based general game playing. Künstliche Intelligenz, 25(1):25–33, 2011
  Sebastian Haufe, Daniel Michulke, Stephan Schiffel, and Michael Thielscher
  
• Reasoning about general games described in GDL-II. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 846–851, San Francisco, July 2011
  Stephan Schiffel and Michael Thielscher
  
• The epistemic logic behind the game description language. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 840–845, San Francisco, July 2011
  Ji Ruan and Michael Thielscher
  
• The general game playing description language is universal. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1107–1112, Barcelona, July 2011
  Michael Thielscher
  
• Translating general game descriptions into an action language. In M. Balduccinin and T. Son, editors, Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond, volume 6565 of LNAI, pages 300–314. Springer, 2011
  Michael Thielscher
  
• Distance features for general game playing. In Proceedings of the 4th International Conference on Agents and Artificial Intelligence (ICAART), Vilamoura, Portugal, February 2012
  Daniel Michulke and Stephan Schiffel