Fatal Attractors in Parity Games
Fatal Attractors in Parity Games
复制标题
平价游戏中的致命吸引力
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Nir Piterman
中科院分区：
文献类型：
--
作者：
M. Huth;Jim Huan;Nir Piterman
我们研究了一种新形式的吸引子在平价游戏，并使用它来定义求解器，运行在PTIME和部分，因为他们不完全解决所有的游戏。从技术上讲，对于颜色c，这个新的吸引子决定了参与者c% 2是否可以到达颜色c的一组节点X，同时避免任何颜色小于c的节点。如果参与者c%2可以用这种方式将X中的所有节点吸引回X，那么这样的吸引子是致命的。我们的部分求解器基于致命吸引子检测节点的固定点，并将这些节点正确分类为玩家c%2赢得的节点。实验结果表明，我们的部分求解器完全解决的基准，构建挑战现有的完整的求解器。我们的部分求解器在实践中也有令人鼓舞的运行时间。对于一个部分求解器，我们证明了它的运行时间是在$O（{\mid\！{V}\!\ mid}^3）$，它的输出博弈与吸引子的计算顺序无关，并且它解决了所有的Buchi博弈。
We study a new form of attractor in parity games and use it to define solvers that run in PTIME and are partial in that they do not solve all games completely. Technically, for color c this new attractor determines whether player c% 2 can reach a set of nodes X of color c whilst avoiding any nodes of color less than c. Such an attractor is fatal if player c%2 can attract all nodes in X back to X in this manner. Our partial solvers detect fixed-points of nodes based on fatal attractors and correctly classify such nodes as won by player c%2. Experimental results show that our partial solvers completely solve benchmarks that were constructed to challenge existing full solvers. Our partial solvers also have encouraging run times in practice. For one partial solver we prove that its runtime is in $O({\mid\!{V}\!\mid}^3)$, that its output game is independent of the order in which attractors are computed, and that it solves all Buchi games.