Lattice games without rational strategies

DOI10.1016/J.JCTA.2011.10.005MaRDI QIDQ654900zbMATH OpenOpenAlexWikidataFDO

Authors Alex Fink

Publication date 23 December 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

cellular automatacombinatorial gameslattice gamescomputational universality

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Cellular automata (computational aspects) (68Q80) Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46)

Abstract: We show that the lattice games of Guo and Miller support universal computation, disproving their conjecture that all lattice games have rational strategies. We also state an explicit counterexample to that conjecture: a three dimensional lattice game whose set of winning positions does not have a rational generating function.

Recommendations

• Lattices of games
• scientific article; zbMATH DE number 4059172
• scientific article; zbMATH DE number 912638
• The lattice structure of n-player games
• Algorithms for lattice games
• Hybrid Systems: Computation and Control
• On games without approximate equilibria
• scientific article; zbMATH DE number 4055409
• scientific article; zbMATH DE number 1944386
• Game Theory without Decision-Theoretic Paradoxes

Cites work

• scientific article; zbMATH DE number 3124339 (Why is no real title available?)
• Lattice point methods for combinatorial games
• Misère quotients for impartial games
• Short rational generating functions for lattice point problems
• Simple Computation-Universal Cellular Spaces

Cited in

(10)

• The cardinality of the sets involved in lattice games
• A cellular automaton for blocking queen games
• On lattices from combinatorial game theory: infinite case
• Subtraction games in more than one dimension
• Combinatorics of \textsc{jenga}
• Affine stratifications from finite misère quotients.
• Algorithms for lattice games
• Impartial games emulating one-dimensional cellular automata and undecidability
• From heaps of matches to the limits of computability
• The Ungar games

This page was built for publication: Lattice games without rational strategies

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