Re: Superko detection (was Re: [computer-go] M.Boon-Library)

["Thomas Thomsen" <thomas@xxxxxx>]

Erik van der Werf wrote:
> Does MadLab's search use transposition tables? If so, how does it deal 
> with Graph-History Interaction?
>
> Erik
Yes, MadLab uses transposition tables, both for alpha-beta and proof-number 
search. At one point I was verifying my proof-number searcher by means of 
alpha-beta (to find bugs), and sometimes (seldom though) there would be 
differences due to Graph-History Interaction (GHI).

I believe Akihiro Kishimoto and Martin Müller have solved the GHI problem in 
an non-game-specific way. In MadLab I "solved" the problem in the following 
way. In any given position I look back in the move history until the last 
time one or more stones were captured. I then hash these stones and the 
stone that captured them. (In addition, the number of passes and prisoners 
for each side are hashed). This did the trick in the sense that the 
above-mentioned differences disappeared. The procedure could be iterated 
(also looking at the second-last capture etc.), but that didn't seem 
necessary. But don't ask me if works in extreme cases or on very small 
boards...

All this is according to memory. I can elaborate if anyone is interested, 
but others may very well have better solutions.

Best regards,

-Thomas
www.t-t.dk/madlab

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