page1
Decomposition Search:
A
Combinatorial Games Approach to Game
Tree Search, w i t h Applications to Solving
Go Endgames
M a r t i n
M u l l e r
Electrotechnical Laboratory
Tsukuba, Japan
mueller@etl.go.jp
Abstract
We
develop
a
new
method
called
decomposi-
tion
search for computing minimax solutions to
games that can be partitioned into independent
subgames.
The method does not use traditional
minimax search algorithms such as alpha-beta,
but relies on concepts from combinatorial game
theory
to do
locally
restricted
searches.
This
divide-and-conquer
approach
allows the
exact
solution of much larger problems than is possi-
ble with alpha-beta.
We
show
an
application
of
decomposition
search to the game of Go, which has been tra-
ditionally regarded as beyond the range of ex-
act search-based solution methods.
Our exper-
iments with solving endgames show that alpha-
beta searches already become impractical in po-
sitions with about
15 remaining moves.
How-
ever,
an endgame solver based on decomposi-
tion
search
can
solve
a
much
larger
class
of
endgame
problems
with
solution
lengths
ex-
ceeding 60 moves.
1
I n t r o d u c t i o n
In two-player games with perfect information, minimax-
based search methods have been very successful.
Games
such
as 4-in-a-row, gomoku or nine men's morris have
been solved, and heuristic game-playing programs have
reached
world championship level
in
a number of pop-
ular games.
In chess and checkers,
endgame databases
constructed
using retrograde analysis have uncovered
a
wealth
of new
information
and
forced
the
rewriting of
the textbooks.
Today, the conditions under which these standard ap-
proaches are successful are well understood.
One class of
games in which they have not succeeded is combinatorial
games. Such a game can be represented as a combinato-
rial sum of local games, called subgames.
Decomposition
search is
a new computational method
for solving combinatorial games.
Decomposition search
decomposes a game into a sum of subgames, performs a
particular kind of local search for each subgame, applies
combinatorial game theory to evaluate the resulting local
game graphs, and determines overall optimal play from
the combinatorial game values of subgames.
By reducing the scope of searches from global to local,
the
new
method
can
compute
minimax
solutions
and
determine optimal play in such games much faster than
classical
techniques such
as alpha-beta,
which can
not
exploit the extra structure given by the decomposition.
The structure
of this
paper
is
as follows:
Section
2
reviews
several
existing divide-and-conquer
approaches
to
solving
games,
including
the
combinatorial
game-
theoretical
approach
to the
analysis of games with de-
composable
state.
Section
3
introduces
decomposition
search,
a four
step
algorithm
for
finding
the
minimax
solution and optimal play in combinatorial games.
Sec-
tion 4 applies decomposition search to Go endgames, and
Section
5
compares
the
performance
of decomposition
search with standard alpha-beta game tree search, using
Go endgames as examples.
2
Divide-and-Conquer Approaches to
Solving
Games
Research in game tree search follows two general goals:
reducing the size of the search space, and traversing the
space
in
clever
ways
in
order
to
find
solutions
early.
For solving games with large state spaces,
divide-and-
conquer approaches are attractive:
the idea is to identify
simpler subproblems that can be solved more easily, and
can contribute to an overall solution.
2.1
Heuristic Problem Decomposition:
Identifying Subgoals
In
complex
games,
the
ultimate
goal
of
the
game
is
difficult
to
reach
directly.
Therefore,
players
identify
subgoals and
search
specifically
to achieve these goals.
For example, bridge players analyze single-suit play, and
chess players seek ways to capture a particular piece or
break through a pawn chain.
A narrowly focused search
to achieve
a subgoal
is
typically much easier
than full
width game search, yet achieving a subgoal can have a
significant impact on the outcome of the game.
578
COMPUTER GAME PLAYING