Author: KarinsDad
Date: 22:10:01 02/27/99
Go up one level in this thread
On February 26, 1999 at 15:18:07, Dann Corbit wrote: >On February 26, 1999 at 15:00:11, Bruce Moreland wrote: > >> >>On February 26, 1999 at 14:02:28, Dann Corbit wrote: >> >>>I have a notion about hashing I thought I might toss out. >>> >>>If you took (say) a 20 bit hash to create a million element table, those table >>>entries could be LRU caches instead of just lists. Each LRU cache would keep >>>the hottest entries on top, and the old ones would get flushed to disk. My >>>notion is to create a permanent hash file of (x) terabytes. I know that >>>conceivably, it would rapidly grow to infinite size. I doubt if that is >>>practially the case, however, since the real number of chess positions examined >>>in games is definitely very finite. >>> >>>Dumb idea? I know disk is thousands of times slower than ram, but if cache hits >>>were high it seems it might be a good idea [probably need a few hundred megs of >>>physical ram to make it practical]. Basically, you would never have a hash >>>collision. Either the position is there calculated already or it is not, and if >>>not, then you calc it and save it. Dann, I doubt this would work. The reason is that you would be spending so much time saving info to the hard disk that you would not have enough time to calculate (granted, some calculations would merely be a hard disk lookup). Why don't you give it a try with a much smaller sample set? You would probably have to modify your program so that it searched a lot fewer nodes (and in return would be a much weaker program), but the intent is to test out the idea. Possibly, time could be saved by saving some nodes to disk while it's your opponent's move (i.e. for learning). KarinsDad :) >> >>I don't think this would work for beans. If you play a game, your hash table >>eventually fills up. If you play another one, it fills up, but with different >>stuff. The entries are shared, but the positions are radically different. >> >>After a few games you have lots of different entries for each hash element, >>none of which will ever happen again, practically. >> >>Now you are stuck doing a disk access per node, which is no fun. >I would have a hundred memory areas per cache or so. >If you counted all the positions your game has ever played from the first game >it ever attempted up to now, do you think it would be more than one million >distinct positions? If you did have that many, and had one hundred million >nodes for each of those million positions, that is only 1e14 nodes, if none of >the surrounding nodes overlapped. I suspect that most of them do. > >How many times have the positions overlapped? > >I don't think we have a clear answer without some math.
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.