Game Development Reference
InDepth 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 blowup 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 surelywinning strategy in
G
for the
objective Parity(
pr
), then player 1 also has a memoryless surelywinning
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
Search Nedrilad ::
Custom Search