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


GNU Go Documentation

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

13.0.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.

 
  +---B--------------+
  | C 4 A . . . . . .|
  D 5 1 3 9 . . . . .|
  E 6 2 8 . . X . . .|
  | F 7 . . . . . . .|
  | . +-> . . . . . .|
  | . . . . . . . . .|
  | . O . . . X . . .|
  | . . . . . . . . .|
  | . . . . . . . . .|
  +------------------+

path

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 (13.0.2 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.


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

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