Playing games with algorithms: algorithmic combinatorial game theory
From MaRDI portal
Abstract: Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in Combinatorial Game Theory, which analyzes ideal play in perfect-information games, and Constraint Logic, which provides a framework for showing hardness. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.
Recommendations
Cited in
(42)- Games with combinatorial constraints
- Threes!, Fives, 1024!, and 2048 are hard
- The complexity of Snake and undirected NCL variants
- A simple proof that the \((n^{2} - 1)\)-puzzle is hard
- Two-player tower of Hanoi
- Complexity, appeal and challenges of combinatorial games
- \textsf{PSPACE}-complete two-color planar placement games
- Towards an algorithmic guide to Spiral Galaxies
- Lemmings is PSPACE-complete
- Solving games dependence of applicable solving procedures
- Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
- An algorithmic analysis of a combinatorial game
- \textsc{Havannah} and \textsc{TwixT} are PSPACE-complete
- Sequentially swapping colored tokens on graphs
- scientific article; zbMATH DE number 5823948 (Why is no real title available?)
- On the complexity of connection games
- The computational complexity of Portal and other 3D video games
- Strings-and-coins and Nimstring are PSPACE-complete
- Games, puzzles, and computation
- scientific article; zbMATH DE number 5145315 (Why is no real title available?)
- Playing Games with Approximation Algorithms
- Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp
- Algorithmic Game Theory: A Snapshot
- Impartial games emulating one-dimensional cellular automata and undecidability
- From heaps of matches to the limits of computability
- scientific article; zbMATH DE number 16390 (Why is no real title available?)
- scientific article; zbMATH DE number 1754580 (Why is no real title available?)
- Sequentially swapping colored tokens on graphs
- Permutation reconstruction from differences
- scientific article; zbMATH DE number 1834637 (Why is no real title available?)
- Gaming is a hard job, but someone has to do it!
- Computational Hardness of Multidimensional Subtraction Games
- Complexity limitations on one-turn quantum refereed games
- Token Swapping on Trees
- Particle computation: complexity, algorithms, and logic
- Puzzle and dragons is hard
- Quantified Boolean Solving for Achievement Games
- The combinatorial game \textsc{Nofil} played on Steiner triple systems
- An algorithmic analysis of the Honey-Bee game
- A general upper bound for the runtime of a coevolutionary algorithm on impartial combinatorial games
- Playing snake on a graph
- Hashiwokakero is NP-complete
This page was built for publication: Playing games with algorithms: algorithmic combinatorial game theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3574125)
