page5
5
E x p e r i m e n t s
The
performance of decomposition
search
is compared
with standard full board alpha-beta search on two rep-
resentative examples from a set of Go endgame puzzles
in [Berlekamp and Wolfe, 1994].
In the examples, terri-
tories have been slightly strengthened
to make it easier
to prove their safety.
The endgames are equivalent to the
original version.
In each experiment, the full board prob-
lem was solved from scratch.
No precomputed database
of subgames was used.
5.1
Full-board Minimax Search
The
minimax
implementation
used
a
standard
alpha-
beta
search.
The
size
of the
transposition
table
was
32k
entries for
the
small problems,
4M
entries
for
the
big ones.
Since naive full-board search would be too ex-
pensive, alpha-beta search was allowed to use the same
knowledge about safe territories and the same local prun-
ing rules as LOGS.
In contrast to LCGS, pass moves must be generated,
because in positions where there is no good move, play-
ers must be allowed to pass,
instead of being forced
to
damage their own position.
5.2
First Example: 20 Point Problem
The first Go endgame example, on a 9 x 9 board, is based
on problem C.9 of [Berlekamp and
Wolfe,
1994].
After
computing safe stones and territories, the total remain-
ing endgame area
is
20
points.
There
are six
regions
labeled A to F, with sizes ranging from 2 to 6.
Figure 5:
Problem C.9 and its decomposition
This problem is trivial for decomposition search,
yet
already challenging for minimax.
For more detailed test-
ing, a series of simplified problems was created, in which
several
local endgame situations were replaced
by con-
stant territories.
Figure 6 shows such a simplified prob-
lem of size 10 consisting of areas A, B and C. Areas D, E
and F have been
'played out' and replaced
by constant
territories, as shown by the markings in the figure.
White is to play first in all problems.
Table 1 shows
the total node count for the LCGS phase of decomposi-
tion search, followed by the node count and solution time
in seconds for alpha-beta, as measured on a Macintosh
G3/250.
The solution times for decomposition search are
not shown, since they were
all very similar at 0.2 -
0.3
seconds.
The size of the transposition table (4M entries)
was insufficient for the full 20 point problem, resulting in
an enormous increase in solution time to over 28 hours.
Figure 6:
Problem C.9 reduced to areas A + B + C
Areas
(Size)
Nodes
DS
Node*
aB
Time
aB
A (4)
21
39
<0.1
A +
B (7)
26
526
0 1
A +
B
+
C (10)
31
5905
1 9
A
+
B
+
C
+
D
(16)
42
1097589
295
9
A
+
B
+
O
+
D + E
(18)
45
10243613
2461.0
A
+
B
+
C
+
D
+
E
+
F (20)
48
463941123
103406.2
Table 1:
Comparison of decomposition search and alpha-
beta in problem C.9
5.3
Second Example:
89 Point
Problem
The
second
example,
C . l l
of
[Berlekamp
and
Wolfe,
1994],
is
a Go endgame problem on
a
19 x
19 board.
Figure 7 shows the initial position and its partition into
subgames.
After determining safe stones and territories,
89 unsettled points remain, partitioned into 29 distinct
endgame areas of sizes 1 to 6.
Figure 7:
C . l l :
an 89 point endgame problem
An optimal 62
move solution sequence
computed
by
decomposition search is shown in Figure 8.
On the sys-
tem described above, the complete solution takes 1.1 sec-
onds, including 0.4 seconds for LCGS searching a total
of 420 nodes in the 29 subgames.
The remaining time
is taken
up
by
proving
the safety of territories
and
by
operations on combinatorial games.
Alpha-beta search
behaved
as in the
first
example.
Node counts and so-
lution times for the first
few subproblems are shown in
Table 2.
582
COMPUTER
GAME PLAYING