Author: KarinsDad
Date: 10:34:31 01/22/99
Go up one level in this thread
On January 22, 1999 at 13:05:51, Eugene Nalimov wrote: >On January 22, 1999 at 08:52:52, Robert Hyatt wrote: > >>On January 22, 1999 at 00:31:40, KarinsDad wrote: >> >>>On January 21, 1999 at 23:46:27, Robert Hyatt wrote: >>> >>>>On January 21, 1999 at 19:04:21, KarinsDad wrote: >>>> >>>>>On January 21, 1999 at 12:37:32, Heiner Marxen wrote: >>>>> >>>>>[snip] >>>>> >>>>>> >>>>>>Another method (which I happen to use) to avoid bucket overlaps >>>>>>is ``quadratic rehashing´´. Instead of using a constant increment, >>>>>>we linearly increase the steps: inc=1,2,3,4,5,... >>>>>> >>>>>>XX.X..X...X....X >>>>>>.YY.Y..Y...Y....Y >>>>>>..ZZ.Z..Z...Z....Z >>>>>> >>>>>>Also, the slots of a bucket are still somewhat nearby, which is good >>>>>>for cache locality. >>>>>> >>>>>>Knuth seems to not mention this method, and I do not remember where >>>>>>I found it, so I cannot give a reference. >>>>>> >>>>>>Heiner >>>>> >>>>>I like this. I think I'll try this out. However, I think it needs a modification >>>>>due to the following possiblity: >>>>> >>>>>XX.X..X......... >>>>>YY.Y..Y...Y..... >>>>>ZZ.Z..Z...Z....Z >>>>> >>>>>Thanks Heiner :) :) >>>>> >>>>>KarinsDad >>>> >>>> >>>>Just note this will kill a PC. Because it fetches 32 byte lines from memory in >>>>a burst cycle. for best performance you should use all those 32 bytes since you >>>>had to wait on them. If you do anything else, you will end up hitting one line >>>>per probe with a big cache miss penalty for each probe. >>>> >>>>This only works on architectures like the Cray where memory is organized a lot >>>>differently with no cache of any kind... just high sustained thruput.. >>> >>>Robert, >>> >>>Thanks for the input. >>> >>>I have been thinking about this method a little bit this evening and although I >>>came up with some good ideas, I keep pounding into the problem of 95% of the >>>hash is full, how can I continue to find open slots without overwriting the >>>nodes (for my program, this would currently be more preferable)? >>> >>>It may not be solvable this way, or at least not in a reasonable amount of time. >>> >>>On the other hand, each of the solutions in this thread seem to run into that >>>problem to some extent. >>> >>>KarinsDad :) >> >>You can't go very far here. Because you probe at _every_ node in the tree. If >>you make your probe 10x slower by looping, you will _really_ feel the slow-down, >>and it isn't clear that getting too cute is important, when you can buy a gig of >>memory for about $1,000 now... > >That depends. Not every chess program user can afford to buy 1Gb >of RAM. And must popular motherboards will not accept that much. > >Based on my experience, all depends on how fast you can fill your >hash table. As soon as it's *totally* full, more complex replacement >schema can be better, even if it causes some nps degradation. > >As long as program has a lot of RAM, and plays mostly blitz (or fast >enough games), simple schemas must be Ok. Let's take Crafty as >example (all numbers are very crude approximations): its' current >speed is ~1Mnps. As you don't cache q-nodes, it has to store 500K >positions per second. So, when time control is "move in 10 seconds", >you have to store max 5M positions. That's only 40Mb. I think that >serious degradation will start when you'll have to store 10 times >as much positions as you have hash entries. So, on your machine you >probably will be Ok even for games with standard time controls, if >you'll allocate 128Mb for hash. > >Average Crafty user has much smaller hash. From the other side, >his/her nps is much less, too... > >So for current machines you can be right... But if you'll try to >play 1-to-100 match again, or run your program on WinCE (reasonable >fast CPU and 2Mb of RAM), more complex hash management will be Ok. > >Eugene Yes, these are considerations that I had to make when designing my program. My theory is that it should run well on average systems from the last few years in standard tournament speeds (e.g. 40 in 120, rest in 60). My personal view is that although blitz chess is fine for a fun game, it's a game of who can swindle who the quickest. Blunders are the name of the game. It's next to worthless to play it against a computer, even if you crank the program down a lot (for most players). So, my initial design goals were to create a good sized hash as my "maximum" (such as 32MB), and then attempt an implementation that would "fit" within that maximum with a minimum of overwrites or replacements of nodes. If my program plays lousy chess against other programs in blitz, but plays strong chess in slower times, then I have still achieved one of my design goals. Regardless of how I program it, it should still play a fair blitz game against humans (i.e. me). 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.