Game Development Reference
In-Depth Information
to have worst-case running time O ( n ). Note that in order to achieve this
running time it is su cient to consider a naive brute-force search solution that
(i) generates all n sets of vertices of size at most , and (ii) for each of them
verifies if they are 0-closed or 1-closed, and runs the O (2 ) divide-and-conquer
algorithm to check if they are a 0-dominion or a 1-dominion.
Exercise 3.14 Assume that a brute-force search O ( n )-time implementa-
tion of procedure dominion ( G, ) is used. Argue that the worst-case running
time of the algorithm parity-win-dominion ( G ) can be characterised by the
recurrence:
( n )) + O ( n ( n ) ) ,
T ( n )
T ( n
1) + T ( n
(3.3)
T (1) = O (1) .
First, argue that the worst case is when the parity-win ( G ) call is made in
procedure parity-win-dominion ( G ), and then both parity-win-dominion ( G )
and parity-win-dominion ( G ) calls are made in procedure parity-win ( G ).
Then, argue that since the set reach i ( W i )isan i -dominion in game G , and
since there is no dominion of size at most in G , it must be the case that
the number of vertices in game G = G
reach i ( W i ) is at most n
\
( n ).
It turn s o ut that if the maximum size ( n ) of dominions sought is chosen
to be
2 n
is the number of vertices, then the size of the
tree of r ec ursive calls of algorithm parity-wi n- dominion ( G ) can be bounded
by n O ( n ) . It then follows that T ( n )= n O ( n ) .
, where n =
|
V
|
Exercise 3.15 For every positive integer n , construct a labelled binary
tree τ n in the following way. The root of τ n is labelled by n . A node labelled
byanumber k> 3 has two ch ildren: a left child labelled by k
1 and a
2 k
right child labelled by k
. Nodes labelled by numbers 1, 2, and 3 are
leaves.
Prove th at o n every path from the root of τ n to one of its leaves there are
at most
2 n
1
2 j 2 <n
right tu rns. Use induction and the fact that if
2 n
1
1
2 ( j +1) 2 then n
2 j 2 . Conclude that the number of leav es o f τ n is
2 n
n O ( n ) , and th at if the function T ( n ) satisfies (3.3) for ( n )=
then
T ( n )= n O ( n ) .
Theorem 3.8 (Jurdzinski et al. [2008]) The winning sets and positional
winn in g strategies of both players in parity games can be computed in time
n O ( n ) .