Game Development Reference
In-Depth Information
6.3 Games with imperfect information: surely-winning
In a game with imperfect information, the set of locations is partitioned
into information sets called observations . Player 1 is not allowed to see
what is the current location of the game, but only what is the current
observation. Observations provide imperfect information about the current
location. For example, if a location encodes the state of a distributed system,
the observation may disclose the value of the shared variables, and hide the
value of the private variables; or in a physical system, an observation may
give a range of possible values for parameters such as temperature, modelling
sensor imprecision. Note that the structure of the game itself is known to
both players, imperfect information arising only about the current location
while playing the game.
6.3.1 Game structure with imperfect information
A game structure with imperfect information is a tuple G
=
is
a set of observations that partitions the set L of locations. For each location
∈ L , we denote by obs( ) the unique observation o ∈O such that ∈ o .For
each play π = 0 1 ... , we denote by obs( π ) the sequence obs( 0 )obs( 1 ) ...
and we analogously extend obs( · ) to histories, sets of plays, etc.
The game on G is played in the same way as in the perfect information
case, but now only the observation of the current location is revealed to
Player 1. The effect of the uncertainty about the history of the play is formally
captured by the notion of observation-based strategy.
An observation-based strategy for Player 1 is a function α : L +
L, l I , Σ , Δ ,
O
, where
L, l I , Σ , Δ
is a game graph (see Section 6.2) and
O
Σ
such that α ( π )= α ( π ) for all histories π, π ∈ L + with obs( π )=obs( π ). We
often use the notation α o to emphasise that α is observation-based. Outcome
and consistent plays are defined as in games with perfect information.
An objective ϕ in a game with imperfect information is a set of plays
as before, but we require that ϕ is observable by Player 1, i.e., for all
π ∈ ϕ , for all π such that obs( π )=obs( π ), we have π ∈ ϕ . In the sequel,
we often view objectives as sets of infinite sequences of observations, i.e.,
ϕ ∈O
ω , and we also call them observable objectives. For example, we assume
that reachability and safety objectives are specified by a union of target
observations, and parity objectives are specified by priority functions of the
form p :
. The definition of surely-winning strategies is adapted
accordingly, namely, a deterministic observation-based strategy α for player 1
is surely-winning for an objective ϕ
O→{
0 ,...,d
}
ω in G if obs(Outcome 1 ( G, α ))
∈O
ϕ .