[gnugo-devel] more on dfa

[Dave Denholm]

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