Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Storing the PV in a search routine

Author: Don Dailey

Date: 09:42:35 06/12/98

Go up one level in this thread


On June 12, 1998 at 07:02:57, Guido Schimmels wrote:

>
>On June 10, 1998 at 13:59:09, Bruce Moreland wrote:
>
>>...
>>I made a single array, which is sized at max depth squared, plus max
>>depth, all over two (   (D^2+D)/2   ).
>>
>>I made an another array of pointers into this array, there are max depth
>>pointers.
>>
>>I then initialized the pointers so that the first one points at element
>>0, the second one points at element D, the third points at element 2D-1,
>>the fourth points at element 3D-2, etc.
>>
>>The point is that each of these arrays needs one less element, because
>>the maximum length of the PV is shorter the deeper you already are.
>>Levy calls this a triangular array, which seems reasonable to me.
>>
>>I was being anal about memory at the time.  If you want, you can just
>>make an array that is D^2 and forget about it, it's not like we have to
>>worry about blowing RAM much these days, except with hash tables.
>
>>bruce
>
>Exactly what I was doing for years :)
>But  it has become obsolete, as I now get the PV from a special backup
>table. When I get a fail high/low on those positions later in the
>search,
>I will not erase this information, but will store the new score along
>with
>it's depth and move in additional fields of this special table, so I
>never
>forget which positions where PV once and often have two or three
>moves in the table to use for sorting.
>
>
>>Another thing is that if you fail high at depth zero, you can stick the
>>move you failed high on in the array, and then just terminate it at
>>length 1, so you will have return a PV of sorts if you are in a
>>fail-high state.
>
>>Remember also that your array length can be undefined if you fail low.
>
>>I actually spend some energy trying to make sure that what's in the
>array is something reasonable.
>
>>If I fail high on the move that had been the PV up until now, I don't
>>kill the old PV, I let it sit in there, so I can be sure to search it
>>first when I re-search.
>
>>Also, if I fail low, I keep the old PV around, since it's the best thing
>>I have.
>
>>If I fail high on a new move, then fail low on the re-search, I put the
>>PV from before the fail high back, but this is a serious decision and
>>some would argue that this is wrong, and this doesn't pertain directly
>>to this topic anyway.
>
>Example from my PV table:
>pv_score = 100
>pv_move = e2e4
>pv_depth = 5
>all_score = 80
>all_move = d2d4
>all_depth = 6
>cut_score = 90
>cut_move = e2e4
>cut_depth = 4
>
>In my example the question about move sorting is, try d2d4 first,
>which failed low last time, or e2e4 which was a PV move before that ?
>You have experimented with those kind of stuff as I can see from the
>above.
>Any Suggestions ?
>
>- Guido

Hi Guido,

I'm interested in more details about your backup table.  Is this
something separate from your hash table?  You use this thing to
implement a principal variation?   Is it similar to the common
technique of "walking the hash table" to get a PV?

- Don







This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.