## Strategy Construction for Parity Games with Imperfect Information

*Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen,
Thomas A. Henzinger,
and Sangram Raje*

We consider imperfect-information parity games, in which
strategies rely on observations that provide imperfect information
about the history of a play. To solve such games, i.e., to determine
the winning regions of players and corresponding winning strategies,
one can use the subset construction to build an equivalent
perfect-information game. Recently, an algorithm that avoids
the inefficient subset construction has been proposed. The algorithm
performs a fixed-point computation in a lattice of antichains, thus
maintaining a succinct representation of state sets. However, this
representation does not allow to recover winning strategies.
In this paper, we build on the antichain approach to develop an
algorithm for constructing the winning strategies in parity games with
imperfect information. We have implemented this algorithm as a
prototype. To our knowledge, this is the first implementation of a
procedure for solving imperfect-information parity games on graphs.

*Proceedings of the
19th International Conference on Concurrency Theory*
(CONCUR),
Lecture Notes in Computer Science 5201,
Springer,
2008,
pp. 325-339.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2008 Springer.