Game Development Reference
In-Depth Information
NP
coNP. A major open problem is to know whether parity games with
perfect information can be solved in polynomial time.
We present an algorithmic solution for parity games using a reduction to
safety games. A variant of this reduction has been presented by Bernet et al.
[2002]. In the worst case, it yields safety games of size exponentially larger
than the parity game. Such a blow-up is not surprising since safety games
can be solved in polynomial time. The reduction gives some insight into the
structure of parity games.
Consider a game graph G =
L, l I , Σ , Δ
and a priority function pr : L
{
defining the parity objective Parity( pr ) that requires the minimal
priority occurring infinitely often to be even. We extend the locations of G
with tuples
0 , 1 ,...,d
}
of counters associated with the odd priorities (we
assume that d is odd). The counters are initialised to 0, and each visit to a
state with odd priority p increments the counter c p . Intuitively, accumulating
visits to an odd priority is potentially bad, except if a smaller even priority
is also eventually visited. Therefore, each visit to a state with even priority
p resets all counters c p with p >p .
Under these rules, if player 1 has a surely-winning strategy in G for the
objective Parity( pr ), then player 1 also has a memoryless surely-winning
strategy, and thus can enforce that each counter c p remains bounded by n p ,
the number of locations with priority p . On the other hand, if Player 1 has
no strategy that maintains all counter c p below n p , then it means that no
matter the strategy of Player 1, there exists a strategy of Player 2 such that
the outcome of the game visits some location with odd priority p at least
twice, without visiting a location of smaller priority. Since we can assume
that Player 1 uses a memoryless strategy, this shows that Player 2 can force
infinitely many visits to an odd priority without visiting a smaller priority,
thus Player 1 cannot win the parity game.
Formally, we define G =
c 1 ,c 3 ,...,c d
L ,l I , Σ , Δ
where
L = L
×
[ n 1 ]
×
[ n 3 ]
×
...
×
[ n d ] where [ n i ] denotes the set
{
0 , 1 ,...,n i
}∪{∞}
,
and n i is the number of locations with priority i in G ;
l I =( l I , 0 , 0 ,..., 0);
Δ =
{
(( 1 ,c ) ,σ, ( 2 , update( c, p )))
|
( 1 ,σ, 2 )
Δ and p = pr ( q )
}
where
,p )=
c 1 ,...,c p− 1 , 0 ,..., 0
p even
update(
c 1 ,c 3 ,...,c d
c 1 ,...,c p− 1 ,c p +1 ,c p +1 ,...,c d
p odd
where we let c p +1=
for c p ∈{
n p ,
∞}
.
× N d
The safety objective for G is Safe(
pr ) where
pr = L
2 )isthe
T
T
( L