File: PATTERNS

package info (click to toggle)
gnugo 2.4-2
  • links: PTS
  • area: main
  • in suites: potato
  • size: 1,816 kB
  • ctags: 1,828
  • sloc: ansic: 22,091; tcl: 401; sh: 376; makefile: 202
file content (837 lines) | stat: -rw-r--r-- 30,200 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
                          The Pattern Code


Overview
--------

A database of patterns is supplied in patterns.db These are ascii
representations, of the form:

Pattern EB115

??o|          sente hane
?Oo|
XX*|
...|
?.?|

:8,50,0,O,5,5,5,0,0,sente_hane_helper

where 'O' marks a friendly stone, 'X' marks enemy stones, '.' marks an 
empty vertex, '*' marks O's next move, 'o' marks a square either
containing 'O' or empty but not X. (The symbol 'x', which does
not appear in this pattern, means 'X' or '.') Finally '?' Indicates a
location where we don't care what is there, except that it cannot be
off the edge of the board.

The line of |'s along the right in this example is the edge of the
board itself---this is an edge pattern. Corners can also be
indicated. So this pattern describes a hane on the first line. The 'o'
makes sure that it would not be in atari immediately, though the
matcher can check for this automatically (see class).  Elements are
not generated for '?' markers, but they are not completely ignored -
see below.
	
The line beginning : describes various attributes of the pattern, such
as its symmetry and its importance.  Optionally, a function called a
``helper'' can be provided to assist the matcher in deciding the worth
of the move, and a simple measure of the influence of nearby stones
can be factored in. In this case, there is a helper, the
sente_hane_helper, which may be found in helpers.c. Most patterns do
not require a helper, and this field is filled with NULL.

The matcher searches the board for places where this layout appears on
the board, and chooses the highest scoring pattern.


Pattern Attributes
------- ----------

After the pattern, some supplementary information in the format:

  :trfno, patwt, assistance, classification, 
       obonus, xbonus, splitbonus, minrand, maxrand, helper_function

Here trfno represents the number of transformations of the pattern to
consider, usually 8 (no symmetry, for historical reasons), or one of |
\ / - + X, where the line represents the axis of symmetry.  (E.g. |
means symmetrical about a vertical axis.)  patwt is the numerical
pattern value - if there is a helper function (see below), it is the
maximum weight it can return.

The assistance attribute reflects the fact that a pattern may have
different values depending on external circumstances. For example, a
pattern to connect is less important where I am powerful, but more
important where my opponent is powerful. There are two different
methods of assistance, wind assistance and moyo assistance.

Wind assistance, wind(ucutoff, uvalue, mycutoff, myvalue), is based on
the power of the stones in a neighborhood of the considered move. My
power (mypower) and your power (upower) are measured by the function
testwind(). The actual value of the wind assistance is given by the
formula:

  uvalue*min(upower,abs(ucutoff)) + myvalue*min(mypower,abs(mycutoff)).

upower and ucutoff must have the same sign, as must mypower and
mycutoff.  In practice we have mostly used positive values for these
parameters. We have always given uvalue and myvalue the value 1 or
in rare instances 2. 

Moyo assistance, moyo(moyocutoff, moyovalue), is based on an
estimation of "moyo", in practice a combination of territory and
influence for both players. The function delta_moyo() computes the
difference in moyo between the current position and after the move has
been made. The actual value of the moyo assistance is given by the
formula:

  moyovalue*min(deltamoyo,moyocutoff)


The classification scheme is as follows : a sequence of
zero or more of the following characters, each with a
different meaning.

s  :  no checking is done. This is appropriate for sacrifice patterns.
      Otherwise, the matcher requires that the stone played cannot
      be trivially captured.

n  :  in addition to usual check that the stone played cannot be
      trivially captured, it is also confirmed that an opponent
      move here could not be captured.

O  :  it is checked that every friendly ('O') stone of the pattern
      belongs to a dragon which is classified as ALIVE or UNKNOWN.

o  :  it is checked that every friendly ('O') stone of the pattern
      belongs to a dragon which is classified as DEAD or UNKNOWN.

X  :  it is checked that every opponent ('X') stone of the pattern
      belongs to a dragon which is classified as ALIVE or UNKNOWN.

x  :  it is checked that every opponent ('X') stone of the pattern
      belongs to a dragon which is classified as DEAD or UNKNOWN

D  :  if it is found that an O stone at (m,n) of the pattern can be 
      captured (worm[m][n].attacki != 0) then the move at * is tried.
      If it is found to defend the stone, worm[m][n].defend is set
      to equal *. This means that the defender will later use this
      move to defend the stone.

C  :  if two distinct O dragons occur in the pattern, the pattern
      is given the connection_value.

B  :  if two distinct X dragons occur in the pattern, the pattern
      is given the connection_value.

A  :  if it is found that an X stone at (m,n) of the pattern can be 
      captured but also defended (worm[m][n].attacki != 0 and
      worm[m][n].defendi != 0) then the move at * is tried.
      If it is found to also attack the stone, worm[m][n].attack is
      set to equal *. This means that the attacker will later use this
      move to attack the stone.

Most likely class to use is OX (which rejects pattern if either sides
stones are dead). The string '-' may be used as a placeholder. (In
fact any characters other than the above and ',' are ignored.)

o and O could conceivably appear in a class, meaning it applies only
to UNKNOWN. X and x could be used together.

Some care must be taken with the A and D classes. If more than one
worm that can be attacked or defended is present in the pattern, only
one of them, arbitrarily chosen, will be found. 

The classes B and C can be used together. If both connection values
are greater than 0, the pattern is given a combined value which is the
larger of them plus a fraction of the smaller one.

The values obtained for the B and C classes are further limited by the
sum of the primary pattern weight (patwt) and the assistance value.
The bonuses described below are applied after this limitation.

The field obonus is a bonus which is added when the pattern
contains any dragon of color O with dragon[m][n].weak != 0. As
explained on docs/MOYO, this means that the dragon has size
at least 2 and between 0 and 20 points of area, computed by
the Bouzy 4/0 algorithm. Similarly the xbonus is added when the
pattern contains at least one weak X dragon.

The field splitbonus is a bonus which is added when the move splits
opponent dragons on a large scale or joins own dragons in the same
manner. See docs/MOYO for an explanation of the meta_connect
property.

To avoid playing the same moves each game, minrand and maxrand
specifies a random adjustment of the move value, uniformly distributed
between minrand and maxrand, inclusively. This feature is primarily
used for fuseki moves, where the choice of exact moves is a matter of
inspiration anyway.

helper_fn is the name of a c function which will be invoked
to assist in the evaluation of the pattern. It will be passed
the co-ordinates on the board of the pattern element marked '*',
the rotation of the pattern which has been matched,
and the color of the piece for whom the move is being considered.
('O' in the key above). Facilities are provided for navigating
around the pattern taking the rotation into account.


Tuning the Pattern Database
---------------------------

Since the pattern database GNU Go's personality to a very great
extent, much time can be devoted to ``tuning'' it.  Here are some
suggestions.

If you want to experiment with modifying the pattern database, invoke
with the -a option.  This will cause every pattern to be evaluated,
even if its maximum possible contribution is smaller than a pattern
already found. This makes the program less efficient, but then you can
see how much you must increase a pattern value in order to `promote' a
better move over the move actually chosen.

You can obtain a Smart Go Format (SGF) record of your game in at least
two different ways. One is to use CGoban to record the game. You can
also have GNU Go record the game in Smart Go Format, using the -o
option. It is best to combine this with -a. Do not try to read the sgf
file until the game is finished and you have closed the sgf
window. This does not mean that you have to play the game out to its
conclusion. You may close the CGoban window on the game and GNU Go
will close the sgf file so that you can read it.

If you record a game in SGF form using the -o option, GNU Go will add
labels to the board to show all the moves it considered, with their
values. This is an extremely useful feature, since one can see at a
glance whether the right moves with appropriate weights are being
proposed by the pattern matcher. If bad moves are being proposed, one
may modify a pattern to exclude it, or reduce the value of the
pattern.  If important moves are not proposed at all, you may have
found a gap in the pattern database, and you can add a pattern. If the
right move is proposed but with too low a score, this may be a sign
that you should adjust its weight upwards. It is almost always best
to make the *minimum* adjustment needed to correct the bad behavior.

If you decide to add a pattern, give some thought to adding the
pattern in exactly the right generality by putting ? at irrelevant
locations, and by using the o and x options.

First, due to a bug of unknown nature, it occasionally happens
that GNU Go will not receive the SIGTERM signal from CGoban that it
needs to know that the game is over. When this happens, the sgf file
ends without a closing parenthesis, and CGoban will not open the
file. You can fix the file by typing:

 echo ")" >>[filename]  

at the command line to add this closing parenthesis. Or you could
add the ) using an editor.

Pattern weights exceeding 99 can be displayed by CGoban but you may
have to resize the window in order to see all three digits. Grab the
lower right margin of the CGoban window and pull it until the window
is large. All three digits should be visible.

If you are playing a game without the -o option and you wish to
analyze a move, you may still use CGoban's ``Save Game'' button to get
an SGF file. It will not have the values of the moves labelled, of
course.

Once you have a game game saved in SGF format, you can analyze any
particular move by running:

  gnugo -l [filename] -L [move number] -t -a -w

to see why GNU Go made that move, and if you make changes to the
pattern database and recompile the program, you may ask GNU Go to
repeat the move to see how the behavior changes.

Alternatively, you can use the CGoban tools to delete all moves after
and including the one you want to study, and then load without the -L
option.

If a pattern is contributing a bad move, you can adjust its weight
downward, or you you can adjust the weight of a pattern which is
contributing a good move up. If no pattern is contributing the move
that you think should be made, then you may add a pattern.

You can also get a visual display of the dragons by compiling with a
color option and displaying in an rxvt window, using the -T
option. (Xterm will probably not display the colors so use rxvt or
GNU/Linux console.)  Be sure that you have uncommented either of the
color options in the make file, and from the rxvt window, try:

  gnugo -l [filename] -L [move number] -T

This is very handy in recognizing at a glance which strings GNU Go has
amalgamated into a single dragon, and the status of the dragon. Live
dragons are flagged green, dead dragons white, dragons of unknown
status yellow, and dragons of critical status red. See DRAGON for
definitions of these terms.

If you want to get the same game over and over again, you can
eliminate the randomness in GNU Go's play by changing the value of
seed in main.c to a fixed nonzero integer. If seed==0, then GNU Go
will play a different game each time.



Defensive Patterns
--------- --------

Usually a pattern will only contribute a move if its value is
large enough to outweigh all other moves which have been
found. There is an exception to this, however. If the
pattern classification string contains a `D', the pattern
is a defensive one. If an O string is found in the pattern
which can be captured, and if the move at * defends it,
then the point of defense (worm[m][n].defendi, worm[m][n].defendj)
is moved to *. This means that even if the pattern has small
value, the defensive move will be remembered later when 
defender() is run.


Offensive Patterns
--------- --------

Another exception is patterns with a classification string containing
an `A'. These patterns are offensive ones. If an X string is found in
the pattern which can be captured but also defended, and if the move
at * also attacks it, then the point of attack (worm[m][n].attacki,
worm[m][n].attackj) is moved to *. This means that even if the pattern
has small value, the offensive move will be remembered later when
attacker() is run. Notice that this means that the suggested move
will never find an attack that wasn't found otherwise, but it can be
used to capture enemy stones more efficiently or with better shape
than the move attacker() would have found unassisted.



Helper functions
----------------

Helper functions can be provided to assist the matcher in weighing up
the importance of a move. The helper is supplied with the compiled
pattern entry in the table, and the (absolute) position on the board
of the '*' point.

One difficulty is that the helper must be able to cope with all the
possible transformations of the pattern.  To help with this, a
transformation number is supplied.  This number can be passed to a
utility function offset() with the relative co-ordinates in the
original, untransformed pattern. This function will return the actual
board co-ordinates to use for the indicated stone.

The actual helper functions are in helpers.c. They are declared
in patterns.h.

As an example to show how to write a helper function, we consider
defend_bamboo_helper. This begins with a comment:

/*

?X?        ?X?         
O.O        ObO 
O.*        Oat

*/

The image on the left is the actual pattern. On the right we've
taken this image and added letters to label (ti, tj), (ai, aj)
and (bi, bj). Of course t is always at *, the point where GNU
Go will move if the pattern is adopted.


int
defend_bamboo_helper (struct pattern *pat, int transformation, int ti, int tj, int color)
{
  int ai, aj, bi, bj, ci, cj;
  int tval=0;
  int other=OTHER_COLOR(color);

  offset(0, -1, ti, tj, &ai, &aj, transformation);
  offset(-1, -1, ti, tj, &bi, &bj, transformation);

  if (strategic_distance_to(other, ti, tj)>10)
    return (0);          /* solid connection is better */
  if (trymove(bi, bj, other)) {
    if (trymove(ai, aj, color)) {
      if (safe_move(ti, tj, other))
	  tval=compute_score(ti, tj, color, pat);
      popgo();
    }
    popgo();
  }
  return (tval);
}

The offsets tell GNU Go the positions of the two stones at a=(ai,aj)
and b=(bi,bj). The pattern is subjected to two tests. First, the
strategic_distance to X (see DRAGONS) .

This function defend_bamboo_helper was written before the 
autohelper functions oplay_attack and xplay_attack became
available. Its functionality could be duplicated using an
autohelper. Autohelpers are discussed below.



"Wind Assistance" 
-----------------

Each pattern can take additional numbers in the : line. For example

"connect if invaded"

OX..
.*.O
.?.?

:8,55,wind(20,1,0,0),-,0,0,0,NULL

These represent additional biases to the score for the influence of
nearby stones. The first pair are a multiplier and a cutoff for enemy
stones, and the second for friendly stones. The actual weight
(computed in the function compute_score()) is given by the formula:

patwt+uvalue*min(upower,abs(ucutoff))+myvalue*min(mypower,abs(mycutoff)).

Typically uvalue (if nonzero) would have the value 1, meaning that the
score increases by 1 for each increase in upower, up to a maximum of
ucutoff, after which it does not increase. Thus in this example, the
value of the pattern can increase up to 75, becoming more valuable
when the opponent becomes strong in the area. This is a good feature
for patterns which help the safety of our group.



Autohelpers
-----------

In addition to the hand-written helper functions in helpers.c there
can be automatic helper functions. These are briefly described in
the pattern database and compiled into C source which goes into
patterns.c.

The "pattern compiler" is based on the idea of constraint diagrams and
expressions. To give an example, one pattern consists of a pair of
diagrams:

Pattern 707

|oOOX           maybe capture corner
|..XO
|.*XO
|..??
+----

:8,85,0,s,10,0,0,NULL

|obbX
|..Aa
|.*Aa
|..??
+----

;(lib(A)<=4) && (lib(a)>=lib(A)-1) && (lib(b)>=lib(A))

The first diagram and the colon line has exactly the same
interpretation as usual. The diagram below and the
semicolon line are optional and can only be used to
reject the pattern given above. Note that some strings
now have labels which are referred to in the
constraint.

Only strings for which we have constraints need be
labeled. Labels may be any letter except OoXx. To make
the database consistent and easy to read it is our
convention that X strings should be upper-case and O
strings lower-case, but the implementation does not
enforce this.  Neither does it require that all stones in
a string be labeled (it goes with the first appearance)
but it is good practice to do so anyway.

The constraint expression is transformed by mkpat into an
automatically generated helper function (there is a new
field in the pattern struct, so it does not conflict with
the old helper). lib(x) can be regarded as a macro which
is expanded by mkpat into worm[xi][xj].liberties. The
resulting expression must be valid c code, otherwise the
generated patterns.c won't compile. In principle any code
can be written on the line but to keep the database
maintainable we should restrict ourselves to
boolean and arithmetic expressions, which anyone should
be able to understand and write with no more than a
little trouble. If the expression evaluates to true the
pattern is accepted by the autohelper, if false it is
rejected.


Autohelper Functions
--------------------
lib(x)
lib2(x)
lib3(x)
lib4(x)

Number of first, second, third, and fourth order liberties of a worm
respectively. See the documentation on worms in doc/DRAGON for
definitions.


xlib(x)
olib(x)

The number of liberties that an enemy or own stone, respectively,
would obtain if played at the empty intersection x.


ko(x)

True if x is either a stone or an empty point involved in a ko
position.


status(x)
alive(x)
unknown(x)
critical(x)
dead(x)

Status of a dragon. status(x) returns an integer that can have the
values ALIVE, UNKNOWN, CRITICAL, or DEAD. The four other functions
returns true if the dragon has the corresponding status and false
otherwise. See the documentation on dragons in doc/DRAGON for
definitions.


genus(x)

The number of eyes of a dragon. It is only meaningful to compare this
value against 0, 1, or 2.


xarea(x)
oarea(x)
xmoyo(x)
omoyo(x)
xterri(x)
oterri(x)

Functions related to various kinds of influence and territory
estimations, as described in doc/MOYO. xarea(x) evaluates to true if
x is either a living enemy stone or an empty point within his "area".
oarea(x) is analogous but with respect to our stones and area. The
main difference between area, moyo, and terri is that area is a very
farreaching kind of influence, moyo gives a more realistic estimate of
what may turn in to territory, and terri gives the points that already
are believed to be secure territory.


weak(x)

True for a dragon that is perceived as weak. The definition of weak is
given in doc/MOYO.


attack(x)
defend(x)

Results of tactical reading. attack(x) is true if the worm can be
captured, defend(x) is true if there also is a defending move. Please
notice that defend(x) will return false if there is no attack on the
worm.


safe_xmove(x)
safe_omove(x)

True if an enemy or own stone, respectively, can safely be played at
x. By safe it is understood that the move is legal and that it cannot
be captured right away.


odefend_against(x,y)
xdefend_against(x,y)

True if an own stone at x would stop the enemy from safely playing at
y, and conversely for the second function.

does_defend(x,y)
does_attack(x,y)

True if a move at x defends/attacks the worm at y. For defense a move
of the same color as y is tried and for attack a move of the opposite
color.

xplay_defend(a,b,c,...,z)
oplay_defend(a,b,c,...,z)
xplay_attack(a,b,c,...,z)
oplay_attack(a,b,c,...,z)

These functions make it possible to do more complex reading
experiments in the constraints. All of them work so that first the
sequence of moves a,b,c,... is played through with alternating colors,
starting with X or O as indicated by the name. Then it is tested
whether the worm at z can be attacked or defended, respectively. It
doesn't matter who would be in turn to move, a worm of either color
may be attacked or defended. For attacks the opposite color of the
string being attacked starts moving and for defense the same color
starts. The defend functions return true if the worm cannot be
attacked in the position or if it can be attacked but also defended.
The attack functions return true if there is a way to capture the
worm, whether or not it can also be defended.

eye(x)
proper_eye(x)
marginal_eye(x)

True if x is an eye space for either color, a non-marginal eye space
for either color, or a marginal eye space for either color,
respectively.


Implementation
--------------

The pattern code in GNU Go 2.4 is fairly straightforward conceptually,
but because the matcher consumes a significant part of the time in
choosing a move, the code is optimized for speed. Because of this
there are implementation details which obscure things slightly.

In GNU Go 2.4, the ascii patterns.db file is precompiled into tables
(see patterns.h) by a standalone program mkpat.c, and the resulting
file patterns.c is compiled and linked into the main gnugo executable.

Each pattern is compiled to a header, and a sequence of elements,
which are (notionally) checked sequentially at every position and
orientation of the board. These elements are relative to the pattern
'anchor' (or origin).  One X or O stone is (arbitrarily) chosen to
represent the origin of the pattern. (We cannot dictate one or the
other since some patterns contain only one colour or the other.)  All
the elements are in co-ordinates relative to this position. So a
pattern matches "at" board position (m,n,o) if the the pattern anchor
stone is on (m,n), and the other elements match the board when the
pattern is transformed by transformation number 'o'. (See below for
the details of the transformations, though these should not be
necessary)

There are two modes of operation:

i) Each pattern can be compiled to one entry in patterns.c,
   describing the number of permutations in which it
   must be tested on the board. These transformations
   are calculated by the matcher at runtime.

# This is obsolete, I guess. /gf
ii) All the transformations of each pattern are calculated
   by mkpat, and each is written out as a separate
   pattern. This results in larger executable size
   and longer compile time, but much faster performance
   at run time.


Symmetry and transformations
----------------------------

In general, each pattern must be tried in each of 8 different
permutations, to reflect the symmetry of the board. But some
patterns have symmetries which mean that it is unnecessary
(and therefore inefficient) to try all eight. The first
character after the ':' can be one of '8','|','\','/',
'X', '-', '+', representing the axes of symmetry.


transformation   I    -    |     .     \    l    r     /
                ABC  GHI  CBA   IHG   ADG  CFI  GDA   IFC
                DEF  DEF  FED   FED   BEH  BEH  HEB   HEB
                GHI  ABC  IHG   CBA   CFI  ADG  IFC   GDA

                 a    b    c     d     e    f    g     h

Then if the pattern has the following symmetries, the
following are true...

|  c=a, d=b, f=e, h=g
\  e=a, g=c, f=b, h=d
/  h=a, f=c, g=b, e=d
X  a=d=e=h, b=c=f=g


To keep the implementation simple, we currrently
support only |, \, X

We can choose to use transformations a,d,f,g  as the
unique transformations for patterns with either | or \
symmetry.

Thus we choose to order the transformations a,f,d,g,....
and choose first 2 for X, the first 4 for both | and \,
and all 8 for non-symmetrical patterns.

[With hindsight, I'm sure there must have been
 an obvious geometrical justifaction for why
 we have chosen the rotations...
 Each of the reflection operations (e-h) is equivalent
 to reflection about one arbitrary axis followed by
 one of the rotations (a-d).
 We can choose to reflect about the axis of symmetry
 (which causes no net change) and can therefore conclude
 that each of e-h is equivalent to the reflection (no-op)
 followed by a-d.
 This argument therefore extends to include - and / as
 well as | and \.
]



Implementation Details
----------------------

i) An entry in the pattern header states whether the anchor is an X or
an O. This helps performance, since all transformations can be
rejected at once if the anchor stone does not match. (Ideally, we
could just define that the anchor is always O or always X, but some
patterns contain no O's and some contain no X's.)

ii) The pattern header contains the size of the pattern (ie the
co-ordinates of the top left and bottom right elements) relative to
the anchor. This allows the pattern can be rejected quickly if there
is not room for the pattern to fit around the anchor stone in a given
orientation (ie it is too near the edge of the board).  The bounding
box information must first be transformed like the elements before it
can be tested, and after transforming, we need to work out where the
top-left and bottom-right corners are.

iii) The edge constraints are implemented by notionally padding the
pattern with rows or columns of '?' until it is exactly 19 elements
wide or high. Then the pattern is quickly rejected by (ii) above if it
is not at the edge. So the example pattern above is compiled as if it
was written


"example"
.OO????????????????
*XX????????????????
o??????????????????
:8,80


iv) The elements in a pattern are sorted so that non-space
elements are checked before space elements. It is hoped that,
for most of the game, more squares are empty, and so the
pattern can be more quickly rejected doing it this way.

v) The patterns themselves are sorted by decreasing
maximum-weight, which is the maximum value the pattern can
take, taking weight and wind assistance into account.  For
this to work, the weight stored for patterns with helpers
must be the maximum which the helper can return. As a hint,
to simplify maintenance, the helper can access the stored
weight from the pattern structure passed in.

vi) The actual tests are performed using an 'and-compare'
sequence. Each board position is a 2-bit quantity.
%00 for empty, %01 for O, %10 for X.
We can test for an exact match by and-ing with %11 (no-op),
then comparing with 0,1 or 2. The test for 'o' is the
same as a test for 'not-X', ie not %10. So and with %01
should give 0 if it matches. Similarly 'x' is a test that
bit 0 is not set.



The "grid" optimisation
-----------------------

This is a compile time option. By editing the makefile,
you can use this faster code to match patterns. The only 
disadvantage to using this code is that it might be harder 
to understand and debug.

As described in (vi), the comparisons between pattern and
board are performed as 2-bit bitwise operations. Therefore they
can be performed in paralled, 16-at-a-time on a 32-bit machine.

Suppose the board is layed out as follows :

 .X.O....OO
 XXXXO.....
 .X..OOOOOO
 X.X.......
 ....X...O.

which is internally stored internally in a 2d array (binary)

 00 10 00 01 00 00 00 00 01 01
 10 10 10 10 01 00 00 00 00 00
 00 10 00 00 01 01 01 01 01 01
 10 00 10 00 00 00 00 00 00 00
 00 00 00 00 10 00 00 00 01 00


we can compile this to a composite array in which each element
stores the state of a 4x4 grid of squares :

 ????????  ????????  ???????? ...
 ??001000  00100001  10000100
 ??101010  10101010  10101001
 ??001000  00100000  10000001

 ??001000  00100001  ...
 ??101010  10101010
 ??001000  00100000
 ??001000  10001000 

...

 ??100010  ...
 ??000000
 ????????
 ????????


Where '??' is off the board.

We can store these 32-bit composites in a 2d merged-board array,
substituting the illegal value %11 for '??'.

Similarly, for each pattern, mkpat produces appropriate 32-bit and-value
masks for the pattern elements near the anchor. It is a simple matter
to test the pattern with a similar test to (vi) above, but for 32-bits
at a time.

The Joseki Compiler
--- ------ --------

GNU Go includes a joseki compiler in patterns/joseki.c. This
processes an sgf file (with variations) and produces a sequence
of patterns which can then be fed back into mkpat. The joseki
database is in files in patterns/ called hoshi.sgf, komoku.sgf, 
sansan.sgf, mokuhadzushi.sgf and takamoku.sgf. 

Not every node in the sgf file contributes a pattern. The nodes
which contribute patterns have the joseki in the upper right
corner, with the boundary marked with an "A" and the value
given by a comment.

Advanced Features
-------- --------

The joseki compiler is able to generate a constraint line in the .db. 
The square symbol is a shortcut for oarea(), the triangle is xarea() and the
circle is (!oarea()&&!xarea()) = an empty area.

The delimiter between value and classification in the SGF 
comment must be ";", for example:

81;
D

Spaces and \n may be omitted.

These features are experimental and are currently not used in the 
joseki files. A file patterns/fuseki2.sgf is included as a 
demonstration.