Skip to main content
SpringerLink
Log in

Representing and Reasoning about Game Strategies

  • Published:
Journal of Philosophical Logic Aims and scope Submit manuscript

Abstract

As a contribution to the challenge of building game-playing AI systems, we develop and analyse a formal language for representing and reasoning about strategies. Our logical language builds on the existing general Game Description Language (GDL) and extends it by a standard modality for linear time along with two dual connectives to express preferences when combining strategies. The semantics of the language is provided by a standard state-transition model. As such, problems that require reasoning about games can be solved by the standard methods for reasoning about actions and change. We also endow the language with a specific semantics by which strategy formulas are understood as move recommendations for a player. To illustrate how our formalism supports automated reasoning about strategies, we demonstrate two example methods of implementation: first, we formalise the semantic interpretation of our language in conjunction with game rules and strategy rules in the Situation Calculus; second, we show how the reasoning problem can be solved with Answer Set Programming.

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

Fig. 1

Similar content being viewed by others

Notes

  1. The game can be viewed as a variation of tic-tac-toe or a simplified Gomoku game.

  2. Only ¬ and ∧ are treated as primitives.

  3. While all examples in this paper are based on the CrossDot game, some examples are specifically numbered just for the purpose of cross-referencing.

  4. To avoid too much complexity, we follow [6] not offering any solution to the frame problem here. Game descriptions simply include all necessary frame axioms.

  5. In this case, we might have to give the trivial strategy the lowest priority in the disjunction.

  6. We may understand the concept in the following way. Given an arbitrary state transition model M=(G,v) and a strategy S of player i in M, let \(M^{\prime }\) be another state transition model that is exactly the same as M except for the legality of actions for player i in such a way that the legality relation \(l^{\prime }\) in \(M^{\prime }\) is \(l\cap S\), where l is the legality relation in M. We then view \(M^{\prime }\) as the reduction of M once player i complies with strategy S.

  7. For instance, the description of game rules for Chinese Go is quite similar to the one for Japanese Go but their complexity is significantly different.

References

  1. Alur, R., Henzinger, T.A., Kupferman, O. (2002). Alternating-time temporal logic. Journal of the ACM, 49(5), 672–713.

    Article  Google Scholar 

  2. Brewka, G., Benferhat, S., Berre, D.L. (2004). Qualitative choice logic. Artificial Intelligence, 157(1–2), 203–237.

    Article  Google Scholar 

  3. Chatterjee, K., Henzinger, T.A., Piterman, N. (2010). Strategy logic. Information and Computation, 208(6), 677–693.

    Article  Google Scholar 

  4. Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., Schneider, M.T. (2011). Potassco: The Potsdam answer set solving collection. AI Communications, 24(2), 107–124.

    Google Scholar 

  5. Gelfond, M. (2008). Answer sets. In V. van Harmelen, F. Lifschitz, B. Porter (Eds.), Handbook of knowledge representation (285–31). Elsevier.

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

    Google Scholar 

  7. Goranko, V., & Van Drimmelen, G. (2006). Complete axiomatization and decidability of alternating-time temporal logic. Theoretical Computer Science, 353(1), 93–117.

    Article  Google Scholar 

  8. Haufe, S., & Thielscher, M. (2012). Automated verification of epistemic properties for General Game Playing. In Proceedings of the Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning (pp. 339–349). AAAI Press.

  9. Lifschitz, V. (2002). Answer set programming and plan generation. Artificial Intelligence, 138(1–2), 39–54.

    Article  Google Scholar 

  10. Lorini, E. (2010). A dynamic logic of agency II: deterministic DLA, coalition logic, and game theory. Journal of Logic, Language and Information, 19(3), 327–351.

    Article  Google Scholar 

  11. Mogavero, F., Murano, A., Vardi, M.Y. (2010). Reasoning about strategies. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010 (pp. 133–144).

  12. Pauly, M. (2002). A modal logic for coalitional power in games. Journal of logic and computation, 12(1), 149–166.

    Article  Google Scholar 

  13. Pauly, M., & Parikh, R. (2003). Game logic - an overview. Studia Logica, 75(2), 165–182.

    Article  Google Scholar 

  14. Ramanujam, R., & Simon, S.E. (2008). Dynamic logic on games with structured strategies. In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR’08) (pp. 49–58).

  15. Reiter, R. (1991). The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. In V. Lifschitz (Eds.), Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy (pp. 359–380). Academic Press.

  16. Reiter, R (2001). Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT Press.

  17. Robson, J.M. (1983). The complexity of go. In Proceedings of the 9th IFIP World Computer Congress on Information Processing (pp. 413–417).

  18. Schiffel, S., & Thielscher, M. (2011). Reasoning about general games described in GDL-II. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11) (pp. 846–851). AAAI Press.

  19. Thielscher, M. (2009). Answer set programming for single-player games in general game playing. In Proceedings of the International Conference on Logic Programming (ICLP) (pp. 327–341). Springer.

  20. Thielscher, M. (2011). General game playing in AI research and education. In Proceedings of the German Conference on Artificial Intelligence (KI) (pp. 26–37). Springer.

  21. van Benthem, J. (2001). Games in dynamic-epistemic logic. Bulletin of Economic Research, 53(4), 219–48.

    Article  Google Scholar 

  22. van Benthem, J. (2008). In praise of strategies. In J. V. Eijck, R. Verbrugge (Eds.), Games, Actions, and Social Software, ILLC scientific publications. Institute for Logic, Language and Computation (ILLC). University of Amsterdam.

  23. van Benthem, J. (2013). Reasoning about strategies. In Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky (pp. 336-347). Springer.

  24. van der Hoek, W., Jamroga, W., Wooldridge, M. (2005). A logic for strategic reasoning. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS-05) (pp. 157–164). ACM.

  25. Walther, D., van der Hoek, W., Wooldridge, M. (2007). Alternating-time temporal logic with explicit strategies. In Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge (pp. 269–278).

Download references

Acknowledgments

The first author was partially supported by the Australian Research Council through project DP0988750 and National Natural Science Foundation of China through projects 61003203 and 61262029. The second author was the recipient of an ARC Future Fellowship (project number FT 0991348). He is also affiliated with the University of Western Sydney. We thank the anonymous reviewers for their constructive comments and suggestions. We also thank Guifei Jiang for her valuable input.

Author information

Authors and Affiliations

  1. The University of Western Sydney, New South Wales, Australia

    Dongmo Zhang

  2. The University of New South Wales, New South Wales, Australia

    Michael Thielscher

Authors
  1. Dongmo Zhang
    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 Dongmo Zhang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, D., Thielscher, M. Representing and Reasoning about Game Strategies. J Philos Logic 44, 203–236 (2015). https://doi.org/10.1007/s10992-014-9334-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10992-014-9334-6

Keywords

Search

Navigation