Zobrist Hashing
An efficient hashing algorithm used to store state of the board in abstract board games like Chess and Go and "Chain Reaction".
These hashes are used to implement Transposition Tables, which is used to avoid analyzing the same board position twice, by storing the score, or best possible move at a board position.
It is the first known instance of a generally useful underlying technique called tabulation hashing.
How does it work
Each independent element on the board is represented using a number, an unsigned int more specifically, or we can say a "bitstring".
In fact, this random generated number represents every possible state of the board (or attempts to).
In chess, for example, it represents every piece, every position, and 2 colors, that is,
There may be extra bitstrings for more niche or unique moves like "castling", but you get the general idea.
Now each position, at any time on the board, can be computed as a XOR of the individual bit strings that were previously found to represent individual components.
These are generally done with 64 bit uints, assuming that hash collision does not occur across the board, or even if they do, it doesn't greatly affect the results of the Transposition table
Updating the position
Instead of having to recalculate every piece's every position again, we can use the property of XOR that a^a = 0 and use that to make a new hash.
XOR with a position that existed but no longer does to remove that position.
XOR with the new position that didn't exit but now does.