Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: How important is a big hash table? Measurements... (here is my data)

Author: Vincent Diepeveen

Date: 09:23:39 03/31/03

Go up one level in this thread


On March 31, 2003 at 11:40:24, Robert Hyatt wrote:

i do not know who is the poppycock fairy tale teller here who says: "this is
impossible". just do effort and perhaps you'll figure out how too.

>On March 31, 2003 at 10:01:34, Vincent Diepeveen wrote:
>
>>On March 30, 2003 at 21:57:54, Robert Hyatt wrote:
>>
>>>On March 30, 2003 at 14:09:33, Tom Kerrigan wrote:
>>>
>>>>On March 30, 2003 at 10:50:44, Robert Hyatt wrote:
>>>>
>>>>>Now I hope you will choose to dump that "this disproves the hyatt claim"
>>>>>stuff, you clearly didn't disprove _anything_...
>>>>
>>>>I was of course referring to:
>>>>
>>>>"The simple rule is that the hash table needs to be at _least_ large enough to
>>>>hold the entire tree."
>>>>
>>>>Don't you think the word "need" is a little strong in this situation? I mean,
>>>>chess programs work fine without huge hash tables, so maybe they don't "need"
>>>>them.
>>>
>>>From a simple theoretical point of view, the hash table is used to do two
>>>things.
>>>
>>>1.  Avoiding searching duplicate sub-trees once a single position has been
>>>searched fully;
>>>
>>>2.  grafting information from one part of the tree to another, which rather
>>>than speeding the search up, makes the search more accurate.  For example,
>>>you can't solve fine 70 without this particular aspect since the solution is
>>>26 plies deep but we all find it at a significantly shallower depth than that,
>>>but only if we have hash tables.
>>>
>>>As a result, it is _possible_ that any position you store is a "key" position,
>>
>>That is a matter of a good replacement algorithm. It is impossible that diep
>>loses 'key' positions just like that. Chance is near zero that a key position
>>gets overwritten just like that. Especially if depth is like 3 ply left to go,
>>this is practically hardly possible considering the 8 probes i do.
>
>That is poppycock.  There is no way to recognize a "key" position with 100%
>accuracy, and that is a well-known problem without a solution.  Depth is a
>good indicator of worth, but it is not the _only_ indicator.
>
>
>
>>
>>>and if you can't hang on to it long enough, either (1) or (2) (or both) will
>>>not happen, and the tree you search will be larger or less accurate (or both)
>>>than it could be.  The only way to be _sure_ you don't lose something important
>>>is to have a table large enough to hold everything you store.  Anything less and
>>>the probability increases that critical information gets overwritten.  So for
>>>_optimal_ results, holding the entire tree is best.  It is likely that less
>>>hash table memory will still produce good results, but on occasion it will not
>>>produce the best results.  The data I posted shows one example where a bigger
>>>table produces a more accurate result on one of six positions.  Without the
>>>key entry (or entries) that get overwritten with smaller sizes, the search
>>>result is less accurate.  With more space, the real (better) score is found.
>>>
>>>So while it might be reasonable to quibble about whether the entire tree needs
>>>to be stored in the normal case or not, it is intuitively obvious that if you
>>>_can_ do that, you will get the best possible result.  Whether this result is
>>>as good as, or worse than, the result you get from smaller tables is another
>>>issue with probability analysis involved.
>>>
>>>
>>>
>>>
>>>>
>>>>I notice that you didn't present any data on how much of the search tree was
>>>>being stored in the hash tables, and without that data you obviously can't point
>>>>to a significant performance increase when the entire table is stored, so I
>>>>don't see that you even touched on the issue, much less proved it or disproved
>>>>it.
>>>>
>>>>-Tom
>>>
>>>I believe _did_ give as much info about how much of the tree was stored, as I
>>>possibly could.  Based on table size vs search space size.  All I can't be
>>>sure of is what percentage of the search space is q-search which doesn't impact
>>>table entries at all.
>>>
>>>However, it is likely that looking down the numbers, you see that the larger
>>>the table, the better the search, whether the improvement is significant or
>>>not.  Better is _still_ better.  And in some cases, better == much better, as
>>>in the bt2630 position 6 that a larger table produces a better score on.



This page took 0.01 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.