The study of partial-observation games is considerably more complicated than games of perfect observation. Several results and properties of perfect-observation omega-regular games break under partial observation, such as determinacy, existence of pure memoryless optimal strategies, and even decidability for general omega-regular objectives.
We present a survey of basic results in the theory of partial-observation
games on graphs, about the structural complexity of winning strategies (randomization
and memory requirements) and the algorithmic complexity of deciding the winner
of the game. Then we present recent results and open problems for partial-observation
stochastic games with reachability objectives, and establish surprising connections
between some of these problems and classical problems for counter systems.