Skip to main content
SpringerLink
Log in

Logical-Epistemic Foundations of General Game Descriptions

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are specified in the general Game Description Language (GDL), a variant of Datalog with function symbols that uses a few game-specific keywords. A recent extension of basic GDL allows the description of nondeterministic games with any number of players who may have incomplete, asymmetric information. In this paper, we analyse the epistemic structure and expressiveness of this language in terms of modal epistemic logic and prove two main results: (1) The operational semantics of GDL entails that the situation at any stage of a game can be characterised by a multi-agent epistemic (i.e., S5-) model; (2) GDL is sufficiently expressive to model any situation that can be described by a (finite) multi-agent epistemic model.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Apt, Krzysztof, Howard A. Blair, and Adrian Walker, Towards a theory of declarative knowledge, in J. Minker, (ed.), Foundations of Deductive Databases and Logic Programming, chap. 2, Morgan Kaufmann, 1987, pp. 89–148.

  2. Aumann Robert, Adam Brandenburger (1995) Epistemic conditions for Nash equilibrium. Econometrica 63, 1161–1180

    Article  Google Scholar 

  3. Fagin, Ronald, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, Reasoning About Knowledge, The MIT Press: Cambridge, MA, 1995.

  4. Gelder, Allen Van, The alternating fixpoint of logic programs with negation, in Proceedings of the 8th Symposium on Principles of Database Systems, ACM SIGACTSIGMOD, 1989, pp. 1–10.

  5. Gelfond, Michael, and Vladimir Lifschitz, The stable model semantics for logic programming, in R. Kowalski, and K. Bowen, (eds.), Proceedings of the International Joint Conference and Symposium on Logic Programming (IJCSLP), MIT Press, Seattle, OR, 1988, pp. 1070–1080.

  6. Genesereth Michael, Nathaniel Love, Barney Pell (2005) General game playing: Overview of the AAAI competition. AI Magazine 26(2):62–72

    Google Scholar 

  7. Halpern, Joseph Y., and Moshe Y. Vardi, The complexity of reasoning about knowledge and time, in Proceedings 18th ACM Symposium on Theory of Computing, 1986, pp. 304–315.

  8. Hintikka, Jaakko, Knowledge and Belief, Cornell University Press, Ithaca, NY, 1962.

  9. Huang, Xiaowei, Ji Ruan, and Michael Thielscher, Model checking for reasoning about incomplete information games, in Proceedings of the Australasian Conference on Artificial Intelligence, Springer LNAI 8272, Dunedin, New Zealand, 2013, pp. 246–258.

  10. Kripke Saul (1963) Semantical analysis of modal logic. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 9, 67–96

    Article  Google Scholar 

  11. Lloyd, John, Foundations of Logic Programming, second, extended edn., Series Symbolic Computation, Springer, 1987.

  12. Lloyd, John W., Rodney W. Topor,(1986) A basis for deductive database systems II. J. Log. Program. 3(1):55-67

    Google Scholar 

  13. Love, Nathaniel, Timothy Hinrichs, David Haley, Eric Schkufza, and Michael Genesereth, General Game Playing: Game Description Language Specification, Tech. Rep. LG–2006–01, Stanford Logic Group, Computer Science Department, Stanford University, 2006.

  14. Moore, Robert C., A formal theory of knowledge and action, in J.F. Allen, J. Hendler, and A. Tate, (eds.), Readings in Planning, Morgan Kaufmann Publishers, San Mateo, CA, 1990, pp. 480–519.

  15. Pell, Barney, Strategy Generation and Evaluation for Meta-Game Playing, Ph.D. thesis, Computer Laboratory, University of Cambridge, 1993.

  16. Pitrat, Jacques, A general game playing program, in N. Findler, and B. Meltzer, (eds.), Artificial Intelligence and Heuristic Programming, Edinburgh University Press, 1971, pp. 125–155.

  17. Pritchard, David, The Encyclopedia of Chess Variants, Godalming, 1994.

  18. Rao, Anand S., and Michael P. Georgeff, Modeling rational agents within a BDI-architecture, in James F. Allen, Richard Fikes, and Erik Sandewall, (eds.), KR, Morgan Kaufmann, 1991, pp. 473–484.

  19. Ruan, Ji, and Michael Thielscher, Strategic and epistemic reasoning for the game description language GDL-II, in Proceedings of the European Conference on Artificial Intelligence (ECAI 2012), IOS Press, Montpellier, France, 2012, pp. 696–701.

  20. Ruan Ji, Wiebe van der Hoek, Michael Wooldridge (2009) Verification of games in the Game Description Language. Journal Logic and Computation 19(6):1127–1156

    Article  Google Scholar 

  21. Thielscher, Michael, A general game description language for incomplete information games, in Proceedings of the Conference on the Advancement of Artificial Intelligence (AAAI), Atlanta, 2010, pp. 994–999.

  22. Thielscher, Michael, The general game playing description language is universal, in Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Barcelona, 2011, pp. 1107–1112.

  23. Wooldridge, Michael, An Introduction to Multiagent Systems, John Wiley & Sons, 2002.

  24. Wooldridge, Michael, and Alessio Lomuscio, A computationally grounded logic of visibility, perception, and knowledge, Logic Journal of the IGPL 9(2):257–272, 2001.

    Google Scholar 

  25. Wright, Georg H. von, An Essay in Modal Logic, North-Holland, Amsterdam, 1951.

Download references

Author information

Authors and Affiliations

  1. School of Computer and Mathematical Sciences, Auckland University of Technology, Auckland, 1142, New Zealand

    Ji Ruan

  2. School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW, 2052, Australia

    Michael Thielscher

Authors
  1. Ji Ruan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Thielscher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ji Ruan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ruan, J., Thielscher, M. Logical-Epistemic Foundations of General Game Descriptions. Stud Logica 102, 321–338 (2014). https://doi.org/10.1007/s11225-014-9547-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-014-9547-2

Keywords

Search

Navigation