Re: [computer-go] transposition-table and position-repetition

[Christoph Vielhauer <c_vielhauer@xxxxxxxxx>]

Hi Mark,

this is the example that got me and my transposition-table confused:

Starting position:
5......
4.xxxx.
3.ooox.
2.o.ox.
1..x...
*123456

First move-sequence  (12 moves)
W1,4 B1,5 W1,1 B2,1 W4,1 B1,3 W3,2 B5,1 W2,1 B1,2 W1,4 B1,3.  
After B1,3 the position is the same as after W2,1 ==> draw

Second move sequence (10 moves)
W1,4 B1,5 W1,1 B2,1 W4,1 B5,1 W3,2 B3,1 W2,1 B1,3 

Both sequences lead to this position:
5x.....
4.xxxx.
3xooox.
2.ooox.
1oo.ox.
*123456

When the first sequence had been evaluated it ended in a position-repetition. A draw was put in the transposition-table. (After B1,3 the position is the same as after W2,1.)

In the second sequence, the position after B1,3 is an easy win for black, but the wrong result is read from the transposition-table :-(

With respect to the posititon, the direct-ko rule and the stone(s) captured by the last move, the two sequences are identical.

My next "guess" is including the stones captured afer the last "irreversible" move (W2,1 in both cases) in the hashcode and in the testing for equality. But I am far from being convinced that this is a good general solution.

 

Kind Regards

Christoph

Mark Boon <tesujisoftware@xxxxxxxxxxxxxxxxx> wrote:

On 9/27/05, Christoph Vielhauer <c_vielhauer@xxxxxxxxxxxxxxxxx> wrote:

Thanks for your help!

 

Mark: In my example the last move does not result in a ko in either move-sequence. Also, the stones captured by the last move are identical. But the sets of stones captured in the course of the whole move-sequences are in fact different. Does this count?

 

I don't think I've seen this before so I think it would be interesting to look at these sequences. It seems you'll have to look at one of the articles mentioned before to find a general solution.

 

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

---

Yahoo! for Good
 
Click here to donate to the Hurricane Katrina relief effort. 
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/