Re: [gnugo-devel] more on dfa

[Arend Bayer]

Dave wrote:

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

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

I wouldn't be aware of that. It is right that check_pattern_light() does
a loop over all elements, but as far as I can see this could for most
cases be avoided (esp. once we use matchpat_goal_anchor()).

However, your approach would on the way also reduce the size of the DFA,
which would make it more attractive to try other optimizations that
increase the size. Also, you could use it in exactly those cases where
there is just one pattern left to be checked. This would require an
additional pass at DFA build time.

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

This would however interphere with using matchpat_goal_anchor(), which we
should be doing some day (i.e. once someone gets around to implementing
it...).

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

I don't think so.

About your suggestion using short ints: Our largest DFA, owl_defendpats,
has ~33000 states (and of course much fewer attributes). I.e. either
using unsigned short ints, or relative signed short ints (I am pretty sure
there are no extremely long jumps) should work without problems. Or am I
overlooking s.th.?

Arend