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

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?

Mark Boon <tesujisoftware@xxxxxxxxxxxxxxxxx> wrote:

I think what you describe is a general case of a well-known specific problem. And that is that sometimes the same position can be reached in different ways where one ends in a ko-capture and the other doesn't. This can result in incorrect results because the number of legal subsequent moves is different in the positions that otherwise look the same.

The solution you described is probably formally the correct way to solve it, but as you already noticed, not very efficient. The short-cut that is usually taken here is to include a hash-code of the stones captured by the last move into the the positional hash-code. That way you keep the efficiency at the cost of some small overhead.

I'm not sure if it has ever been proven that this always leads to correct results, but I think so far everyone who ran into this problem has been able to solve it in the way I described. In case you have an example where you reached the position in different ways without capturing a different set of stones then it would be interesting to publish it here, as I think that would be a first.

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

I am currently working on a program solving local life/death-problems, using a "normal" alpha-beta algorithm.

In order to avoid unnecessary long (and possible endless) move-sequences, a draw-result is returned when a postion is repeated in a sequence of moves.

After introducing a transpositon-table, I ran into this problem:

A certain position has been investigated, resulting (correctly) in a black win. Later the same position occured for the second time. This time, it was reached by another, much longer sequence of moves. Now, white could enforce a draw, with the help of a possible position-repetition.

My transposition table was still in test mode - otherwise the position wouldn't have been investigated the second time. It responded with an error message, beacuse the same position occured again with an incompatible result.

My first thought was, that positions may only be taken as equal, when the sets of preceeding positons are also equal. So I tried storing the set of preceeding positions in the transposition table as well. This worked correctly, but apart from using a lot more memory, the program became much slower ( the number of "hits" in the transposition table dropped sharply - not really surpising). So I don't think this is a really good solution.

Is there a better way to handle move and/or position-repetitions, especially with respect to the transposition table?

Best Regards

Christoph

PS. This seems like a "standard-problem" to me, but I couldn't find any discussion about this so far.

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/