Re: [gnugo-devel] fast_defense() improvement

[Arend Bayer]

> The idea is simple : there might be some adjacent opponent stones in atari,
> checking if capturing them wouldn't give enough liberties to win, proved to
> be cheap enough.
> 
> No breakage. Performance impact :
> - reading nodes :      -4.7%
> - owl nodes :        < +0.1%
> - connection nodes : < +0.01%
> 
> My imprecise timings give me a 4% speedup.
> 
> nando
> 
> - new function count_adj_stones() in board.c
> - fast_defense() looks for neighbor opponent strings in atari

Excellent! The "controversial" part was the following:

> +    /* Let's totalize liberties of the friendly strings around the 
> +     * lunch.
> +     */
> +    memset(mw, 0, sizeof(mw));
> +    adj2 = chainlinks(adjs[j], adjs2);
> +    for (k = 0; k < adj2; k++) {
> +      alib = findlib(adjs2[k], MAXLIBS, alibs);
> +      for (l = 0; l < alib; l++) {
> +     mw[alibs[l]]++;
> +     if (mw[alibs[l]] == 1)
> +       total++;
> +      }
> +    }
> +
> +    /* The captured string is treated as common liberties, and
> +     * some adjustements are made :
> +     * - we're adding a stone for capturing the lunch (-1)
> +     * - opponent might be able to remove a liberty (-1)
> +     * - and possibly force us to connect (-1)
> +     */
> +    total += countstones(adjs[j]) - 2;
> +    if (mw[lib] < 2)
> +      total--;
> +
> +    if (total >= goal_liberties) {
> +      *move = lib;
> +      return 1;

I think this extremely safe if we additionally allow for throw-ins:
Under the assumption that there is a single move to connect all
neighbouring strings of the lunch, we would achieve total - 3 if we
can play there next. If only one stone of the lunch is adjacent to the
string in question, the opponent can prevent this with a throw-in,
leading to total - 4. Almost certainly there are more involved damezumari
situations, but I doubt GNU Go would successfully attack in this case
anyway, as the defender would get stay a couple of more moves at a number
of liberties close to the one it is trying to get, by which time the number
of goal liberties has probably dropped.

So this is what the attached patch does. I have also rewritten the
liberty counting to avoid having to call memset() every time, as I would
expect this to be a bottleneck (we already spend some 2% of total run
time in memset()).

Nando, Paul, are you both happy with this? For nngs3.tst, it is almost
as good as Nando's patch (5% instead of 5.6% save of reading nodes).

Arend