Fixing the repetition detection hash table

Currently I try to speed up iCE a bit and investigate where iCE spends its time, yeah I'm profiling it a bit. One of the functions that used more than it should was the calculateRepetitions() function.

This function is used to determine whether this position was encountered before so a 3fold repetition is likely. The function has to parts, whenever a new position is entered it increments for this position (zobrist key & size_of_hash -1) a counter in a small hash table by 1 and then checks the value of the counter. If it is now 1 this means it was 0 before and we have never seen this position before. We can be sure this position is not repeated and exit. If the counter is 2 or more we might have a repetition or a hash key collision (we don't know). We now scan through the list of previous positions up to the latest non reversible move. This takes a bit longer.

When we unmake a move we decrement the counter in the hash table. This means the hash table is always almost empty. It only takes 1 slot for every real move on the board + 1 slot for every ply of search.

To see why this function takes so long despite its hash early exit I measured how many early exits I take and how often I scan through the list of keys after all. To my surprise I only had an early exit rate of at most 20% and in longer searches it went down to 10%.

How could that be ?

I looked at the content of the table and it contained negative values, it was full of them. This should not have happened. It is of course not possible to encounter a position less than never.

It turned out that I introduced an inconsistency when I added Null Move. I did not increment the hash slot when doing a Null Move but I decremented it when I undid the Null Move. So after a while most of the slots contained negative values and provided no value anymore.

After fixing that my early exit rate went up to 99,95% and calculateRepetitions() went almost into non existence in my function profile list.