Combinatorial game theory provides results for the class of two-player, deterministic games with perfect information. With the aim of generalizing this theory to the class of non-perfect information games in mind, we introduce and analyze three variants of the game of Nim. In these variants, the opponent only receives partial information on the move executed by the opponent. We model the variants as games in extensive form and compute Nash equilibria for different starting configurations. For one variant, this provides a full characterization of the game. For the other variants, we prove some partial and structural results, but a full characterization remains elusive.
Albert, M.H., Nowakowski, R.J. & Wolfe, D. (2019). Lessons in Play (2nd ed.). CRC Press.
2.
Berlekamp, E.R., Conway, J.H. & Guy, R.K. (1982). Winning Ways for Your Mathematical Plays (2nd ed. 2001–2004). Academic Press.
3.
Bowling, M., Burch, N., Johanson, M. & Tammelin, O. (2017). Heads-up limit hold’em poker is solved. Communications of the ACM, 60(11), 81–88. doi:10.1145/3131284.
4.
Ciancarini, P. & Favini, G.P. (2007). Representing Kriegspiel states with metapositions. IJCAI, 07, 2450–2455.
5.
Ciancarini, P. & Favini, G.P. (2010). Monte Carlo tree search in Kriegspiel. Artificial Intelligence, 174, 670–684. doi:10.1016/j.artint.2010.04.017.
6.
Cincotti, A. & Iida, H. (2007). The Game of Synchronized Cutcake. 2007 IEEE Symposium on Computational Intelligence and Games.
7.
Ferguson, T.S. (2014). Game Theory. Los Angeles: Mathematics Department, University of California.
8.
Hayward, R.B. & Toft, B. (2019). Hex: The Full Story. CRC Press.
9.
Huggan, M. & Nowakowski, R.J. (2018). Simultaneous combinatorial game theory. Arxiv preprint.
10.
Kuhn, H.W. (1953). Extensive games and the problem of information. In Contributions to the Theory of Games II. Annals of Mathematics Studies (Vol. 28, pp. 193–216). Princeton University Press.
11.
Moravčík, M., Schmid, M., Burch, N., et al. (2017). DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337), 508–513. doi:10.1126/science.aam6960.
12.
Nisan, N., Roughgarden, T., Tardos, É. & Vazirani, V.V. (2007). Algorithmic Game Theory. New York, New York: Cambridge University Press.
13.
Siegel, A.N. (2013). Combinatorial Game Theory. American Mathematical Society.
14.
Silver, D., Schrittwieser, J., Simonyan, K., et al. (2017). Mastering the game of Go without human knowledge. Nature, 550, 354–359. doi:10.1038/nature24270.
15.
Uiterwijk, J.W.H.M. (2016). 11 × 11 domineering is solved: The first player wins. In Computers and Games. CG 2016. Lecture Notes in Computer Science (Vol. 10068, pp. 129–136). Springer.
16.
Von Stengel, B. (2002). Computing equilibria for two-person games. In Handbook of Game Theory with Economic Applications (Vol. 3, pp. 1723–1759). Amsterdam: Elsevier.
