[gnugo-devel] breakin code explanations

[Arend Bayer]

(Moved back to list as this should be interesting to more people.)

On Sun, 27 Jul 2003 address@hidden wrote:

> 
> > Can you say a little more precisely where exactly you think my comments are
> > unsufficient? breakin.c contains a lot of comments as far as I can
> > recall. This uses the recursive reading in readconnect.c which tries to
> > connect from a string to a goal area.
> 
> The file begins with a prefatory remark which reads as follows:
> 
> /* This module looks for break-ins into territories that require
>  * deeper tactical reading and are thus impossible to detect for the
>  * influence module. It gets run after the influence module and revises
>  * its territory valuations.
>  *
>  * The procedure is as follows: We look at all big (>= 10) territory regions
>  * as detected by the influence code. Using the computation of
>  * connection distances from readconnect.c, we compute all nearby vertices
>  * of this territory. We look for the closest safe stones belonging to
>  * the opponent.
>  * For each such string (str) we call
>  * - break_in(str, territory) if the opponent is assumed to be next to move,
>  *   or
>  * - block_off(str, territory) if the territory owner is next.
>  * If the break in is successful resp. the blocking unsuccessful, we
>  * shrink the territory, and see whether the opponent can still break in.
>  * We repeat this until the territory is shrunk so much that the opponent
>  * can no longer reach it.
>  */
> 
> This is helpful but seems unfinished.
Where is it unfinished?

> Why is the process repeated?
> 
> To elaborate on the last question, as I understand it the
> entire effect of the break in code is through calls to
> add_expand_territority_expand_move. No data about the size of
> the break in is retained. But once a break in is found, it is

I think here is the misunderstanding. The main effect of the break-in code
is, as mentioned above, revising the territory valuation. This is done via
the calls to influence_erase_territory(). The process is repeated to see
how far the break-in can go, i.e. how much territory we have to erase.

The heuristic for this is somewhat crude: If a successful break-in is
found, it is assumed that the closest 3-5 intersections of the territory
in question cannot get defended. They are then stored in the
non_territory[] array and removed from the goal list, and the break-in
try is repeated with the smaller goal (see comments heading
break_in_goal_from_str()). (Doing this with 3-5 intersections should
guarantuee that we are never to far off from the correct value.)

> I think that describing what happens in an explicit example would
> be helpful.

I don't have an sgf-reader here, so I cannot give too many details. But
the file break_in.sgf you looked at should be a correct example.

The crucial part is, of course, the analysis of the move at G7. Note that
while this move is played, it is correctly assumed unsafe both with and
without the break-in code, hence without the break-in code its territorial
value is -1.01. But when running with -d0x102000 you see traces such as
"Erasing territory at E8 -b." They come from:

  Trying to break (white to move) white's territory E9 (1)  F9 (1)  G9 (1)  H9 
(1)  J9 (1)  E8 (1)  F8 (1)  G8 (1)  H8 (1)  J8 (1)  G7 (1)  H7 (1)  J7 (1)  H6 
(1)  J6 (1)  G5 (1)  H5 (1)  J5 (1)  H4 (1)  J4 (1)  G3 (1)  H3 (1)  J3 (1)  H2 
(1)  J2 (1)  H1 (1)  J1 (1)
  Trying to break in from D6 to:
E9 (1)  F9 (1)  G9 (1)  E8 (1)  F8 (1)  G8 (1)  H8 (1)  H7 (1)  J7 (1)  H6 (1)  
J6 (1)  H5 (1)  J5 (1)  H4 (1)  J4 (1)
block_off D7, result 0 PASS (88, 14644 nodes, 0.67 seconds)

This means that, white to move cannot prevent black to break into this
territory from D7. You can see the reading for this by doing
block_off D7 E9 F9 G9 E8 F8 G8 H8 H7 J7 H6 J6 H5 J5 H4 J4
block_off D7, result 0 PASS (88, 14644 nodes, 0.67 seconds)

At the first go, territory at E8 and G5 is erased, and then the same is
repeated with a smaller goal (a couple of times in this case). This is
how G7 gets its territorial evaluation of 14 pts.

(You mentioned that G7 gets a connect/cut bonus in an earlier e-mail,
but that is true without the break-in code, too.)

Arend