Re: [gnugo-devel] joseki database

[Trevor Morris]

At 10:44 PM 12/1/2002 +0200, Paul Pogonyshev wrote:
>i estimate the size of joseki database as more than 700k (counting only 
>patval structures). this looks like a lot of space. what i think might help 
>here is a tree-based pattern matcher. i mean a tree which resembles the ones 
>in .sgf files used to construct the database.
>
>will the current tree-based pattern matcher work here (possibly with some 
>modifications)? and what is the current state of experimental reading as a 
>whole, is there a chance it might become useful?

Here's the current result of read-by-pattern (attack only):
reading:62: FAILED: correct: 2 (F2|G3)  answer: 0
reading:65: PASSED: correct: 0  answer: 0
reading:147: PASSED: correct: 1 H1  answer: 1 H1
reading:168: FAILED: correct: 2 B2  answer: 1 G1

I've not timed it recently, but it's certainly slower.

Defend by pattern currently crashes.

I've not kept up with the changes in the reading code, but I think it may
make sense to replace the simpler functions with results from pattern
based reading, leaving the back-filling move generation functions.  It's
my feeling (perhaps mine alone!) that it can be made faster than the
hand-generated functions alone.

All that aside, it's much easier to try different pattern matching schemes
using the reading-by-pattern code.  This may be useful.

The tree-based reading is faster than the DFA for the reading code.  It
needs some work when applied to larger databases, though.  I'm not
certain that it deals with edge constraints properly.  It does have some
advantages over the DFA.  My current experients with the DFA are to
see if it can be made faster than the tree-based pattern matching.  It
seems like the DFA should be able to be made faster.  In particular,
the next thing to try with the DFA is to create an optimal path to minimize
average search length.  The tree-based reading does this better naturally.

The tree-based reading should be able to work with any pattern database,
but definitely with work, as many of the special features aren't even
attempted to be implemented (like ',' in the pattern).

HTH,
Trevor