Game Development Reference
Figure 2.1 A game graph
Example 2.2 We can specify the following winning condition for Eva over
the game graph from Figure 2.1, where the colours are identified with the
vertices: y 2 ∈
Inf( α )
x 1 ,x 2 }⊆
Inf( α ) . This means that Win contains all
in which x 1 , x 2 , and y 2 appear infinitely often, or
in which y 2 and at least one of x 1 or x 2 appear only finitely often.
Now let us think of a play being built up by the two players by moving a
token along the edges of the graph: Eva chooses the next move from vertices
in V E and Adam from vertices of V A . Then we are interested in the question
of whether Eva has a way to play such that she is sure to win, no matter
how Adam plays, i.e., we are interested in the question of whether Eva has a
winning strategy. This is formalised in the following definitions.
A strategy for Eva is a function σ : V ∗ V E →
V such that σ ( xv )= v
implies ( v, v )
E . A play v 0 v 1 v 2 ···
is played according to σ if
i : v i ∈
V E →
σ ( v 0 ···
v i )= v i +1 .
Strategies for Adam are defined similarly with V A instead of V E .
Given an initial vertex v 0 and a strategy σ (for Eva or Adam), the set
Out ( σ, v 0 ) contains all plays starting in v 0 that are played according to σ
(the possible outcomes of σ ).
A strategy σ for Eva in a game
=( G, Win ) is a winning strategy from
vertex v 0 if Eva wins all plays α that start in v 0 and are played according to
σ , i.e., c ( α )
Win for all α
Out ( σ, v 0 ). Similarly, a strategy σ for Adam
is winning from v 0 if c ( α ) /
Win for all α
Out ( σ, v 0 ).
Example 2.3 We continue Example 2.2 and define a winning strategy for
Eva. Note that the only choice that Eva can make is in x 1 , where she can
choose to move to y 1 or to y 2 . If she always decides to move to y 2 , then
Adam could win by never moving to x 2 : the resulting play would contain
y 2 infinitely often but x 2 only finitely often and thus would be winning for
If Eva always decides to move to y 1 , then Adam could win by alternating