Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old May 28th 04, 02:10 AM
Shaun Press
 
Posts: n/a
Default Hash table percentages

Question: What is a good percentage of hash table hits during a search?
10%, 50%, some other number?

Details: My program does a standard (I assume) AB search with
null-moving (R=2) and iterative deppening. The hash table is 2^18 and I
am using 18 bit keys (eg table size in bits and key size are the same).
The only other quirk is that the first move at root is searched with a
window of (prev_score-100,prev-score+100) with the usual search fail
high, search fail low detections and researches. Subsequent moves get
searched with a window of (previous beta, previous beta+1) with a
research window of (beta+1, +infinity) for a fail high. A hash table hit
is one where the hash key and the checksum key match, although the
returned value could be a bound and not an exact score.
I am only getting between 7% and 12% hits from my hash table. This seems
low. Is there something wrong with my implementation of either my search
or my hashing?
  #2   Report Post  
Old May 28th 04, 10:34 AM
David Richerby
 
Posts: n/a
Default Hash table percentages

Shaun Press wrote:
The hash table is 2^18 and I am using 18 bit keys (eg table size in bits
and key size are the same).


With an 18-bit key, as soon as there are 2^9=512 positions in your hash
table, there's a greater than 50% chance that two of them have the same
key. (Google for "Birthday Paradox".) You do have some way of detecting
this, don't you? Storing the whole board structure in the hash table so
that you can detect collisions uses a lot of memory and a lot of time to
do the comparison; storing a 64-bit hash key in the table doesn't use up
much memory and the critical "greater than 50% chance of collisions" point
is sqrt(2^64) = 2^32 = approximately 4x10^9 positions, which is much
bigger than the size of the hash table.


Dave.

--
David Richerby Salted Technicolor Bulb (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a light bulb but it's in
realistic colour and covered in salt!
  #3   Report Post  
Old May 28th 04, 10:58 AM
Tommy
 
Posts: n/a
Default Hash table percentages


"Shaun Press" wrote

Details: My program does a standard (I assume) AB search with
null-moving (R=2) and iterative deppening. The hash table is 2^18 and I
am using 18 bit keys (eg table size in bits and key size are the same).


umh... why don't you use zobrist keys and the % operator?
A zobrist key is (usually) a 64bit key which can be incrementally and
quickly calculated from most board games.
"zobrist_key % number_of_elements" returns an index that will fall within
the allocated hash-table.

A hash table hit is one where the hash key and the
checksum key match, although the
returned value could be a bound and not an exact score.


yeah, because of the % operator, 2 different positions could map to the same
location in the transposition table. This is why you then need to store the
whole zobrist key as one of the elements in the hash table and compare the 2
zobrist keys to see if they are the same (the one you used to index the hash
table and the one stored in the hash table).

I am only getting between 7% and 12% hits from my hash table. This seems
low. Is there something wrong with my implementation of either my search
or my hashing?


7% seems not bad at all to me!
Well, it greatly depends on the board position. Some positions are full of
transpositions some others do not have many.
Also, a 7% is a lot if they are all exact matches and many of them occur in
the first plies (levels), in fact such a 7% would provide HUGE savings in
the search. A 7% where all the matches are on the last plies or even worse
leaves and maybe they are not even exact scores, well such 7% is not likely
to provide any savings.

Question: What is a good percentage of hash table hits during a search?
10%, 50%, some other number?


50% is a joke!
As I said, 7% seems quite a lot to me, so....

Remeber that a 7% hit-rate does not translate to 7% savings!
Assuming that the branching factor from your position is 30 and this
branching factor does not change during the search, and you are doing a 6
ply-search.
30^6 = 729,000,000 nodes to analyse.
now if at the first ply you find an exact match for 15 of the first 30
childs, so, you only have 15 hits, this translates to:
15*30^5 = 364,500,000
So, with a 0.000004% hit-rate you get a saving of 50% in the complexity of
the search, from 729,000,000 nodes to 364,500,000.

Of course the above example is very extreme, something like that is never
going to happen, but it should give you the idea.
A 7% of hits translate to 7% of savings only if those hits happen on
terminal nodes, leaves. Now, considering most of the nodes are leaves, a
good percentage of such 7% is likely to be leaves, but not all of them! A
couple of them might in the first 2 plies, many others from ply 3 to 5.

Have a look at: http://www.seanet.com/~brucemo/topics/zobrist.htm
and: http://www.seanet.com/~brucemo/topics/hashing.htm

Tommy


  #4   Report Post  
Old May 28th 04, 11:17 AM
Tommy
 
Posts: n/a
Default Hash table percentages


"David Richerby" wrote

With an 18-bit key, as soon as there are 2^9=512 positions in your hash
table, there's a greater than 50% chance that two of them have the same
key. (Google for "Birthday Paradox".) You do have some way of detecting
this, don't you? Storing the whole board structure in the hash table so
that you can detect collisions uses a lot of memory and a lot of time to
do the comparison; storing a 64-bit hash key in the table doesn't use up
much memory and the critical "greater than 50% chance of collisions" point
is sqrt(2^64) = 2^32 = approximately 4x10^9 positions, which is much
bigger than the size of the hash table.


Yes, exactly.
2^32 is 4 billion positions, which on most current computers translates to 1
hour of search (assuming 1M nodes/sec) and a transposition table of around
50GBytes in memory!!!
So.... it is more than acceptable (at least for now.... probably in 15 years
time it will not be!)

Using a 18-bit key is definately not acceptable, I forgot to mention that in
my last post (in which i suggested to use 64-bit zobrist keys). I am glad
you made that clear.

Tommy



  #5   Report Post  
Old June 1st 04, 05:11 PM
Vincent Diepeveen
 
Posts: n/a
Default Hash table percentages


"Shaun Press" wrote in message
...
Question: What is a good percentage of hash table hits during a search?
10%, 50%, some other number?


in diep about 4% of the probes give a cutoff, heavily depending upon
position.

using 64 bits zobrist would be wise instead of 18+18.

Details: My program does a standard (I assume) AB search with
null-moving (R=2) and iterative deppening. The hash table is 2^18 and I
am using 18 bit keys (eg table size in bits and key size are the same).
The only other quirk is that the first move at root is searched with a
window of (prev_score-100,prev-score+100) with the usual search fail
high, search fail low detections and researches. Subsequent moves get
searched with a window of (previous beta, previous beta+1) with a
research window of (beta+1, +infinity) for a fail high. A hash table hit
is one where the hash key and the checksum key match, although the
returned value could be a bound and not an exact score.
I am only getting between 7% and 12% hits from my hash table. This seems
low. Is there something wrong with my implementation of either my search
or my hashing?



Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Which pawn positions go into a pawn hash table? pd42 rec.games.chess.computer (Computer Chess) 9 June 1st 04 05:21 PM
hash table collisions Paul Rushmer rec.games.chess.computer (Computer Chess) 21 April 1st 04 10:25 AM
Chessbase engines loses so easy! kostas_1966 rec.games.chess.computer (Computer Chess) 14 November 5th 03 11:57 PM
Large Chess Variants and Type 1 hash table collisions John Weathers rec.games.chess.computer (Computer Chess) 1 August 26th 03 08:52 PM
Hash Table and Quiescence Search Jih-tung Pai rec.games.chess.computer (Computer Chess) 4 August 25th 03 04:59 PM


All times are GMT +1. The time now is 11:00 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017