Re: [Computer-go] Indexing and Searching Go Positions -- Literature Wanted

2019-09-17 Thread Erik van der Werf
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

2019-09-17 Thread Dave Dyer
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

2019-09-17 Thread Erik van der Werf
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

2019-09-17 Thread Brian Sheppard via Computer-go
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

2019-09-17 Thread Erik van der Werf
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] Indexing and Searching Go Positions -- Literature Wanted

2019-09-17 Thread Stephen Martindale
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