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