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.


-----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 

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.

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 mailing list

Reply via email to