Game Development Reference
InDepth 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 nondeterminism.
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 surelywinning, it would be of no help to Player 1 that
Player 2 also has imperfect information. Indeed, a surelywinning 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
surelywinning 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
observationbased strategy α
o
∈A
G
such that for all β
∈B
G
we have
outcome(
G, α
o
,β
)
∈
ϕ if and only if there exists an observationbased 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
}
Search Nedrilad ::
Custom Search