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