Draw by position repetition

[bob]

I made a silly error, the repeated positions don't need to be consecutive as in 7,6,5.

I can also see now that odd and even ply positions can't be equal.

So I need a way to count the positions when we get to them, which instantly brings me to this idea as I am writing this:

Use a small table, for the sake of argument, say size 2^10 = 1024.

Code: Select all

int[] table = new int[1024]; // java code

Then, if we have a 64 bit zobrist, for a particular position, we can use first 10 bits to index this into the table, and do:

Code: Select all

int numberOfAppearances = ++table[key&1023];
if(numberOfAppearances == 3) return 0;

This table would have to also contain positions encountered prior to search, but this is trivial.

So assuming the above is correct, what size table would be good?
If a game has 100 moves, then the 100 positions (or 101) would have to pack into a table size 1024, giving a 1 in 10 chance of a collision with different positions (I think thats right), but this is not good, so maybe 2^16 = 65,536 would be better to virtually eliminate this.

Or is this high a value going to impact on performance like a big hash table does?

Any thoughts?

I don't like the idea. It makes a parallel search more complicated to implement. I prefer a simple list, N entries from the game history (I clear this list on any non-reversible real move made OTB) and M additional entries to be used to hold the zobrist signatures for each ply in the current search path. To look for a repetition, you look backward from the current position, checking every other ply, for "50-move-rule-counter" positions. No point in searching farther back since a non-reversible makes a repetition with earlier positions impossible. This is easier to utilize in a parallel search, when you are ready to go in that direction. It is also extremely fast and will barely even show up on a profile run.

You only need 100 entries in this table total, obviously, as once you have 100 entries stored one side will claim a 50 move draw and terminate the search instantly anyway.

[cms271828]

Hi, I kind of understand, and I have my own solution, but it seems inefficient, the part where I 'reset' the table.

I was going to have an array, with N entries from the game history from positions after the last capture/pawn move.

And the following entries for the search itself.

So when we reach a node (shouldn't need to bother with root), we can store the zobrist at the correct position.

Eg

zobrist = currentZobristForNode();
pos[7] = zobrist
Then loop through pos[5], pos[3], pos[1], and if 'zobrist' appears 3 times (including the one at the current node for which we stored pos[7]) we can return 0.

But supposing in this current node, the last move was a capture/pawn move, then we could do:
pos[7] = 0, and continue as normal

So that we should loop through pos[5], pos[3]... until we come to the end, or we have a 0, implying any array elements before this 0 cannot be reached again.

I believe this will work, except for the flaw below:
Once we get to a node for the opposite side, and do pos[10] = zobrist, then when we search back through 8,6,4,... we will not see the 0 stored.

Which would kind of mean checking every element for 0, and just the odd/even ones for equal zobrists.

I think I'm on the right lines, but I need to refine this idea.

[tvrzsky]

In my engine I was doing it folowing way before switching to use hashtable for detection of repetitions:
I had one additional array LastIrreversibleMove[] which contains for each ply number of ply at which last irreversible move occured. So if you currently are at ply 7 and last irreversible move occured at ply 1, then LastIrreversibleMove[7] should be 1. This array is maintained during the make move routine like this:
If the move is irreversible then store the number of the current ply (LastIrreversibleMove[CurrentPly] = CurrentPly)
else copy the value from the previous ply (LastIrreversibleMove[CurrentPly] = LastIrreversibleMove[CurrentPly-1]).
Then you search your pos[] array backwards starting from ply-4 going in steps of 2 until you find repetion (return 0) or get under LastIrreversibleMove[CurrentPly].

[cms271828]

I kind of see, but not sure how you are using hashtables, wouldn't you need a reasonably large table to avoid different positions hashing to same index in table?

[tvrzsky]

I kind of see, but not sure how you are using hashtables, wouldn't you need a reasonably large table to avoid different positions hashing to same index in table?

Not only size of the table is important, but how it works as well. If you use some kind of linear probing (you examine not only one slot in the table but up to the whole bucket in case of necessity, i. a. when some slot is used for repetion mark) then it is highly impropable that all slots in one bucket would have been used for repetitions.

[cms271828]

Well, I've got an array set up to store the zobrist keys, and another array of ints which pairs up with this which stores the entry in the array to search back up to, so when a pawn/capture move is done this number is set to the current position in array.

This seems to work without null or TT, but this is bugging me:
When I enable the TT, the search never finds a repeat of 3 positions. I guess thats because when it finds position for a 2nd time, it returns the value stored in the TT, and no further branches are searched from that node.

So I don't get how we can look for 3 repeated positions (at different plies) within the search tree, as the TT may prevent them from being searched further.

Any ideas? Thanks

[cms271828]

I think this post has got burried under the other posts, I could really do with some advice on the repetition detection problem I have, stated in previous message.

Any help is greatly appreciated, thanks

[bob]

Well, I've got an array set up to store the zobrist keys, and another array of ints which pairs up with this which stores the entry in the array to search back up to, so when a pawn/capture move is done this number is set to the current position in array.

This seems to work without null or TT, but this is bugging me:
When I enable the TT, the search never finds a repeat of 3 positions. I guess thats because when it finds position for a 2nd time, it returns the value stored in the TT, and no further branches are searched from that node.

So I don't get how we can look for 3 repeated positions (at different plies) within the search tree, as the TT may prevent them from being searched further.

Any ideas? Thanks

You use the TT differently. If you do a probe, and get an exact match, you check a "open" flag (this flag is set when this position is reached in the search, it is cleared when that search is done). If the open flag is set, this is a 2-fold repetition. You can add a counter if you want, but most consider 2 repeats in the search as a repetition.

The down-side is that you have to access this hash table twice. Once when you enter search at ply=N (to either store the current position with open=1, or set open=1 in an existing exact match. Then you have to access it again when you complete the search at ply=N to prevent this position from causing false rep matches in other branches.

This is more overhead, more memory traffic, and in addition, it becomes more problematic when you do a parallel search.

[cms271828]

Hmmm,

If I just adapt my code to return 0, when it sees a position twice (instead of 3 times), that might work since...

The first time it sees that position, it won't be in the hash table, and the 2nd time, with the rep-detection code coming first in the negamax function/method, 0 will be returned immediately, so no probe into hash.

So I guess when running the program, supposing engine is down on material, and it can get a repeated position (twice repeated), it will take that. Then after making its move on board, and opponents move, it will continue going for the repeated position, and the gui will decide when its actually a draw.

I'm not 100% sure this is logically correct, and I haven't modified my code yet, but it would work better, as with the FEN I was using...

FEN r1b5/knB1pq2/p2P1pq1/P5pq/7p/8/8/K7 w - - 0 1

It takes an 8 ply search to see that position repeated 3 times, but only a 4 ply to see it twice, so I could return 0 much quicker, giving better play.

Any thoughts?

[bob]

Hmmm,

If I just adapt my code to return 0, when it sees a position twice (instead of 3 times), that might work since...

The first time it sees that position, it won't be in the hash table, and the 2nd time, with the rep-detection code coming first in the negamax function/method, 0 will be returned immediately, so no probe into hash.

So I guess when running the program, supposing engine is down on material, and it can get a repeated position (twice repeated), it will take that. Then after making its move on board, and opponents move, it will continue going for the repeated position, and the gui will decide when its actually a draw.

I'm not 100% sure this is logically correct, and I haven't modified my code yet, but it would work better, as with the FEN I was using...

FEN r1b5/knB1pq2/p2P1pq1/P5pq/7p/8/8/K7 w - - 0 1

It takes an 8 ply search to see that position repeated 3 times, but only a 4 ply to see it twice, so I could return 0 much quicker, giving better play.

Any thoughts?

You still have to do the /open/close/ type operation. Just because you get a hash hit does _not_ imply you also are repeating a prior position. The hash hit can come from a previous search, a different branch, etc. none of which have a thing to do with repetitions. You must be able to determine that "this entry is on a currently active path being searched". Hence the overhead.