[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] more on dfa
From: |
Dave Denholm |
Subject: |
[gnugo-devel] more on dfa |
Date: |
05 Oct 2002 17:45:23 +0100 |
Hi,
I can't find the article now, but there was some discussion at one point
about
how the dfa spiral is somewhat wasteful if it is looking near an edge, but is
having
to look at distant pattern elements.
Something I've been thinking about : could we truncate the length of the
strings which
the dfa scans for. So rather than producing a definitive list of which patterns
match,
the dfa produces a (longer) list of patterns which are worth matching
"carefully".
25 elements might be a reasonable compromise, so that the dfa will output all
the
patterns which match within the immediate vicinity of the anchor.
Given that the matcher often has to anyway visit the pattern elements to check
other
constraints, the added cost of checking the pattern elements against the board
may
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
not,
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
spiral.
[ ie how many times it went that far, and how many patterns matched at that
distance].
Has anyone already tried / discounted such a scheme ?
Only thing I have got as far as noticing was that pattern A414 is an extreme
example of
the problem...
Pattern A414
# gf Revised constraint. (3.1.14)
??xxx?? cap to prevent escape
??...??
oo.*.oo
oo...oo
??.X.??
the anchor has to be the 'X' at the bottom, and the dfa has to spiral out quite
some way
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
forced to
perform the full traversal of its data many times.
Another approach would be to somehow encode that the dfa spiral should be
centred
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
certainly
don't want to spiral round all empty intersections in case they stumble upon an
'X' stone
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
away,
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
down to
8 bits per entry. They would have to be relative, and there would have to be a
fair
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 ?
dd
--
address@hidden http://www.insignia.com
- [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