Hi Zaidgs,

Storing the hash data works as follow:

Make a really really big array. Your first 64-bit key with be an index in to this array. You'll have to use a modulous or bit-mask to make the index fit properly.

i.e. index = keyA % sizeOfHashTable;

Each element in your array will hold the following information:
long long keyA;
long long keyB;
long score;
long depth;
char type;

type is the type of score the hash represents (upper limit, lower limit, or exact). depth is the depth of search the score represents. keyA and keyB are obviously your keys.

Forget vectors.. Use a statically allocated array. Yes, it will be huge. This is normal. I read in a paper somewhere the every time you double the size of your hash table, you can expect a 7% increase in speed; This is not something I've independantly confirmed.

Hash table bugs are hard to track down. The following method will help ease you in slowly, letting you verify the basics work properly.


1. Create a set of test cases. Record the first eight moves of a game, along with the scores the computer is assigning to each move on the first ply. Do this for several games.

2. Create some simplified test cases-- these are positions that have very few pieces, and exhibit unusual conditions; i.e. Castling, En-Passant, Check-mate, and stale-mate. Record the moves, and and important scoring details as in 1. etc....


Now that you are armed with test data:

1. Implement the key generation. That is, for each move generated a corresponding hash key pair is generated.

2. Just AFTER you call your evaluation function, store the result in the hash table. The depth will be 0 and the hash type will be exact.

i.e.

myScore = StaticEvaluation ( board);

myHashTable[board.keyA % kHashTableSize].keyA = board.keyA;
myHashTable[board.keyA % kHashTableSize].keyB = board.keyB;
myHashTable[board.keyA % kHashTableSize].depth = 0; // for now
myHashTable[board.keyA % kHashTableSize].type = kHashExact;
myHashTable[board.keyA % kHashTableSize].score = myScore;



3. Just BEFORE your evaluation, check if there is a hash entry. If so, extract it. Run your evalation, and compare the evals score to the hashed score.. If they are different throw up an error.

Now you're ready to test.

Run through your test suites. If you get your scores-are-different error then you have a bug and must fix it.

Make sure the exact same plays, for the exact same reasons, are made. If they are not, you have a bug somewhere, and you must find out why the numbers do not match.

Be sure to check castling, check, check-mate, stale-mate, and en-passant. This WILL come back to bite you if you're not certain it's working...

At this point you are simply verifying the hashing algorithm.. Once you are certain it is working you can have it return the score from the hash table instead of calling your evaluation function. Re run your test suite.. It should still play exactly the same way as without the hashing, as we're not yet skipping anything except the evaluation.

Once you are certain this is working, you can implement the full gamit of hash optimizations. My memory is not good enough for me to explain everything right now... From this point on your game may or may not play the same way, which is normal, but this is best left for another topic.

Good luck,
Will


P.S. Hash tables are not perfect. Things like stale-mates and check-mates are bound to screw it up for you, since they are usually dependant on the current move-number... The hash table is not aware of this so you will need to handle these things carefully.

In the checkers engine that i am making, i will be using the following for its transposition tables.

it uses two hash tables, one contains the score for an entire tree, the other contains the score for a leaf.

When it is ready to recur(is that the right word?) to explore the subtree it does a check of treehash. if it did not contain an entry then it adds it afterwoods.

When it is checking the leaves, it goes and checks leafhash before evaluating (i will most likely be using a quite slow pattern matching evaluation function so it would be well worth it). if it does not already exist then after evaluation it adds the entry.

Now heres a little thing that i think is nifty: for each subtree in the hash table, i store its score, its activity, its ansesters (going from it back to the root), and array indexes to where all of its leaves (which could also be subtrees) are stored in the hash table.

Now before the search i go through the entire subtree hash table (i need to figure someway to stop this, doing this for a 1k hash table is ok, but for a table going into the 2+ megs...)
Now for each subtree i mark it inactive (hash.active = 0)

Then after the search i go over it again, if hash.active = 0 then it is removed. that way i get to reuse most of the tree between searches!

Then again what works for others may or may not work for you.

One is glad to be of service in the first day of the ninth memenium (9000 days since january 1 1980).
DENC

Zaidgs: I had that same question not long ago. In this forum:

Subject:
Hash table use in Chess Quiescence Search

Link:
http://www.gamedev.net/community/forums/topic.asp?topic_id=229888


Glad to hear your hasing is up to snuff.. Did you run in to any problems?

Good luck,
Will