×

Logical-epistemic foundations of general game descriptions. (English) Zbl 1329.03051

Summary: 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.

MSC:

03B42 Logics of knowledge and belief (including belief change)
91A44 Games involving topology, set theory, or logic

Software:

GDL
PDFBibTeX XMLCite
Full Text: DOI

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 · Zbl 0841.90125 · doi:10.2307/2171725
[3] Fagin, Ronald, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, Reasoning About Knowledge, The MIT Press: Cambridge, MA, 1995. · Zbl 0839.68095
[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. · Zbl 0793.68039
[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. · Zbl 0841.90125
[6] Genesereth Michael, Nathaniel Love, Barney Pell (2005) General game playing: Overview of the AAAI competition. AI Magazine 26(2):62-72
[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. · Zbl 0118.01305
[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 · Zbl 0118.01305 · doi:10.1002/malq.19630090502
[11] Lloyd, John, Foundations of Logic Programming, second, extended edn., Series Symbolic Computation, Springer, 1987. · Zbl 0118.01305
[12] Lloyd, John W., Rodney W. Topor,(1986) A basis for deductive database systems II. J. Log. Program. 3(1):55-67 · Zbl 0591.68087
[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. · Zbl 0765.68194
[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. · Zbl 1327.68282
[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 · Zbl 1185.68678 · doi:10.1093/logcom/exp039
[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. · Zbl 1079.91500
[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. · Zbl 0974.68203
[25] Wright, Georg H. von, An Essay in Modal Logic, North-Holland, Amsterdam, 1951. · Zbl 0043.00701
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.