Game Development Reference
In-Depth Information
o 1
o 2
c 3
o 3
0
1
4
c 3
Σ
init
HTH
HTT
c 1
c 2
Σ
c 1
o 5
2
5
8
Σ
c 3
HHT
TTH
TTT
c 2
o 4
c 2 ,
c 3
c 1 ,
c 3
c 2
c 3
Σ
7
3
6
HHH
THH
THT
c 1
Σ
Figure 6.4 The 3-coin game graph with alphabet Σ =
. The
transitions between states 2, 3, 5, and 6 are omitted for the sake of clarity
{
c 1 ,c 2 ,c 3 }
independent sets of
, and an algorithm to compute q would immediately solve
IndependentSet, showing that such an algorithm running in polynomial
time cannot exist unless P = NP . The idea of this reduction can be extended
to show that Cpre A requires exponential time (Berwanger et al. [2008], Filiot
et al. [2009]).
G
Exercise 6.11 Compute the winning cells in the two versions of the 3-coin
game with the symbolic algorithm using the antichain representation. The
3-coin game graph is given in Figure 6.4. We give here the solutions to this
exercise.
We first consider the version in which Player 2 is allowed to exchange the
positions of the coins that are not toggled. To compute the winning cells
of the game with imperfect information, we compute the set of all cells
that are able to force the cell
{
7
}
. We give here the sequence of antichains
computed by our algorithm:
X 0 = {{ 7 }},
X 1 = X 0 Cpre( X 0 )= {{ 1 },{ 2 },{ 3 },{ 7 }},
X 2 = X 1 Cpre( X 1 )= {{ 1 },{ 2 },{ 3 },{ 4 },{ 5 },{ 6 },{ 7 }} = X 1
and the fixed-point is reached. As
, this shows that Player 1
does not have a deterministic winning strategy in this game.
{
0
} ∈
X 1
We now consider the version where Player 2 is not allowed to exchange the
position of the coins that are not toggled. To compute the winning cells
of the game with imperfect information, we compute the set of all cells