page3
player, because players can switch between subgames at
every move.
Another difference between local and full state search
is
the treatment
of cycles.
To prevent
infinite
games,
the
repetition
of a game position
is forbidden
in
most
games, or limited to a small number as in chess.
How-
ever, the same local position can re-occur repeatedly as
long as the whole game keeps changing.
Combinatorial
game evaluation is defined only for games without cycles.
Therefore, decomposition search deals only with locally
acyclic games, and with those cyclic games where cycles
do not enter into optimal play.
M o v e
G e n e r a t i o n
LCGS must generate all legal local moves for both play-
ers, except in a terminal position or if moves can
prov-
ably
be
pruned.
Such
exact
pruning
rules
are
game-
specific.
Examples are restricting the number of equiva-
lent moves generated
to a single one, or pruning locally
bad moves which are dominated by other moves.
T e r m i n a l
Positions a n d
L o c a l
S c o r i n g
Termination rules decide when a position can be evalu-
ated without further expanding the game graph.
LCGS
defines the following termination rules:
•
No legal moves
•
No good move, game recognized as constant
•
Value of position already known
The first two cases represent
local terminal positions,
which
evaluate
to
an
integer.
This
number,
the
local
score,
is game-specific
and
computed
according
to
the
rules of the game.
In the third case,
if the value of a position is already
known from another source, such as a transposition ta-
ble, game-specific knowledge, or a precomputed local po-
sition database, LCGS can be terminated as well.
The
value
retrieved
for
such
a
position
is
a combinatorial
game, which has previously been computed by local eval-
uation as discussed in the next section.
3.4
L o c a l
E v a l u a t i o n :
M a p p i n g
G a m e
G r a p h s
t o
C o m b i n a t o r i a l
G a m e s
Local evaluation computes the combinatorial game value
of a given
acyclic local game graph with evaluated leaf
nodes.
Let the players be Black and White, with positive
scores good for Black.
If from a local position p Black
can move to
and White can move to
and
if the
evaluations
of these
follow-up positions
are
already known, then the evaluation C(p) is given by the
combinatorial game expression
This expression
can
be
brought
into a canonical
form
using standard rules of combinatorial game theory.
Re-
peated bottom-up application of the formula eventually
yields an evaluation of each node in the game graph.
Cycles
t h a t
d o n o t
A f f e c t
t h e
G a m e
V a l u e
Cycles
can
occur
during
LCGS,
even
if they
have
no
effect
on
optimal
play.
If evaluation
fails
due
to
cy-
cles, bounds are computed by forbidding one player all
moves
that
would
repeat
a position.
This
transforms
the game graph into an acyclic graph, a different one for
each player.
If both bounds coincide, optimal play does
not depend on cycles.
Otherwise, decomposition search
stops and indicates a local evaluation failure.
3.5
Sum
Game Play
To find an optimal move in a sum game, the final step
of decomposition search selects a move which most im-
proves the position.
This improvement is measured by a
combinatorial game called
the
incentive of a move.
The
incentives of all moves in all subgames are computed lo-
cally.
If one incentive dominates all others,
an optimal
move has been determined.
This is the usual case for
games with a rich set of values such as Go.
Since incentives are combinatorial games and therefore
only partially ordered, it can happen that more than one
nondominated candidate move remains.
In this case, an
optimal move is found by a more complex procedure in-
volving the combinatorial summation of games [Conway,
1976].
Since such a summation can be an expensive opera-
tion, there is no worst case guarantee that decomposition
search is always more efficient than minim ax search. In
practice,
it seems to work
much better.
The algorithm
presents many opportunities for complexity reduction of
intermediate expressions during local evaluation as well
as during summation.
Even though all search and most analysis is local, de-
composition
search
yields globally optimal
play,
which
can
switch
back
and
forth
between
subgames
in
very
subtle ways, as in the example of Figure 8.
3.6
R e u s i n g
D e c o m p o s i t i o n
S e a r c h
R e s u l t s
D u r i n g
P l a y
The result of decomposition search is a complete descrip-
tion and evaluation of all reasonable local play sequences,
which makes perfect overall play possible.
Results of lo-
cal
analysis can
be saved
in
a database.
During play,
each full board position corresponds
to a set of match-
ing local
positions,
one from each
subgame.
Positions
and their combinatorial game values are retrieved
from
the database.
As long as the
opponent follows analyzed
lines,
f o l -
lowup moves can be played from the information stored
in the database, without further search.
If the opponent
plays a less-than-optimal move that was pruned
during
LCGS and reaches an
unevaluated position,
the corre-
sponding subgame is re-searched from the new position.
3 . 7
L i m i t a t i o n s
o f
D e c o m p o s i t i o n
S e a r c h
There
are
two
types
of
limitations
for
decomposition
search:
cyclic subgames and bounded computational re-
sources.
As discussed
in
Section
3.4,
cyclic
subgames
580
COMPUTER
GAME PLAYING