PSPACE-Hardness of some combinatorial games (Q1090274): Difference between revisions

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.