Re: [gnugo-devel] Search algorithm

[Gunnar Farnebäck]

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.

/Gunnar