We consider two-player parity games with imperfect information 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 of imperfect information. One major obstacle in adapting the classical procedure is that the complementation of attractor sets would break the invariant of downward-closedness on which the antichain representation relies. We overcome this difficulty by decomposing problem instances recursively into games with a combination of reachability, safety, and simpler parity conditions. We also report on an experimental implementation of our algorithm: to our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs.
Information and Computation
1206 - 1220
Berwanger D, Chatterjee K, De Wulf M, Doyen L, Henzinger TA. Strategy construction for parity games with imperfect information. Information and Computation. 2010;208(10):1206-1220. doi:10.1016/j.ic.2009.09.006
Berwanger, D., Chatterjee, K., De Wulf, M., Doyen, L., & Henzinger, T. A. (2010). Strategy construction for parity games with imperfect information. Information and Computation, 208(10), 1206–1220. https://doi.org/10.1016/j.ic.2009.09.006
Berwanger, Dietmar, Krishnendu Chatterjee, Martin De Wulf, Laurent Doyen, and Thomas A Henzinger. “Strategy Construction for Parity Games with Imperfect Information.” Information and Computation 208, no. 10 (2010): 1206–20. https://doi.org/10.1016/j.ic.2009.09.006.
D. Berwanger, K. Chatterjee, M. De Wulf, L. Doyen, and T. A. Henzinger, “Strategy construction for parity games with imperfect information,” Information and Computation, vol. 208, no. 10, pp. 1206–1220, 2010.
Berwanger D, Chatterjee K, De Wulf M, Doyen L, Henzinger TA. 2010. Strategy construction for parity games with imperfect information. Information and Computation. 208(10), 1206–1220.
Berwanger, Dietmar, et al. “Strategy Construction for Parity Games with Imperfect Information.” Information and Computation, vol. 208, no. 10, Elsevier, 2010, pp. 1206–20, doi:10.1016/j.ic.2009.09.006.
Material in IST: