Name
Abstract | ||
|---|---|---|
We encode arbitrary finite impartial combinatorial games in terms of lattice points in rational convex polyhedra. Encodings provided by these lattice games can be made particularly efficient for octal games, which we generalize to squarefree games. These encompass all heap games in a natural setting where the Sprague-Grundy theorem for normal play manifests itself geometrically. We provide an algorithm to compute normal play strategies.The setting of lattice games naturally allows for misère play, where 0 is declared a losing position. Lattice games also allow situations where larger finite sets of positions are declared losing. Generating functions for sets of winning positions provide data structures for strategies of lattice games. We conjecture that every lattice game has a rational strategy: a rational generating function for its winning positions. Additionally, we conjecture that every lattice game has an affine stratification: a partition of its set of winning positions into a finite disjoint union of finitely generated modules for affine semigroups. This conjecture is true for normal-play squarefree games and every lattice game with finite misère quotient. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.aam.2010.10.004 | Advances in Applied Mathematics |
Keywords | Field | DocType |
. combinatorial game,lattice game,misere play,affine semigroup,generating function. 1,normal play strategy,finite misere quotient,lattice point method,arbitrary finite impartial combinatorial,combinatorial game,larger finite set,finite disjoint union,heap game,convex polyhedron,lattice point,normal play,lattice points,combinatorial games,stratification,generating function,primary,data structure | Combinatorial game theory,Discrete mathematics,Combinatorics,Finite set,Square-free integer,Mathematical analysis,Convex polytope,Lattice (group),Rational function,Disjoint union,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
46 | 1 | 0196-8858 |
Citations | PageRank | References |
4 | 0.76 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan Guo | 1 | 62 | 7.96 |
| Ezra Miller | 2 | 16 | 3.69 |