Recent results and questions in combinatorial game complexities
type: Item
instance of: scholarly article
title: Recent results and questions in combinatorial game complexities
zbMATH Open document ID: 0977.91011
DOI: 10.1016/S0304-3975(00)00062-1
published in: Theoretical Computer Science
publication date: 2000-10-26T00:00:00Z
review text: This paper is a survey article. First, a polynomial strategy for impartial acyclic games is presented. Here, the Beat Dong game, the game involving stars and buttoms, the octal games, the poset games and the Wythoff game are discussed. In the subsequent sections, the author treats cyclic games, annihilation games and partizan games. In the discussion upon partizan games the use of the simplicity theorem is mentioned.
Mathematics Subject Classification ID: 91A46
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 91-02
zbMATH DE Number: 1521892
zbMATH Keywords: combinatorial games
zbMATH Keywords: complexity
zbMATH Keywords: efficiency
zbMATH Keywords: tractability
author: Aviezri S. Fraenkel
reviewed by: K. Chandrasekhara Rao
MaRDI profile type: Publication
cites work: Some combinatorial game problems require Ω( n k ) time
cites work: Q3944542
cites work: Q4299345
cites work: Nonhomogeneous spectra of numbers
cites work: Q4099541
cites work: All Games Bright and Beautiful
cites work: A Gamut of Game Theories
cites work: Loopy Games
cites work: Q5823285
cites work: A Combinatorial Problem Which Is Complete in Polynomial Space
cites work: Misère annihilation games
cites work: Q4770810
cites work: Systems of Numeration
cites work: Heap games, numeration systems and sequences
cites work: PSPACE-Hardness of some combinatorial games
cites work: Computing a perfect strategy for nxn chess requires time exponential in n
cites work: Epidemiography. II: Games with a dozing yet winning player
cites work: Q4099857
cites work: A deletion game on hypergraphs
cites work: Strategy for a class of games with dynamic ties
cites work: Strategies for compounds of partizan games
cites work: Theory of annihilation games
cites work: Complexity of problems in games, graphs and algebraic equations
cites work: Theory of annihilation games. I
cites work: The generalized Sprague-Grundy function and its invariance under certain mappings
cites work: A Curious Nim-Type Game
cites work: Nim-type games
cites work: The complexity of pursuit on a graph
cites work: Q3973046
cites work: Classes of Pebble Games and Complete Problems
cites work: Sums of Zuchswang games
cites work: GO Is Polynomial-Space Hard
cites work: Playing disjunctive sums is polynomial space complete
cites work: Games of no chance. Combinatorial games at MSRI. Workshop, July 11--21, 1994 in Berkeley, CA, USA
cites work: Q3245637
cites work: Gobang is PSPACE-complete
cites work: Hex ist Pspace-vollständig. (Hex is Pspace-complete)
cites work: Constant bounds on the moments of the height of binary search trees
cites work: Q3721817
cites work: N by N Checkers is Exptime Complete
cites work: On the complexity of some two-person perfect-information games
cites work: Algebraic solutions of partizan games with cycles
cites work: Graphs and composite games
cites work: A complete analysis of von Neumann's Hackendot
cites work: Q3123651
cites work: Q5524370
cites work: Q5665234
Wikidata QID: Q126323969
description: scientific article; zbMATH DE number 1521892