Algorithms for lattice games

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, <CitationRef CitationID="CR7">2009</CitationRef>; Guo and Miller, Adv Appl Math 46:363–378, <CitationRef CitationID="CR6">2010</CitationRef>). 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, <CitationRef CitationID="CR11">2005</CitationRef>; Plambeck and Siegel, J Combin Theory Ser A, 115: 593–622, <CitationRef CitationID="CR12">2008</CitationRef>). The methods are based on the theory of short rational generating functions (Barvinok and Woods, J Am Math Soc, 16: 957–979, <CitationRef CitationID="CR2">2003</CitationRef>). Copyright Springer-Verlag 2013