Algorithms for lattice games (Q378325)

In a previous paper, the authors have reformulated the theory of impartial combinatorial games using the language of combinatorial commutative algebra and convex rational polyhedral geometry. From the authors' abstract: This paper provides effective methods for the polyhedral formulation of impartial finite combinatorial games as lattice games. 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. The methods are based on the theory of short rational generating functions.