Game Development Reference
In-Depth Information
a, b
a, b
a, b
a, b
a, b
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
is disclosed, then the updated knowledge
is post σ ( s )
o where post σ ( s )=
s :( , σ, )
, 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