摘要 Abstract
我们引入了成就位置博弈这一概念,这是一种涵盖制作者-制作者和制作者-破坏者约定的位置博弈惯例。我们考虑在同一顶点集上的两个超图,一个红色超图和一个蓝色超图。两名玩家,左玩家和右玩家,轮流选择之前未被选中的顶点。当某位玩家首先填满与其颜色对应的边时(左玩家为蓝色边,右玩家为红色边),该玩家获胜(也可能出现平局)。我们研究了此类博弈的一般性质。特别地,我们证明了许多对制作者-制作者博弈成立的原则可以推广到成就位置博弈中。此外,我们研究了在所有蓝色边大小最多为 $p$ 且所有红色边大小最多为 $q$ 的情况下,决定左玩家作为先手是否有必胜策略的算法复杂性问题。当 $p,q \leq 2$ 时,该问题属于P类;但当 $p \geq 3$ 且 $q=2$ 时,问题是NP难的;当 $p=2$ 且 $q \geq 3$ 时,问题是coNP完全的;当 $p,q \geq 3$ 时,问题是PSPACE完全的。上述最后的结果的一个推论是,在制作者-制作者约定下,决定在一个等级为4的超图上经过一轮非最优玩之后,第一个玩家是否有必胜策略的问题也是PSPACE完全的。
We introduce achievement positional games, a convention for positional games which encompasses the Maker-Maker and Maker-Breaker conventions. We consider two hypergraphs, one red and one blue, on the same vertex set. Two players, Left and Right, take turns picking a previously unpicked vertex. Whoever first fills an edge of their color, blue for Left or red for Right, wins the game (draws are possible). We establish general properties of such games. In particular, we show that a lot of principles which hold for Maker-Maker games generalize to achievement positional games. We also study the algorithmic complexity of deciding whether Left has a winning strategy as first player when all blue edges have size at mot $p$ and all red edges have size at most $q$. This problem is in P for $p,q \leq 2$, but it is NP-hard for $p \geq 3$ and $q=2$, coNP-complete for $p=2$ and $q \geq 3$, and PSPACE-complete for $p,q \geq 3$. A consequence of this last result is that, in the Maker-Maker convention, deciding whether the first player has a winning strategy on a hypergraph of rank 4 after one round of (non-optimal) play is PSPACE-complete.