10. The DFA pattern matcher

In this chapter, we describe the principles of the GNU Go DFA pattern matcher. The aim of this system is to permit a fast pattern matching when it becomes time critical like in owl module (The Owl Code). Since GNU Go 3.2, this is enabled by default. You can still get back the traditional pattern matcher by running configure --disable-dfa and then recompiling GNU Go.

Otherwise, a finite state machine called a Deterministic Finite State Automaton (What is a DFA) will be built off line from the pattern database. This is used at runtime to speedup pattern matching (Pattern matching with DFA and Incremental Algorithm). The runtime speedup is at the cost of an increase in memory use and compile time.

10.1 Introduction to the DFA

The general idea is as follows:

For each intersection of the board, its neighbourhood is scanned following a predefined path. The actual path used does not matter very much; GNU Go uses a spiral as shown below.

In each step of the path, the pattern matcher jumps into a state determined by what it has found on the board so far. If we have successfully matched one or several patterns in this step, this state immediately tells us so (in its attribute). But the state also implicitly encodes which further patterns can still get matched: The information stored in the state contains in which state to jump next, depending on whether we find a black, white or empty intersection (or an intersection out of board) in the next step of the path. The state will also immediately tell us if we cannot find any further pattern (by telling us to jump into the error state).

These sloppy explanations may become clearer with the definitions in the next section (What is a DFA).

Reading the board following a predefined path reduces the two dimentional pattern matching to a linear text searching problem. For example, this pattern

?X?
.O?
?OO

scanned following the path

 B
C4A
5139
628
 7

gives the string "OO?X.?*O*?*?" where "?" means 'don't care' and "*" means 'don't care, can even be out of board'.

So we can forget that we are dealing with two dimensional patterns and consider linear patterns.

10.2 What is a DFA

The acronym DFA means Deterministic Finite state Automaton (See http://www.eti.pg.gda.pl/~jandac/thesis/node12.html or Hopcroft & Ullman "Introduction to Language Theory" for more details). DFA are common tools in compilers design (Read Aho, Ravi Sethi, Ullman "COMPILERS: Principles, Techniques and Tools" for a complete introduction), a lot of powerfull text searching algorithm like Knuth-Morris-Pratt or Boyer-Moore algorithms are based on DFA's (See http://www-igm.univ-mlv.fr/~lecroq/string/ for a bibliography of pattern matching algorithms).

Basically, a DFA is a set of states connected by labeled transitions. The labels are the values read on the board, in GNU Go these values are EMPTY, WHITE, BLACK or OUT_BOARD, denoted respectively by '.','O','X' and '#'.

The best way to represent a DFA is to draw its transition graph: the pattern "????..X" is recognized by the following DFA:

This means that starting from state [1], if you read '.','X' or 'O' on the board, go to state [2] and so on until you reach state [5]. From state [5], if you read '.', go to state [6] otherwise go to error state [0]. And so on until you reach state [8]. As soon as you reach state [8], you recognize Pattern "????..X"

Adding a pattern like "XXo" ('o' is a wildcard for not 'X') will transform directly the automaton by synchronization product (Building the DFA). Consider the following DFA:

By adding a special error state and completing each state by a transition to error state when there is none, we transform easily a DFA in a Complete Deterministic Finite state Automaton (CDFA). The synchronization product (Building the DFA) is only possible on CDFA's.

The graph of a CDFA is coded by an array of states: The 0 state is the "error" state and the start state is 1.

----------------------------------------------------
 state  |   .    |   O    |   X    |   #    |  att
----------------------------------------------------
      1 |      2 |      2 |      9 |      0 |
      2 |      3 |      3 |      3 |      0 |
      3 |      4 |      4 |      4 |      0 |
      5 |      6 |      0 |      0 |      0 |
      6 |      7 |      0 |      0 |      0 |
      7 |      0 |      0 |      8 |      0 |
      8 |      0 |      0 |      0 |      0 | Found pattern "????..X"
      9 |      3 |      3 |      A |      0 |
      A |      B |      B |      4 |      0 |
      B |      5 |      5 |      5 |      0 | Found pattern "XXo"
----------------------------------------------------

To each state we associate an often empty list of attributes which is the list of pattern indexes recognized when this state is reached. In '‘dfa.h’' this is basically represented by two stuctures:

/* dfa state */
typedef struct state
{
  int next[4]; /* transitions for EMPTY, BLACK, WHITE and OUT_BOARD */
  attrib_t *att;
}
state_t;

/* dfa */
typedef struct dfa
{
  attrib_t *indexes; /* Array of pattern indexes */
  int maxIndexes;

  state_t *states; /* Array of states */
  int maxStates;
}
dfa_t;

10.3 Pattern matching with DFA

Recognizing with a DFA is very simple and thus very fast (See 'scan_for_pattern()' in the '‘engine/matchpat.c’' file).

Starting from the start state, we only need to read the board following the spiral path, jump from states to states following the transitions labelled by the values read on the board and collect the patterns indexes on the way. If we reach the error state (zero), it means that no more patterns will be matched. The worst case complexity of this algorithm is o(m) where m is the size of the biggest pattern.

Here is an example of scan:

First we build a minimal DFA recognizing these patterns: "X..X", "X???", "X.OX" and "X?oX". Note that wildcards like '?','o', or 'x' give multiple out-transitions.

----------------------------------------------------
 state  |   .    |   O    |   X    |   #    |  att
----------------------------------------------------
      1 |      0 |      0 |      2 |      0 |
      2 |      3 |     10 |     10 |      0 |
      3 |      4 |      7 |      9 |      0 |
      4 |      5 |      5 |      6 |      0 |
      5 |      0 |      0 |      0 |      0 |    2
      6 |      0 |      0 |      0 |      0 |    4    2    1
      7 |      5 |      5 |      8 |      0 |
      8 |      0 |      0 |      0 |      0 |    4    2    3
      9 |      5 |      5 |      5 |      0 |
     10 |     11 |     11 |      9 |      0 |
     11 |      5 |      5 |     12 |      0 |
     12 |      0 |      0 |      0 |      0 |    4    2
----------------------------------------------------

We perform the scan of the string "X..XXO...." starting from state 1:

Current state: 1, substring to scan : X..XXO....

We read an 'X' value, so from state 1 we must go to state 2.

Current state: 2, substring to scan : ..XXO....

We read a '.' value, so from state 2 we must go to state 3 and so on ...

Current state:     3, substring to scan : .XXO....
Current state:     4, substring to scan : XXO....
Current state:     6, substring to scan : XO....
Found pattern 4
Found pattern 2
Found pattern 1                 

After reaching state 6 where we match patterns 1,2 and 4, there is no out-transitions so we stop the matching. To keep the same match order as in the standard algorithm, the patterns indexes are collected in an array and sorted by indexes.

10.4 Building the DFA

The most flavouring point is the building of the minimal DFA recognizing a given set of patterns. To perform the insertion of a new pattern into an already existing DFA one must completly rebuild the DFA: the principle is to build the minimal CDFA recognizing the new pattern to replace the original CDFA with its synchronised product by the new one.

We first give a formal definition: Let L be the left CDFA and R be the right one. Let B be the synchronised product of L by R. Its states are the couples (l,r) where l is a state of L and r is a state of R. The state (0,0) is the error state of B and the state (1,1) is its initial state. To each couple (l,r) we associate the union of patterns recognized in both l and r. The transitions set of B is the set of transitions (l1,r1)—a—>(l2,r2) for each symbol 'a' such that both l1—a—>l2 in L and r1—a—>r2 in R.

The maximal number of states of B is the product of the number of states of L and R but almost all this states are non reachable from the initial state (1,1).

The algorithm used in function 'sync_product()' builds the minimal product DFA only by keeping the reachable states. It recursively scans the product CDFA by following simultaneously the transitions of L and R. A hast table (gtest) is used to check if a state (l,r) has already been reached, the reachable states are remapped on a new DFA. The CDFA thus obtained is minimal and recognizes the union of the two patterns sets.

For example these two CDFA's:

Give by synchronization product the following one:

It is possible to construct a special pattern database that generates an "explosive" automaton: the size of the DFA is in the worst case exponential in the number of patterns it recognizes. But it doesn't occur in pratical situations: the DFA size tends to be stable. By stable we mean that if we add a pattern which greatly increases the size of the DFA it also increases the chance that the next added pattern does not increase its size at all. Nevertheless there are many ways to reduce the size of the DFA. Good compression methods are explained in Aho, Ravi Sethi, Ullman "COMPILERS: Principles, Techniques and Tools" chapter Optimization of DFA-based pattern matchers.

10.5 Incremental Algorithm

The incremental version of the DFA pattern matcher is not yet implemented in GNU Go but we explain here how it will work. By definition of a deterministic automaton, scanning the same string will reach the same states every time.

Each reached state during pattern matching is stored in a stack top_stack[i][j] and state_stack[i][j][stack_idx] We use one stack by intersection (i,j). A precomputed reverse path list allows to know for each couple of board intersections (x,y) its position reverse(x,y) in the spiral scan path starting from (0,0).

When a new stone is put on the board at (lx,ly), the only work of the pattern matcher is:

 for(each stone on the board at (i,j))
    if(reverse(lx-i,ly-j) < top_stack[i][j])
      {
         begin the dfa scan from the state
         state_stack[i][j][reverse(lx-i,ly-j)];
      }

In most situations reverse(lx-i,ly-j) will be inferior to top_stack[i][j]. This should speedup a lot pattern matching.

10.6 Some DFA Optimizations

The DFA is constructed to minimize jumps in memory making some assumptions about the frequencies of the values: the EMPTY value is supposed to appear often on the board, so the the '.' transition are almost always successors in memory. The OUT_BOARD are supposed to be rare, so '#' transitions will almost always imply a big jump.

This document was generated by Daniel Bump on February, 19 2009 using texi2html 1.78.