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

• fsttcs05.ps · application/postscript · 280 kbytes

• 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.