PSPACE-Hardness of some combinatorial games (Q1090274): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0097-3165(87)90074-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2077313418 / rank | |||
Normal rank |
Revision as of 01:55, 20 March 2024
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