论文标题
简单随机游戏算法的比较（完整版）
Comparison of Algorithms for Simple Stochastic Games (Full Version)
论文作者
论文摘要
简单的随机游戏是基于回合的2.5播放器零和图形游戏，具有可及性目标。问题是要计算两名球员的获胜概率以及最佳策略。在本文中，我们将三种已知类别的算法类别（价值迭代，策略迭代和二次编程）进行了比较。此外，我们建议对所有算法进行一些改进，包括基于二次编程的第一种方法，避免将随机游戏转换为停止游戏。我们广泛的实验表明，这些改进可以导致大幅加速。我们在Prism-Games 3.0中实现了所有算法，从而提供了第一个实施二次编程，以求解简单的随机游戏。
Simple stochastic games are turn-based 2.5-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms -- value iteration, strategy iteration and quadratic programming -- both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.
