computer-go: RE: B* search

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> Isn't this a good argument for something like B* search, which was
> built to take advantage of these kinds of estimates? How well do you
> think this avoid the brittleness problem you speak of, David?
>
> -Patrick Bridges

I've been doing some experiments with B* Probability Based Search (as
described in a paper by Hans J. Berliner and Chris McConnell, Artificial
Intelligence 86(1): 97-156 (1996)).

SmartGo currently relies on selective full-board alpha-beta search to find
its best move, and I replaced that with B*, using the uncertainty at each
terminal node (unsettled groups) to give optimistic and pessimistic bounds
for the evaluation. My preliminary conclusions are:
- On average, B* played slightly better than alpha-beta.
- The B* search made fewer blunders due to uncertain evaluation, as it
looked deeper along those paths.
- The B* search made other kinds of blunders due to not looking far enough
ahead for some moves. For example, if the evaluation was deemed stable after
one move, the opponent's response wasn't even considered.

One thing to observe is that Berliner based each optimistic and pessimistic
estimate on a 3-4 ply brute force search, which gave him good bounds. This
is not something a Go program can afford to do with current hardware.

I'm currently working on a mixture of alpha-beta search and B* search to
gain some of the advantages of B* without losing the benefits of alpha-beta.
We'll see how it goes...

Anders Kierulf
www.smartgo.com