Abstract
This paper provides effective methods for the polyhedral formulation of impartial finite combinatorial games as lattice games (Guo et al. Oberwolfach Rep 22: 23–26, 2009; Guo and Miller, Adv Appl Math 46:363–378, 2010). Given a rational strategy for a lattice game, a polynomial time algorithm is presented to decide (i) whether a given position is a winning position, and to find a move to a winning position, if not; and (ii) to decide whether two given positions are congruent, in the sense of misère quotient theory (Plambeck, Integers, 5:36, 2005; Plambeck and Siegel, J Combin Theory Ser A, 115: 593–622, 2008). The methods are based on the theory of short rational generating functions (Barvinok and Woods, J Am Math Soc, 16: 957–979, 2003).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barvinok A (2006) The complexity of generating functions for integer points in polyhedra and beyond. International Congress of Mathematicians, vol III. European Mathematical Society, Zurich, pp 763–787
Barvinok A, Woods K (2003) Short rational generating functions for lattice point problems. J Am Math Soc 16(4): 957–979 (electronic)
Bouton CL (1901/02) Nim, a game with a complete mathematical theory. Ann Math (2) 3(1–4):35–39
Dawson T (1934) Fairy chess supplement. The problemist: British Chess Problem Society 2(9), 94, problem no. 1603
Fink A (2011) Lattice games without rational strategies. J Comb Theory Ser A 119(2): 450–459
Guo A, Miller E (2010) Lattice point methods for combinatorial games. Adv Appl Math 46: 363–378. doi:10.1016/j.aam.2010.10.004 (arXiv:math.CO/0908.3473; Erratum: preprint, 2011)
Guo A, Miller E, Weimerskirch M (2009) Potential applications of commutative algebra to combinatorial game theory. In: Kommutative Algebra, abstracts from the April 19–25, 2009 workshop, organized by W. Bruns, H. Flenner, and C. Huneke, Oberwolfach Rep 22:23–26
Guy RK, Smith CAB (1956) The G-values of various games. Proc Camb Philos Soc 52: 514–526
Miller E (2010) Affine stratifications from finite misère quotients (preprint, 2010. arXiv:math. CO/1009. 2199v1)
Miller E, Sturmfels B (2005) Combinatorial commutative algebra. Graduate texts in mathematics, vol 227. Springer–Verlag, New York
Plambeck TE (2005) Taming the wild in impartial combinatorial games. Integers 5(1), G5, p 36 (electronic)
Plambeck TE, Siegel AN (2008) Misère quotients for impartial games. J Combin Theory Ser A 115(4): 593–622 (arXiv:math.CO/0609825v5)
Weimerskirch M (2009) An algorithm for computing indistinguishability quotients in misère impartial combinatorial games (preprint)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guo, A., Miller, E. Algorithms for lattice games. Int J Game Theory 42, 777–788 (2013). https://doi.org/10.1007/s00182-012-0319-9
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-012-0319-9