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