[computer-go] Mega transposition table

[Łukasz Lew]

On 1/19/07, Mark Boon <tesujisoftware at gmail.com> 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 <eduardo_sabbatella at yahoo.com.ar>
> > 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 <lukasz.lew at gmail.com> 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
> >> > <erikvanderwerf at gmail.com> wrote:
> >> > > On 1/19/07, A van Kessel
> >> > <adriaan.van.kessel at rivm.nl> 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
> >> > > computer-go at computer-go.org
> >> > >
> >> >
> >> http://www.computer-go.org/mailman/listinfo/computer-go/
> >> > >
> >> > > _______________________________________________
> >> > computer-go mailing list
> >> > computer-go at computer-go.org
> >> >
> >> 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
> >> computer-go at computer-go.org
> >> http://www.computer-go.org/mailman/listinfo/computer-go/
> >>
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>