Workspaces ---- 337staff act actionwebs actionwebslocal agv apesless apon automotive bcvtb bhc bipeds capecode certafcs cg chess chessadmin chesslocal chessworkshop clotho cosmoi cps cpslab croquet cyphysim dataflow ddosos denso densoeal densosas design dgc3 dgc3exec directors drosonetsim dsc eecs124 eecs149 eecs149lab eecs20 escher gm gsoc handsimdroid hcddes hcssas hilv hybrid hyper iab ieee1588 instructors mast metropolis modelica naomi nes nsferc pa presenters pret pss ptalon ptango ptconf ptdb ptemaf ptesdf ptexternal pthomas ptides ptidesarch ptolemy ptopenmodelica ptpresenters pturing reactable reap researchers scos softdevel softwalls spfsos superb tbd thales triq vw

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.

 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.