Lattice point methods for combinatorial games

Abstract

We encode arbitrary finite impartial combinatorial games in terms oflattice points in rational convex polyhedra. Encodings provided by theselatticegamescan be made particularly efficient for octal games, which we generalize tosquarefree games. These encompass all heap games in a natural setting where theSprague–Grundy theorem for normal play manifests itself geometrically. We providepolynomial time algorithms for computing strategies for lattice games provided thatthey have a certain algebraic structure, called anaffine stratification.