Author: Robert Hyatt
Date: 18:57:54 03/30/03
Go up one level in this thread
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, 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.