Game Development Reference
In-Depth Information
the exact position of the coins, but only the number of heads and tails. In this
game, does Player 1 have a strategy such that for all strategies of Player 2,
the game reaches HHH and avoids TTT? We are interested in observation-
based strategies which rely on the information available to Player 1. In fact,
Player 1 has no deterministic observation-based strategy to win the 3-coin
game, because Player 2 can always find a spoiling counter-strategy using his
ability to exchange coins after Player 1's move. If we do not allow Player 2
to exchange the coins, then Player 1 has a deterministic observation-based
winning strategy consisting in successively trying to toggle every coin. This
strategy requires memory and it is easy to see that memory is necessary to
win this game. On the other hand, if we allow Player 1 to take his decision
using a source of randomisation, then she would be able to win the original
3-coin game with probability 1. This shows that randomised strategies are
in general more powerful than deterministic strategies.
We study in this chapter mathematical models and algorithms for games
with imperfect information. The model that we consider is asymmetric in
the sense that Player 1 has imperfect information about the state while
Player 2 has perfect knowledge (Reif [1984], Chatterjee et al. [2007], De
Wulf et al. [2006]). This model is useful for the design of control programs
embedded in an environment that provides observations about its state via
shared variables or sensors. We discuss the asymmetry of the definition
in Section 6.3.1 and we argue that the existence of deterministic winning
strategies for Player 1 does not depend on the ability or not for Player 2 to
see the exact position of the game. In the rest of Section 6.3, we present the
theory and algorithms to decide the existence of observation-based winning
strategies. We use a reduction of games with imperfect information to games
with perfect information, and we exploit the structure of this reduction
to obtain a tailored data-structure and symbolic algorithms. We focus on
reachability and safety objectives which ask Player 1 to respectively reach
and avoid a designated set of target configurations. For parity objectives,
we choose to provide a reduction to safety games. We also briefly present
algorithms to construct winning strategies.
In Section 6.4, we introduce randomised observation-based strategies and
we present an algorithmic solution for reachability and Buchi objectives. The
algorithm computes the set of winning positions of the game and constructs
a randomised observation-based winning strategy.
Search Nedrilad ::

Custom Search