论文标题
解决多项式时间中排名3的破坏者游戏的一般情况
Solving the General Case of Rank-3 Maker-Breaker Games in Polynomial Time
论文作者
论文摘要
在超图上进行了一款排名3的破坏者游戏，其中最多3个顶点都有所有超重配件。游戏的两个玩家（称为Maker and Breaker）交替移动。在他轮流的情况下，制造商选择了一个顶点以从所有Hyperedges中撤回，而转弯的Breaker则选择一个顶点，并删除所有包含该顶点的Hyperedges。当他回合结束时，制造商赢了，完全覆盖了一些超奇，即，撤回了该超越的最后一个顶点。当她转弯结束时，Breaker获胜，所有Hyperedges都已删除。 解决制造商的游戏是选择最佳动作或等效地，决定哪个玩家在配置中具有获胜策略的计算问题。在多项式之前已经证明了解决两个排名3游戏的堕落案例的复杂性。在本文中，我们表明，在多项式时间内，排名3的制造商游戏的一般情况也可以解决。
A rank-3 Maker-Breaker game is played on a hypergraph in which all hyperedges are sets of at most 3 vertices. The two players of the game, called Maker and Breaker, move alternately. On his turn, maker chooses a vertex to be withdrawn from all hyperedges, while Breaker on her turn chooses a vertex and delete all the hyperedges containing that vertex. Maker wins when by the end of his turn some hyperedge is completely covered, i.e. the last remaining vertex of that hyperedge is withdrawn. Breaker wins when by the end of her turn, all hyperedges have been deleted. Solving a Maker-Breaker game is the computational problem of choosing an optimal move, or equivalently, deciding which player has a winning strategy in a configuration. The complexity of solving two degenerate cases of rank-3 games has been proven before to be polynomial. In this paper, we show that the general case of rank-3 Maker-Breaker games is also solvable in polynomial time.
