page4
can be handled only in the case where cycles don't affect
optimal play.
Resource exhaustion is detected during algorithm exe-
cution if any of the following hold:
game decomposition
fails or results in very large subgames, LCGS exceeds a
preset time or space limit, or intermediate combinatorial
game expressions become too complex.
Practical limits
are
highly
game-specific,
and
depend
on
the
shape
of
local game graphs built during LCGS and on the com-
plexity of the combinatorial games involved.
For exam-
ple,
impartial games such
as N i m are generally easier
to
evaluate than partizan games such
as Go.
4
Applying Decomposition Search to
Go
Endgames
This section discusses how to apply decomposition search
to
the
game of Go.
Game decomposition
is
achieved
through the recognition of safe stones and territories and
the resulting board partition.
Other Go-specific aspects
are pruning moves during LCGS and scoring of terminal
positions.
4 . 1
S u b g a m e
I d e n t i f i c a t i o n
i n
G o
b y
B o a r d
P a r t i t i o n
A
Go
position
can
be
decomposed
when
parts
of the
board are isolated from the rest by walls of safe stones.
Moves in one part have no effect
on other parts
across
such a wall.
Figures 2 and 3 show the two decomposition
steps:
first,
finding
safe stones and territories, and then
identifying subgames as the connected components of the
remaining points on the Go board.
Figure 2:
Recognition of safe stones and territories
Figure 3:
Decomposition of Go endgame position
F i n d i n g Safe
Stones a n d
T e r r i t o r i e s
Safe
territories
are
'finished'
subgames:
they
can
be
evaluated
by
a number,
the
size of the
territory.
A r -
eas which are completely surrounded
by one player are
candidate
territories.
Territories
are
found
by
goal-
directed search, applying the techniques of [Miiller, 1995;
1997] to prove the safety of candidate territories.
Play in territories that have been proven safe is sim-
ple.
The player never plays first in any territory.
If the
opponent
attacks
the player's
territory,
a goal-directed
search is performed to
find
a refutation which
restores
the safety of the area.
4 . 2
L C G S
i n
G o
An
endgame
area consists
of unsettled
stones,
and
of
empty points which are not territory.
Safe stones, usu-
ally
of both
colors,
surround
each
endgame
area,
as
shown
in
Figure
3.
During
endgame
play,
unsettled
stones either become safe or are captured.
Empty points
will either be occupied or become part of a safe territory.
A rare special case are shared empty points in seki.
S c o r i n g L o c a l
T e r m i n a l
Positions
i n
G o
Scoring assigns an integer to each terminal position.
In
Chinese rules,
scoring measures the difference
between
how
many
stones
and
empty
points
belong
to
either
color.
In
Japanese
rules,
territory
and
prisoners
are
counted.
Both
kinds of scoring
are straightforward
in
a
terminal
position
since
the
status
of all
stones
and
empty points is known exactly.
P r u n i n g
M o v e s
In contrast to the speculative pruning in selective search
methods,
only
moves that
are
provably
worse-or-equal
than others can be eliminated.
For example, if a move
achieves control of all points in the local area,
it is op-
timal,
and
all other
moves can
be
pruned.
In
almost
surrounded areas such as the one shown in Figure 4, the
move
at
the
entrance
at
a
is
the only
good
move for
either
player.
Figure 4:
Area with unique best move at a
4 . 3
F u l l
B o a r d
M o v e
S e l e c t i o n
i n
G o
Full board move selection in Go distinguishes three cases:
1. If the opponent just
made a threat
in player's ter-
ritory, reply as in Section 4.1
to keep territory and
stones safe.
2. Otherwise, if the combinatorial game is not finished
yet, play the sum game as in Section 3.5.
3.
Otherwise, perform a cleanup phase:
fill
in the final
neutral points to finish the game.
MIILLER
581