Game Development Reference
In-Depth Information
parity-win-dominion ( G ) can be characterised by the recurrence:
n 2 / 3
,d )+ O ( n d/ 3+ O (1) ) ,
T ( n, d )
T ( n, d
1) + T ( n
T ( n, 1) = O ( n ) ,
and hence also by the recurrence:
T ( n, d ) ≤ n 1 / 3
· T ( n, d − 1) + O ( n d/ 3+ O (1) ) ,
T ( n, 1) = O ( n ) .
Prove that T ( n, d )= O ( n d/ 3+ O (1) ).
Theorem 3.10 (Schewe [2007]) The winning sets and positional win-
ning strategies of both players in parity games can be computed in time
O ( n d/ 3+ O (1) ) .
3.4 Related work
This survey of algorithms for solving parity games is not exhaustive. In
particular, an important class of local search algorithms has not been
included here. This class includes strategy improvement algorithms ,
inspired by policy iteration algorithms for Markov decision processes
(Howard [1960], Puterman [2005]) and stochastic games (Filar and Vrieze
[1997]), and various pivoting algorithms adapted from the theory of the
linear complementarity problem (Cottle et al. [2009]).
The initial impulse for exploring applications of such local search algorithms
to parity games has been the observation by Puri [1995] and Stirling [1995]
that there is a polynomial time reduction from parity games to mean-
payoff games and to simple stochastic games . The reduction has also
been exploited by Jurdzinski [1998] to show that the problems of deciding
the winner in parity, mean-payoff, discounted, and simple stochastic games
are in UP and in co-UP.
Voge and Jurdzinski [2000] have been inspired by the reduction from parity
games to discounted games to devise a discrete strategy improvement
algorithm for parity games. This algorithm has been conjectured to have
worst-case polynomial running time, but in a recent breakthrough Friedmann
[2009] has dashed those hopes by exhibiting a family of parity games with
O ( n ) vertices on which the algorithm performs Ω(2 n ) iterations. Intriguingly,
working with parity games and the discrete strategy improvement algorithm
has enabled Friedmann to devise examples of mean-payoff, discounted, and
simple stochastic games that make the strategy improvement algorithm
Search Nedrilad ::




Custom Search