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

⊆

ϕ
.

Search Nedrilad ::

Custom Search