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

[Chris Fant <chrisfant@xxxxxxxxx>]

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

It is not immediately obvious and turns out nasty indeed.  This is why
I currently have my TT turned off -- because when I wrote it, I did
not understand this interaction.  Look here, in the section called
"Result Caching":

http://www.andromeda.com/people/ddyer/go/search.html
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/