Game Development Reference
In-Depth Information
3.3.4 Divide and conquer with dominion preprocessing by
progress measure lifting
The algorithms in Sections 3.3.2 and 3.3.3 apply very distinct techniques to
e ciently solve parity games with a large and small, respectively, number
of priorities relative to the number of vertices. In this section we show
that the two techniques can be successfully combined to improve the worst-
case running time from O ( dm
( n/ ( d/ 2)) d/ 2 )= O ( n d/ 2+ O (1) ) of the latter
algorithm to O ( n d/ 3+ O (1) ), which is the best currently known for parity
games with d = O ( n ). The improvement requires a vital modification of
the progress measure lifting algorithm from Section 3.3.3.
In Section 3.3.3 we have introduced sets M D of ( d/ 2)-tuples of non-negative
integers ( x d− 1 ,...,x 3 ,x 1 ), where for each odd q the component x q is bounded
by the number n q of vertices of priority q in a set D
·
V . We argued that this
set was su ciently large to express the values of the pointwise-lexicographic
least game parity progress measure, and the algorithm progress-measure-
lifting ( G ) computed the least progress measure by iterative application of
the lift (
,v ) operators.
In this section, for all integers b> 0, we consider an alternative set N b
of ( d/ 2)-tuples of non-negative integers ( x d− 1 ,...,x 3 ,x 1 ) that satisfy the
·
condition odd q x q ≤ b . Note that for every b> 0, the set N b ∪{} is
totally ordered by the lexicographic order on ( d/ 2)-tuples of numbers, and
the lift ( ·,v ) operators can be appropriately modified to select only values in
the set N b ∪{} .
We argue that using sets N b , for appropriately chosen numbers b , instead
of using the set M V , turns the algorithm progress-measure-lifting ( G )into
an e cient procedure for computing 0-dominions of moderate size, or estab-
lishing that no small 0-dominions exist. It is routine and straightforward to
adapt the algorithm progress-measure-lifting ( G ) to compute 1-dominions of
moderate size, or establishing lack thereof, too.
These combined procedures for computing 0-dominions and 1-dominions
of moderate size are then used in a modification of the dovetailing algorithm
parity-win-dominion ( G ) from Section 3.3.2, instead of using the brute-force
search procedure dominion ( G, ). We will refer to this modification of pro-
cedure parity-win-dominion ( G ) as procedure parity-win-dominion ( G ), the
details of which are presented in Figure 3.5. Note that the procedure parity-
win ( G ), that is used in procedure parity-win-dominion ( G ), is a copy of
the procedure parity-win ( G ) from Section 3.3.1 in which both recursive calls
parity-win ( G ) and parity-win ( G ) have been replaced by calls parity-win-
dominion ( G ) and parity-win-dominion ( G ), respectively.