Author: KarinsDad
Date: 12:36:23 08/27/99
Go up one level in this thread
On August 27, 1999 at 13:24:00, Robert Hyatt wrote: >On August 27, 1999 at 11:47:16, KarinsDad wrote: > [snip] >>> >>>There is one serious error associated with hashing: lack of path information. >> >>I don't have that problem. I have a list of parents in each hash node. However, >>this has the detriment of forcing me to back scores up all parent paths and the >>detriment of increasing the size of a hash node. You want to hear the music, you >>have to pay the piper. >> >>KarinsDad :) > > >I'm not sure what you mean by "a list of parents" unless you mean "parent >positions". Which means you miss a lot of transpositions... IE there are >lots of ways to reach the same position without having the same position at >the previous move... > >Did I misunderstand? I have a list of pointers to all other parent hash nodes found so far in the search which corresponded to this position. Therefore, I can back scores up the graph. So, in the position below, the last move could have been Nf3 or it could have been Nc3, but if the search engine found both of the two standard paths to this position, then it would have a pointer back to both parent positions. And the score gets backed up to both previous possible parent positions where one of the knights is on it original square (and yes, I realize that this position can be reached via a series of knight moves for white and knight and bishop moves for black, so there could be more than 2 pointers to previous positions). r n b q k b n r p p p p p p = p - = - = - = p = = - = - = - = - - = - = - = - = = - N - = N = - P P P P P P P P R - B Q K B = R Whenever the search engine finds a position in the hash table, it determines if a path from the current position to that position is in the list of pointers. If not, it is added. If so, then it means that this path has been searched before. Actually, there is a correspondence between moves and children pointers (see below), so I do not have to go to the hash table to figure this out. Everytime I go to the hash table, it is because I have not searched this move before from this position. I also have a list of children pointers in the hash table. So, when I remove nodes from the hash table, I use the children pointers to remove the parent pointers inside the child nodes (and potentially remove the child node itself and possibly it's children if this is the only parent to that child). Since it could require quite a bit of re-searching of the hash table to find all children, grandchildren, etc., it was just easier to suck up the space for the children pointers to speed up removal (this is the real memory hog, not the parent pointers, I might remove this in order to double the number of nodes in my hash table). The main detriment of this technique is that you could have a potential 200 or more bytes per hash node (in situations where you do not get cutoffs) due to having 4 bytes per child or parent more. This gets costly space-wise. It forces me to be smart about removing nodes (which I don't think I am yet). KarinsDad :)
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.