Game Development Reference
In-Depth Information
computed in iterations as follows:
Attr 0
( R )
= R
A
Attr i +1
( R )= Attr i
( R )
A
A
Attr i
{
v
V A |∃
u
( R ):( v, u )
E
}
A
Attr i
{
v
V E |∀
u :( v, u )
E
u
( R )
}
.
A
The set Attr i
( R ) contains those vertices from which Adam can ensure to
reach a vertex in R after at most i moves. For a finite game graph there exists
an index i such that Attr i
A
( R )= Attr i +1
( R ) and we set Attr A ( R )= Attr i
( R )
A
A
A
for this index i .
From the vertices that are not inside Attr A ( R ) Eva has a simple winning
strategy to avoid a visit of R : She always moves to a vertex outside of
Attr A ( R ). The definition of the attractor ensures that such a move is always
possible. Furthermore, from outside the attractor Adam does not have the
possibility to move inside (again by definition of the attractor).
In the product game graph from the example in Figure 2.4 the attractor
for Adam of vertex 3 consists of the grey vertices ( c, 1) , ( d, 2) (in the first
iteration), and ( a, 2) (in the second iteration). A strategy for Eva to avoid
the attractor is given by the dashed arrows.
In the original game, Eva can realise the strategy by running the DFA
A on the play and making her decision based on the current vertex of G ,
the current state of
, and the strategy from the product game. These are
precisely the components required for a strategy automaton as defined in
the previous section.
A
Exercise 2.1 The method illustrated above uses a translation of regular
expressions into deterministic finite automata. Analyse the method when
using non-deterministic finite automata instead and show that it does not
work in general.
For the above example we used a translation from regular expressions
to DFAs. For infinitary conditions (something happens infinitely/finitely
often) standard DFAs are not enough. To treat such conditions we can use
ω -automata.
2.3.1 ω -automata
Automata on infinite words are defined in a similar way to automata on
finite words. The main difference is that a run of such an automaton does not
have a last state because the input is infinite. For automata on finite words,
acceptance of a word by a run is defined in terms of the last state of the run: