[computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

> 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