2
\$\begingroup\$

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!

\$\endgroup\$
7
  • \$\begingroup\$ What is your motivation for hashing this? \$\endgroup\$
    – Pikalek
    Sep 7 '16 at 20:03
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 7 '16 at 20:16
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 7 '16 at 20:19
  • 4
    \$\begingroup\$ 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? \$\endgroup\$
    – DMGregory
    Sep 7 '16 at 23:22
  • \$\begingroup\$ Your right @DMGregory :). I missed the part with "each piece type still has a unique zobrist number for EACH square". \$\endgroup\$ Sep 8 '16 at 9:19
2
\$\begingroup\$

Zobrist hashing is also used for the game Go. Since you basically have the same situation - each cell can only have 3 different states (black piece, white piece or empty), I wouldn't bother changing the standard algorithm other than modifying it for your board size.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.