Author: Bruce Moreland
Date: 10:30:25 12/27/02
Go up one level in this thread
On December 27, 2002 at 03:11:29, Russell Reagan wrote: >On December 27, 2002 at 02:52:43, Bruce Moreland wrote: > >>I suggest that the best way to do this is to make a small hash table and insert >>hash keys of previously seen positions into it when a node is entered, and >>remove them with the node is left. >> >>The table does not need to be large, since depth of search is not infinite. A >>small table won't blow cache. >> >>It can be large enough that collisions are rare. Collisions are handled by >>moving to the next element, anyway. > >What do you mean by "Collisions are handled by moving to the next element"? This >is where things get unclear for me. I understand how a hash table works, how the >keys are generated, how you index the array with a portion of the key, and so >on. But when people start talking about "replacement schemes" and "I use an >8-probe method" and other similar statements like yours above, I get lost. Maybe >now is a good time to get all of that straight. Would you mind explaining? I don't remember the technical term for this kind of table. The main transposition table is huge. This is not the main transposition table. This is a small table. In order to insert an element, you index into the table, and if the element there is empty, you put your key there. If the element is not empty, you see if the next element is empty, and if so you put it there. Because of the 50-move rule and the reality of finite search depth, you aren't likely to have very many live elements in the table at any one time. As long as you make your table a few times bigger than it needs to be, you won't end up filling it, so it will always be possible to find an empty element. When you exit a node, you apply the same process in reverse to remove the key. bruce
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.