Author: Robert Hyatt
Date: 05:27:05 01/14/99
Go up one level in this thread
On January 14, 1999 at 01:39:16, Horace Ho wrote: >Questions again, thanks for your time :-) > >1. How big a hash table is meaningful? What's the > typical ratio between: > a) average total numbers of node my program can > search each turn, and > b) the total number of hash records? this is an easy one. If you ignore repetition draws, 50 move draws and EXACT score hash hits (all of which should cause Search() to exit quickly without storing a new hash entry) then all of the remaining positions should be stored, because _every_ exit from Search() should store the result of that search. If you search 100K nodes per second, and you are going to search 1 minute, you need at least 6M hash entries to be sure you don't overwrite anything that you might need later. And since we are talking about 'hashing' you should double or quadruple this, because the hash signatures are _not_ uniformly distributed over the entire hash table, unfortunately. take your NPS, multiply by the longest search you expect to do, then multiply by some constant since there is no guarantee that you will generate hash addresses that are all unique. > >2. What are stored in each hash record? > - id > - score > - ... and? hash signature (bits not used to index into the hash table) so that you can detect collisions... where two entries with different signatures hash to the same table entry. draft... the depth of search below this position, so that you can tell whether an exact score or bound result is usable. best move for move ordering. other flags as needed like 'this position was threat-extended before, so let's always threat-extend it'. > >3. What's the typical size of each hash record? In Cray Blitz, we got by with 12 bytes, in Crafty, I am rather sloppily using 16 right now, but 8 of that is the full hash signature, which is not really needed... storing 32 bits of the hash signature is probably more than enough if the other 32 bits are used to generate the probe address. > >4. What to do if 1a) is bigger than 1b)? > - throw away some records? or... ? > do what is done everywhere... ie size(memory) >> size(L2 cache). So you try to figure out which positions (entries) should be kept and which should be overwritten. > Is it already meaningless to have a hash table > if 1a) > 1b) ? > >5. I keep hearing Zorbrist. Could someone put me to > the algorithm (or better a c implementation)? > assume pieces are 1=white king, 2=white queen, ..., 6=white pawn, 7=black king, 8=black queen, ..., 12=black pawn, and an empty square has a 0. create an array random[64][12] full of 64 bit random numbers. To compute the zobrist hash signature you do this: signature=0; for (sq=0;sq<64;sq++) if (board[sq]) signature^=random[sq][board[sq]-1]; and that's it. It is neat to notice that you don't have to do this all the time, just once. Then if you move a knight from g1 to f3, you do this to incrementally update the hash signature: signature^=random[g1][white_knight]; signature^=random[f1][white_knight]; and you are done. >Thanks again >horace
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.