Re: [gnugo-devel] Search algorithm

[Jens Yllman]

> 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


Is it not also true that the way moves are selected today is kind of a
pruning. So alpha-beta does not add that much to the pruning. I guess
if/when we get more moves from pattern/heuristics vi might need alpha-beta
pruning. Also I guess that since we already have a pruned set, alpha-beta
might only be bad for our search.

Am I right or am I wrong. I do not have any scientific facts behind my
statement.

Jens Yllman