Author: Robert Hyatt
Date: 10:41:09 03/31/03
Go up one level in this thread
On March 31, 2003 at 12:23:39, Vincent Diepeveen wrote: >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. _I_ don't use the word "impossible" very often. You, on the other hand use it nearly every time you write something. perhaps you should "just do effort and you'll figure out how to" yourself?? "That is impossible and I can proof it." --vincent diepeveen, 1996 through 2003, various citations. By the way, since your comprehension is impaired somehow, "That can not be done with 100% accuracy" does _NOT_ mean "that is impossible to do." There _is_ a difference in the two statements. Figure out what the difference is and you'll understand a _lot_ more of what goes on here. > >>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.