# Zobrist Hashing equivalent for Simple Knights Game with only 1 unique piece

I looked over the Zobrist hashing function used for getting a unique hash id of the board state in a chess game. https://en.wikipedia.org/wiki/Zobrist_hashing

Martin Fierz explains it very well in his post:

Assume you have a board with S squares and P different types of pieces. You allocate an array:

int zobristnumbers[S][2*P];


and fill it with random numbers. The hash number is now calculated as an XOR over the occupied squares of the entire board:

key = 0;
for(i=0; i<S; i++) {    if(board[i] != EMPTY)
key ^= zobristnumbers[i][piece[i]];
}


Now this works very well for chess because you have 6 unique pieces and 64 squares - so the probability of getting a clash in the keys is very small.

I am trying to find a variant of this hashing function or another one, which would work smoothly in a more simple zero-sum game called Knights: 49 squares, and only one kind of piece - a knight from chess - which moves exactly like a knight in chess.

I want to use it as a transposition table key, for storing best moves and game states.

Any ideas or hints of how could this be achieved?

Thanks!

• What is your motivation for hashing this? Sep 7 '16 at 20:03
• 1. I would like to order the moves in alphabeta prunning with iterative deepening. For this I need to store the moves in a hashtable so that I cant retrieve them quickly. Sep 7 '16 at 20:16
• 2. I would like to store repeated states in a transposition table. They can occur frequently because of transpositions—different permutations of the move sequence that end up in the same position. This way I don't need to compute them again when I search the same tree. Sep 7 '16 at 20:19
• Why do you expect the probability of a hash collision would increase with fewer squares and piece types? Each piece type still has a unique zobrist number for each square it could appear on, and the range of the output hash is the same as before while the state space you're indexing has gotten substantially smaller (assuming a similar total number of piece instances on board at a time), so I would expect you'd see a lower probability of hash collisions for your case. Where has our reasoning diverged? Sep 7 '16 at 23:22
• Your right @DMGregory :). I missed the part with "each piece type still has a unique zobrist number for EACH square". Sep 8 '16 at 9:19