[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Alpha-beta pruning vs transposition tables
Also of interest: if you don't store the pruned values, using TT+AB
can explore more nodes than TT alone (6724 vs 5478 for Tic Tac Toe).
On Tuesday, March 8, 2005, at 08:42 PM, Peter Drake wrote:
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/
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/