Solving Simple Stochastic Games with Few Random Vertices

Hugo Gimbert, Florian Horn

Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms comp…