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