Strategy construction for parity games with imperfect information Conference Paper

Author(s): Berwanger, Dietmar; Chatterjee, Krishnendu; Doyen, Laurent; Henzinger, Thomas A; Raje, Sangram
Title: Strategy construction for parity games with imperfect information
Title Series: 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.
Conference Title: CONCUR: Concurrency Theory
Volume: 5201
Conference Dates: August 19-22, 2008
Conference Location: Toronto, Canada
ISBN: 978-3-95977-017-0
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Location: Berlin, Heidelberg
Date Published: 2008-07-30
Start Page: 325
End Page: 339
DOI: 10.1007/978-3-540-85361-9
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work