×

Epistemic GDL: a logic for representing and reasoning about imperfect information games. (English) Zbl 1519.68252

Summary: This paper proposes a logical framework for representing and reasoning about imperfect information games. We first extend Game Description Language (GDL) with the standard epistemic operators and provide it with a semantics based on the epistemic state transition model. We then demonstrate how to use the language to represent the rules of an imperfect information game and formalize common game properties as well as epistemic properties. We also show how to use the framework to reason about players’ own and each others’ knowledge during game playing. Furthermore, we prove that the model-checking problem of the framework is in \(\Delta_2^\mathrm{P}\), even though its lower bound is \(\Theta_2^\mathrm{P}\). These results indicate that the framework makes a good balance between expressive power and computational efficiency. Finally we provide a sound and complete axiomatic system for this logic. With action, temporal and epistemic operators, the completeness proof requires a novel combination of techniques used for completeness of dynamic logic and epistemic temporal logics. The proof theory provides a feasible tool to analyze properties of a family of games.

MSC:

68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
68Q60 Specification and verification (program logics, model checking, etc.)
68T30 Knowledge representation
91A27 Games with incomplete information, Bayesian games

Software:

GDL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jiang, G.; Zhang, D.; Perrussel, L.; Zhang, H., Epistemic GDL: A logic for representing and reasoning about imperfect information games, (Proceedings of the 25th International Joint Conference on Artificial Intelligence. Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI’16 (2016)), 1138-1144
[2] Perea, A., Epistemic Game Theory: Reasoning and Choice (2012), Cambridge University Press
[3] van Benthem, J., Logic in Games (2014), MIT Press · Zbl 1291.03003
[4] Alur, R.; Henzinger, T. A.; Kupferman, O., Alternating-time temporal logic, J. ACM, 49, 5, 672-713 (2002) · Zbl 1326.68181
[5] Pauly, M., A modal logic for coalitional power in games, J. Log. Comput., 12, 1, 149-166 (2002) · Zbl 1003.91006
[6] Chatterjee, K.; Henzinger, T. A.; Piterman, N., Strategy logic, Inf. Comput., 208, 6, 677-693 (2010) · Zbl 1205.68197
[7] Mogavero, F.; Murano, A.; Vardi, M. Y., Reasoning about strategies, (Proceedings of the 30th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Proceedings of the 30th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS’10 (2010)), 133-144 · Zbl 1245.68138
[8] van Benthem, J., Reasoning about strategies, (Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky (2013), Springer), 336-347 · Zbl 1264.03052
[9] van Eijck, J., PDL as a multi-agent strategy logic, (Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge. Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge, TARK’13 (2013)), 206-215
[10] Jamroga, W.; van der Hoek, W., Agents that know how to play, Fundam. Inform., 63, 2, 185-219 (2004) · Zbl 1102.68106
[11] van der Hoek, W.; Wooldridge, M., Cooperation, knowledge, and time: alternating-time temporal epistemic logic and its applications, Stud. Log., 75, 1, 125-157 (2003) · Zbl 1034.03013
[12] Ågotnes, T.; van der Hoek, W.; Wooldridge, M., Reasoning about coalitional games, Artif. Intell., 173, 1, 45-79 (2009) · Zbl 1180.68271
[13] Berthon, R.; Maubert, B.; Murano, A.; Rubin, S.; Vardi, M. Y., Strategy logic with imperfect information, (Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science. Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’17 (2017), IEEE), 1-12 · Zbl 1458.68113
[14] Belardinelli, F., A logic of knowledge and strategies with imperfect information, (Proceedings of the 8th Workshop on Logical Aspects of Multi-Agent Systems. Proceedings of the 8th Workshop on Logical Aspects of Multi-Agent Systems, LAMAS’15 (2015)), 1-15
[15] van Benthem, J., Games in dynamic-epistemic logic, Bull. Econ. Res., 53, 4, 219-248 (2001) · Zbl 1230.03046
[16] Lorini, E.; Schwarzentruber, F., A modal logic of epistemic games, Games, 1, 4, 478-526 (2010) · Zbl 1311.91047
[17] Maubert, B.; Pinchinat, S.; Schwarzentruber, F., Reachability games in dynamic epistemic logic, (Proceedings of the 28th International Joint Conference on Artificial Intelligence. Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI’19 (2019)), 499-505
[18] Huang, X.; van der Meyden, R., A temporal logic of strategic knowledge, (Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning, KR’14 (2014)), 418-427
[19] Mogavero, F.; Murano, A.; Perelli, G.; Vardi, M. Y., Reasoning about strategies: on the model-checking problem, ACM Trans. Comput. Log., 15, 4, 1-47 (2014) · Zbl 1354.68178
[20] Huang, X.; Meyden, R. V.D., An epistemic strategy logic, ACM Trans. Comput. Log., 19, 4, 1-45 (2018) · Zbl 1407.03020
[21] Genesereth, M.; Love, N.; Pell, B., General game playing: overview of the AAAI competition, AI Mag., 26, 2, 62-72 (2005)
[22] Love, N.; Hinrichs, T.; Haley, D.; Schkufza, E.; Genesereth, M., General Game Playing: Game Description Language Specification (2006), Stanford Logic Group, Computer Science Department, Stanford University
[23] Zhang, D.; Thielscher, M., Representing and reasoning about game strategies, J. Philos. Log., 44, 2, 203-236 (2015) · Zbl 1347.68327
[24] Thielscher, M., A general game description language for incomplete information games, (Proceedings of the 24th AAAI Conference on Artificial Intelligence. Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI’10 (2010)), 994-999
[25] Thielscher, M., GDL-III: a description language for epistemic general game playing, (Proceedings of the 26th International Joint Conference on Artificial Intelligence. Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI’17 (2017)), 1276-1282
[26] Schiffel, S.; Thielscher, M., Reasoning about general games described in GDL-II, (Proceedings of the 25th AAAI Conference on Artificial Intelligence. Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI’11 (2011)), 846-851
[27] Schiffel, S.; Thielscher, M., Representing and reasoning about the rules of general games with imperfect information, J. Artif. Intell. Res., 49, 171-206 (2014) · Zbl 1364.68338
[28] Huang, X.; Ruan, J.; Thielscher, M., Model checking for reasoning about incomplete information games, (Proceedings of the 26th Australasian Joint Conference on Advances in Artificial Intelligence. Proceedings of the 26th Australasian Joint Conference on Advances in Artificial Intelligence, AI’13 (2013)), 246-258
[29] Ruan, J.; Thielscher, M., The epistemic logic behind the game description language, (Proceedings of the 25th AAAI Conference on Artificial Intelligence. Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI’11 (2011)), 840-845
[30] Ruan, J.; Thielscher, M., Strategic and epistemic reasoning for the game description language GDL-II, (Proceedings of the 20th European Conference on Artificial Intelligence. Proceedings of the 20th European Conference on Artificial Intelligence, ECAI’12 (2012)), 696-701 · Zbl 1327.68282
[31] Engesser, T.; Mattmüller, R.; Nebel, B.; Thielscher, M., Game description language and dynamic epistemic logic compared, (Proceedings of the 27th International Joint Conference on Artificial Intelligence. Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI’18 (2018)), 1795-1802
[32] Dima, C.; Tiplea, F. L., Model-checking ATL under imperfect information and perfect recall semantics is undecidable (2011), CoRR
[33] Kozen, D.; Parikh, R., An elementary proof of the completeness of PDL, Theor. Comput. Sci., 14, 1, 113-118 (1981) · Zbl 0451.03006
[34] Halpern, J. Y.; van Der Meyden, R.; Vardi, M. Y., Complete axiomatizations for reasoning about knowledge and time, SIAM J. Comput., 33, 3, 674-703 (2004) · Zbl 1059.68127
[35] Schobbens, P.-Y., Alternating-time logic with imperfect recall, Electron. Notes Theor. Comput. Sci., 85, 2, 82-93 (2004) · Zbl 1270.68287
[36] Pritchard, D. B., The Encyclopedia of Chess Variants, Games & Puzzles (1994)
[37] Fagin, R.; Moses, Y.; Halpern, J. Y.; Vardi, M. Y., Reasoning About Knowledge (2003), MIT Press · Zbl 1060.03008
[38] Reiter, R., The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression, (Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, 27 (1991)), 359-380 · Zbl 0755.68124
[39] Ågotnes, T., Action and knowledge in alternating-time temporal logic, Synthese, 149, 2, 375-407 (2006) · Zbl 1107.03013
[40] Gottlob, G., NP trees and Carnap’s modal logic, J. ACM, 42, 2, 421-457 (1995) · Zbl 0886.68069
[41] Busard, S.; Pecheur, C.; Qu, H.; Raimondi, F., Reasoning about memoryless strategies under partial observability and unconditional fairness constraints, Inf. Comput., 242, 128-156 (2015) · Zbl 1319.68141
[42] Piccione, M.; Rubinstein, A., On the interpretation of decision problems with imperfect recall, Games Econ. Behav., 20, 1, 3-24 (1997) · Zbl 0885.90147
[43] Waugh, K.; Zinkevich, M.; Johanson, M.; Kan, M.; Schnizlein, D.; Bowling, M. H., A practical use of imperfect recall, (Proceedings of the 8th Symposium on Abstraction, Reformulation, and Approximation. Proceedings of the 8th Symposium on Abstraction, Reformulation, and Approximation, SARA’09 (2009)), 175-182
[44] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Dev., 3, 2, 114-125 (1959) · Zbl 0158.25404
[45] Halpern, J. Y.; Moses, Y., A guide to completeness and complexity for modal logics of knowledge and belief, Artif. Intell., 54, 3, 319-379 (1992) · Zbl 0762.68029
[46] van der Hoek, W.; Pauly, M., Modal logic for games and information, (Blackburn, P.; van Benthem, J.; Wolter, F., Handbook of Modal Logic, vol. 3 (2006), Elsevier), 1077-1148
[47] J. van Benthem, D. Klein, Logics for analyzing games, in: Stanford Encyclopedia of Philosophy.
[48] Nuel, B.; Michael, P.; Ming, X., Facing the Future: Agents and Choices in Our Indeterminist World (2001), Oxford University Press
[49] Herzig, A.; Troquard, N., Knowing how to play: uniform choices in logics of agency, (Proceeding of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems. Proceeding of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS’06 (2006)), 209-216
[50] Herzig, A.; Lorini, E., A dynamic logic of agency I: STIT, capabilities and powers, J. Log. Lang. Inf., 19, 1, 89-121 (2010) · Zbl 1189.03025
[51] Belle, V.; Lakemeyer, G., Reasoning about imperfect information games in the epistemic situation calculus, (Proceedings of the 24th AAAI Conference on Artificial Intelligence. Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI’10 (2010)), 255-260
[52] Xiong, L.; Liu, Y., Strategy representation and reasoning for incomplete information concurrent games in the situation calculus, (Proceedings of the 25th International Joint Conference on Artificial Intelligence. Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI’16 (2016)), 1322-1329
[53] Haufe, S.; Thielscher, M., Automated verification of epistemic properties for general game playing, (Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR’12 (2012)), 339-349
[54] Zhang, D.; Thielscher, M., A logic for reasoning about game strategies, (Proceedings of the 29th AAAI Conference on Artificial Intelligence. Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI’15 (2015)), 1671-1677
[55] Thielscher, M., GDL-III: a proposal to extend the game description language to general epistemic games, (Proceedings of the European Conference on Artificial Intelligence. Proceedings of the European Conference on Artificial Intelligence, ECAI’16 (2016)), 1630-1631
[56] Sistla, A. P.; Clarke, E. M., The complexity of propositional linear temporal logics, J. ACM, 32, 3, 733-749 (1985) · Zbl 0632.68034
[57] van Ditmarsch, H.; Knight, S., Partial information and uniform strategies, (Proceedings of the 15th International Workshop on Computational Logic in Multi-Agent Systems. Proceedings of the 15th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA’14 (2014)), 183-198 · Zbl 1425.68397
[58] Huang, X.; Van Der Meyden, R., Symbolic model checking epistemic strategy logic, (Proceedings of the 28th AAAI Conference on Artificial Intelligence. Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI’14 (2014)), 1426-1432
[59] Huang, X., Bounded model checking of strategy ability with perfect recall, Artif. Intell., 222, 182-200 (2015)
[60] Aucher, G.; Maubert, B.; Pinchinat, S.; Schwarzentruber, F., Games with communication: from belief to preference change, (Proceedings of the 18th International Conference Principles and Practice of Multi-Agent Systems. Proceedings of the 18th International Conference Principles and Practice of Multi-Agent Systems, PRIMA’15 (2015)), 670-677
[61] van Benthem, J.; Liu, F., Dynamic logic of preference upgrade, J. Appl. Non-Class. Log., 17, 2, 157-182 (2007) · Zbl 1186.03034
[62] Roy, O., A dynamic-epistemic hybrid logic for intentions and information changes in strategic games, Synthese, 171, 2, 291 (2009) · Zbl 1198.03018
[63] van Benthem, J.; Pacuit, E.; Roy, O., Toward a theory of play: a logical perspective on games and interaction, Games, 2, 1, 52-86 (2011) · Zbl 1311.91048
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.