Author: Guido Schimmels
Date: 03:46:54 06/15/98
Go up one level in this thread
On June 12, 1998 at 12:42:35, Don Dailey wrote:
>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
Yes, it's a separate table. I have three kinds of tables:
1. depth priority replacement table
2. always replacement table
3. PV table
When I want to store a position of type PV, I will store MAX_DEPTH+1
instead of the real depth in my depth priority hashtable. Then I have a
index
for my PV table I set to zero before every search. This index I store
in my hashtable as well instead of bestmove and score.
(implemented as a variant record). Then I will store depth, bestmove and
score into PV_table[counter] and finally increment the counter.
struct PV_table {
hashkey
pv_score
pv_move
pv_depth
all_score
all_move
all_depth
cut_score
cut_move
cut_depth
}
When I lookup the hashtable, I do as follows:
if((Depth(table) == MAX_DEPTH+1) {
pv_table = & PV_table(Index(table)];
...
}
else {
/* ALL or CUT */
}
When a PV position changes into CUT or ALL next time, I will not remove
this position from the PV table, but fill the appropriate fields (see
the above
struct) of the table.
Thus I will never loose a PV position *and* I will not forget which
positions
where PV one time before during the current search *and* I will often
have
more than one move for sorting for these crucial positions.
If you use aspiration windows, the PV table can be small, if you use
null windows (PVS ...), it can be even smaller. I make it big enough
to allow a search time of one hour to fill.
If it's full I overwrite positions with:
'cut_depth > pv_depth || all_depth > pv_depth' (which is the vast
majority).
One additional gimmick of this backup table is, I can output it as a
tree,
giving me some more insight about the search.
- Guido
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.