Algorithms for Stochastic Parity Games

摘要

A stochastic graph game is played by two-players on a game graph with probabilistic transitions. We present a strategy improvement algorithm for stochastic graph games with omega-regular conditions specified as parity objectives. From the strategy improvement algorithm we obtain a randomized sub-exponential time algorithm to solve stochastic parity games.