Game Development Reference

In-Depth Information

Antichains for randomised strategies
When computing the set of

surely-winning locations of a game with imperfect information, we have

shown that antichains of sets of locations are a well-suited data-structure.

This idea can be extended for computing the sets of almost-surely-winning

locations of a game with imperfect information.

Let
G
=

be a game structure with imperfect information,

and let
H
be its extended knowledge based construction, i.e.,
H
= Knw(
G
)=

L, l
I
,
Σ
,
Δ
,

O

(
s
,
)iff
s

s
and
=
.

Q, q
I
,
Σ
,
Δ
H

. We define

⊆

Q

×

Q
as (
s,
)

⊆

This order has the following properties:

•

if a state
q
in
H
is almost-surely-winning for the observable reachability

objective Reach(

), then for all
q

q
in
H
,
q
is almost-surely-winning

T

for the objective Reach(

T

);

, all the sets
W
0
,W
1
,...
, and

•

given an observable reachability objective

T

X
0
,X
1
,...
are

-downward closed.

Exercise 6.12

Define the operations

,

for the order

. Define the

operations PosReach and Apre so that they operate directly on

-antichains.

Exercise 6.13
Apply the fixed-point algorithm above to compute the

almost-surely-winning positions in the 3-coin example when Player 2 is

allowed to switch coins. Make sure to use antichains during your computations.

Extract from the fixed-point an almost-surely-winning observation-based

randomised strategy.

We give the solution to the exercise below. To determine the set of cells

in our 3-coin game from which Player 1 has a randomised strategy that

allows her to win the game with probability one, we execute our fixed-point

algorithm. In the computations, we may denote sets of locations by the

sequence of their elements, e.g.,

01235

denotes the set

{

0
,
1
,
2
,
3
,
5

}

.

.
W
1
= PosReach(
W
0
)is

obtained by the following fixed-point computation.
X
0

W
0

=

{

012345678

}×{

0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8

}

,
7),
X
1

=(

7

=

X
0

Apre(
W
0
,X
0
)=

} ×

{
0
,
1
,
2
,
3
,
5
,
6
,
7
}{
01234678
}×{
0
,
1
,
2
,
3
,
4
,
6
,
7
}
=
X
2
.
W
2
=
W
1
. This

fixed-point tells us that Player 1 has a randomised strategy to win the 3-coin

game with probability one. The randomised strategy can be extracted from

the antichain
W
1
and is as follows. In the first round, all choices of Player 1

are equivalent, so she can play
c
1
. Then she receives the observation
o
2
and

updates her knowledge to

{

01234578

}×{

0
,
1
,
2
,
3
,
4
,
5
,
7

}{

01235678

which is subsumed by all the elements of

the antichain. Then, she plays any action which is associated to those elements

with positive probability. The action
c
1
is associated with

{

1
,
2
,
3

}

{

01235678

}×

{

0
,
1
,
2
,
3
,
5
,
6
,
7

}

, action
c
2
is associated with

{

01234578

}×{

0
,
1
,
2
,
3
,
4
,
5
,
7

}

,

Search Nedrilad ::

Custom Search