you're reading...

SACT Seminar: The Complexity of General Game Playing

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)



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: