Game Development Reference
In-Depth Information
a, b
a
2
3
a, b
b
1
b
o 1
a, b
a, b
2
3
4
a, b
a
o 2
o 3
o 4
Figure 6.2 A game structure with imperfect information G
Note that games with perfect information can be obtained as the special
case where
O
=
{{
}|
L
}
.
Example Consider the game structure with imperfect information in Fig-
ure 6.2. The observations are o 1 = { 1 } , o 2 = { 2 , 2 } , o 3 = { 3 , 3 } , and
o 4 = { 4 } . The transitions are shown as labelled edges, and the initial state
is 1 . The objective of Player 1 is ϕ = Reach( o 4 ), i.e., to reach location
4 . We argue that the game is not surely-winning for Player 1. Let α be
an arbitrary deterministic strategy for Player 1. Consider the strategy β
for Player 2 as follows: for all π
L +
o 2 ,if α ( π )= a ,
then in the previous round β chooses the state 2 ,andif α ( π )= b , then
in the previous round β chooses the state 2 . Given α and β , the play
outcome( G, α, β ) never reaches 4 . Similarly, Player 2 has no strategy β to
ensure that obs(outcome 2 ( G, β ))
such that Last( π )
ϕ where ϕ = Safe(
{
o 1 ,o 2 ,o 3 }
)isthe
complement of ϕ . Hence the game is not determined.
We briefly discuss the definition of games with imperfect information. In
traditional games with perfect information played on graphs (see Exercise 6.3),
locations are partitioned into locations of Player 1 and locations of Player 2,
and the players choose edges from the locations they own. It can be shown
that for perfect information games, this model is equivalent to our definition
(see Exercise 6.3). When extending the classical game model to imperfect
information, we need to remember that Player 1 does not see what is the
current location, and therefore he could not in general choose an edge from
the current location. Instead, one may ask Player 1 to choose in each round
one edge per location, thus to be prepared to all situations. This would
require an alphabet of actions of the form L
Δ which is of exponential size.
We prefer a simpler definition where an alphabet Σ of actions is fixed, and