Time: 1:00pm Wednesday 27 November.
Location: SIT 402
Speaker: Abdallah Saffidine, NICTA
Paper: The Complexity of General Game Playing
The Game Description Language (GDL) used in General Game Playing (GGP) competitions provides a compact way to express multi-agents systems. Multiple features of GDL contribute to making it a convenient tool to describe multi-agent systems.
We study the computational complexity of reasoning in GGP using various combinations of these features. We identify variables and non-monotonic fluents as important features increasing the complexity. On the other hand, focusing on the decidable fragment of GDL , we show that negation, nesting of function symbols, and auxiliary predicates do not affect the complexity.
Our analysis offers a complexity landscape for GGP with fragments ranging from NP to EXPSPACE in the single-agent case, and from PSPACE to 2 EXPTIME in the multi-agent case.
Joint work with Édouard Bonnet (Université Paris-Dauphine, France)