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