Re: Hash Tables??
[ WinBoard Forum ]
Geschrieben von: / Posted by: Dann Corbit at 01 August 2001 21:24:11:
Als Antwort auf: / As an answer to: Hash Tables?? geschrieben von: / posted by: Saif Murad at 01 August 2001 21:11:22:
>I know Chess programs use hash tables but what exactly are they? What do they do?
A hash table is a data structure used to find things quickly.
Here are some explanations about how they work:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html
http://www.math.grin.edu/~stone/courses/fundamentals/hash-tables.htmlIn chess, they are used for several important tasks. Imagine you are calculating which chess move to make. I might move my knight first, and then my rook. Or I might move my rook first and then my knight. If the intervening move by the opponent is the same, then both end positions will be identical.
Chances are good I will have done extensive calculations to find out the value of the chess position. It would be a shame to have to calculate it again if I have already performed the calculation, as it takes a lot of computer time.
What hashing is used for in this situation is a quick lookup of work that has already been accomplished. I will store a calculation in a table, along with a "hash key". This hash key will be performed by some rapid operation that creates a sort of "unique signature." When I am wondering if I need to perform an operation or not, I can produce the "hash key" for the current position. Then I look into my table to see if that key is already stored there. If the key is stored in the table, I will look at how good the answer in the table is. Is the answer deep enough already, so that I don't need to recalculate? If it is, I just get the data from the hash table instead of calculating it all over again. This is a very big time savings.
Besides pieces, pawns are usually hashed as well. Since hash tables are a very generic data structure, they can easily be used for other things in the chess program as well. Hash tables offer a very large improvement to program speed. If your program does not use hash tables, it will not be able to rise out of the bottom 1/2 of chess programs. We can consider hash tables to be a fairly necessary feature for a good program.
Does this answer your question?