Author: Robert Hyatt
Date: 17:11:00 11/22/00
Go up one level in this thread
On November 22, 2000 at 15:46:53, martin fierz wrote: >On November 22, 2000 at 13:58:28, Robert Hyatt wrote: > >>On November 22, 2000 at 12:28:05, martin fierz wrote: >> >>>On November 22, 2000 at 10:06:24, Robert Hyatt wrote: >>> >>>>On November 22, 2000 at 05:38:32, martin fierz wrote: >>>> >>>>>hi, >>>>> >>>>>i was wondering about this PV-hashtable thing: in my checkers program, i do not >>>>>generate a separate PV. i have two hashtables, a 'shallow' and a 'deep' one, >>>>>positions close to the root of the tree are stored in shallow, the rest in deep. >>>>>in shallow, i take care not to fill the table and not to overwrite entries. i >>>>>took this idea from the crafty source code. in deep i overwrite everything >>>>>without looking twice. question: i have no PV, but i have a guarantee that for >>>>>the first 10 ply i have a hash move - because thats about what fits in shallow. >>>>>for the next 10 ply i won't have a hash move. do you think that this is a >>>>>serious problem? should i be generating a PV and stuffing hash moves back in the >>>>>table (that surely costs some speed...)? typical search depths are 15-19 ply in >>>>>a couple of seconds. do these last 5-9 ply really matter? >>>>> >>>>>cheers >>>>> martin >>>> >>>> >>>>They are often important for debugging, more than anything else. IE the goal >>>>is to play the right move. Nothing says you have to have the right PV, when >>>>playing a game. But if you can't see the PV when testing, you have a harder >>>>problem to understand what is going on and why. >>>> >>>>DB didn't have a separate PV because the hardware didn't support the idea. They >>>>seemed to play just fine. So yes, it can work... >>> >>>thanks for the answer. of course i can get a PV from the hashtable this way, as >>>long as the position is still in the hashtable, which it is for the first 10 >>>ply. but i see what you mean, i could get the whole PV to see which position >>>determines the final evaluation and also to see if the quiescense search is >>>performing properly. i suppose i should implement it :-) >>> >>>cheers >>> martin >> >> >>Remember that hashing is all about probability and distribution. There is >>absolutely no guarantee that you will get all 10 PV moves for ply 1 through >>10, even if you have 1 million entries in that hash table. You can still get >>overwrites that clobber the positions. The larger the tree, the greater the >>probability that your PV will come up 'short' on occasion. > >this is true if you overwrite your entries. in the hashtable for the positions >close to the root i avoid overwriting and in case of collisions do some ugly >stuff which puts the colliding position in another place, where it can be found >again. of course there is still a minute probability that more positions than i >thought would get the same hashkey, but that is really small. Think about this... as you search thru the first 10 plies, you can change your mind on PV moves _many_ times. How can you _guarantee_ that you don't overwrite one, unless you set up a big linked list? A 10 ply search can traverse a _bunch_ of positions... with a lot of potential PV moves at the upper plies in that range... I'm not sure how you can be certain you don't overwrite one. I have the opposite problem.. when you get a hash hit, the PV stops at that point since nothing below that node gets searched, and the hash entry doesn't contain the pv to go with the position... I dislike that when debugging, but there is no reasonable solution.
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.