Author: Robert Hyatt
Date: 13:09:21 08/27/99
Go up one level in this thread
On August 27, 1999 at 15:36:23, KarinsDad wrote: >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 :) Not to mention the fact that you have to have a hash table big enough so that entries don't get overwritten? My xeon has 512mb, but that isn't _near_ enough to guarantee that I can keep everything... Sounds like overkill that will really slow you down, for minimal gain... but it is worth experimenting with...
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.