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


GNU Go Documentation

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

13. The DFA pattern matcher

In this chapter, we describe the principles of the gnugo DFA pattern matcher. The aim of this system is to permit a fast pattern matching when it becomes time critical like in owl module (15.1 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 (13.0.2 What is a DFA) will be built off line from the pattern database. This is used at runtime to speedup pattern matching (13.0.3 Pattern matching with DFA and 13.0.5 Incremental Algorithm). The runtime speedup is at the cost of an increase in memory use and compile time.

13.0.1 Introduction to the DFA  Scanning the board along a path
13.0.2 What is a DFA  A recall of language theory.
13.0.3 Pattern matching with DFA  How to retrieve go patterns with a dfa ?
13.0.4 Building the DFA  Playing with explosives.
13.0.5 Incremental Algorithm  The joy of determinism.
13.0.6 Some DFA Optimizations  Some possible optimizations.


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