Top

Published in:

2019 | OriginalPaper | Chapter

Game Equivalence and Bisimulation for Game Description Language

Authors : Guifei Jiang, Laurent Perrussel, Dongmo Zhang, Heng Zhang, Yuzhi Zhang

Published in: PRICAI 2019: Trends in Artificial Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper investigates the equivalence between games represented by state transition models and its applications. We first define a notion of bisimulation equivalence between state transition models and prove that it can be logically characterized by Game Description Language (GDL). Then we introduce a concept of quotient state transition model. As the minimum equivalent of the original model, it allows us to improve the efficiency of model checking for GDL. Finally, we demonstrate with real games that bisimulation equivalence can be generalized to characterize more general game equivalence.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising

next chapter Characterizing the Expressivity of Game Description Languages

Alur, R., Henzinger, T.A., Kupferman, O., Vardi, M.Y.: Alternating refinement relations. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 163–178. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055622CrossRef

Baier, C., Katoen, J.P., Larsen, K.G.: Principles of Model Checking. MIT Press, Cambridge (2008)MATH

van Benthem, J.: Modal Correspondence Theory. Ph.D. thesis, University of Amsterdam (1977)

van Benthem, J.: Correspondence theory. In: Gabbay, D., Guenthner, F. (eds.) Handbook of Philosophical Logic. SYLI, pp. 167–247. Springer, Dordrecht (1984). https://doi.org/10.1007/978-94-009-6259-0_4CrossRef

van Benthem, J.: Logic in Games. MIT Press, Cambridge (2014)MATHCrossRef

van Benthem, J., Bezhanishvili, N., Enqvist, S.: A new game equivalence and its modal logic. In: Proceedings Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017), pp. 57–74 (2017)

Blackburn, P., van Benthem, J., Wolter, F.: Handbook of Modal Logic, vol. 3. Elsevier, Amsterdam (2006)MATH

Elmes, S., Reny, P.J.: On the strategic equivalence of extensive form games. J. Econ. Theor. 62(1), 1–23 (1994)MathSciNetMATHCrossRef

Genesereth, M., Love, N., Pell, B.: General game playing: overview of the AAAI competition. AI Mag. 26(2), 62–72 (2005)

10.

Goranko, V.: The basic algebra of game equivalences. Studia Logica 75(2), 221–238 (2003)MathSciNetMATHCrossRef

11.

Grädel, E., Otto, M.: The freedoms of (guarded) bisimulation. In: Baltag, A., Smets, S. (eds.) Johan van Benthem on Logic and Information Dynamics. OCL, vol. 5, pp. 3–31. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06025-5_1CrossRef

12.

Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. J. ACM (JACM) 32(1), 137–161 (1985)MathSciNetMATHCrossRef

13.

Jiang, G., Zhang, D., Perrussel, L., Zhang, H.: Epistemic GDL: a logic for representing and reasoning about imperfect information games. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pp. 1138–1144 (2016)

14.

Love, N., Hinrichs, T., Haley, D., Schkufza, E., Genesereth, M.: General game playing: game description language specification. Stanford Logic Group Computer Science Department Stanford University (2006). http://logic.stanford.edu/reports/LG-2006-01.pdf

15.

Michon, J.A.: The game of jam: an isomorph of tic-tac-toe. Am. J. Psychol. 80(1), 137–140 (1967). http://www.jstor.org/stable/1420555CrossRef

16.

Park, D.: Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) GI-TCS 1981. LNCS, vol. 104, pp. 167–183. Springer, Heidelberg (1981). https://doi.org/10.1007/BFb0017309CrossRef

17.

Pauly, M.: Logic for Social Software. Ph.D. thesis. University of Amsterdam (2001). ILLC Dissertation Series 2001–10

18.

Pell, B.: Strategy generation and evaluation for meta-game playing. Ph.D. thesis. University of Cambridge (1993)

19.

Reiter, R.: The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. Artif. Intell. Math. Theory Comput.: Pap. Honor. John McCarthy 27, 359–380 (1991)MathSciNetMATHCrossRef

20.

Ruan, J., van Der Hoek, W., Wooldridge, M.: Verification of games in the game description language. J. Log. Comput. 19(6), 1127–1156 (2009)MathSciNetMATHCrossRef

21.

Thielscher, M.: A general game description language for incomplete information games. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 994–999 (2010)

22.

Thompson, F.: Equivalence of games in extensive form. Class. Game Theory, 36 (1997)

23.

Zhang, D., Thielscher, M.: A logic for reasoning about game strategies. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), pp. 1671–1677 (2015)

24.

Zhang, D., Thielscher, M.: Representing and reasoning about game strategies. J. Philos. Log. 44(2), 203–236 (2015)MathSciNetMATHCrossRef

25.

Zhang, H., Liu, D., Li, W.: Space-consistent game equivalence detection in general game playing. In: Cazenave, T., Winands, M.H.M., Edelkamp, S., Schiffel, S., Thielscher, M., Togelius, J. (eds.) CGW/GIGA -2015. CCIS, vol. 614, pp. 165–177. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39402-2_12CrossRef

Title: Game Equivalence and Bisimulation for Game Description Language
Authors: Guifei Jiang
Laurent Perrussel
Dongmo Zhang
Heng Zhang
Yuzhi Zhang
Publisher: Springer International Publishing
Book: PRICAI 2019: Trends in Artificial Intelligence
Print ISBN: 978-3-030-29907-1

Electronic ISBN: 978-3-030-29908-8

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-29908-8_46

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner