Re: [gnugo-devel] Search algorithm

[Arend Bayer]

Gunnar wrote:
> Daniel Jacober wrote:
> > I'm a student of computer sience in Switzerland. For my AI classes I'm
> > writing a document about GO. Therefore I also analysed your
> > documentation and source code. I was particularly looking for the kind
> > of algorithms you're using.
> > 
> > One thing I couldn't find out is wether you also use Alpha-Beta
> > Prunning to reduce the size of the search tree. Could you also tell me
> > why you're (or why you're not) using Alpha-Beta Prunning.
> 
> We don't. Historically this is because the reading started with
> win/lose outcomes only and then alpha-beta reduces to a simpler search
> which just terminates when a win is found. Later on ko results were
> added and then alpha-beta would be meaningful, but due to ko results
> being relatively uncommon we have not found it worth the extra code
> complexity. Also there's an issue with the caching of read results
> which needs to contain more information when used with alpha-beta.

However, in my opinion (I am not sure this opinion is shared by the rest
of the GNU Go team though) we will need alpha-beta in the long run. The 
reason is the following:
Ko searches have considerable higher branching factor, but they are
pretty rare. At the current depth settings, this means that they consume
a small portion of the total time, but this can change drastically when
depth levels get increased. (In fact, many of the extremely slow moves
in level 15 or higher reported on this list involve kos.) 

The extra code complexity is not negligeable, unfortunately.

Arend