Hello,

I did a search on this group for information concerning hash tables
keys and collisions, and most people seemed to argue that while a
32-bit key will result in many dangerous type 1 collisions, a 64-bit
key should drive this to an acceptable level of risk.

I am writing a program that will play several variants of the Japanese
game Shogi, an Eastern cousin of chess that is played on a 9x9 board.
One of the variants that I am supporting in this program is the 12x12
game of Chu Shogi, which has 30 different types of pieces.

I have encountered a problem where my program dies from attempting to
search an illegal move, and after much debugging, the problem seems to
stem from retrieving a "best move" from the transposition table when a
type-1 collision has occurred. Still, I am amazed at this considering
that I am using two 64-bit keys (thus, really a 128-bit key) to
distinguish between board positions.

I am wondering several things:

1) Am I right in thinking that 64-bits should not be enough for larger
games such as Chu Shogi?

2) If 128 bits is not enough, then what would be enough for Chu Shogi?
Perhaps, 12x12 = 144 bits?

3) Do chess programs really just assume that no type-1 collisions will
occur?
If not, then how can I guard against type-1 collisions? Storing a
complete board representation is not possible because of the need for
relatively small hash entries. Checking for legality before attempting
to use a best move seems like it would be rather costly in
performance...

Any advice would be greatly appreciated!

Sincerely,

John Weathers

On 26 Aug 2003 (John Weathers) wrote:
Hello,
[64 bit hash, Shogi, ...]
I have encountered a problem where my program dies from attempting to
search an illegal move, and after much debugging, the problem seems to
stem from retrieving a "best move" from the transposition table when a
type-1 collision has occurred. Still, I am amazed at this considering
that I am using two 64-bit keys (thus, really a 128-bit key) to
distinguish between board positions.

Don't trust the hash move. Test it.

I am wondering several things:

1) Am I right in thinking that 64-bits should not be enough for larger
games such as Chu Shogi?

No, I think, 64 bits are enough. Even if there are a million
times more theoretical positions represented by the same hash
value, most of them do not occur in the particular game.

2) If 128 bits is not enough, then what would be enough for Chu Shogi?
Perhaps, 12x12 = 144 bits?

Somebody once counted or guessed the number of possible chess
Positions. Say it would be 2^128 because a position can be
stored in about 16 byte. Then there are 2^128/2^64 = 2^64
collisions for each hash key. That is fine for chess.
Do the same calculation or guess for your game and for
a similar chance you get the number of bits with
#positions/2^64 = 2^bits.

3) Do chess programs really just assume that no type-1 collisions will
occur?

Yes. The advantages are bigger than the rare theoretical
errors. I don't know the real numbers, but let's assume
the number of searched positions in the game is
100000*3600 = 2^28 (100000 nodes per second for one hour).
That is nothing compared to 2^64 hash keys.

If not, then how can I guard against type-1 collisions? Storing a
complete board representation is not possible because of the need for
relatively small hash entries. Checking for legality before attempting
to use a best move seems like it would be rather costly in
performance...

But that is what chess programs do. Either the moves are
generated first and the hash move has to be in the list
or the hash move is tested explicitly. This adds a few
more 'bits' to the hash key because the hashed position
is not the real position if the hash move is impossible.

It is strange. We believe that hash collisions never occur
but the correctness of moves and board integrity is even
more important.

Harald