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

# 12. Pattern Based Reading

In the tactical reading code in ‘`reading.c`’, the code generating the moves which are tried are all hand coded in C, for efficiency. There is much to be said for another type of reading, in which the moves to be tried are generated from a pattern database.

GNU Go does three main types of pattern based reading. First, there is the OWL code (Optics with Limit Negotiation) which attempts to read out to a point where the code in ‘`engine/optics.c`’ (see section Eyes and Half Eyes) can be used to evaluate it. Like the tactical reading code, a persistent cache is employed to maintain some of the owl data from move to move. This is an essential speedup without which GNU Go would play too slowly.

Secondly, there is the ‘`engine/combination.c`’ which attempts to find combinations—situations where a series of threats eventually culminates in one that cannot be parried.

Finally there is the semeai module. A semeai is a capturing race between two adjacent DEAD or CRITICAL dragons of opposite colors. The principal function, `owl_analyze_semeai()` is contained in ‘`owl.c`’. Due to the complex nature of semeais, the results of this function are more frequently wrong than the usual owl code.

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

## 12.1 The Owl Code

The life and death code in ‘`optics.c`’, described elsewhere (see section Eyes and Half Eyes), works reasonably well as long as the position is in a terminal position, which we define to be one where there are no moves left which can expand the eye space, or limit it. In situations where the dragon is surrounded, yet has room to thrash around a bit making eyes, a simple application of the graph-based analysis will not work. Instead, a bit of reading is needed to reach a terminal position.

The defender tries to expand his eyespace, the attacker to limit it, and when neither finds an effective move, the position is evaluated. We call this type of life and death reading Optics With Limit-negotiation (OWL). The module which implements it is in ‘`engine/owl.c`’.

There are two reasonably small databases ‘`patterns/owl_defendpats.db`’ and ‘`patterns/owl_attackpats.db`’ of expanding and limiting moves. The code in ‘`owl.c`’ generates a small move tree, allowing the attacker only moves from ‘`owl_attackpats.db`’, and the defender only moves from ‘`owl_defendpats.db`’. In addition to the moves suggested by patterns, vital moves from the eye space analysis are also tested.

A third database, ‘`owl_vital_apats.db`’ includes patterns which override the eyespace analysis done by the optics code. Since the eyeshape graphs ignore the complications of shortage of liberties and cutting points in the surrounding chains, the static analysis of eyespace is sometimes wrong. The problem is when the optics code says that a dragon definitely has 2 eyes, but it isn’t true due to shortage of liberties, so the ordinary owl patterns never get into play. In such situations ‘`owl_vital_apats.db`’ is the only available measure to correct mistakes by the optics. Currently the patterns in ‘`owl_vital_apats.db`’ are only matched when the level is 9 or greater.

The owl code is tuned by editing these three pattern databases, principally the first two.

A node of the move tree is considered `terminal` if no further moves are found from ‘`owl_attackpats.db`’ or ‘`owl_defendpats.db`’, or if the function `compute_eyes_pessimistic()` reports that the group is definitely alive. At this point, the status of the group is evaluated. The functions `owl_attack()` and `owl_defend()`, with usage similar to `attack()` and `find_defense()`, make use of the owl pattern databases to generate the move tree and decide the status of the group.

The function `compute_eyes_pessimistic()` used by the owl code is very conservative and only feels certain about eyes if the eyespace is completely closed (i.e. no marginal vertices).

The maximum number of moves tried at each node is limited by the parameter `MAX_MOVES` defined at the beginning of ‘`engine/owl.c`’. The most most valuable moves are tried first, with the following restrictions:

- If `stackp > owl_branch_depth` then only one move is tried per variation.
- If `stackp > owl_reading_depth` then the reading terminates, and the situation is declared a win for the defender (since deep reading may be a sign of escape).
- If the node count exceeds `owl_node_limit`, the reading also terminates with a win for the defender.
- Any pattern with value 99 is considered a forced move: no other move is tried, and if two such moves are found, the function returns false. This is only relevant for the attacker.
- Any pattern in ‘`patterns/owl_attackpats.db`’ and ‘`patterns/owl_defendpats.db`’ with value 100 is considered a win: if such a pattern is found by `owl_attack` or `owl_defend`, the function returns true. This feature must be used most carefully.

The functions `owl_attack()` and `owl_defend()` may, like `attack()` and `find_defense()`, return an attacking or defending move through their pointer arguments. If the position is already won, `owl_attack()` may or may not return an attacking move. If it finds no move of interest, it will return `PASS`, that is, `0`. The same goes for `owl_defend()`.

When `owl_attack()` or `owl_defend()` is called, the dragon under attack is marked in the array `goal`. The stones of the dragon originally on the board are marked with goal=1; those added by `owl_defend()` are marked with goal=2. If all the original strings of the original dragon are captured, `owl_attack()` considers the dragon to be defeated, even if some stones added later can make a live group.

Only dragons with small escape route are studied when the functions are called from `make_dragons()`.

The owl code can be conveniently tested using the ‘`--decide-owl location`’ option. This should be used with ‘`-t`’ to produce a useful trace, ‘`-o`’ to produce an SGF file of variations produced when the life and death of the dragon at location is checked, or both. ‘`--decide-position`’ performs the same analysis for all dragons with small escape route.

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

## 12.2 Combination reading

It may happen that no single one of a set of worms can be killed, yet there is a move that guarantees that at least one can be captured. The simplest example is a double atari. The purpose of the code in ‘`combination.c`’ is to find such moves.

For example, consider the following situation:

    +---------
    |....OOOOX
    |....OOXXX
    |..O.OXX..
    |.OXO.OX..
    |.OX..OO..
    |.XXOOOXO.
    |..*XXOX..
    |....XOX..
    |.XX..X...
    |X........

Every ‘`X`’ stone in this position is alive. However the move at ‘`*`’ produces a position in which at least one of four strings will get captured. This is a combination.

The driving function is called `atari_atari` because typically a combination involves a sequence of ataris culminating in a capture, though sometimes the moves involved are not ataris. For example in the above example, the first move at ‘`*`’ is not an atari, though after ‘`O`’ defends the four stones above, a sequence of ataris ensues resulting in the capture of some string.

Like the owl functions `atari_atari` does pattern-based reading. The database generating the attacking moves is ‘`aa_attackpats.db`’. One danger with this function is that the first atari tried might be irrelevant to the actual combination. To detect this possibility, once we’ve found a combination, we mark that first move as forbidden, then try again. If no combination of the same size or larger turns up, then the first move was indeed essential.

- `void combinations(int color)`

  > Generate move reasons for combination attacks and defenses against them. This is one of the move generators called from genmove().

- `int atari_atari(int color, int *attack_move, char defense_moves[BOARDMAX], int save_verbose)`

  > Look for a combination for `color`. For the purpose of the move generation, returns the size of the smallest of the worms under attack.

- `int atari_atari_confirm_safety(int color, int move, int *defense, int minsize, const char saved_dragons[BOARDMAX], const char saved_worms[BOARDMAX])`

  > Tries to determine whether a move is a blunder. Wrapper around atari_atari_blunder_size. Check whether a combination attack of size at least `minsize` appears after move at `move` has been made. The arrays `saved_dragons[]` and `saved_worms[]` should be one for stones belonging to dragons or worms respectively, which are supposedly saved by `move`.

- `int atari_atari_blunder_size(int color, int move, int *defense, const char safe_stones[BOARDMAX])`

  > This function checks whether any new combination attack appears after move at (move) has been made, and returns its size (in points). `safe_stones` marks which of our stones are supposedly safe after this move.

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

This document was generated on January 20, 2026 using texi2html 1.82.