[computer-go] Lazy Evaluation in Monte Carlo/Alpha Beta Search for Viking4

[Magnus Persson]

Quoting Rémi Coulom <Remi.Coulom at univ-lille3.fr>:

> I tend to be a believer in min-max. I love having an algorithm that 
> is anytime. Also it is very clever at following long lines of forced 
> moves deeper than the rest, which is really efficient for ko fights. 
> But I might be wrong.

The ability to follow forced lines is what I miss most. But even alpha-beta
speed up a lot in such situation. It is not as evident for 9x9 but for 7x7
which I often play with long thinking times it can go 3-4 ply deeper in
straightforward tactical situations.


> Anyway, I am certain that neither of the two approaches will produce 
> a super-strong player. Global tree search simply does not work. We 
> have to find something else.

I agree that it is not enough, but I tend to believe that global search 
will be
part of a super-strong player. The question is *what more* is needed. 
Note that
with global search I allow some heavy pre-pruning of moves.

One thing is pattern matching. I see two complimentary kinds. Pre-computed
patterns that are harvested from human games. For efficient move ordering this
should be effective. It is also efficent for pruning moves that should never
contaminate a strong players thinking. I do this in Viking4 already but I am
using hand made patterns which is too tedious and error prone.

The second area is dynamic pattern learning. Sooner or later every game of go
creates unique patterns and there may be more to be learned than killer moves
and the history heuristic used in global search programs.

How much can the quality of the simulations be improved for Monte Carlo
programs? Early on I felt that it was very easy to improve Viking in this area
but later I reached a point where adding more knowledge introduced more
problems than improvements. But I think what I have done can be done much
better. And there are probably a lot of things I never even tried.

If there is a problem with global search then the search has to become more
focused. One idea I have been playing around with is to collect more data from
the simulations such as which groups died in games that were lost and then
collect a set of conditions that are not allowed to be violated in the
simulation. In a first pass a shallow global search learns that a partuclar
group is prone to die. Then a local search learns how to defend that group
properly. In a third stage the simulations of a final global search uses the
knowledge gained from the local search to improve evaluation.

Just some ideas to play around with.

MP