Re: computer-go: Alpha-Beta Search

[Daniel Bump <bump@xxxxxxxxxxxxxxxxxx>]

> The Knuth Paper to read is:
> 
> Knuth and Moore "An analysis of alpha-beta pruning" Artificial
> Intelligence 6(4), 293-326, 1975.
> 
> Note that you will only get the reduction of the branch factor to the
> square root of the branch factor if the search is perfectly ordered by
> the goodness (according to the evaluation function) of the moves. So
> provided your ordering is reasonably good most of the time you will get
> fairly close to optimal pruning.

As I recall the Knuth-Moore analysis assumes that all terminal
nodes are at the same depth. This is unrealistic.

In practice, correct ordering of the moves can lead to much
better improvement than their analysis suggests, because
finding the correct refutation will often prune an enormous
subtree. In Go, a reading problem which I have experience with
is to decide whether a string can be captured.  A wise
ordering of the nodes can easily lead to a thousand fold
improvement in speed or better.

Daniel Bump
http://www.gnu.org/software/gnugo/devel.html