Game Development Reference
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 , Emerson and Jutla ,
Thomas [1995, 2002] and Henzinger .
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