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]).

∩

Search Nedrilad ::

Custom Search