Lattice point methods for combinatorial games

Loading...
Thumbnail Image

Date

2011

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

390
views
612
downloads

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.

Department

Description

Provenance

Subjects

Citation

Citation

Guo, Alan (2011). Lattice point methods for combinatorial games. Honors thesis, Duke University. Retrieved from https://hdl.handle.net/10161/3749.


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.