Game Development Reference

In-Depth Information

and action
c
3
is associated with

{

01234678

}×{

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

}

. Let us

consider the different cases:

•

If the action
c
1
is played then the knowledge of Player 1 becomes

. This

knowledge is subsumed by all the elements in
{
01235678
} ×

{
0
,
1
,
2
,
3
,
5
,
6
,
7
}
and the action associated with those element is 1. After

playing 1 the knowledge of Player 1 is now
{
1
,
2
}
. Again this knowledge

is subsumed by all the elements of the fixed-point so Player 1 can play

each action in
{c
1
,c
2
,c
3
}
with positive probability. Note that with this

knowledge, it is su
cient to choose play with positive probability in the

set of actions

{

5
,
6

}

, but this optimisation is not necessary if we want to

win with probability one, it only reduces the expected time for winning.

{

c
2
,c
3
}

•

If the action
c
2
is played then the knowledge of Player 1 becomes

{

4
,
5

}

. This

knowledge

is

subsumed

by

all

the

elements

in

{

01234578

} ×

{

and the action associated with those element is
c
2
. After

playing
c
2
the knowledge of Player 1 is now

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

}

{

2
,
3

}

. And we can start again

with positive probability.

•
The reasoning is similar for action
c
3
.

playing all actions in

{

c
1
,c
2
,c
3

}

So we see that our algorithm proposes at each even round to play an action

at random then to replay the same action. With this strategy, if Player 1

plays each action with probability

1

3

when her knowledge is subsumed by

1

3

{

1
,
2
,
3

}

, she has a probability

to reach 7 every two rounds and so she wins

with probability 1.

References

J. Bernet, D. Janin, and I. Walukiewicz. Permissive strategies: from parity games

to safety games.
Inf. Theorique et Applications
, 36(3):261-275, 2002.

N. Bertrand, B. Genest, and H. Gimbert. Qualitative determinacy and decidability

of stochastic games with signals. In
Proc. of LICS: Logic in Computer Science
.

IEEE Computer Society Press, 2009. To appear.

D. Berwanger, K. Chatterjee, L. Doyen, T. A. Henzinger, and S. Raje. Strategy

construction for parity games with imperfect information. In
Proc. of CONCUR:

Concurrency Theory
, Lecture Notes in Computer Science 5201, pages 325-339.

Springer-Verlag, 2008.

D. Berwanger, K. Chatterjee, M. De Wulf, L. Doyen, and T. A. Henzinger. Alpaga:

A tool for solving parity games with imperfect information. In
Proc.ofTACAS:

Tools and Algorithms for the Construction and Analysis of Systems
, Lecture

Notes in Computer Science 5505, pages 58-61. Springer-Verlag, 2009.

K. Chatterjee, L. Doyen, T. A. Henzinger, and J.-F. Raskin. Algorithms for omega-

regular games of incomplete information.
Logical Methods in Computer Science
,

3(3:4), 2007.

Search Nedrilad ::

Custom Search