Author: Robert Hyatt
Date: 08:40:24 03/31/03
Go up one level in this thread
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.