Earlier Version

Strategy construction for parity games with imperfect information

D. Berwanger, K. Chatterjee, L. Doyen, T.A. Henzinger, S. Raje, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008, pp. 325–339.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ; ;
Series Title
LNCS
Abstract
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 of 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.
Publishing Year
Date Published
2008-07-30
Volume
5201
Page
325 - 339
Conference
CONCUR: Concurrency Theory
IST-REx-ID

Cite this

Berwanger D, Chatterjee K, Doyen L, Henzinger TA, Raje S. Strategy construction for parity games with imperfect information. In: Vol 5201. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2008:325-339. doi:10.1007/978-3-540-85361-9
Berwanger, D., Chatterjee, K., Doyen, L., Henzinger, T. A., & Raje, S. (2008). Strategy construction for parity games with imperfect information (Vol. 5201, pp. 325–339). Presented at the CONCUR: Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-540-85361-9
Berwanger, Dietmar, Krishnendu Chatterjee, Laurent Doyen, Thomas A Henzinger, and Sangram Raje. “Strategy Construction for Parity Games with Imperfect Information,” 5201:325–39. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008. https://doi.org/10.1007/978-3-540-85361-9.
D. Berwanger, K. Chatterjee, L. Doyen, T. A. Henzinger, and S. Raje, “Strategy construction for parity games with imperfect information,” presented at the CONCUR: Concurrency Theory, 2008, vol. 5201, pp. 325–339.
Berwanger D, Chatterjee K, Doyen L, Henzinger TA, Raje S. 2008. Strategy construction for parity games with imperfect information. CONCUR: Concurrency Theory, LNCS, vol. 5201. 325–339.
Berwanger, Dietmar, et al. Strategy Construction for Parity Games with Imperfect Information. Vol. 5201, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008, pp. 325–39, doi:10.1007/978-3-540-85361-9.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar