Game Development Reference
In-Depth Information
between x 1 and x 2 . This would result in a game that contains y 2 only finitely
often but x 1 and x 2 infinitely often.
From these considerations we see that Eva has to make her choices depend-
ing on the behaviour of Adam. A possible way for her to win is to always
remember which of the x i was visited before. When she has to make a choice
at x 1 , then she moves to y 1 if the previous x i was also x 1 , and she moves
to y 2 if the previous x i was x 2 . Playing according to this strategy, Eva can
ensure that the infinity sets of the possible plays are
{
y 1 ,x 1 }
,
{
y 1 ,x 2 }
,or
{
and thus winning for her.
Note that this strategy is winning from every vertex, i.e., it does not
depend on the initial vertex of the play.
y 1 ,y 2 ,x 1 ,x 2 }
The winning area for Eva is the set W E of all vertices from which Eva
has a winning strategy:
W E =
{
v
V
|
Eva has a winning strategy from v
}
.
The winning area for Adam is denoted W A and is defined in the same way.
A game
=( G, Win )is determined if from each vertex either Eva or
Adam has a winning strategy, i.e., if W E
G
W A = V . The games that we
consider in this tutorial are all determined.
The notion of strategy is very general because it allows the players to base
their decision of the next move on the whole history of the play. This means
that strategies are infinite objects in general. Very often simpler types of
strategies are su cient. The simplest are positional strategies , which only
depend on the current vertex. For Eva a positional strategy corresponds to a
function σ : V E
V E (and similarly for
Adam). The analysis in Example 2.3 has shown that Eva does not have a
positional winning strategy for the considered game.
A generalisation of positional strategies are finite memory strategies .
These are given by a deterministic finite automaton ( Q, C, q in ,δ,σ ) with input
alphabet C , state set Q , initial state q in , transition function δ , and (instead
of final states) the strategy function σ : Q × V E → V with ( v, σ ( q, v )) ∈ E
for each v ∈ V E and q ∈ Q . The idea is that the finite automaton reads
the (colour sequence of the) history of the play, and the strategy function
chooses the next move depending on the current vertex and the state of the
automaton. In this way Eva can use a bounded amount of information on
the history of the play.
V with ( v, σ ( v ))
E for each v
Example 2.4 The strategy we have defined in Example 2.3 is a finite
memory strategy. The corresponding automaton is shown in Figure 2.2. An