Game Development Reference
In-Depth Information
a
b
C c ( a + b ) cC + C d ( a + b ) dC
c
d
Figure 2.3 Eva wins a play if none of its prefixes matches the regular
expression
volume. Other good presentations of can be found in Zielonka [1998] and
Thomas [1997].
2.3 Transformation of winning conditions
The goal of this section is to show how to use automata theory to transform
complex winning conditions into simpler ones such that solving the simpler
game also allows us to solve the original game.
We start with an illustrative example. Consider a game graph with colours
C =
. The winning condition is specified by a regular expression r
(over the alphabet C ): Eva wins a play if none of its prefixes matches the
regular expression r . An example for such a game is shown in Figure 2.3.
The regular expression in this example defines all words such that there exist
two occurrences of c without any occurrence of c or d in between, or two
occurrences of d without an occurrence of c or d in between. Eva wins if no
prefix of the play satisfies this property. In the depicted game graph she can
achieve this goal by the following strategy σ :
{
a, b, c, d
}
from the d vertex she always moves to b , and
from the b vertex she moves
- to c if b was reached from d , and
- to a if b was reached from a or c .
We now illustrate a general method to compute such strategies. Instead of
developing a direct algorithm, we use the fact that regular expressions can
be translated into equivalent deterministic finite automata, abbreviated as
DFA. 1 Given such an automaton
A
we can build the product of the game
graph G and
reads the play in G . This is illustrated
in Figure 2.4, where on the left-hand side the game graph G and the DFA
A
in such a way that
A
A
1 For background on finite automata we refer the reader to Hopcroft and Ullman [1979].