Show simple item record

dc.contributor.author Guo, A
dc.contributor.author Miller, E
dc.date.accessioned 2011-05-12T01:09:41Z
dc.date.issued 2011-01-01
dc.identifier.citation Advances in Applied Mathematics, 2011, 46 (1-4), pp. 363 - 378
dc.identifier.issn 0196-8858
dc.identifier.uri http://hdl.handle.net/10161/3749
dc.description Honors thesis en_US
dc.description.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. © 2010 Elsevier Inc. All rights reserved.
dc.format.extent 363 - 378
dc.language.iso en_US en_US
dc.relation.ispartof Advances in Applied Mathematics
dc.relation.isversionof 10.1016/j.aam.2010.10.004
dc.title Lattice point methods for combinatorial games
dc.type Journal Article
dc.department Mathematics en_US
pubs.issue 1-4
pubs.organisational-group /Duke
pubs.organisational-group /Duke/Trinity College of Arts & Sciences
pubs.organisational-group /Duke/Trinity College of Arts & Sciences/Mathematics
pubs.organisational-group /Duke/Trinity College of Arts & Sciences/Statistical Science
pubs.publication-status Published
pubs.volume 46
dc.identifier.eissn 1090-2074

Files in this item

This item appears in the following Collection(s)

Show simple item record