Game Development Reference

In-Depth Information

3

Algorithms for Solving Parity Games

Marcin Jurdzinski

University of Warwick

Abstract

This is a selective survey of algorithms for solving parity games, which are

infinite games played on finite graphs. Parity games are an important class of

omega-regular games, i.e., games whose payoff functions are computable by a

finite automaton on infinite words. The games considered here are zero-sum,

perfect-information, and non-stochastic. Several state-of-the-art algorithms

for solving parity games are presented, exhibiting disparate algorithmic

techniques, such as divide-and-conquer and value iteration, as well as hybrid

approaches that dovetail the two. While the problem of solving parity games

is in NP and co-NP, and also in PLS and PPAD, and hence unlikely to

be complete for any of the four complexity classes, no polynomial time

algorithms are known for solving it.

3.1 Games on graphs

A
game graph
(
V,E,V
0
,V
1
) consists of a directed graph (
V,E
), with a set

of vertices
V
and a set of edges
E
, and a partition
V
0
V
1
=
V
of the set

of vertices. For technical convenience, and without loss of generality, we

assume that every vertex has at least one outgoing edge. An infinite game

on the game graph is played by two players, called player 0 and player 1,

player Even and player Odd, or player Min and player Max, etc., depending

on the context. A play of the game is started by placing a token on a starting

vertex
v
0
∈

V
, after which infinitely many rounds follow. In every round, if

the token is on a vertex
v

E
going

out of vertex
v
and places the token on
w
, and if the token is on a vertex

∈

V
0
then player 0 chooses an edge (
v, w
)

∈

Search Nedrilad ::

Custom Search