On 1/19/07, Mark Boon <[EMAIL PROTECTED]> wrote:
This seems to be only a small variation of hashing methods I was
taught at university in the 80s.
The method I always used was simply putting the new value and key in
the place of the old one, with one simple addition. In case the spot
is filled it would look at the next 'n' spots until it found an empty
one (or one with the same key of course). If not, simply replace the
old values with the new. But I must say for me the transposition
lookup was not a critical piece in terms of performance because
evaluations were so many orders of magnitude more expensive. So I
used n=10 for a dramatically better usage of the available space in
the table. I did no real research in terms of table-use, speed and
number of collisions as a function of 'n'.
This is what I meant by clustering.
It's most simple.
I use cluster_size = 4. In some applications I have a performance
bottleneck here.
What ticked me off with the cuckoo method is apparently it can loop
and a rehash is needed. Ouch, that better not happen very often!
Mark
On 19-jan-07, at 11:00, Łukasz Lew wrote:
> Take a look at
> http://en.wikipedia.org/wiki/Cuckoo_hashing
> also.
>
> Lukasz
>
> On 1/19/07, Eduardo Sabbatella <[EMAIL PROTECTED]>
> wrote:
>> Right now my two main concerns are about:
>>
>> 1) feasability, perhaps even prunning with UCT for
>> storing usefull games, no more than 5 ply can be
>> stored on nowadays memory constraints.
>>
>> 2) techniques for prunning gametree on big "databases"
>> of game configurations. This thing by itself its a
>> quite big topic.
>>
>> About the hash method in your email, I have just print
>> out the paper and I will read it on my commuting back
>> home. I can't say much about hashing techniques
>> specially needed in this situation.
>>
>> I was planning to use Berkeley DB or something. Is it
>> too bad? o_O
>>
>> Many thanks,
>> Eduardo
>>
>> --- £ukasz Lew <[EMAIL PROTECTED]> escribió:
>>
>> > I believe that clustering algorithm is algorithm is
>> > both more
>> > practical and elegant, than
>> > two big, and other multilevel schemes.
>> > - It uses memory in more efficient manner effecting
>> > in reduction of
>> > collision rate.
>> > - It allows for more than 2 entries on the same hash
>> > before loosing
>> > the information
>> >
>> > I would also would like to point that there is a new
>> > (2001) clever
>> > method of hashing
>> > i.e. Cuckoo Hashing that has the potential of
>> > replacing all other methods.
>> >
>> > If one is really serious about hash performance then
>> > there is this
>> > 2006-hot article:
>> >
>> http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf
>> >
>> > Hope this helps :)
>> > £ukasz
>> >
>> >
>> > On 1/19/07, Erik van der Werf
>> > <[EMAIL PROTECTED]> wrote:
>> > > On 1/19/07, A van Kessel
>> > <[EMAIL PROTECTED]> wrote:
>> > > > Erik van der Werf's thesis was mainly about
>> > > > transposition table replacement algorihtms,
>> > IIRC.
>> > >
>> > > No it wasn't. I think you're confusing me with
>> > Dennis Breuker.
>> > >
>> > > see:
>> > http://www.xs4all.nl/~breukerd/thesis/index.html
>> > >
>> > > I have some knowledge on transposition tables, and
>> > have even done some
>> > > experiments along the lines as suggested by the
>> > original poster, but
>> > > it was definitely not the main topic of my thesis
>> > (which btw can be
>> > > found at
>> >
>> http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz).
>> > >
>> > >
>> > > > My personal summary: it is very hard to be more
>> > clever
>> > > > (at replacement) than "always replace when
>> > hitting an occupied slot".
>> > >
>> > > Yes, "new" does quite well under most
>> > circumstances. However,
>> > > something like "TwoBig" should be easy to
>> > implement with UCT. An
>> > > interesting question may be how to efficiently
>> > free memory from
>> > > entries that become irrelevant in the continuation
>> > of a game (after
>> > > the actual moves made have ruled out portions of
>> > the full game-graph),
>> > > but this is probably not an issue in the context
>> > of the original
>> > > poster's question.
>> > >
>> > > Erik
>> > > _______________________________________________
>> > > computer-go mailing list
>> > > [email protected]
>> > >
>> >
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>> > >
>> > > _______________________________________________
>> > computer-go mailing list
>> > [email protected]
>> >
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
>>
>>
>>
>>
>>
>>
>> __________________________________________________
>> Preguntá. Respondé. Descubrí.
>> Todo lo que querías saber, y lo que ni imaginabas,
>> está en Yahoo! Respuestas (Beta).
>> ¡Probalo ya!
>> http://www.yahoo.com.ar/respuestas
>>
>> _______________________________________________
>> computer-go mailing list
>> [email protected]
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
> _______________________________________________
> computer-go mailing list
> [email protected]
> http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
