RE: computer-go: RE: B* search

["Daniel Stokeley" <D.Stokeley@xxxxxxxxxxxx>]

> 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 conducted some research into applying the B* Search algorithm to Go as my
final year project. The main problem I had was that I was working from
scratch to develop a system, had about 1 months coding time and had never
played Go when I began the project...

Bearing that in mind, I found that as you say, the optimistic and
pessimistic bounds are not estimable with a shallow search of even 3-ply,
and resorted to simple 1 and 2 ply searches on a small board. The major
problem with B* is the need for accuracy in the evaluation function. Given
that evaluation is one of the harder aspects of computer Go, this is made
harder in B* by the need for an accurate estimation of the current value,
together with a reasonably accurate optimistic value. Obtaining these with
search is unfeasible.
	If however, you do have very good static evaluators, then B* ought to be
very promising as it will rapidly choose moves that are obviously the best,
and investigate only the relevant portions of the search tree.

This posting is also a support for the effort that Mark Boon et al. are
making in "opening up" parts of their code to others. Had such code been
available when I began my project, I might have made a better job of it and
been able to investigate further. As it is, the only classes that might be
of use to this group are the board display classes - in Java Swing, if
anyone wants one and doesn't feel like writing their own.... it even
displays stones rendered in Houdini :)

If somebody does want to read my report then email me direct, i'm not
posting a general link because it isn't up to the general standard of work
being produced in the field at present.

tot ziens

Dan Stokeley

dan@xxxxxxxxxxxxxxxxx
University Of Exeter