scientific article; zbMATH DE number 16390
Annihilation Gamescomputational complexityGames with DrawsGeneralized Sprague-Grundy FunctionsNim-Like Gamessurvey of combinatorial gamesTuring machine
Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) 2-person games (91A05) Games involving graphs (91A43) Combinatorial games (91A46)
[For the entire collection see Zbl 0721.00028.] In this very readable paper, the author, a noted expert in combinatorial games, provides a useful survey of combinatorial games and their computational complexity; e.g., Nim-Like Games, Games with Draws, Generalized Sprague-Grundy Functions, Annihilation Games, and Provably and Conditionally Intractable Games. Basic notions of computational complexity in terms of deterministic and non-deterministic Turing machine computations are also presented in addition to the author's survey of combinatorial games, and can provide the basis for further inquiry by a reader relatively unfamiliar with this material. What the reviewer found to be rather interesting to game-theorists in general is the author's graph-theoretic proof by reduction ad absurdum of the Zermelo-von Neumann theorem for 2-person, deterministic, perfect information games whose game-graph may be infinite.
- Recent results and questions in combinatorial game complexities
- scientific article; zbMATH DE number 1834637
- Playing games with algorithms: algorithmic combinatorial game theory
- scientific article; zbMATH DE number 7075886
- Games of no chance 3. Papers from the workshop on combinatorial game theory, Banff, Canada, June 2005
- The complexity of short two-person games
- Recent results and questions in combinatorial game complexities
- The computational complexity of Angry Birds
- Complexity of question/answer games
- Topological games at Princeton, a mathematical memoir
- The complexity of speedrunning video games
- Games, puzzles, and computation
- Domino Games and Complexity
- Playing games with algorithms: algorithmic combinatorial game theory
- scientific article; zbMATH DE number 1834637 (Why is no real title available?)
- Automata, Languages and Programming
- A note about games-composition dimension
- The complexity of pursuit on a graph
- Games with winning conditions of high Borel complexity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3973044)
