Generalized Geography is a combinatorial game played on a directed graph. Players take turns moving a token from vertex to vertex, deleting a vertex after moving the token away from it. A player unable to move loses. It is well known that the computational complexity of determining which player should win from a given position of Generalized Geography is PSPACE-complete. We introduce several rule variants to Generalized Geography, and we explore the computational complexity of determining the winner of positions of many resulting games. Among our results is a proof that determining the winner of a game known in the literature as Undirected Partizan Geography is PSPACE-complete, even when restricted to being played on a bipartite graph.
翻译：通用地理是一个在定向图形上播放的组合游戏。 玩家轮流将一个牌子从顶点移动到顶点, 在将牌子移走后删除一个顶点。 一个不能移动的玩家会输掉。 众所周知, 确定哪个玩家应该从通用地理的某个位置赢得的计算复杂性是完成 PSPACE 的。 我们引入了几个通用地理规则变量, 我们探索了确定许多由此产生的游戏位置的赢家的计算复杂性。 我们的结果之一是证明, 确定文献中称为非定向Partizan 地理的游戏的赢家是完成 PSPACE 的, 即使仅限于在双向图表上播放 。
相关内容
微信扫码咨询专知VIP会员