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