Algorithms for lattice games

DOI10.1007/S00182-012-0319-9zbMATH Open1278.91031arXiv1105.5413OpenAlexW1977575010MaRDI QIDQ378325FDOQ378325

Authors: Alan Guo, Ezra Miller 

Publication date: 11 November 2013

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

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.

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

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

zbMATH Keywords

rational pointscombinatorial gameconvex polyhedronaffine semigrouplattice gameshort generating functionmisère quotient

Mathematics Subject Classification ID

Combinatorial games (91A46)

Cites Work

• Title not available (Why is that?)
• Misère quotients for impartial games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Short rational generating functions for lattice point problems
• Lattice point methods for combinatorial games
• The complexity of generating functions for integer points in polyhedra and beyond
• Title not available (Why is that?)
• Lattice games without rational strategies

Cited In (12)

• 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
• Title not available (Why is that?)
• Lattice point methods for combinatorial games
• The Ungar games
• Lattice games without rational strategies
• The lex game and some applications

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)