Game Development Reference
player according to his strategy , which may be randomised and history-
dependent . Thus, every pair of strategies for both players determines a play
of the game, which is a Markov chain obtained by applying the strategies to
the original game. The aim of player
is to maximise the expected payoff
associated to runs in plays, or to play so that a certain property is satisfied.
usually (but not necessarily) aims at the opposite.
In computer science, turn-based stochastic games are used as a natural
model for discrete systems where the behaviour in each state is either con-
trollable, adversarial, or stochastic. The main question is whether there is
a suitable controller (strategy of player
) such that the system satisfies a
certain property no matter what the environment and unpredictable users
do. For a successful implementation of a controller, it is also important what
kind of information about the computational history is required and whether
the controller needs to randomise. This is the main source of motivation for
considering the abstract problems presented in the next sections.
Since real-world computational systems are usually very large and complex,
they can be analysed only indirectly by constructing a simplified formal
model . A formal model of a given system is an abstract computational device
which faithfully reflects the important behavioural aspects of the system.
For purposes of formal modeling, the expressive power of finite-state devices
is often insu cient, and some kind of unbounded data storage (such as
counters, channels, stacks, queues, etc.) is needed to obtain a su ciently
precise model. Hence, in the computer science context, the study of turn-
based stochastic games is not limited just to finite-state games, but also
includes certain classes of infinite-state games which correspond to various
types of computational devices such as pushdown automata, channel systems,
vector addition systems, or process calculi.
We start by recalling some notation and basic concepts that are necessary
for understanding the material presented in subsequent sections.
Words, paths, and runs
In this chapter, the set of all real numbers is denoted by R, and we also use
the standard way of writing intervals of real numbers (e.g., (0 , 1] abbreviates
Let M be a finite or countably infinite alphabet. A word over M is a
finite or infinite sequence of elements of M . The empty word is denoted
by ε , and the set of all finite words over M is denoted by M ∗ . Sometimes
∈ R |