Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

zbMath1192.91051arXivcs/0106019MaRDI QIDQ3574125

Robert A. Hearn, Erik D. Demaine

Publication date: 9 July 2010

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02) Combinatorial games (91A46)

Related Items (24)

Threes!, Fives, 1024!, and 2048 are hard ⋮ The complexity of Snake and undirected NCL variants ⋮ Computational Hardness of Multidimensional Subtraction Games ⋮ On the complexity of connection games ⋮ A simple proof that the \((n^{2} - 1)\)-puzzle is hard ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ The Computational Complexity of Portal and Other 3D Video Games ⋮ Impartial games emulating one-dimensional cellular automata and undecidability ⋮ Havannah and TwixT are PSPACE-complete ⋮ From heaps of matches to the limits of computability ⋮ Complexity limitations on one-turn quantum refereed games ⋮ Token Swapping on Trees ⋮ Particle computation: complexity, algorithms, and logic ⋮ Puzzle and dragons is hard ⋮ Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Permutation reconstruction from differences ⋮ Gaming is a hard job, but someone has to do it! ⋮ \textsf{PSPACE}-complete two-color planar placement games ⋮ An algorithmic analysis of the Honey-Bee game ⋮ Hashiwokakero is NP-complete ⋮ Two-player tower of Hanoi ⋮ Lemmings is PSPACE-complete ⋮ Strings-and-Coins and Nimstring are PSPACE-complete

Uses Software

• ZRAM

This page was built for publication: Playing Games with Algorithms: Algorithmic Combinatorial Game Theory