Re: [Computer-go] Indexing and Searching Go Positions -- Literature Wanted
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 > 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 a
Re: [Computer-go] Indexing and Searching Go Positions -- Literature Wanted
At 07:07 AM 9/17/2019, Brian Sheppard via Computer-go 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. Correct, but it's only useful for game recognition, not for any other kind of search. It was intended for the pre-digital "what game is that" problem for printed games. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Indexing and Searching Go Positions -- Literature Wanted
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
Re: [Computer-go] Indexing and Searching Go Positions -- Literature Wanted
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 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
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
