PSPACE-Hardness of some combinatorial games (Q1090274)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | PSPACE-Hardness of some combinatorial games |
scientific article |
Statements
PSPACE-Hardness of some combinatorial games (English)
0 references
1987
0 references
PSPACE-hardness of four families of win-lose-draw games played on a digraph with blocking, capture, or annihilation rules is proved. Special cases of three of the families are shown to be PSPACE-complete. Further, the PSPACE-completeness of six families of win-lose games in which two players mark or remove nodes of digraphs according to given rules is proved. The first two families contain partizan games, the last eight impartial games. All the games have been defined previously in the literature or are slight variations of such games.
0 references
games on digraphs
0 references
combinatorial games
0 references
PSPACE-hardness
0 references
blocking, capture
0 references
annihilation
0 references
PSPACE-completeness
0 references
partizan games
0 references
impartial games
0 references