[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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.
    Mark Boon

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



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 mailing list