Game Development Reference

In-Depth Information

product

game

parity game

G ×A
Win

(
G,Win
)

compute

translate

winning strategy

with memory
A
Win

positional

winning strategy

Figure 2.6 Schema for game reductions

2.3.2 Game reductions

The general idea for game reductions is to transform games with a complicated

winning condition into games with a simpler winning condition (over a bigger

game graph) such that a winning strategy for the simpler but bigger game

can be transformed into a winning strategy for the original game (using

additional memory).

At the beginning of this section we have already seen how to translate a

winning condition that specifies forbidden prefixes by a regular expression

into a safety game. The general translation scheme that we apply is as follows

(illustrated in Figure 2.6):

•

Start from a game

G

=(
G, Win
) with some
ω
-regular winning condition

C
ω
.

•
Construct a deterministic
ω
-automaton
A
Win
for
Win
.

•

Win

⊆

Take the product of
G
and

A
Win
(the automaton reads the labels of the

vertices in
G
).

•

The new winning condition is the acceptance condition of

A
Win
(e.g., a

parity condition).

•
Winning strategies on the product game are winning strategies on the

original game with (additional) memory
A
Win
.

We show how to use this technique to reduce Muller games to parity games.

For this purpose we construct a deterministic parity automaton that reads

sequences
α
from
C
ω
and accepts if
α
satisfies the given Muller condition.

The construction is based on the data structure of 'latest appearance record'

(LAR) Buchi [1983], Gurevich and Harrington [1982].
2
The underlying idea

is to recall the order in which the colours of the play appeared (starting

with an arbitrary order). An LAR is thus a permutation of the colours over

which the Muller condition is defined. When reading the next colour of the

2
In Buchi [1983] LARs are called order vectors and they are attributed to McNaughton.

Search Nedrilad ::

Custom Search