Informace o publikaci
Comparison of algorithms for simple stochastic games
| Autoři | |
|---|---|
| Rok publikování | 2022 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Information and Computation |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | https://doi.org/10.1016/J.IC.2022.104885 |
| Popis | Simple stochastic games are turn-based 21-player zero-sum graph games with a reachability objective. The problem is to compute the winning probabilities 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. |