*banner
 

Semi-perfect Information Games
Krishnendu Chatterjee, Tom Henzinger

Citation
Krishnendu Chatterjee, Tom Henzinger. "Semi-perfect Information Games". FSTTCS, December, 2005.

Abstract
Much recent research has focused on the applications of games with \omega-regular objectives in the control and verification of reactive systems. However, many of the game-based models are ill-suited for these applications, because they assume that each player has complete information about the state of the system (they are perfect-information games). This is because in many situations, a controller does not see the private state of the plant. Such scenarios are naturally modeled by partial-information games. On the other hand, these games are intractable; for example, partial-information games with simple reachability objectives are 2EXPTIME-complete. We study the intermediate case of semiperfect-information games, where one player has complete knowledge of the state, while the other player has only partial knowledge. This model is appropriate in control situations where a controller must cope with plant behavior that is as adversarial as possible, i.e., the controller has partial information while the plant has perfect information. As is customary, we assume that the controller and plant take turns to make moves. We show that these semiperfect-information turn-based games are equivalent to perfect-information concurrent games, where the two players choose their moves simultaneously and independently. Since the perfect-information concurrent games are well-understood, we obtain several results of how semiperfect-information turn-based games differ from perfect-information turn-based games on one hand, and from partial-information turn-based games on the other hand. In particular, semiperfect-information turn-based games can benefit from randomized strategies while the perfect-information variety cannot, and semiperfect-information turn-based games are in NP and coNP for all parity objectives.

Electronic downloads

Citation formats  
  • HTML
    Krishnendu Chatterjee, Tom Henzinger. <a
    href="http://chess.eecs.berkeley.edu/pubs/78.html"
    >Semi-perfect Information Games</a>, FSTTCS,
    December, 2005.
  • Plain text
    Krishnendu Chatterjee, Tom Henzinger. "Semi-perfect
    Information Games". FSTTCS, December, 2005.
  • BibTeX
    @inproceedings{ChatterjeeHenzinger05_SemiperfectInformationGames,
        author = {Krishnendu Chatterjee and Tom Henzinger},
        title = {Semi-perfect Information Games},
        booktitle = {FSTTCS},
        month = {December},
        year = {2005},
        abstract = {Much recent research has focused on the
                  applications of games with \omega-regular
                  objectives in the control and verification of
                  reactive systems. However, many of the game-based
                  models are ill-suited for these applications,
                  because they assume that each player has complete
                  information about the state of the system (they
                  are perfect-information games). This is because in
                  many situations, a controller does not see the
                  private state of the plant. Such scenarios are
                  naturally modeled by partial-information games. On
                  the other hand, these games are intractable; for
                  example, partial-information games with simple
                  reachability objectives are 2EXPTIME-complete. We
                  study the intermediate case of
                  semiperfect-information games, where one player
                  has complete knowledge of the state, while the
                  other player has only partial knowledge. This
                  model is appropriate in control situations where a
                  controller must cope with plant behavior that is
                  as adversarial as possible, i.e., the controller
                  has partial information while the plant has
                  perfect information. As is customary, we assume
                  that the controller and plant take turns to make
                  moves. We show that these semiperfect-information
                  turn-based games are equivalent to
                  perfect-information concurrent games, where the
                  two players choose their moves simultaneously and
                  independently. Since the perfect-information
                  concurrent games are well-understood, we obtain
                  several results of how semiperfect-information
                  turn-based games differ from perfect-information
                  turn-based games on one hand, and from
                  partial-information turn-based games on the other
                  hand. In particular, semiperfect-information
                  turn-based games can benefit from randomized
                  strategies while the perfect-information variety
                  cannot, and semiperfect-information turn-based
                  games are in NP and coNP for all parity objectives.},
        URL = {http://chess.eecs.berkeley.edu/pubs/78.html}
    }
    

Posted by Krishnendu Chatterjee, PhD on 9 May 2006.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess