Game values and computational complexity: an analysis via black-white combinatorial games

DOI10.1007/978-3-662-48971-0_58MaRDI QIDQ3459906zbMATH OpenOpenAlexFDO

Authors Daniel Grier, Jochen Messner, Luke Schaeffer, S. Fenner, Thomas Thierauf

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48971-0_58

zbMATH Keywords

computational complexitycombinatorial gamesposet gamesblack-white gamesColGraph Nimnumeric games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Combinatorial games (91A46)

Recommendations

• scientific article; zbMATH DE number 7075886
• PSPACE-Hardness of some combinatorial games
• Pomax games -- a family of integer-valued partizan games played on posets
• The complexity of poset games
• On the computational complexities of various geography variants

Cited in

(4)

• The computational complexity of forced capture Hnefatafl
• On the algorithmic complexity of the Mastermind game with black-peg results
• \textsf{PSPACE}-complete two-color planar placement games
• ON THE COMPLEXITY OF COMPUTING VALUES OF RESTRICTED GAMES

This page was built for publication: Game values and computational complexity: an analysis via black-white combinatorial games

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