page2
2.2
S p l i t t i n g
a
G a m e
V e r t i c a l l y :
E n d g a m e
D a t a b a s e s
A very successful divide-and-conquer method in the com-
putational analysis of games has been the construction of
endgame databases.
In this approach, a game is split ver-
tically into progressively
simpler games along the
time
axis.
Converging games such
as
checkers,
nine
men's
morris or chess can be split
in this way,
because
they
simplify towards
the
end
of the
game when
fewer
and
fewer pieces remain on the board.
Endgame
databases
are
built
bottom-up,
starting
from
the
simplest
subgames,
by
retrograde
analysis
[Thompson, 1986].
The optimal play outcome, and op-
tionally the distance to a win or conversion
to another
subgame, is computed for all positions in the subgame.
Databases
are
used
during heuristic
search:
whenever
search hits a database position, the exact value can be
used in place of the heuristic evaluation.
2.3
T h e
M a t h e m a t i c s
o f
D e c o m p o s i t i o n :
T h e
C o m b i n a t o r i a l
G a m e
A p p r o a c h
t o
t h e
A n a l y s i s
o f
G a m e s
Combinatorial game theory
[Conway,
1976; Berlekamp
et al., 1982] provides the mathematical basis for a more
radical divide-and-conquer
method:
it
breaks
up game
positions
into pieces
and
analyzes
the
overall game in
terms of these smaller local subgames.
Figure 1:
A three heap Nim position and its subgames
Each move in the game corresponds to a move in one
subgame and leaves all other subgames unchanged.
A
game ends when all subgames have ended, and the final
outcome of the game can be determined from the sub-
game outcomes.
A well-known example of a combinato-
rial game is Nim, shown in Figure 1, which is played with
heaps of tokens.
At each move, a player removes an arbi-
trary number of tokens from a single heap, and whoever
runs out of moves first loses.
Each Nim heap constitutes
one subgame.
While winning a single subgame is trivial,
winning the sum of several heaps requires either exhaus-
tive analysis, or,
much more efficiently,
a computation
using the calculus of combinatorial games.
3
Decomposition Search
This section develops decomposition search as a frame-
work for solving games through decomposition, a partic-
ular kind of local search
named
local combinatorial game
search
(LCGS)
and
the
analysis
of the
resulting
local
game graphs by applying combinatorial game theory.
3 . 1
D e f i n i t i o n
o f
D e c o m p o s i t i o n
S e a r c h
Let G be a game that decomposes into a sum of subgames
Let
the combinatorial game evaluation
of G
be
Decomposition
search
is
defined
as
the
following
four
step
algorithm
for
determining
optimal
play of G:
1. Game
decomposition
and
subgame
identification:
given G,
find
an equivalent sum of subgames
2.
Local combinatorial game search
(LCGS): for each
G,, perform a search to find its game graph
3.
Evaluation: for each game graph
evaluate
all terminal positions,
then
find
the combinatorial
game evaluation of all interior nodes, leading to the
computation of
4. Sum game play:
through combinatorial game anal-
ysis of the set of combinatorial games
select
an optimal move in
The
following subsections
describe
the
four steps
of
decomposition search in more detail, discuss how to use
the
results
of decomposition
search
during
game
play,
and describe limitations of the method.
3.2
G a m e
D e c o m p o s i t i o n
a n d
S u b g a m e
I d e n t i f i c a t i o n
The precondition for applying decomposition search to a
game position is that it can be split into subgames which
fit the
combinatorial
games
model
outlined
in
Section
2.3.
The specific
decomposition
procedure
depends
on
the game rules.
In some games, such as N i m , Amazons and many of
those
analyzed
in
the
book
Winning Ways [Berlekamp
et a/.,
1982],
a suitable decomposition follows directly
from the rules of the game.
Figure 1 shows the decom-
position of a N i m position.
In other games, such as Go,
more game-specific knowledge is necessary to find a good
decomposition of a given position.
3.3
L o c a l
C o m b i n a t o r i a l
G a m e
S e a r c h
Local
combinatorial game search
(LCGS)
is
the
main
information gathering step of decomposition search.
It
is performed
independently
for
each
subgame.
LCGS
generates
a game graph
representing
all relevant
move
sequences
that
might
be
played
locally
in
the
course
of a game.
LCGS works differently
from minimax tree
search
in a number of ways,
including move generation
and recognition of terminal positions.
Differences
B e t w e e n
L C G S
a n d
M i n i m a x
Search
The
game
graph
built
by
LCGS
differs
from
the
tree
generated by
minimax search.
In the case of minimax,
players
move alternately,
so
each
position
is
analyzed
with respect to the player on move. In contrast, there is
no player-to-move-next in a subgame.
All possible local
move sequences must be included in the analysis, includ-
ing sequences with several successive moves by the same
MULLER
579