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

[Don Dailey <drd@xxxxxxx>]

Are you sure that you are not see GHI (graph history interaction?)
Other than this, there should be no nasty effects.

TT's can be tricky to implement also, due to the logic of which value
to store as it relates to upper and lower bounds.   It's very easy to
get this wrong. 

One other thing is comparing a cached value stored at one depth to
a needed value at another depth.    This is not really a "problem",
but it can cause strange behavior if you don't understand what is
going on.

Pruning a branch should have absolutely no effect on the root score,
unless you are using more pruning that just alpha/beta.

- Don


   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/

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