Game Development Reference

In-Depth Information

a, b

a, b

a, b

a, b

{
2
,
2
}

{
3
,
3
}

{
1
}

{
4
}

a, b

Figure 6.6 The knowledge-based subset construction for the game of Fig-

ure 6.3

information. The decision problems are computationally harder to solve

(deciding if a location is almost-surely-winning is EXPTIME-complete in our

setting, and it becomes 2EXPTIME-complete in the symmetric setting). We

choose to present the asymmetric setting for the sake of consistency with

the first part of this chapter, because it is a simpler setting, and because the

techniques that we present can be adapted to solve the more general case.

6.4.2 An algorithm for reachability objectives

We present an algorithm for computing the locations of a reachability game

with imperfect information
G
from which Player 1 has an almost-surely-

winning strategy. The algorithm can be extended to solve Buchi objectives

(Chatterjee et al. [2007]). The case of co-Buchi and parity objectives remains

open.

Extended subset construction
First, note that the reduction to games

with perfect information
G
K
of Section 6.3 does not preserve the notion of

almost-surely-winning. The knowledge-based subset construction for the the

game of Figure 6.3 is given in Figure 6.6. It is easy to see that for all strategies

of Player 1, Player 2 can avoid

3
,
3
}

{

4

}

by always choosing from

{

the

transition back to

. In the original game, this amounts to allow Player 2

to freely 'switch' between location
3
and
3
. However, against Player 1's

strategy of playing
a
and
b
uniformly at random, Player 2 cannot really

decide which location of
3
or
3
is reached, since both have probability
2

to be reached regardless of Player 2's strategy. So, we have to enrich the

knowledge-based subset construction to take this phenomenon into account.

In the new construction, locations are pairs (
s,
) consisting of a cell
s
and

a location

{

1

}

s
. To reduce ambiguity, we call such pairs
states
. The cell
s

encodes the knowledge of Player 1, and the location
keeps track of the

choice of Player 2, forcing Player 2 to stick to his choice. Of course, we need

to take care that the decisions of Player 1 do not depend on the location
,

but only on the cell
s
.

∈

Search Nedrilad ::

Custom Search