This page is still very much incomplete. Eventually it should contain detailed descriptions of the search algorithms used by Kombilo. (This should be integrated into the libkombilo documentation.)
List of Algorithms:
Here are some general remarks:
Board coordinates
We use the following coordinate system (given here for board size 19x19):
(0,0) ---------------------- (18,0) | | | | | | | | | | | | | | | | (0,18) --------------------- (18,18)
This corresponds nicely to the system used by SGF ((0,0) = aa, (18,18) = ss).
Board symmetries
There are 8 symmetries of the square, and hence of the go board. We enumerate them as follows
0. x -> x, y -> y 1. x -> 18-x, y -> y 2. x -> x, y -> 18-y 3. x -> 18-x, y -> 18-y 4. x -> y, y -> x 5. x -> 18-y, y -> x 6. x -> y, y -> 18-y 7. x -> 18-y, y -> 18-x
So for instance the symmetry 0 is the identity map, and symmetry 1 is reflection with respect to the vertical axis.
Furthermore, given a position, there is the color swap which exchanges black and white stones.
The Pattern class
A pattern, say
XXOo ..Xx ..O*
is given by
- sizeX = 4 - sizeY = 3 - and a string initialPos = "XXOo..Xx..O*"
Here we use the following notation for search patterns:
. must be empty X must have a black stone O must have a white stone x must be black or empty o must be white or empty * can be arbitrary
We use an analogous coordinate system as for the board, so a point with coordinates (i,j) is stored at position (i + j*sizeX) in the string.
The area of the board where we want to search for the given pattern (or, in other words, the set of permissible translations) is described by
left, right, top, bottom
where the rectangle with corners (left,top) and (right,bottom) is the set of possible positions for the upper left point of the pattern. For instance, if all entries are 0, then the upper left corner is the only one where we would look for the pattern.
Possibly a list of continuations
corresponding PatternList
This is a list of all reflections, rotations etc. of the pattern, in other words the set of images of the patterns under symmetries of the board.
Continuations
When doing a pattern search, we want to keep track of possible continuations. Of course, for images of the original pattern under a symmetry, any continuation has to be "re-mapped" to the original pattern. Furthermore, when showing continuations, symmetry needs to be taken into account, for instance in
+-------- |........ |........ |.....a.. |...X.... |........ |..b..... |........ |........
the positions a and b are equivalent, and only one of them should be shown as a possible continuation.
To keep track of all this, we use, for each pattern in the pattern list, a dictionary Symmetries such that if a continuation is played in the pattern at the point (i,j), then Symmetries[color, i, j] == (c,x,y) which means that the result should be shown at (x,y) in the original pattern with color c. ('color' is the color (black/white) of the continuation.)
