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.