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
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
>> To: computer-go
>> 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
