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

affine semigroupcombinatorial gameconvex polyhedronlattice gamemisère quotientrational pointsshort generating function

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.

Review text

In a previous paper, the authors have reformulated the theory of impartial combinatorial games using the language of combinatorial commutative algebra and convex rational polyhedral geometry. From the authors' 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ère 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)

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

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)