Don Daily wrote
I noticed a trend in computer chess towards throwing out more and
more moves. Years ago it was only alpha/beta pruning but then later
null move pruning, then other kinds of pruning and now the tree
is being cut in many places. Chess search trees now look much
more like the intial (highly selective) approach that was rejected
just a few decades ago.
Yes, the current chess-searches are not anymore brute force at all. E.g. the
History Heuristic as its implemented selects basically the first k (k==3)
moves. But in contrast to the original pruning methods its "soft-pruning".
The search depth of the remaining moves is reduced by R (R==1). An incorrect
pruning decission is not taken "forever". The general idea is to use
information from the search tree to shape the search tree. Ulf Lorenz from
the Univ. Paderborn considers the search tree as an adaptable error filter.
In Suzie we (Peter Woitke, Stefan Mertin and Chrilly) use Null-Move Pruning,
Multi-Cut and Futility Pruning. History Pruning does not work so far.
move-ordering is not very good and the History-Heurisitic relies on the
fact, that the k+1...n-th have a very low probability to generate a cutoff.
The poor move-ordering is related to a significant odd-even effect. Suzie
evaluates the last move too high. In chess the simple "capture the highest
piece with the lowest one" (MVLV) rule is very effective and simple. There
is no similar simple rule in Go. This has also a major impact on search
efficiency.
Suzie searches currently about 10KNodes/sec. The typical search depth is 7.
This is for 9x9 not very impressive. With better move-ordering depth 8-9
should be possible.
A major problem is quiescence search. We have not found so far a simple and
efficient rule. Either the rule is too selective or the quiescence explodes.
Again in chess MVLV is very effective. Each capture reduces the search tree
and the quiescence-search terminates by itself. Generating just captures is
in Go not sufficient. The tactical searcher in the evaluation takes captures
already into account. But if one generates forcing moves like e.g.
building/destroying 2-eyes, semiais ... there is no natural termination
limit.
Another surprising result is, that we have found so far no reasonable
search-extensions. This is related to the relative unstable evaluation. The
programm gets too much possibilities to "cheat". But this should hold also
for the pruning techniques. The pruning methods have a clear positive
effect. Depth 7 means, Suzie searches at most 8 Plies (7 normal and 1
quiescence-moves). In chess a 7 Ply search can also 15 Plies long.
UCT and Monte Carlo. It's not as much Monte Carlo any longer.
Yes, ecaxtly. I also think that the difference is fuzzy. Both methods fit
into the adaptable error filter model of Ulf.
Chrilly
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
