Re: computer-go: Alpha-Beta Search

["Gary Boos" <gboos@xxxxxxx>]

Ahhh - that gives insight into why 9 kyu (like me) can be just as smart    
and experienced at board games but can't read out a given life and death   
battle anywhere near what the more experienced go player can.
        Gary
--------------
-----Original Message-----
From: Daniel Bump <bump@xxxxxxxxxxxxxxxxx>
To: computer-go@xxxxxxxxxxxxxxxxx <computer-go@xxxxxxxxxxxxxxxxx>
Cc: bump@xxxxxxxxxxxxxxxxx <bump@xxxxxxxxxxxxxxxxx>
Date: Tuesday, November 16, 1999 7:54 PM
Subject: Re: computer-go: Alpha-Beta Search


>
>> 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