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

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

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