[computer-go] Alpha-beta pruning vs transposition tables

[Peter Drake <drake@xxxxxxxxxx>]

I discovered something of which I hadn't been aware:  alpha-beta 
pruning and transposition tables can interact in nasty ways.  Perhaps 
everyone else already knew this.

The problem is that, when a branch is pruned, the root of that branch 
is given an evaluation which may not be entirely accurate.  It's enough 
to prove that the branch is irrelevant for this move, but storing this 
value in a transposition table can lead to an incorrect result when the 
position is encountered again.

Clearly, not storing pruned values in the table would avoid this 
problem.  Is it safe to store them as long as they aren't kept around 
for the next search?

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/