Strategy Iteration using Non-Deterministic Strategies for Solving Parity Games
Strategy Iteration using Non-Deterministic Strategies for Solving Parity Games
复制标题
使用非确定性策略进行策略迭代来解决奇偶博弈
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Michael Luttenberger
中科院分区：
文献类型：
--
作者：
Michael Luttenberger
本文将通过策略迭代来解决奇偶性博弈的想法扩展到非确定性策略：在非确定性策略中，玩家将自己限制在给定节点上的一些可能行动的非空子集中，而不是将自己限制在一个行动中。我们证明了Bjoerklund， Sandberg和Vorobyov的策略改进算法可以很容易地适应更一般的非确定性策略设置。进一步，我们证明了应用“所有有利的开关”启发式会导致在非确定性策略设置中选择“局部最优”的后继策略，从而获得Schewe算法的简单证明。与Bjoerklund等人的算法相反，我们直接针对奇偶性游戏呈现了我们的算法，这让我们能够将其与Jurdzinski和Voege的算法进行比较：我们发现两种算法中使用的估值在一个玩家可以“投降”的奇偶性游戏领域是一致的。因此，我们的算法也可以看作是Jurdzinski和Voege对不确定性策略的推广。最后，使用非确定性策略使我们能够证明改进步骤的数量由上面的O（1.724^n）限定。对于策略改进算法，这个界限以前只知道可以通过使用随机化来实现。
This article extends the idea of solving parity games by strategy iteration to non-deterministic strategies: In a non-deterministic strategy a player restricts himself to some non-empty subset of possible actions at a given node, instead of limiting himself to exactly one action. We show that a strategy-improvement algorithm by by Bjoerklund, Sandberg, and Vorobyov can easily be adapted to the more general setting of non-deterministic strategies. Further, we show that applying the heuristic of "all profitable switches" leads to choosing a "locally optimal" successor strategy in the setting of non-deterministic strategies, thereby obtaining an easy proof of an algorithm by Schewe. In contrast to the algorithm by Bjoerklund et al., we present our algorithm directly for parity games which allows us to compare it to the algorithm by Jurdzinski and Voege: We show that the valuations used in both algorithm coincide on parity game arenas in which one player can "surrender". Thus, our algorithm can also be seen as a generalization of the one by Jurdzinski and Voege to non-deterministic strategies. Finally, using non-deterministic strategies allows us to show that the number of improvement steps is bound from above by O(1.724^n). For strategy-improvement algorithms, this bound was previously only known to be attainable by using randomization.