Game Development Reference

In-Depth Information

H

1

1

T

2

2

H

3

3

Figure 6.1 The 3-coin game

We focus on
ω
-regular sets of plays expressed by the parity condition (see

Section 6.2) and we briefly present properties and algorithmic solutions for

such games. The theory and algorithms for games with perfect information

has been extensively studied by Martin [1975], Emerson and Jutla [1991],

Thomas [1995, 2002] and Henzinger [2007].

Turn-based games of perfect information make the strong assumption that

the players can observe the state of the game and the previous moves before

playing. This is however unrealistic in the design of reactive systems because

the components of a system have an internal state that is not visible to the

other components, and because their execution is concurrent, each compo-

nent choosing moves independently of the others. Such situations require

us to introduce games with
imperfect information
where the players have

partial information about the play. We illustrate the games with imperfect

information with the 3-coin game, shown in Figure 6.1.

Three coins
c
1
,c
2
,c
3
are arranged on a table, either
head
or
tail
up.

Player 1 does not see the coins, but he is informed of the number of

heads (H) and tails (T). The coins are manipulated by Player 2. The

objective of Player 1 is to have all coins head up (HHH) while avoiding

at all cost a configuration where all coins show tail (TTT). The game is

played as follows. Initially, Player 2 chooses a configuration of the coins

with two heads and one tails. Then, the following rounds are played:

Player 1 can choose one coin in the set

and ask Player 2 to

toggle that coin. Player 2 must execute the choice of Player 1 and he

may further decide to exchange the positions of the two other coins. The

game stops whenever the three coins are all head up (Player 1 wins) or

all tail up (Player 2 wins). Otherwise Player 2 announces the number of

heads and tails, and the next round starts.

{

c
1
,c
2
,c
3
}

This is a game with imperfect information for Player 1 as she does not know

Search Nedrilad ::

Custom Search