Author: Vincent Diepeveen
Date: 07:01:34 03/31/03
Go up one level in this thread
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. >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.