[Solved]: Why is the initial state of Zobrist hashing random?

Problem Detail: 

When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?

Asked By : ross.squires

Answered By : Yuval Filmus

The initial elements are chosen randomly to minimize hash collisions. You can think of the Zobrist hash as a random hash function $h$, mapping board positions to bit vectors of length $N$, chosen from some collection of hash functions. What we are trying to accomplish is this: given any choice of positions $p_1,\ldots,p_n$ arising in the program, we want that with high probability over the choice of $h$, $h(p_i) \neq h(p_j)$.

The Zobrist hash family is 3-wise independent: for any 3 distinct positions $p_1,p_2,p_3$, the hashes $h(p_1),h(p_2),h(p_3)$ are uniformly distributed over all triplets of binary vectors of length $N$. In particular, the probability that $h(p_i) = h(p_j)$ is $2^{-N}$ (we actually only need 2-wise independence for this), and so the expected number of collisions is $\binom{n}{2} 2^{-N}$, which is the same as the expected number of collisions for a completely random hash function.

The Zobrist hash function has an important advantage over a completely random hash function: it is easy to compute. Moreover, it is easy to update after a move of a single piece on the board. It is this last property which makes it especially attractive for hashing board positions.

By choosing the initial elements at random, we guarantee that whatever the board positions $p_1,\ldots,p_n$ are, the probability of collision is small (assuming that the positions are chosen independently of the hash function). There could also be some intelligent choice for the initial elements satisfying that, but it is not clear what this choice should be, and how to analyze it. On the other hand, a random choice succeeds with high probability, which is why we choose the Zobrist table randomly.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22033