Game Development Reference
InDepth Information
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.
Player
usually (but not necessarily) aims at the opposite.
In computer science, turnbased 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 realworld 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
finitestate
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 finitestate games, but also
includes certain classes of
infinitestate
games which correspond to various
types of computational devices such as pushdown automata, channel systems,
vector addition systems, or process calculi.
5.1.1 Preliminaries
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
x
∈
R

0
<x
≤
1
}
Search Nedrilad ::
Custom Search