[computer-go] Mega transposition table

[Łukasz Lew]

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/
>