Re: [gnugo-devel] Search algorithm

[Martin Holters]

tor 2005-08-18 klockan 10:58 +0200 skrev 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.
> 
> 

Actually, the optimisations I was working on mentioned in
http://lists.gnu.org/archive/html/gnugo-devel/2005-08/msg00018.html
where beginnings of alpha-beta-pruning for the reading code. I stopped
dead when I ran across the caching/hash problem as I could not verify
whether the pruning was correct - ideally, it shouldn't change anything
but the reading node counts, but with the caches giving bogus results
every once in a while, I could not check this.

Nevertheless, with regression breakage that was pretty small, indicating
that I at least was pretty close to a correct implementation, I got
reading node count decreases by about 8%. Impact on time was negligible,
but at least the additional complexity didn't result in a slowing down
that was higher than the gain from pruning. Timing results on my machine
are rather imprecise, though.

/Martin