page6
Areas
(Size)
Node* DS
Node*
aB
Time
aB
A
(3)
5
15
<0.1
A + B
(6)
10
178
<0 1
A + B + C
(8)
13
899
0.3
A + B + C + D
(10)
16
2663
0.7
A + B + C + D + E
(14)
21
45446
16.7
A + B + C + D + E + F
(17)
26
209815
66.1
A + B + C + D + E + F + G
(22)
35
10350151
3192.9
A + B + C + D + E + F + G + H
(24)
38
78629573
25044 2
Table 2:
Performance of alpha-beta on problem C . l l
Figure 8:
An optimal solution to problem C . l l
As a final test two games starting from the initial posi-
tion of C . l l were played against the current world cham-
pion Go program
The Many Faces of Co.
Playing Black,
the decomposition search program gained one point over
the game-theoretically optimal result.
Playing White, it
gained five points.
Considering the small differences in
value of the endgame plays involved, the total gain of six
points in two experiments is significant.
5.4
D i s c u s s i o n
The
discussion
compares
decomposition
search
and
alpha-beta in
terms of time requirements,
results gen-
erated and information on alternative moves.
T i m e
R e q u i r e m e n t
The fundamental disadvantage of alpha-beta relative to
decomposition search is clearly demonstrated by the re-
sults:
alpha-beta requires time that is exponential in the
size of the
whole problem,
while LCGS' worst case
time
is exponential
in
the size
of the
biggest
subproblem.
If
local combinatorial game evaluations can
be computed
and compared without
too much overhead,
a dramatic
speedup results.
R e u s i n g
P a r t i a l
R e s u l t s
Another advantage of decomposition search
over alpha-
beta is that it generates useful partial results in the form
of evaluated subgames.
Frequently occurring games and
their
combinatorial
game
evaluation
can
be
stored
in
a
persistent
database.
If some
local
searches
can
be
avoided or terminated
early
by a database hit,
further
speedups
result.
This
method
works
for
any
combi-
natorial
game,
whereas
in
the
case
of minimax search
databases can
be
built only
for
the endgame
phase
of
converging games.
I n f o r m a t i o n o n
A l t e r n a t i v e
M o v e s
Alpha-beta returns the best move and the minimax score
of
a
position.
Evaluating
alternative
moves
requires
more search.
On the other hand, data generated during
decomposition
search
easily
yields
further
information
such as other optimal moves and the amount by which
a bad move is inferior to an optimal one.
6
S u m m a r y
Decomposition
search
is
a
new
computational
method
to find minimax solutions of combinatorial games.
The
method provides a framework to restrict search
to sub-
games,
and
uses
powerful
mathematical
techniques
of
combinatorial game theory
to combine the local results
and
achieve
globally
optimal
play.
As
a
divide-and-
conquer
method,
decomposition
search
results
in
vast
improvements compared to alpha-beta search.
An
application
of
decomposition
search
to
Go
has
demonstrated
perfect
play
in
long
endgame
problems,
which
far
exceed
the
capabilities of conventional game
tree search methods.
References
[Berlekamp and Wolfe, 1994]
E.
Berlekamp
and
D.
Wolfe.
Mathematical
Go:
Chilling
Gets
the
Last
Point.
A K
Peters,
Wellesley,
1994.
[Berlekamp et
al,
1982]
E. Berlekamp, J.
Conway, and
R.
Guy.
Winning
Ways.
Academic
Press,
London,
1982.
[Conway, 1976]
J.
Conway.
On
Numbers
and
Games.
Academic Press,
London/New York,
1976.
[Muller,
1995]
M.
Muller.
Computer
Go
as
a
Sum
of
Local
Games:
An
Application
of
Combinatorial
Game
Theory.
PhD
thesis,
ETH
Zurich,
1995.
Diss.Nr. 11.006.
[Muller,
1997]
M.
Muller.
Playing it safe:
Recognizing
secure territories in Computer Go by using static rules
and search.
In H.
Matsubara,
editor,
Proceedings
of
the
Game Programming
Workshop
in
Japan
'97, pages
80-86,
Computer
Shogi
Association,
Tokyo,
Japan,
1997.
[Thompson, 1986]
K. Thompson. Retrograde analysis of
certain endgames. ICC A Journal, 9(3): 131-139, 1986.
MULLER
583