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

["Xu, Mousheng" <moushengxu@xxxxxxxxxxxxxxxx>]

Stuart,

	Great thanks!
	It helped a lot, but there is still one remaining question, and
I am trying to say out how I understand it as a student, and you tell me
if I am right or wrong as a professor:
------------------------
	min-parent: min_socre, max_score
	max-child: min_score, max_score

	if(alphabeta(max-child) > min-parent.min_score) {
		don't search any siblings and return;
	}
	else {
		continue for next sibling;
	}
------------------------

	If the above is true, then my difficulty is "why"? Is there an
intuitive or simple understanding or explanation?
	
	Is "alpha" the max value, and "beta" the min value? Then what is
the meaning of the value returned by alphabeta(...)?

	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