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.cms271828 wrote: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.
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[] table = new int[1024]; // java code
This table would have to also contain positions encountered prior to search, but this is trivial.Code: Select all
int numberOfAppearances = ++table[key&1023]; if(numberOfAppearances == 3) return 0;
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?
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.