Author: Don Dailey
Date: 14:02:06 01/23/99
Go up one level in this thread
On January 23, 1999 at 12:11:25, KarinsDad wrote: >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 Do you have any documentation? I am interested in anything drastically different than what you have seen in the literature. I would like to find out more about what you are trying. - Don
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.