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

Reply via email to