Game Development Reference
In-Depth Information
each action selects some outgoing edges. In this definition, all locations belong
to Player 1 and the choices of Player 2 are modelled by non-determinism.
Another point of interest is the fact that games with imperfect information
sound asymmetric, as only Player 1 has a partial view of the play. It should be
noted however that for surely-winning, it would be of no help to Player 1 that
Player 2 also has imperfect information. Indeed, a surely-winning strategy
of Player 1 has to ensure that all outcomes are in the objective, and this
requirement is somehow independent of the ability or not of Player 2 to see
the current location. In terms of strategies, one can show that to spoil a not
surely-winning strategy of Player 1, Player 2 does not need to remember the
history of the play, but only needs to count the number of rounds that have
been played. We say that a deterministic strategy β : L +
×
Σ
L for Player 2
is counting if for all π, π
L + such that
π |
and Last( π )=Last( π ),
|
π
|
=
|
Σ, we have β ( π, σ )= β ( π ).
and for all σ
Theorem 6.5 (Chatterjee et al. [2007]) Let G be a game structure with
imperfect information and ϕ be an observable objective. There exists an
observation-based strategy α o
∈A G such that for all β
∈B G we have
outcome( G, α o )
ϕ if and only if there exists an observation-based strategy
α o
G such that for all counting strategies β c
∈A
∈B
G we have
outcome( G, α o c )
ϕ.
Exercise 6.5
Prove Theorem 6.5.
The requirement that observations partition the set of locations of the
games may seem to be restrictive. For example, in a system using sensors,
it would be more natural to allow overlapping observations. For instance,
if a control program measures the temperature using sensors, the values
that are obtained have finite precision ε . When the sensor returns a value
t , the actual temperature lies within the interval [ t
ε, t + ε ]. Clearly, for a
measure t such that
t
[ t
ε, t + ε ]
|
t
|
, we have that [ t
ε, t + ε ]
=
.
As a consequence, the temperature observations overlap and do not form a
partition of the space of values.
Exercise 6.6 Show that a game structure with imperfect information
in which the observations do not partition the state space can be trans-
formed into an equivalent game structure with imperfect information with
partitioning observations in polynomial time.
Consider the game structure with imperfect information in Figure 6.3.
The alphabet of actions is Σ =
and the objective for Player 1 is to
reach location 4 . The partition induced by the observations is represented
{
a, b
}