www.delorie.com/gnu/docs/gnugo/gnugo_165.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.0.5 Incremental Algorithm

The incremental version of the DFA pattern matcher is not yet implemented in gnugo 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.


  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003