Game Development Reference
In-Depth Information
5
Turn-Based Stochastic Games
Antonın Kucera
Masaryk University
Abstract
In this chapter, we give a taxonomy of winning objectives in stochastic
turn-based games, discuss their basic properties, and present an overview
of the existing results. Special attention is devoted to games with infinitely
many vertices.
5.1 Introduction
Turn-based stochastic games are infinitely long sequential games of perfect
information played by two 'ordinary' players and a random player. Such
games are also known as simple stochastic games and are a special type
of (simultaneous-choice) stochastic games considered by Shapley [1953].
Intuitively, a turn-based stochastic game is a directed graph with a finite
or countably infinite set of vertices, where each vertex 'belongs' either to
player
. An example of a turn-based
stochastic game with finitely many vertices is given below.
, player
, or the random player
0 . 2
0 . 1
0 . 1
s 1
v 2
v 1
s 3
0 . 7
s 2
u
0 . 4
0 . 9
0 . 6
The outgoing transitions of stochastic vertices (drawn as circles) are selected
randomly according to fixed probability distributions. In the other vertices
(boxes and diamonds), the outgoing transitions are selected by the respective
 
Search Nedrilad ::




Custom Search