Author: KarinsDad
Date: 09:11:25 01/23/99
Go up one level in this thread
On January 23, 1999 at 10:51:52, Don Dailey wrote: [snip] > >Hi KarinsDad, > >I am wondering if you knew that even if you doubled your hash >table size you only get about 6 percent node count reduction. >But we are not talking about 6 percent, we are talking about >being paranoid about what you do when your table is 95 percent >full. You are in effect seeking a solution (and apparently >willing to pay any cost) to make it possible to improve your >odds of finding a spare location in your table. And even this >only addresses (no pun intended) a very narrow range of time >controls, anything more and your table is full, less and your >table is fine. Really, you are talking about adding a lot of >baggage to your search to get perhaps a 1 or 2 percent node >count reduction. But the baggage itself is counter productive, >linked list reduce the number of hash table entries you will >get with a give amount of memory, and multiple probes will >more than likely eat enough processor time to kill any tiny >node reduction you get and probably any elaborate schemes you >can think of might be theoretically fun to work with >but useless. Remember, you are fighting for almost nothing, >1 or 2 percent. I think if I was going to use anything >more complicated than simple open addressed hash tables with >overwriting I would probably experiment with set associative >type of schemes. I think Bob may have used this in Cray >Blitz, you'll have to ask him for the details. The basic >idea (in case you do not already know this, forgive me if you do) >is that you partition your table entries into sets of n records >(try something like 4 or 8) and you confine your probes to these >entries. You might just sequentially look at these n records for >a hit, or an empty location if you are writing. But everything >I said applies here too, this at very most would be a minor >improvement if any at all. I have this recollection that there >was something different about the Cray (as told to me by Bob) >that made this scheme nicely workable on a Cray. I have experimented >with lots of stuff (just like you are proposing) and never came >up with anything better than KISS (keep it simple stupid.) > >A lot more interesting and beneficial is knowing WHEN to overwrite >an entry and when not to. This might gain you a lot because >some overwrite schemes can lose important information. The idea >of using 2 hash tables is an example of such an idea. I don't >know if you are using this idea, but it will gain you much more >than figuring out a way to find an empty table location on the >8th probe when your tables just happen to be about 95 percent full. > >You must have done some time tests right? What kind of data do >you have to report? Or are you just in the design phase and >considering your options? > > >- Don Don, Good input. It sounded like you were not responding to the system I am in process of using (posted elsewhere in this thread on a different branch). Since my nodes are so large (256 bytes) the linked list system does not take up a relatively large amount of space (compared to the other 248 bytes in the node). The problem I have is that my search algorithm is drastically different than anything I've read in the literature. Hence, for my program, it is more imperative to not overwrite nodes whenever possible. Since I am still in the design/code phase, I do not yet have a working model to take real legitimate tests from yet. I'm hoping for this within the next month, however, my partner and I are having difficulty getting together and working on it, so what we do work on separately tends to be more minor elements of the program. If you have read my other post, you would have noticed that I've basically solved the 95% full issue by putting a tree under the hash. This doesn't mean that the hash I put in place the first time will not give me the best distribution across the hash, it just means that with almost 4000 nodes per hash element (using a small hash table of 16K pointers, I'll probably need to increase this), I'm bound to get some reasonable amount of distribution. If I find that some elements only have a few hundred nodes and that others have 8000 or more (which on average is only 0.5 more probes for a search or delete and 1 more probe for an add), than I will search for a better algorithm to get a more even distribution. In my case, doubling the hash table (from 60MB to 120MB with a 750MB needed) will improve my program dramatically since my alpha nodes will take up 1 node out of 12 searched, my beta nodes will take up 1 node out of 3, and my non-quiescent nodes will take up 1 node out of 1. The bottom line is how often I run into each of the above. If I run into a lot of alpha nodes, I'm in good shape. I just won't know until I get it all coded, debugged, and tested against a variety of positions. The concept of knowing when to overwrite a position is one that I have put on the back burner. Once I get it up and running, I'll worry about improving it both heuristically and algorithmically (is that a word?). Thanks :) KarinsDad
This page took 0 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.