Game Development Reference
In-Depth Information
to the parity condition, i.e., Player 0 wins a play π if the least priority seen
infinitely often in π is even, otherwise Player 1 wins.
Thus the arena G := ( V,E,V 0 ,V 1 ,B, Ω) of a backtracking game is a defined
as for parity games, extended by a subset B ⊆ V of backtrack positions. A
play of G from initial position v 0 is formed as follows. If, after n steps the
play has gone through positions v 0 v 1 ...v n and reached a position v n ∈ V σ ,
then Player σ can select a successor v n +1 ∈ v n E ; this is called an ordinary
move. But if v n
B is a backtrack position, of priority Ω( v n )= q ,say,
then Player σ may also choose to backtrack; in that case she selects a
number i<n subject to the conditions that Ω( v i )= q and Ω( v j )
q
for all j with i<j<n . The play then proceeds to position v n +1 = v i
and we set d ( q )=
. This number d ( q )is
relevant for the rest of the game, because the play ends when d ( q ) further
positions of priority q have been seen without any occurrence of a priority
<q . Therefore, a play is not completely described by the sequence v 0 v 1 ...
of the positions that have been visited. For instance, if a player backtracks
from v n in v 0 ...v i ...v j ...v n , it matters whether she backtracks to i or j ,
even if v i = v j because the associated numbers d ( p ) are different. For a more
formal description of how backtracking games are played we refer to Dawar
et al. [2006].
It is easy to see that backtracking games are Borel games, so by Martin's
Theorem, they are determined. Since parity games are positionally determined
the question arises whether this also holds for backtracking games. However,
simple examples show that this is not the case and, indeed, no fixed amount
of finite memory su ces for winning strategies.
|{
k : i
k<n
Ω( v k )= q
}|
Theorem 4.28 Backtracking games in general do not admit finite-memory
winning strategies.
Exercise 4.6
Find an example proving this.
Thus, winning strategies for backtracking games are more complex than
the strategies needed for parity games. Also the computational complexity of
computing winning regions is higher for backtracking games than for parity
games. While it is known that winning regions of parity games can be decided
in NP
Co-NP (and it is conjectured by many that this problem is actually
solvable in polynomial time), the corresponding problem for backtracking
games is Pspace-hard. Further, for any fixed number of priorities, parity
games can be decided in Ptime, but backtracking games with just two
priorities are already NP-hard (see Dawar et al. [2006]).