Re: [gnugo-devel] tactics code cleanup

[Evan Berggren Daniel]

On Sat, 30 Nov 2002, Arend Bayer wrote:

>
> Btw, your mail-program kills spaces at the end of lines, so the patch
> applied only with -l.

Weird.  I use pine, and always have.  Have my patches had problems before?
I'll look into what it's doing.

>
> Evan wrote:
>
> > The performance differnce as a result of the patch is a slight slowdown
> > (reading nodes in reading.tst 97293 -> 98746).  However, this seems to be
> > a result of poor ordering.  My patch removes some overlap between the
> > different functions, but also removes the ordering of the function calls.
> > Tuning of the move ordering should solve this.
>
> I thought we had agreed that it is not sufficient to count reading nodes
> for reading.tst.

It's not precise, but I figured it was sufficient to classify the overall
change as "small."  I'll run more, though.


> > I plan to redo the move ordering patch I sent in earlier on a larger test
> > suite, so that should fix the performance problem.
>
> Sorry, this adresses only some of the performance problems. The other
> is that we now generate more moves than necessary, if some of the
> earlier helper functions already produce a successful move. As most of
> the time in tactical reading is spent generating moves, this is an
> important performance issue. This can only be checked by careful timing.
>
> This has been discussed on the mailing list.
>
> This means we need to think carefully in how many batches we want to
> generate moves in the attack?/defend? functions. With your patch it's
> just 2. I'd guess that 3 or 4 is rather what we want.

OK, I'll go add that.  Would turning the trymove block into a macro be in
order?

>
> Also there are other reasons for the ordering of function calls as they
> are:
>
> > -  /* We place the more speculative moves trying to break chain links
> > -   * with 2 or 3 liberties last, because these moves often are not
> > -   * really relevant.
> > -   */
>
> E.g. here I would assume this has not only to do with performance
> tuning. If there is a direct move to defend, then a breack_chain3 move
> will most likely also defend. But of course what we want to return is the
> direct move. (Could be important in many situations.)

Two thoughts:

The order_moves tuning should fix this somewhat.  If it doesn't already,
it could award a bonus for moves near the string.

In many cases we only care about success or failure (eg when checking
whether the attack move worked).  When called by the move generation or
owl code, we are currently asking the wrong question.  What we really want
is a list of all moves that attack or defend the string.  Perhaps only
getting some of them is a viable performance tradeoff, but I don't think
we should count on attack() or find_defense() returning the best move;
that would seem to be beyond the intent of the function, especially since
"best" may be a changing criteria (eg if for move generation, we would
prefer an attack that kills unconditionally instead of in a ladder; for
owl code we prefer the attack that is also a vital point).  I plan to
write these functions at some point soon, unless there is a sense that
they aren't so useful after all.

> So in summary, this patch is welcome, but please be more careful when
> making such big changes. You have to assume that the place of every single
> function call was carefully chosen when the function was originally
> introduced.

Point taken.

> And here I am absulutely sure we DON'T want to have these in the first
> batch. attack2() has to be a fast function if it can kill directly.
>
> Similar issues are all over the place in your patch.

OK.  I'll fix that.

>
> > +      /* Check if the two liberties are located like the figure above. */
> > +      if (alib != SW(blib)
> > +          && alib != NW(blib)
> > +          && alib != NE(blib)
> > +          && alib != SE(blib))
> > +        continue;
> > +
> > +      ai = I(alib);
> > +      aj = J(alib);
> > +      bi = I(blib);
> > +      bj = J(blib);
> > +      /* Which of the two corner points should we use? One of them is
> > +       * always occupied by the string at (str), the other one is either
> > +       * free or occupied by something else.
> > +       */
> As an aside, this comment seems wrong to me (both before and after your
> patch).

Agreed.

>
> > -static int
> > -edge_closing_backfill(int str, int apos, int *move)
> > +static void
> > +edge_closing_backfill_moves(int str, int apos, struct reading_moves *moves)
> >  {
> >    int color = board[str];
> >    int other = OTHER_COLOR(color);
> > @@ -4168,7 +3942,7 @@
> >      if (ON_BOARD(apos - up))
> >        continue;
> >      if (board[apos + up] != color)
> > -      return 0;
> > +      return;
> >      if (board[apos + right] == EMPTY
> >     && (!ON_BOARD(apos - right)
> >         || board[apos - right] == color))
> > @@ -4180,14 +3954,14 @@
> >        right = -right;
> >      }
> >      else
> > -      return 0;
> > +      return;
> >
> >      if (board[apos + up + right] != other)
> > -      return 0;
> > +      return;
> >
> >      bpos = apos + up + 2 * right;
> >      if (!ON_BOARD(bpos))
> > -      return 0;
> > +      return;
> >
> >      cpos = apos + 2 * right;
> >
> > @@ -4204,13 +3978,11 @@
> >        number_o++;
> >
> >      if (number_o > number_x)
> > -      return 0;
> > +      return;
> >
> > -    *move = apos + right;
> > -    return WIN;
>
> edge_close_backfill() seems to have returned WIN without even checking
> whether the string can be defended. So either I am completely
> misunderstanding this function, or this is a gross bug.
>
> As a start, a patch to correct this (and testing what this does) would
> be very welcome.

edge_close_backfill() is currently called as

if (edge_closing_backfill())
  ADD_CANDIDATE_MOVE();

This is confusing and different from all other such functions, but is not
actually a bug in the behavior of the code.


> > +static void
> > +break_chain3_moves(int str, struct reading_moves *moves)
> > @@ -4658,6 +4421,7 @@
> >       */
> >      findlib(apos, 3, libs);
> >
> > +#if 1
> >      /* If the 3 liberty chain easily can run away through one of the
> >       * liberties, we don't play on any of the other liberties.
> >       */
> I am sure you didn't want to inclose this.

Correct.

> >    /* We do not wish to consider the move if it can be
> >     * immediately recaptured, unless stackp <= backfill2_depth.
> > +   * This doesn't actually seem to impact reading node counts.
> >     */
> IIRC, this has nothing to do with reading node counts, but with correctness.
> If stackp > backfill2_depth, the necessary attack move (recapturing this
> stone) might not be generated, leading to incorrect results.

Ah, ok.

> > +#if 1
> > +    if (approxlib(possible_moves[v], color, 5, NULL) == 1 && stackp > 
> > backfill2_depth)
>
> Btw, I think we prefer to keep line lengths below 80.

Oops.

Thanks for the detailed comments.

Evan Daniel