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
