A Chess forum. ChessBanter

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

Go Back   Home » ChessBanter forum » Chess Newsgroups » rec.games.chess.computer (Computer Chess)
Site Map Home Register Authors List Search Today's Posts Mark Forums Read Web Partners

Large Chess Variants and Type 1 hash table collisions



 
 
Thread Tools Display Modes
  #1  
Old August 26th 03, 05:55 PM
John Weathers
external usenet poster
 
Posts: n/a
Default Large Chess Variants and Type 1 hash table collisions

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

  #2  
Old August 26th 03, 09:52 PM
Harald Luessen
external usenet poster
 
Posts: n/a
Default Large Chess Variants and Type 1 hash table collisions

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

 




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT +1. The time now is 02:41 PM.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.Content Relevant URLs by vBSEO 2.4.0
Copyright 2004-2017 ChessBanter.
The comments are property of their posters.