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.