International Journal of Game Theory Социальные науки (прочее)
Digraph placement games
Аннотация
This paper considers a natural ruleset for playing a partisan combinatorial game on a directed graph, which we call Digraph placement . Given a digraph G with a not necessarily proper 2-coloring of V ( G ), the Digraph placement game played on G by the players Left and Right, who play alternately, is defined as follows. On her turn, Left chooses a blue vertex which is deleted along with all of its out-neighbours. On his turn Right chooses a red vertex, which is deleted along with all of its out-neighbours. A player loses if on their turn they cannot move. We show constructively that Digraph placement is a universal partisan ruleset; for all partisan combinatorial games X there exists a Digraph placement game, G , such that $$G = X$$ . Digraph placement and many other games including Nim , Poset Games , Col , Node Kayles , Domineering , and Arc Kayles are instances of a class of placement games that we call conflict placement games. We prove that X is a conflict placement game if and only if it has the same literal form as a Digraph placement game. A corollary of this is that deciding the winner of a Digraph placement game is PSPACE-hard. Next, for a game value X we prove bounds on the order of a smallest Digraph placement game G such that $$G = X$$ .