Game Development Reference
In-Depth Information
6
Games with Imperfect Information:
Theory and Algorithms
Laurent Doyen
CNRS and ENS Cachan
Jean-Francois Raskin
Universite Libre de Bruxelles
Abstract
We study observation-based strategies for two-player turn-based games
played on graphs with parity objectives. An observation-based strategy
relies on imperfect information about the history of a play, namely, on the
past sequence of observations. Such games occur in the synthesis of a con-
troller that does not see the private state of the plant. Our main results are
twofold. First, we give a fixed-point algorithm for computing the set of states
from which a player can win with a deterministic observation-based strategy
for a parity objective. Second, we give an algorithm for computing the set
of states from which a player can win with probability 1 with a randomised
observation-based strategy for a reachability objective. This set is of interest
because in the absence of perfect information, randomised strategies are
more powerful than deterministic ones.
6.1 Introduction
Games are natural models for reactive systems. We consider zero-sum two-
player turn-based games of infinite duration played on finite graphs. One
player represents a control program, and the second player represents its
environment. The graph describes the possible interactions of the system,
and the game is of infinite duration because reactive systems are usually not
expected to terminate. In the simplest setting, the game is turn-based and
with perfect information, meaning that the players have full knowledge of
both the game structure and the sequence of moves played by the adversary.
The winning condition in a zero-sum graph game is defined by a set of plays
that the first player aims to enforce, and that the second player aims to avoid.
Figure 6.5 is taken from the final version of Berwanger et al. [2008] that appeared in Information
and Computation 208(10), pp. 1206-1220, ISSN: 0890-5401. It is republished here by permission of
Elsevier.
Search Nedrilad ::




Custom Search