[gnugo-devel] Large scale attacks patch

[Stéphane Nicolet]

The patch below tries to implement a way to find the most efficient
killing of a stone (or of small dragons).


    White (O) has captured 0 pieces
    Black (X) has captured 0 pieces

    A B C D E F G H J K L M N O P Q R S T
 19 . . . . . . . . . . . . X . . . . . . 19
 18 . . . . . . O X . . . . . X O . . O . 18
 17 . . O . . O O X . . . X X O O O . . O 17
 16 . . O X . O X X . + . X O . . X O O X 16
 15 . . . O . O O . X . X X O . O O X X X 15
 14 . . . . . . . O X . . . X O X O X . . 14
 13 . . . O . . O O X . . . X(O)X X . . . 13
 12 . . . . . X X X . . . . . . . . . . . 12
 11 . . . O . . . . . . . . . . . . X . . 11
 10 . . O X X . . . . + . . . . . + . . . 10
  9 . . O . . . . . . . . . . . . O . . .  9
  8 . . O X . . . . . . . . . . . . X . .  8
  7 . . O X . . . . . . . . . X . . . X .  7
  6 . O X . . . . . . X . X . . . X X O .  6
  5 . O X . . . . X . . . X O . . . O O .  5
  4 . . O X X X . X O + X O . O . O . . .  4
  3 . . O O O . O . X X X O . . . . . . .  3
  2 . . . . . . . O O X O O X . . . . . .  2
  1 . . . . . . . . . O . . . . . . . . .  1
    A B C D E F G H J K L M N O P Q R S T


In the previous position (game large_scale1.sgf, move 111), White
has just played 013. This revives the previously dead stone Q9, and
the cvs version rekills Q9 localy with O9, thus letting White enter
the black territory in O12.

The patch solves this problem by trying all the moves around Q9
(moves thare are at a maximum Manhattan distance less than 3, and
which already have another move reason) to check if they kill on
a large scale. It finds the blocking move O12 in that case.

Note that the break-in code alone can't find O12 because Q9 is
critical, so the area below O13 is not considered territory by
the influence module. Only when all the moves around 012 have been
proven to kill Q9 can the break-in code choose the best amaong
them to prevent White from entering the territory.



    White (O) has captured 4 pieces
    Black (X) has captured 3 pieces

    A B C D E F G H J K L M N O P Q R S T
 19 . . . . . . . . . . . O X X . . . . . 19
 18 . . O . . . . . . O X X . X . . . . . 18
 17 O O X O . . . . O . O O X X . . . X . 17
 16 . O X O . O O O . + O X . X . X . . X 16
 15 O X X X O X X X O O . O . . . . X X O 15
 14 X . X X(O)X . O X O . . . . . . . O O 14
 13 . . . . . . . X X . . . . . O . O . . 13
 12 . . . . . . O . . X . X . . . . . . . 12
 11 . . X . . . . . X . . . X . . . . . . 11
 10 . . . + . . . X O O . . . . O + O . . 10
  9 . . . . X . X X O . O O . . . . X O O  9
  8 . . X . X X . O X . X X O O O . X X O  8
  7 X X . O . . O . X . X . X X . . O O .  7
  6 O X X O X X O . . . O X . X . X . O .  6
  5 . O O . O O . O . . O X X O . O . O .  5
  4 . O . O . . . . . O . X . O . + X X O  4
  3 . . . . . . . . . . O X O . X . X X O  3
  2 . . . . . . . . . . O O O X X O O X O  2
  1 . . . . . . . . . . . . X . X X . O .  1
    A B C D E F G H J K L M N O P Q R S T


This a similar situation. White has just played E14, threatening
to rescue the previously dead stone G12. Without the patch, gnugo
plays F13 to rekill G12, letting White play E13 with terrible
consequences (see the game large_scale2.sgf, move 159).
The patch finds the killing move E13 against G12 and plays it.


I am running regression now. From a previous regression run that
I have done with a (very slightly) different version of the
patch, I expect something like 15 passes (plus the previous
two new test cases) and 15 fails. However, at least 10 of these
fails seem to be new, alternate killing moves that are not
in the set yet. Wether they are acceptable will remain to be
decided by the strong players.

Stephane.

large_scale.patch
Description: application/text

large_scale1.sgf
Description: Binary data

large_scale2.sgf
Description: Binary data