Tuesday, July 12, 2011

Probabilties and bad estimates

I'm somehow not good in estimating probabilities. I recently implemented some more caching in the engine and for space reasons I only saved part of the 64 bit board identifier.

I thought that using 2^20 hash slots which also verify 20 bits of the key just by the slot no and 20 more bits from the key are enough to safely detect collisions, when 2 different boards map to the hash same slot. But I was wrong. With my first verification run with a 12 ply search against 25 positions an undetected collision crashed the engine as it returned a move from another board, that was not legal on the actual board. It tried to capture its own pawn with a rook.

I knew there was a distant probability that this can happen (so like once in a thousands years), but as it happened so fast I must have greatly misjudged the probability for that.

Looks like I need additional collision detection code for that.