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

Search Nedrilad ::

Custom Search