Joint work with Wiebe van der Hoek and Michael Wooldridge. Published in the Proceedings of Workshop on Logic, Rationality and Interaction (LORI07), Beijing, August 2007.
PDF Download: Strategy Logics and the Game Description Language.
Any comments are welcome!
ABSTRACT: The Game Description Language (GDL) is a special purpose declarative language for defining games. GDL is used in the AAAI General Game Playing Competition, which tests the ability of computer programs to play games in general, rather than just to play a specific game. Participants in the competition are provided with a game specified in GDL, and then required to play this game. Recently, there has been much interest in the use of strategic cooperation logics for reasoning about game-like scenarios, Alternating-time Temporal Logic (ATL) is perhaps the best known example. The aim of this paper is to make a link between ATL and GDL. We show that a GDL specification can be viewed as a specification of an ATL model, and that ATL can thus be interpreted over GDL specifications. Our main result is that it is possible to translate a propositional GDL specification into an “equivalent” ATL specification, which is only polynomially larger than the original GDL specification. As a corollary, we are able to characterise the complexity of reasoning about GDL-specified games using ATL: it is EXPTIME-complete.
Acknowledgment: We would like to thank Dirk Walther and two anonymous reviewers for comments and helpful suggestions.
Related posts:
- My Coming talk in Liverpool: Connecting Dynamic Epistemic and Temporal Epistemic Logics For Multi-Agent Systems Title: Connecting Dynamic Epistemic and Temporal Epistemic Logics For Multi-Agent...
- Private: Submission on Healthcare (protected due to review process) \begin{abstract} Healthcare systems are essential in maintaining the well-being of...
Related posts brought to you by Yet Another Related Posts Plugin.
