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 .