Lattice point methods for combinatorial games

DOI10.1016/J.AAM.2010.10.004zbMATH Open1213.91045arXiv0908.3473OpenAlexW2069859193MaRDI QIDQ534200FDOQ534200

Authors: Alan Guo, Ezra Miller 

Publication date: 17 May 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We encode arbitrary finite impartial combinatorial games in terms of lattice points in rational convex polyhedra. Encodings provided by these emph{lattice games} can be made particularly efficient for octal games, which we generalize to emph{squarefree games}. These additionally encompass all heap games in a natural setting, in which 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`ere 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 emph{rational strategy}: a rational generating function for its winning positions. Additionally, we conjecture that every lattice game has an emph{affine stratification}: a partition of its set of winning positions into a finite disjoint union of finitely generated modules for affine semigroups.

Full work available at URL: https://arxiv.org/abs/0908.3473

Recommendations

• Corrigendum to ``Lattice point methods for combinatorial games
• Algorithms for lattice games
• Lattices of games
• scientific article; zbMATH DE number 4059172
• The lattice structure of \(n\)-player games
• On lattices from combinatorial game theory: infinite case
• scientific article; zbMATH DE number 279293
• scientific article; zbMATH DE number 1944386
• A lattice-theoretic approach to a class of dynamic games
• Hybrid Systems: Computation and Control

zbMATH Keywords

generating functioncombinatorial gameconvex polyhedronnormal playaffine semigroup[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=mis%EF%BF%BD%EF%BF%BDre+play&go=Go mis��re play]

Mathematics Subject Classification ID

Combinatorial games (91A46)

Cites Work

• Lectures on Polytopes
• Combinatorial Commutative Algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Misère quotients for impartial games
• Title not available (Why is that?)
• Algorithms for lattice games
• Short rational generating functions for lattice point problems
• Title not available (Why is that?)
• Decompositions of commutative monoid congruences and binomial ideals.

Cited In (13)

• How to play MetaSquares
• Combinatorial games with a pass: a dynamical systems approach
• Subtraction games in more than one dimension
• On lattices from combinatorial game theory modularity and a representation theorem: finite case
• Combinatorics of \textsc{jenga}
• Sprague-Grundy values and complexity for LCTR
• Affine stratifications from finite misère quotients.
• Some games of search on a lattice
• \textsc{polish} -- Let us play the cleaning game
• Decompositions of cellular binomial ideals
• Algorithms for lattice games
• Lattice games without rational strategies
• Title not available (Why is that?)

Uses Software

• Binomials.m2

This page was built for publication: Lattice point methods for combinatorial games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534200)