Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | In this chapter, we describe the principles of the GNU Go DFA |
2 | pattern matcher. The aim of this system is to permit a fast | |
3 | pattern matching when it becomes time critical like in owl | |
4 | module (@ref{The Owl Code}). Since GNU Go 3.2, this is enabled | |
5 | by default. You can still get back the traditional pattern matcher | |
6 | by running @command{configure --disable-dfa} and then recompiling | |
7 | GNU Go. | |
8 | ||
9 | Otherwise, a finite state machine called a Deterministic Finite | |
10 | State Automaton (@ref{What is a DFA}) will be built off line from the | |
11 | pattern database. This is used at runtime to speedup pattern matching | |
12 | (@ref{Pattern matching with DFA} and @ref{Incremental Algorithm}). The | |
13 | runtime speedup is at the cost of an increase in memory use and | |
14 | compile time. | |
15 | ||
16 | ||
17 | @menu | |
18 | * Introduction to the DFA:: Scanning the board along a path | |
19 | * What is a DFA:: A recall of language theory. | |
20 | * Pattern matching with DFA:: How to retrieve go patterns with a DFA? | |
21 | * Building the DFA:: Playing with explosives. | |
22 | * Incremental Algorithm:: The joy of determinism. | |
23 | * DFA Optimizations:: Some possible optimizations. | |
24 | @end menu | |
25 | ||
26 | ||
27 | @cindex pattern matching | |
28 | @cindex fast pattern matching | |
29 | @cindex pattern database | |
30 | @cindex finite state automaton | |
31 | @cindex automaton | |
32 | @cindex dfa | |
33 | @cindex dfa.h | |
34 | @cindex dfa.c | |
35 | @cindex matchpat.c | |
36 | @cindex product | |
37 | ||
38 | ||
39 | @node Introduction to the DFA | |
40 | @section Introduction to the DFA | |
41 | ||
42 | The general idea is as follows: | |
43 | ||
44 | For each intersection of the board, its neighbourhood is scanned following | |
45 | a predefined path. The actual path used does not matter very much; GNU Go | |
46 | uses a spiral as shown below. | |
47 | ||
48 | @ifinfo | |
49 | @example | |
50 | +---B--------------+ | |
51 | | C 4 A . . . . . .| | |
52 | D 5 1 3 9 . . . . .| | |
53 | E 6 2 8 . . X . . .| | |
54 | | F 7 . . . . . . .| | |
55 | | . +-> . . . . . .| | |
56 | | . . . . . . . . .| | |
57 | | . O . . . X . . .| | |
58 | | . . . . . . . . .| | |
59 | | . . . . . . . . .| | |
60 | +------------------+ | |
61 | @end example | |
62 | @end ifinfo | |
63 | @ifnotinfo | |
64 | @image{path} | |
65 | @end ifnotinfo | |
66 | ||
67 | In each step of the path, the pattern matcher jumps into a state | |
68 | determined by what it has found on the board so far. If we have | |
69 | successfully matched one or several patterns in this step, this state | |
70 | immediately tells us so (in its @dfn{attribute}). | |
71 | But the state also implicitly encodes which further patterns can still | |
72 | get matched: The information stored in the state contains in which state | |
73 | to jump next, depending on whether we find a black, white or empty | |
74 | intersection (or an intersection out of board) in the next step of the | |
75 | path. The state will also immediately tell us if we cannot find any | |
76 | further pattern (by telling us to jump into the @dfn{error} state). | |
77 | ||
78 | These sloppy explanations may become clearer with the definitions in | |
79 | the next section (@ref{What is a DFA}). | |
80 | ||
81 | Reading the board following a predefined path reduces | |
82 | the two dimentional pattern matching to a linear text searching problem. | |
83 | For example, this pattern | |
84 | ||
85 | @example | |
86 | ?X? | |
87 | .O? | |
88 | ?OO | |
89 | @end example | |
90 | ||
91 | @noindent | |
92 | scanned following the path | |
93 | ||
94 | @example | |
95 | B | |
96 | C4A | |
97 | 5139 | |
98 | 628 | |
99 | 7 | |
100 | @end example | |
101 | ||
102 | @noindent | |
103 | gives the string @b{"OO?X.?*O*?*?"} | |
104 | where @b{"?"} means @b{'don't care'} and @b{"*"} means @b{'don't care, can | |
105 | even be out of board'}. | |
106 | ||
107 | So we can forget that we are dealing with two dimensional patterns and | |
108 | consider linear patterns. | |
109 | ||
110 | ||
111 | @node What is a DFA | |
112 | @section What is a DFA | |
113 | ||
114 | The acronym DFA means Deterministic Finite state Automaton | |
115 | (See @uref{http://www.eti.pg.gda.pl/~jandac/thesis/node12.html} | |
116 | or @cite{Hopcroft & Ullman "Introduction to Language Theory"} | |
117 | for more details). | |
118 | DFA are common tools in compilers design | |
119 | (Read @cite{Aho, Ravi Sethi, Ullman "COMPILERS: Principles, Techniques and Tools"} | |
120 | for a complete introduction), a lot of | |
121 | powerfull text searching algorithm like @cite{Knuth-Morris-Pratt} | |
122 | or @cite{Boyer-Moore} algorithms are based on DFA's | |
123 | (See @uref{http://www-igm.univ-mlv.fr/~lecroq/string/} for a bibliography | |
124 | of pattern matching algorithms). | |
125 | ||
126 | Basically, | |
127 | a DFA is a set of @dfn{states} connected by labeled @dfn{transitions}. | |
128 | The labels are the values read on the board, | |
129 | in GNU Go these values are EMPTY, WHITE, BLACK or OUT_BOARD, denoted | |
130 | respectively by '.','O','X' and '#'. | |
131 | ||
132 | ||
133 | The best way to represent a DFA is to draw its transition graph: | |
134 | the pattern @b{"????..X"} is recognized by the following DFA: | |
135 | ||
136 | @ifinfo | |
137 | @example | |
138 | @group | |
139 | .,X,O .,X,O .,X,O .,X,O . . X | |
140 | [1]------>[2]----->[3]----->[4]----->[5]--->[6]--->[7]--->[8 OK!] | |
141 | Start | |
142 | @end group | |
143 | @end example | |
144 | @end ifinfo | |
145 | ||
146 | @ifnotinfo | |
147 | @image{dfa} | |
148 | @end ifnotinfo | |
149 | ||
150 | ||
151 | This means that | |
152 | starting from state [1], if you read '.','X' or 'O' on the board, | |
153 | go to state [2] and so on until you reach state [5]. | |
154 | From state [5], if you read '.', go to state [6] | |
155 | otherwise go to error state [0]. | |
156 | And so on until you reach state [8]. | |
157 | As soon as you reach state [8], | |
158 | you recognize Pattern @b{"????..X"} | |
159 | ||
160 | Adding a pattern like @b{"XXo"} ('o' is a wildcard for not 'X') | |
161 | will transform directly the automaton | |
162 | by synchronization product (@ref{Building the DFA}). | |
163 | Consider the following DFA: | |
164 | ||
165 | @ifinfo | |
166 | @example | |
167 | @group | |
168 | Start .,O .,X,O .,O,X .,X,O . . X | |
169 | [1]---->[2]----->[3]----->[4]------>[5]--->[6]---->[7]--->[8 OK!] | |
170 | | ^ ^ ^ | |
171 | | .,O | | | | |
172 | | ---- | | | |
173 | | | X | | | |
174 | | | --- .,X,O | | |
175 | | | | | | |
176 | | X | X | O,. | | |
177 | --------->[9]------>[A]--->[B OK!]- | |
178 | @end group | |
179 | @end example | |
180 | @end ifinfo | |
181 | ||
182 | @ifnotinfo | |
183 | @image{dfa2} | |
184 | @end ifnotinfo | |
185 | ||
186 | By adding a special @dfn{error} state and completing each state | |
187 | by a transition to error state when there is none, we transform | |
188 | easily a DFA in a @dfn{Complete Deterministic Finite state | |
189 | Automaton} (CDFA). The synchronization product | |
190 | (@ref{Building the DFA}) is only possible on CDFA's. | |
191 | ||
192 | ||
193 | @ifinfo | |
194 | @example | |
195 | @group | |
196 | Start .,O .,X,O .,O,X .,X,O . . X | |
197 | [1]---->[2]----->[3]----->[4]------>[5]--->[6]---->[7]--->[8 OK!] | |
198 | | ^ ^ ^ | | | | |
199 | | .,O | | | | | | | |
200 | | ---- | | | | | | |
201 | | | X | | |X,O | .,O |X,.,O | |
202 | | | --- .,X,O | | | | | |
203 | | | | | | | | | |
204 | | X | X | O,. | \ / \ / \ / | |
205 | --------->[9]------>[A]--->[B OK!]- [0 Error state !] | |
206 | @end group | |
207 | @end example | |
208 | @end ifinfo | |
209 | @ifnotinfo | |
210 | @image{cdfa} | |
211 | @end ifnotinfo | |
212 | ||
213 | The graph of a CDFA is coded by an array of states: | |
214 | The 0 state is the "error" state and | |
215 | the start state is 1. | |
216 | ||
217 | @example | |
218 | @group | |
219 | ---------------------------------------------------- | |
220 | state | . | O | X | # | att | |
221 | ---------------------------------------------------- | |
222 | 1 | 2 | 2 | 9 | 0 | | |
223 | 2 | 3 | 3 | 3 | 0 | | |
224 | 3 | 4 | 4 | 4 | 0 | | |
225 | 5 | 6 | 0 | 0 | 0 | | |
226 | 6 | 7 | 0 | 0 | 0 | | |
227 | 7 | 0 | 0 | 8 | 0 | | |
228 | 8 | 0 | 0 | 0 | 0 | Found pattern "????..X" | |
229 | 9 | 3 | 3 | A | 0 | | |
230 | A | B | B | 4 | 0 | | |
231 | B | 5 | 5 | 5 | 0 | Found pattern "XXo" | |
232 | ---------------------------------------------------- | |
233 | @end group | |
234 | @end example | |
235 | ||
236 | To each state we associate an often empty | |
237 | list of attributes which is the | |
238 | list of pattern indexes recognized when this state is reached. | |
239 | In '@file{dfa.h}' this is basically represented by two stuctures: | |
240 | ||
241 | @example | |
242 | @group | |
243 | @code{ | |
244 | /* dfa state */ | |
245 | typedef struct state | |
246 | @{ | |
247 | int next[4]; /* transitions for EMPTY, BLACK, WHITE and OUT_BOARD */ | |
248 | attrib_t *att; | |
249 | @} | |
250 | state_t; | |
251 | ||
252 | /* dfa */ | |
253 | typedef struct dfa | |
254 | @{ | |
255 | attrib_t *indexes; /* Array of pattern indexes */ | |
256 | int maxIndexes; | |
257 | ||
258 | state_t *states; /* Array of states */ | |
259 | int maxStates; | |
260 | @} | |
261 | dfa_t;} | |
262 | @end group | |
263 | @end example | |
264 | ||
265 | @node Pattern matching with DFA | |
266 | @section Pattern matching with DFA | |
267 | ||
268 | Recognizing with a DFA is very simple | |
269 | and thus very fast | |
270 | (See '@code{scan_for_pattern()}' in the '@file{engine/matchpat.c}' file). | |
271 | ||
272 | ||
273 | Starting from the start state, we only need to read the board | |
274 | following the spiral path, jump from states to states following | |
275 | the transitions labelled by the values read on the board and | |
276 | collect the patterns indexes on the way. If we reach the error | |
277 | state (zero), it means that no more patterns will be matched. | |
278 | The worst case complexity of this algorithm is o(m) where m is | |
279 | the size of the biggest pattern. | |
280 | ||
281 | Here is an example of scan: | |
282 | ||
283 | First we build a minimal DFA recognizing these patterns: | |
284 | @b{"X..X"}, @b{"X???"}, @b{"X.OX"} and @b{"X?oX"}. | |
285 | Note that wildcards like '?','o', or 'x' give multiple out-transitions. | |
286 | ||
287 | @example | |
288 | @group | |
289 | ---------------------------------------------------- | |
290 | state | . | O | X | # | att | |
291 | ---------------------------------------------------- | |
292 | 1 | 0 | 0 | 2 | 0 | | |
293 | 2 | 3 | 10 | 10 | 0 | | |
294 | 3 | 4 | 7 | 9 | 0 | | |
295 | 4 | 5 | 5 | 6 | 0 | | |
296 | 5 | 0 | 0 | 0 | 0 | 2 | |
297 | 6 | 0 | 0 | 0 | 0 | 4 2 1 | |
298 | 7 | 5 | 5 | 8 | 0 | | |
299 | 8 | 0 | 0 | 0 | 0 | 4 2 3 | |
300 | 9 | 5 | 5 | 5 | 0 | | |
301 | 10 | 11 | 11 | 9 | 0 | | |
302 | 11 | 5 | 5 | 12 | 0 | | |
303 | 12 | 0 | 0 | 0 | 0 | 4 2 | |
304 | ---------------------------------------------------- | |
305 | @end group | |
306 | @end example | |
307 | ||
308 | We perform the scan of the string | |
309 | @b{"X..XXO...."} starting from state 1: | |
310 | ||
311 | Current state: 1, substring to scan :@b{ X..XXO....} | |
312 | ||
313 | We read an 'X' value, so from state 1 we must go to | |
314 | state 2. | |
315 | ||
316 | Current state: 2, substring to scan : @b{..XXO....} | |
317 | ||
318 | We read a '.' value, so from state 2 we must go to | |
319 | state 3 and so on ... | |
320 | ||
321 | @example | |
322 | Current state: 3, substring to scan : .XXO.... | |
323 | Current state: 4, substring to scan : XXO.... | |
324 | Current state: 6, substring to scan : XO.... | |
325 | Found pattern 4 | |
326 | Found pattern 2 | |
327 | Found pattern 1 | |
328 | @end example | |
329 | ||
330 | After reaching state 6 where we match patterns | |
331 | 1,2 and 4, there is no out-transitions so we stop the matching. | |
332 | To keep the same match order as in the standard algorithm, | |
333 | the patterns indexes are collected in an array and sorted by indexes. | |
334 | ||
335 | @node Building the DFA | |
336 | @section Building the DFA | |
337 | ||
338 | The most flavouring point is the building of the minimal DFA | |
339 | recognizing a given set of patterns. | |
340 | To perform the insertion of a new | |
341 | pattern into an already existing DFA one must completly rebuild | |
342 | the DFA: the principle is to build the minimal CDFA recognizing | |
343 | the new pattern to replace the original CDFA with its | |
344 | @dfn{synchronised product} by the new one. | |
345 | ||
346 | We first give a formal definition: | |
347 | Let @b{L} be the left CDFA and @b{R} be the right one. | |
348 | Let @b{B} be the @dfn{synchronised product} of @b{L} by @b{R}. | |
349 | Its states are the couples @b{(l,r)} where @b{l} is a state of @b{L} and | |
350 | @b{r} is a state of @b{R}. | |
351 | The state @b{(0,0)} is the error state of @b{B} and the state | |
352 | @b{(1,1)} is its initial state. | |
353 | To each couple @b{(l,r)} we associate the union of patterns | |
354 | recognized in both @b{l} and @b{r}. | |
355 | The transitions set of @b{B} is the set of transitions | |
356 | @b{(l1,r1)---a--->(l2,r2)} for | |
357 | each symbol @b{'a'} such that both @b{l1---a--->l2} in @b{L} | |
358 | and @b{r1---a--->r2} in @b{R}. | |
359 | ||
360 | The maximal number of states of @b{B} is the product of the | |
361 | number of states of @b{L} and @b{R} but almost all this states | |
362 | are non reachable from the initial state @b{(1,1)}. | |
363 | ||
364 | The algorithm used in function '@code{sync_product()}' builds | |
365 | the minimal product DFA only by keeping the reachable states. | |
366 | It recursively scans the product CDFA by following simultaneously | |
367 | the transitions of @b{L} and @b{R}. A hast table | |
368 | (@code{gtest}) is used to check if a state @b{(l,r)} has | |
369 | already been reached, the reachable states are remapped on | |
370 | a new DFA. The CDFA thus obtained is minimal and recognizes the | |
371 | union of the two patterns sets. | |
372 | ||
373 | @ifnotinfo | |
374 | For example these two CDFA's: | |
375 | ||
376 | ||
377 | @image{sync-prod1} | |
378 | ||
379 | Give by synchronization product the following one: | |
380 | ||
381 | ||
382 | @image{sync-prod2} | |
383 | @end ifnotinfo | |
384 | ||
385 | It is possible to construct a special pattern database that | |
386 | generates an "explosive" automaton: the size of the DFA is in | |
387 | the worst case exponential in the number of patterns it | |
388 | recognizes. But it doesn't occur in pratical situations: | |
389 | the DFA size tends to be @dfn{stable}. By @dfn{stable} we mean that if we | |
390 | add a pattern which greatly increases the size of the DFA it | |
391 | also increases the chance that the next added pattern does not | |
392 | increase its size at all. Nevertheless there are many ways to | |
393 | reduce the size of the DFA. Good compression methods are | |
394 | explained in @cite{Aho, Ravi Sethi, Ullman "COMPILERS: | |
395 | Principles, Techniques and Tools" chapter Optimization of | |
396 | DFA-based pattern matchers}. | |
397 | ||
398 | @node Incremental Algorithm | |
399 | @section Incremental Algorithm | |
400 | ||
401 | The incremental version of the DFA pattern matcher is not yet implemented | |
402 | in GNU Go but we explain here how it will work. | |
403 | By definition of a deterministic automaton, scanning the same | |
404 | string will reach the same states every time. | |
405 | ||
406 | Each reached state during pattern matching is stored in a stack | |
407 | @code{top_stack[i][j]} and @code{state_stack[i][j][stack_idx]} | |
408 | We use one stack by intersection @code{(i,j)}. A precomputed reverse | |
409 | path list allows to know for each couple of board intersections | |
410 | @code{(x,y)} its position @code{reverse(x,y)} in the spiral scan path | |
411 | starting from @code{(0,0)}. | |
412 | ||
413 | When a new stone is put on the board at @code{(lx,ly)}, the only work | |
414 | of the pattern matcher is: | |
415 | ||
416 | @example | |
417 | @group | |
418 | @code{ | |
419 | for(each stone on the board at (i,j)) | |
420 | if(reverse(lx-i,ly-j) < top_stack[i][j]) | |
421 | @{ | |
422 | begin the dfa scan from the state | |
423 | state_stack[i][j][reverse(lx-i,ly-j)]; | |
424 | @} | |
425 | } | |
426 | @end group | |
427 | @end example | |
428 | ||
429 | In most situations reverse(lx-i,ly-j) will be inferior to | |
430 | top_stack[i][j]. This should speedup a lot pattern matching. | |
431 | ||
432 | @node DFA Optimizations | |
433 | @section Some DFA Optimizations | |
434 | ||
435 | The DFA is constructed to minimize jumps in memory making some | |
436 | assumptions about the frequencies of the values: the EMPTY | |
437 | value is supposed to appear often on the board, so the the '.' | |
438 | transition are almost always successors in memory. The | |
439 | OUT_BOARD are supposed to be rare, so '#' transitions will | |
440 | almost always imply a big jump. | |
441 |