Algorithms for lattice games

DOI10.1007/S00182-012-0319-9MaRDI QIDQ378325zbMATH OpenOpenAlexFDO

Authors Alan Guo, Ezra Miller

Publication date 11 November 2013

Published in International Journal of Game Theory (Search for Journal in Brave)

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

zbMATH Keywords

rational pointscombinatorial gameconvex polyhedronaffine semigrouplattice gameshort generating functionmisère quotient

Mathematics Subject Classification ID

Combinatorial games (91A46)

Abstract: This paper provides effective methods for the polyhedral formulation of impartial finite combinatorial games as lattice games. Given a rational strategy for a lattice game, a polynomial time algorithm is presented to decide (i) whether a given position is a winning position, and to find a move to a winning position, if not; and (ii) to decide whether two given positions are congruent, in the sense of mis`ere quotient theory. The methods are based on the theory of short rational generating functions.

Recommendations

• Lattice point methods for combinatorial games
• Lattice games without rational strategies
• Advances in finding ideal play on poset games
• Lattices of games
• Advances in finding ideal play on poset games

Cites work

• scientific article; zbMATH DE number 6490915 (Why is no real title available?)
• scientific article; zbMATH DE number 3124339 (Why is no real title available?)
• scientific article; zbMATH DE number 2190625 (Why is no real title available?)
• scientific article; zbMATH DE number 2214426 (Why is no real title available?)
• Lattice games without rational strategies
• Lattice point methods for combinatorial games
• Misère quotients for impartial games
• Short rational generating functions for lattice point problems
• The complexity of generating functions for integer points in polyhedra and beyond

Cited in

(12)

• The lex game and some applications
• A lattice-theoretic approach to a class of dynamic games
• On lattices from combinatorial game theory: infinite case
• Subtraction games in more than one dimension
• On lattices from combinatorial game theory modularity and a representation theorem: finite case
• Combinatorics of \textsc{jenga}
• Affine stratifications from finite misère quotients.
• Some games of search on a lattice
• scientific article; zbMATH DE number 5823948 (Why is no real title available?)
• Lattice point methods for combinatorial games
• Lattice games without rational strategies
• The Ungar games

This page was built for publication: Algorithms for lattice games

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