[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] more on dfa
[gnugo-devel] more on dfa
05 Oct 2002 17:45:23 +0100
I can't find the article now, but there was some discussion at one point
how the dfa spiral is somewhat wasteful if it is looking near an edge, but is
to look at distant pattern elements.
Something I've been thinking about : could we truncate the length of the
the dfa scans for. So rather than producing a definitive list of which patterns
the dfa produces a (longer) list of patterns which are worth matching
25 elements might be a reasonable compromise, so that the dfa will output all
patterns which match within the immediate vicinity of the anchor.
Given that the matcher often has to anyway visit the pattern elements to check
constraints, the added cost of checking the pattern elements against the board
be less than the saving from forcing the dfa to iterate out to large distances.
(The pattern could store a flag to say whether the dfa string was truncated or
so that we can tell on a per pattern basis whether the additional checks are
necessary. Or the generated autohelper can perform the full check explicitly.)
I haven't got very far into actually measuring anything. I was going to add some
stuff to the pattern-profiling to measure dfa results vs distance along the
[ ie how many times it went that far, and how many patterns matched at that
Has anyone already tried / discounted such a scheme ?
Only thing I have got as far as noticing was that pattern A414 is an extreme
# gf Revised constraint. (3.1.14)
??xxx?? cap to prevent escape
the anchor has to be the 'X' at the bottom, and the dfa has to spiral out quite
to cover all the elements. (If I understand the dfa correctly, that is.)
A rectangular spiral would have to check around 81 intersections (9*9 grid).
The circular spiral probably has to go even further.
And given that this pattern can match at any isolated stone, the dfa is being
perform the full traversal of its data many times.
Another approach would be to somehow encode that the dfa spiral should be
somewhere other than the anchor stone. ie here it would be centered at the '*'.
I haven't really got a clear idea how this could work in practise, though - we
don't want to spiral round all empty intersections in case they stumble upon an
two intersections away.
Perhaps some hash function which collects the stones in the neighbourhood of
the intersection in question, then chooses an appropriate dfa starting point.
(so that if it is looking at an empty spot with an 'X' stone two intersections
it will use the dfa database which includes pattern A414.)
On a separate issue, I've been wondering whether tha dfa data can be packed
8 bits per entry. They would have to be relative, and there would have to be a
bit of work at compile time to get all the nodes interspersed correctly so that
each node could reach all its neighbours. But it might be possible...
Are there plans to build / modify dfa's at runtime ?
- [gnugo-devel] more on dfa,
Dave Denholm <=
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/07
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/09
- Re: [gnugo-devel] more on dfa, Tanguy URVOY, 2002/10/10
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/10
- Re: [gnugo-devel] more on dfa, Tanguy URVOY, 2002/10/11
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/11
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/12
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/12
- Re: [gnugo-devel] more on dfa, Dave Denholm, 2002/10/14
- Re: [gnugo-devel] more on dfa, Arend Bayer, 2002/10/19