Repetition Detection

[Bill Rogers]

The advanced programmers here know a lot more about this stuff than I do, but even though I could not implement a three move algorythm I did find a short cut that helps to eliminate that possiblity. When ever my program make a move I store a copy of that move and if the program trys to move back to that square I give it a penalty. Not prefect by a long shot but does prevent the repretition a little.
Bill

[hgm]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

Main drawback is that this won't work with an SMP search.

I see no reason why this should not work under SMP. Even with SMP there is only one game history, not? If the different threads would actually start playing different games, rather than merely thinking about them, the implementation is seriously flawed...

[Zach Wegner]

I see no reason why this should not work under SMP. Even with SMP there is only one game history, not? If the different threads would actually start playing different games, rather than merely thinking about them, the implementation is seriously flawed...

It wouldn't work if you include the game history within the tree, while it works if you only store moves that were actually played OTB. Bob is talking about the first case, and it seems you're talking about the second.

[bob]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

Main drawback is that this won't work with an SMP search.

I see no reason why this should not work under SMP. Even with SMP there is only one game history, not? If the different threads would actually start playing different games, rather than merely thinking about them, the implementation is seriously flawed...

The problem is each different thread is searching a _different_ game history, since the "history" is all moves made up to the point where you do the repetition. If you use a global hash then different threads can see all positions that any thread is currently searching, and find repetitions that are false since they don't come from the same path.

If your repetitoin doesn't include search nodes as well as real game positions, it is going to be extremely unreliable since many repetitions occur in the search, with positions that occurred previously in the search, as opposed to repeating just positions that occur in the actual OTB game history...

Perhaps I am not quite understanding what you mean?

[hgm]

Strange. with me game history is anything that is in the past, i.e. what is played on the board or sent to the opponent. What the engine is searching are is a possible future.

And, like I said, it is quick and dirty. If you can call it extremely unreliable depends on your standards. I said it solved 95% of the repetition problem. So it is 5% unreliable. It cannot plan for perpetuals, but in practice t hardly bungles any games because of this.

[bob]

Strange. with me game history is anything that is in the past, i.e. what is played on the board or sent to the opponent. What the engine is searching are is a possible future.

And, like I said, it is quick and dirty. If you can call it extremely unreliable depends on your standards. I said it solved 95% of the repetition problem. So it is 5% unreliable. It cannot plan for perpetuals, but in practice t hardly bungles any games because of this.

In my terminology, "history" is anything that has happened prior to the current _node_ whether the move was really played or not. For example, your approach won't find the rather quick perpetual where you have a black king at h8, white rooks at d8/e8, white king anywhere you want it. Put two black queens on the board anywhere where they can't stop the perpetual by the rook. Since all of that occurs in the tree, you need actual played moves and moves in the current path, since there is no "played moves" starting from there, such as might happen after the last capture before this sequence starts.

Also the same thing happens on positions like Nf3 Nf6 Nh1 Ng8 which is a 2-fold repetition and doesn't need to be searched further unless you think a draw is OK in the position.

I'm not so sure about the 95%, but I could certainly run a test later to see what a difference it makes over 40K games or so.

[bob]

forgot to say I stop searching the move stack when I encounter any pawn move or any capture. obviously those moves irrevocably change the board, so no need to search the stack before those moves. Note the capture move itself might be the start of a draw (with the captured piece off the board)

You can do this without the "testing" by just using the 50-move counter as the number of iterations you want to run the compare loop (divide by 2 since you don't check every ply, just every position with the same side on move.)

[xsadar]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

That's an intriguing idea. Doesn't see repetitions of positions that occur in the search, but at least it keeps repetitions from happening in the game. And it takes essentially zero extra time in the search and is easy to implement.

I think you might even be able to extend the idea a bit to see repeats of positions that occur in the search. When you begin the search of a position, you could lock it in hash with a score of zero. Then when you complete the search of that position, you replace the score with the correct score and unlock it. Seems to me that this might even take less time than the traditional history search at each node. What do people think?

I think he is saying that you _also_ flag them as you are searching them as well. Bruce Moreland did this in Ferret. Issue is a double hash probe, once for normal stuff, once for the repetition, and then at the end of each node, you have to undo the store. Bruce used two hash tables to make SMP search work, if in a complex way. If you use the normal hash, you still have to store an entry when you enter search() recursively, and remove it when you exit. if you don't do it in the search, it is not worth anything as a great number of repetitions happen in the search and if you don't catch it there if you want to avoid it or go for a draw, you might never get the chance...

Hmm... it looks like Bruce Moreland's website described exactly this method. I remembered it describing the separate hash table method you mention, but not the single table method. I probably quickly dismissed the idea because I didn't want to use an always replace hash table or deal with the question of what happens if you have a collision in the history, and that's probably why I don't remember it.

I agree that if you only use the history of moves actually made in the game you can run into serious trouble, but this is still clearly what hgm was talking about (see his other posts). Doing that in my first engine would have been ok, because I was just trying to get a handle on the concepts and didn't care much about playing strength. As it is, I think I left repetition detection out of that engine, so anything would have been better than that.

[hgm]

In my terminology, "history" is anything that has happened prior to the current _node_ whether the move was really played or not.

OK, that explains the miscommunication. In my terminology 'game' means what was played on the board, 'tree' means what is being searched. I do not consider the nodes from the root to the position currently being searched as part of the game. But, as they say, what's in a name?

It would certainly be interesting to determine how much Elo it would cost exactly when you forget about the current tree-branch, at a high level of play. And then compare it to the Elo you lose by not doing any repetition dtection at all. 40K games would be enough, as I expect the latter to cost you a bundle! (>100 Elo).

[bob]

In my terminology, "history" is anything that has happened prior to the current _node_ whether the move was really played or not.

OK, that explains the miscommunication. In my terminology 'game' means what was played on the board, 'tree' means what is being searched. I do not consider the nodes from the root to the position currently being searched as part of the game. But, as they say, what's in a name?

It would certainly be interesting to determine how much Elo it would cost exactly when you forget about the current tree-branch, at a high level of play. And then compare it to the Elo you lose by not doing any repetition dtection at all. 40K games would be enough, as I expect the latter to cost you a bundle! (>100 Elo).

I think the missed communication occurs in the term "history". Or more precisely "the past". I consider history anything that has happend up to now. Not anything that has happened up to the root of the tree we are searching. I find it more convenient to not make any distinction between whether a position occured on the real game board, or in the current search path, or both...

That makes the code _very_ simple and fast.