Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: triangular pv vs. hash move pv

Author: Stuart Cracraft

Date: 12:03:02 09/11/04

Go up one level in this thread


On September 11, 2004 at 10:16:33, Robert Hyatt wrote:

>On September 11, 2004 at 01:03:37, Stuart Cracraft wrote:
>
>>On September 11, 2004 at 00:39:57, Michael Henderson wrote:
>>
>>>On September 11, 2004 at 00:08:20, Stuart Cracraft wrote:
>>>
>>>
>>>>Which should I trust? Seems like the hash table is getting
>>>>overwritten with other variations (not sure why). What
>>>>kind of scenario would cause that? My algorithm is
>>>>length >= depth to replace.
>>>
>>>You should always trust the triangular array...since nothing funny is happening
>>>there.  Hash table moves may vary based on depth for the entry.
>>>
>>>>Seems like triangular would be better and then use that to
>>>>prefill the hash table from the last iteration before the
>>>>next iteration would be best, as Bob Hyatt mentioned.
>>>
>>>it works well :)
>>>
>>>>In looking at both pv's, they look fine and lead to positions
>>>>that are often equal in material without any gross material errors that
>>>>could be attributed to a misimplementation but there are definite
>>>>differences between the two methods for me.
>>>
>>>You have it working correctly
>>>
>>>>Before I throw out the walk-the-hashtablepv, I want to be sure
>>>>that it is really no good. So I want to know exactly how a hash
>>>>table can be damaged such that its PV is corrupted. Under precisely
>>>>what circumstances can this happen?
>>>
>>>Hyatt mentioned extensions having something to do with this...i forgot what is
>>>was though.  What I figured out is that since the hash table does not store path
>>>info, you might start getting stupid moves because the entry is not true to the
>>>position in the PV.
>>>
>>>
>>>>I would have thought length >= depth would have prevented it as long
>>>>as there are no collisions. My hashkey is 64-bits and I am searching
>>>><1M nodes per move for my 1 second searches so I'd expect no collisons.
>>>>Should I have some hook in there to check the collisions aren't happening
>>>>and are causing damage to the pv or is there another hash table side
>>>>effect that results in that damage?
>>>
>>>I don't think you should worry about this since it's very rare :)
>>>
>>>Michael
>>>
>>>>
>>>>Thanks all,
>>>>
>>>>Stuart
>>
>>Michael,
>>
>>Well, here's the result. Two runs on Win-at-Chess at 1 second per move
>>on a P3. The compilation flag UTM is with the triangular array and
>>its entry taken as the best move.
>>
>>Walking the Hash for best move/pv:
>>+ 6.78/27.44 81% 243/300 250.06 74259544 247532/1/296973 0/855173/1429928/507556
>>/17118632/97735
>>
>>Triangular Array for best move/pv:
>>+ 6.78/23.28 82% 248/300 250.70 73645824 245486/1/293757 0/851605/1423773/506165
>>/17084388/98392-DUTM
>>
>>The bottom line is that 5 more positions got solved with the
>>triangular array method than for walking the pv in the hash table.
>>
>>5 positions is a lot since progress has become slower.
>>
>>This is proof enough for me though I hope to hear the specifics from
>>Bob Hyatt of how a hash table can get trashed if there are no collisions
>>and length >= depth for replacement algorithm is used which would seem
>>to all guarantee that nothing worse for the same position would ever be
>>stored. Obviously it's something in the tree that I can't see.
>>
>>Good stuff.
>>
>>Stuart
>
>
>You overwrite for many reasons.  you overwrite P when new draft is >= old draft
>I assume.   You overwrite P when position Q has the _same_ low order bits and
>maps to the same table location as P.  It is simply unreliable if you want an
>accurate PV and/or completely optimal move ordering between the PV of one
>iteration and the first moves searched on the next iteration.

That is true for me as long as your draft is my length.

Sune recommended replacing my replace if length >= depth with
replace always. I did this and the result bumped up dramatically
by a little over 2% on my standard test. I had never tested replace
always strangely. Just a 1-tier table presently. In a 1-tier it
seems that recency is more important than deeper depth. I had
always assumed the latter.

I am going to switch to using the triangular pv array exclusively
for everything this weekend. The hash table requires too much
management for PV handling.

Since the PV table went in for final move choice after the search
(pv[0][0]) instead of hash and the hash table algorithm made
replacement always algorithm, instead of length >= depth, nice
bump in results.

Another jump maybe when my insidepv() routine is modified to use pv[][]
instead of the pre-walked hash before the current iteration starts, and
prefilling the hash with pv[0][*] prior to the next iteration.

So that all helps a lot. Wasn't expecting any of this. Another nice
surprise.

Stuart



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.