Game Development Reference

In-Depth Information

a, b

b

2

3

4

a, b

a, b

a

1

a

a, b

a, b

b

2

3

4

a, b

Figure 6.3 Memory is necessary for Player 1 to surely-win the objective

Reach(
4
)

by the dashed sets. We claim that Player 1 has no memoryless observation-

based surely-winning strategy in this game. This is because from locations

3
and
3
, different actions need to be played to reach
4
, but since
3
and

3
have the same observation, Player 1 has to play the same action in a

memoryless observation-based strategy. However, if Player 1 remembers the

previous observation, then he has a surely-winning strategy, namely if
{
2
}

was observed in the previous round, then play
a
, and if
{
2
}
was observed in

the previous round, then play
b
. This shows that memory may be necessary for

surely-winning in a game with imperfect information even for a reachability

objective. Intuitively, a sequence of past observations provides more precise

knowledge about the current location of the game than the current observation

only. Therefore, Player 1 should store and update this knowledge along the

play to maintain the most precise information possible. Initially, his knowledge

is the singleton

(we assume that the structure of the game is known to

both players), and if the current knowledge is a set
s

{

l
I
}

⊆

L
, Player 1 chooses

action
σ

∈

Σ, and observation
o

∈O

is disclosed, then the updated knowledge

is post
σ
(
s
)

o
where post
σ
(
s
)=

∈

s
:(
, σ,
)

∩

{

L

|∃

∈

∈

Δ

}

, i.e., the set

of all locations reachable from locations in
s
by playing
σ
.

6.3.2 Reduction to games with perfect information

Given a
game structure with imperfect information
G
=

L, l
I
,
Σ
,
Δ
,O
with observable parity objective
ϕ
, we construct an equivalent

game structure (with perfect information)
G
K
=

S, s
I
,
Σ
,
Δ
K

with a parity

objective
ϕ
K
which, intuitively, monitors the knowledge that Player 1 has

about the current location of the play. The game
G
K
is called
knowledge-

based subset construction
. The structure
G
K
=

S, s
I
,
Σ
,
Δ
K

is defined

as follows.

Search Nedrilad ::

Custom Search