Re: [gnugo-devel] DFA should be "best" NFA

[Gunnar Farneback]

Heikki wrote:
> One simple observation: On each move we match each pattern against each
> point on the board (well, almost). This is wasteful. If we could keep
> persisitent state on the patterns, we could possibly save a lot.

If I don't misremember, this is one of Tanguy's favorite ideas,
although it's still to be implemented.

> Most common moves only add stones to the board. If we could keep (at
> each point) a list of patterns that can match with only adding
> stones, these lists could quickly come short and fast to match. Some
> sort of optimized decision tree? Need to rebuild them if stones are
> removed, of course.

Please don't rely on stones almost only being added to the board.
Obviously captured stones will be removed but more importantly the
matcher is used repeatedly in search trees (in particular during owl
reading), meaning that the board state will be affected by both moves
and undoing moves between calls to the matcher.

/Gunnar