Game Development Reference
In-Depth Information
v
V 1 then player 1 moves the token in the same fashion. The outcome of
such a play is then an infinite path
in the game graph.
An infinite game on a graph consists of a game graph a n d a payoff function
π : V ω
v 0 ,v 1 ,v 2 ,...
.A pa y off function assigns a payoff π ( v ) to every infinite
sequence of vertices v =
R
in the game graph. In this chapter we
c onsider only zero-sum games, i.e., if the outcome o f a play is the infinite path
v
v 0 ,v 1 ,v 2 ,...
V ω then player 0 (player Min) has to pay π ( v ) to player 1 (player Max).
We call a game on a graph a qualitative game if the payoff function
is Boolea n , i.e., if π ( V ω )
. In q ualitative games, we say that an
outcome v is winning for player 0 if π ( v ) = 0, and it is losing for player 0
otherwise; and vice versa for player 1. An alternative, and popular, way
of formalising qualitative games is to specify a set W
⊆{
0 , 1
}
V ω of outcomes
that are winning for player 1, which in our formalisation is π 1 (1), i.e., the
indicator set of the Boolean payoff function π .
A strategy for player 0 is a function μ : V +
→ V , such that if v ∈
V and w ∈ V 0 then ( w, μ ( vw )) ∈ E . Strategies for player 1 are defined
analogously. Both players follow their strategies μ and χ , respectively, to
produce an outcome Outcome( v 0 ,μ,χ )= v 0 ,v 1 ,v 2 ,... if for all i ≥ 0, we
have that v i
V 1 implies v i +1 = μ ( v 0 v 1 ···
v i ), and that v i
V 2 implies
v i ). A strategy μ : V ω
v i +1 = χ ( v 0 v 1 ···
V for player 0 is a positional
V and v
strategy if for all w, u
V 0 ,wehave μ ( wv )= μ ( uv ), i.e., the
values of μ are uniquely determined by the last element of its argument. It
follows that a function μ : V 0
V uniquely determines a positional strategy
for player 0, and we often do not distinguish between the two. Positional
strategies for player 1 are defined analogously.
We say that a game, with a game graph ( V,E,V 0 ,V 1 ) and a payoff function
π : V ω
R
, is determined if:
su χ
in μ
π (Outcome( v, μ, χ )) = in μ
su χ
π (Outcome( v, μ, χ )) ,
(3.1)
for all v
V , where μ and χ range over the sets of strategies for player 0
and player 1, respectively. Note that the inequality
su χ
in μ
π (Outcome( v, μ, χ ))
in μ
su χ
π (Outcome( v, μ, χ ))
(3.2)
always, and trivially, holds. One interpretation of determinacy , i.e., when
the converse of inequality (3.2) holds, is that player 0 (player Min) does
not undermine her objective of minimising the payoff if she announces her
strategy to player 1 (player Max) before the play begins, rather than keeping
it secret and acting 'by surprise' in every round. An analogous interpretation
holds for player 1.

Custom Search