2020/09/23 by Jan Křetínský, Emanuel Ramneantu, Alexander Slivinskiy +1
Computer Science · #cs.GT #cs.DS
paper · pdf · doi:10.4204/eptcs.326.9
published as EPTCS 326, 2020, pp. 131-148 · In Proceedings GandALF 2020, arXiv:2009.09360
arxiv created 2020/09/23 · arxiv updated 2020/09/24
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.