Perhaps 'implementation' is not the right word, but IIRC the fundamental problem was that Antti Huima used a 4-segment scheme. With Zobrist hashing (xor update) you need at least 8 segments (or 16 with colour symmetry). Otherwise you get trivial collisions (where positions with only a small number differences map to the same hash). Antoine de Maricourt claims to have posted a proof on this in 2002 ( https://www.mail-archive.com/computer-go@computer-go.org/msg01748.html). Nic Schraudolph designed a 6-segment scheme, but it is uses a different update (non-Zobrist) ( https://www.mail-archive.com/computer-go@computer-go.org/msg01788.html). I have a draft, but he asked me not to distribute. Not sure if it ever got published... Better contact him directly.
Best, Erik On Tue, Sep 17, 2019 at 5:36 PM Stephen Martindale < stephen.c.martind...@gmail.com> wrote: > Thanks for the input, so far. > > Erik, is this the paper that you were referring to: > http://fragrieu.free.fr/zobrist.pdf "A Group-Theoretic Zobrist Hash > Function" Antti Huima. > > If so, do you have any sources on what's wrong with it? You say that his > "implementation" was flawed -- does that mean that the theory in the paper > is sound? > > I found the thread in the mailing list archives that you mentioned but > most of the links are dead, by now, so it isn't totally helpful. > > I have yet to read the link that you posted a few minutes ago. > > *Stephen Martindale* > > +49 160 950 27545 > stephen.c.martind...@gmail.com > > > On Tue, 17 Sep 2019 at 17:01, Erik van der Werf <erikvanderw...@gmail.com> > wrote: > >> https://www.real-me.net/ddyer/go/signature-spec.html >> >> On Tue, Sep 17, 2019 at 4:16 PM Brian Sheppard via Computer-go < >> computer-go@computer-go.org> wrote: >> >>> I remember a scheme (from Dave Dyer, IIRC) that indexed positions based >>> on the points on which the 20th, 40th, 60th,... moves were made. IIRC it >>> was nearly a unique key for pro positions. >>> >>> Best, >>> Brian >>> >>> -----Original Message----- >>> From: Erik van der Werf <erikvanderw...@gmail.com> >>> To: computer-go <computer-go@computer-go.org> >>> Sent: Tue, Sep 17, 2019 5:55 am >>> Subject: Re: [Computer-go] Indexing and Searching Go Positions -- >>> Literature Wanted >>> >>> Hi Stephen, >>> >>> I'm not aware of recent published work. There is an ancient document by >>> Antti Huima on hash schemes for easy symmetry detection/lookup. >>> Unfortunately his implementation was broken, but other schemes have been >>> proposed that solve the issue (I found one myself, but I think many others >>> found the same or similar solutions). You may want to search the archives >>> for "Zobrist hashing with easy transformation comparison". If you like math >>> Nic Schrauolph has an interesting solution ;-) >>> >>> In Steenvreter I implemented a 16-segment scheme with a xor update (for >>> rotation, mirroring and color symmetry). In GridMaster I have an >>> experimental search feature which is somewhat similar except that I don't >>> use hash keys (every possible point on the board simply gets its own bits), >>> and I use 'or' instead of 'xor' (so stones that are added are never >>> removed, which makes parsing game records extremely fast). This makes it >>> very easy to filter positions/games that cannot match, and for the >>> remainder (if needed, dealing with captures) it simply replays (which is >>> fast enough because the number of remaining games is usually very small). >>> I'm not sure what Kombilo does, but I wouldn't be surprised if it's >>> similar. The only thing I haven't implemented yet is lookup of translated >>> (shifted) local patterns. Still pondering what's most efficient for that, >>> but I could simply run multiple searches with a mask. >>> >>> Best, >>> Erik >>> >>> >>> On Tue, Sep 17, 2019 at 10:17 AM Stephen Martindale < >>> stephen.c.martind...@gmail.com> wrote: >>> > >>> > Dear Go programmers, >>> > >>> > I'm interested in experimenting with some new ideas for indexing and >>> searching Goban positions and patterns and I want to stand on the shoulders >>> of giants. Which papers, articles, blog posts or open-source code should I >>> read to get concrete knowledge of the approaches used in the past? >>> > >>> > I know that Kombilo is (or used to be) the state of the art in this >>> field. The source is available but, beyond reading the Libkombilo sources, >>> are there any other, more human friendly resources out there? >>> > >>> > My new ideas are currently insubstantial and vague but I have done >>> some work, in the past, with natural language embeddings and large-database >>> image indexing and searching and concepts from those two domains keep >>> bouncing around in my mind -- I can't help but feel that there must be >>> something there that can be the "next big thing" in Go position indexing. >>> > >>> > Any leads would be appreciated. >>> > >>> > Stephen Martindale >>> > >>> > +49 160 950 27545 >>> > stephen.c.martind...@gmail.com >>> > _______________________________________________ >>> > Computer-go mailing list >>> > Computer-go@computer-go.org >>> > http://computer-go.org/mailman/listinfo/computer-go >>> _______________________________________________ >>> Computer-go mailing list >>> Computer-go@computer-go.org >>> http://computer-go.org/mailman/listinfo/computer-go >>> _______________________________________________ >>> Computer-go mailing list >>> Computer-go@computer-go.org >>> http://computer-go.org/mailman/listinfo/computer-go >>> >> _______________________________________________ >> Computer-go mailing list >> Computer-go@computer-go.org >> http://computer-go.org/mailman/listinfo/computer-go >> > _______________________________________________ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
