[computer-go] Mega transposition table

[Łukasz Lew]

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