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

→

Search Nedrilad ::

Custom Search