Re: computer-go: RE: alpha-beta reduction

[Stuart Cracraft <cracraft@xxxxxxxxxxxxx>]

At 01:27 PM 11/15/99 -0800, you wrote:
>
>Forget about my question in last message. Vincent's email had a pseudo
>code for it. Sorry about that. Could somebody enlighten us more about
>the algorithms and why it helps?
>
>Thanks.
>
>-- Mousheng Xu


In minimax search, certain local minima and local maxima can be
used to bound the search and cause cutoffs, wherein parts of the
tree need not be searched because it is mathematically impossible
for an improved score to be found in the as-yet unsearched subtree.

The reason this is possible is that one knows, from previous searches 
that there is a current "score to beat" (either get higher than or 
lower than). 

Therefore, at one level below a minimizing ply (i.e. a maximize ply,
at which we choose the highest score of the sibling subtrees), if a 
subtree being searched returns a score higher than the least score 
of its parent (minimize) ply, then no remaining siblings need be 
searched at this lower (maximize) ply, because the best one could do is 
to beat a score we have that is already higher than the best 
score that will be selected at the parent ply (which we're minimizing).

The same idea can be applied to maximize / minimize instead of the above
minimize / maximize.

The reduction in nodes is sharp and significant and makes alpha beta minimax
a massive win. For the mathematics, please see the proof by J.S. Moore and
D. E. Knuth.

--Stuart