Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
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
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
When a new stone is put on the board at
(lx,ly), the only work
of the pattern matcher is:
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|