Re: [gnugo-devel] Patch: New move generator

[Gunnar Farneback]

Dan wrote:
> > It only proposes a single defense against combination attacks. This
> >   sometimes leads to suboptimal moves being generated. A good example
> >   is test case strategy3:101.
> 
> This isn't correct. Sometimes we try multiple defenses. See the code 
> around line 1123 in reading.c where the comment is found:
> 
>       /* The atari at (ai,aj) seems to work but we still
>        * must check there is not a better defense. */

Sorry if I wasn't clear. I'm talking about only one defense move being
proposed on the top level, which isn't necessarily the best move. The
code around 1123 is of course important when trying to determine
whether there is a combination attack in the first place. Well, check
out the move valuations in stragey3:101 to see what I mean.

> We all agree that atari_atari is only an inadequate attempt
> to try to find moves with double meanings. But I think it's too
> soon to scrap it until we definitely have something better.

Of course we can't scrap it at this time, but the time is well due to
start building its successor.

Dan wrote in another message:
> In a separate matter the moves at P5 and F6 are
> misevaluated as being worth some 62 and 54
> points. That's a separate matter. The issue is whether
> the point at N11 is found and evaluated correctly. It
> isn't necessarily the best point on the board, so
> as a regression the test is imperfect, but it's a very
> good example.

The problem with P5 and F6 is that the (huge) J14 dragon incorrectly
is classified as WEAKLY_ALIVE instead of STRONGLY_ALIVE. This in turn
is because the surrounding moyo size is evaluated to 0 instead of
something very large, which of course is a bug. Without checking it
further I'm fairly sure it has to do with the cut and connection
inhibit business in the connections analysis to do. Those things are
too messy and need revision. 

> The move at N11 is indeed found by find_double_threats, 
> and the attack either move reason is added. Now, the
> issue is how the move valuation should be assigned.
> It appears to me that this move is worth about 20
> points.

When I count it carefully I get 21 points.

> After Inge's patch, we get:
> 
>     N11: 24.17 (followup) - threatens to capture N10
>     N11: 15.17 (followup) - threatens to capture K14
>   N11: 14.00 - attacks either K14 (14.00) or N10 (23.00)
>   N11: 24.17 - followup
>   N11: -3.55 - shape (shape values +2.00(2) -5.00(2), shape factor 0.864)
> Move generation values N11 to 22.53
> 
> This looks pretty good to me, except for some issues
> about followup (which we're not likely to get right
> anyway given the present paradigm).  With the
> truncated patch inge_1_12.2 which I put up earlier,
> N11 is still undervalued.

Ah, now I see what I had missed in the patch. I only noticed the call
to attacked_worm_value() from the valuation of ATTACK_MOVE and its ko
relatives. I didn't see that that it was also called from
ATTACK_EITHER and DEFEND_BOTH. There it makes sense to take effect on
neighbors into account.

(As a side note the valuation of ATTACK_EITHER and DEFEND_BOTH is a
complete mess. I don't think it's possible to do this well without
actually playing out the local position.)

> I think Gunnar objects to Inge's changes in the
> valuation of worms, but in any case this example might
> be a good one for checking that the valuation is done
> correctly.

The modifications to the ATTACK_EITHER and DEFEND_BOTH valuations are
okay. The modification to ATTACK_MOVE does not make sense and is not
acceptable. The name attacked_worm_value() is misleading since it's
only useful in ATTACK_EITHER and DEFEND_BOTH. Further I have some
comments about the code:

>From move_reasons.c with Inge's full patch:
>  * On the other hand if it has an adjacent critical worm, and
>  * if (pos) does not defend that worm, we subtract the value of the
>  * worm, since (pos) may be defended by attacking that worm. We make at
>  * most one adjustment of each type. 
>  */

This case is not implemented correctly. There is no check whether the
move does defend the worm.

> static float
> attacked_worm_value(int ww)
> {
>   int color;
>   int num_adj;
>   int adjs[MAXCHAIN];
>   int has_live_neighbor = 0;
>   int adjusted_value = 2 * worm[ww].effective_size;

Obviously adjusted_value should also be a float.

>   float adjustment_up = 0.0;
>   float adjustment_down = 0.0;
>   int s;
> 
>   color = OTHER_COLOR(board[ww]);
>   num_adj = chainlinks(ww, adjs);
>   for (s = 0; s < num_adj; s++) {
>     int adj = adjs[s];
> 
>     if (dragon[adj].matcher_status == ALIVE
>         || dragon[adj].matcher_status == CRITICAL)
>       has_live_neighbor = 1;
> 
>     if (dragon[adj].color == color
>         && dragon[adj].matcher_status == DEAD
>         && 2*dragon[adj].effective_size > adjustment_up)
>       adjustment_up = 2*dragon[adj].effective_size;
> 
>     if (dragon[adj].color == color
>         && attack(adj, NULL)

Why not look this up in the worm data?

>         && 2*worm[adj].effective_size > adjustment_down)
>       adjustment_down = 2*worm[adj].effective_size;
>   }
> 
>   if (has_live_neighbor)
>     adjusted_value += adjustment_up;
>   adjusted_value -= adjustment_down;
> 
>   return adjusted_value;
> 
>   /*
>    * FIXME: It might be possible that parts of the dragon
>    *        can be cut in the process of capturing the (ww)
>    *        worm. In that case, not the entire size of the 
>    *        adjacent dead dragon should be counted as a positive
>    *        adjustment.  However, it seems difficult to do this
>    *        analysis, and in most cases it won't apply, so we
>    *        leave it as it is for now.

Don't bother. Unless we change the move valuation paradigm to play out
the local positions we'll never get this right.

>    *
>    * TODO:
>    *   - cache the result?
>    */

Why? There's nothing here taking significant time. It would only add
to code complexity.

> nicklas2  # 1803 (PASS)
> trevor    # 310 (PASS), 411 (PASS)
> global    # 36 (PASS), 44 (FAIL)
> strategy4 # 194 (FAIL)

I've checked four of these (not the ones in global) and they are all
due to the bugs I pointed out above. As it happens the change to the
ATTACK_MOVE valuation is not very effective since in most cases it's
overruled by the OWL_ATTACK_MOVE valuation. This is not the case when
level is less than six because
find_more_owl_attack_and_defense_moves() isn't run then. It would be
interesting to compare the performance with and without Inge's patch
at level 5. I think the differences are likely to be more dramatic
then.

Inge wrote in the original comments to the patch:
> I have started to worki on the move valuation to make that more
> accurate.  The first step is to be more precis in valuation of
> attacked worms.  Not only the worm itself, but also our own worms and
> dragons saved by attacking the worm are now included in the
> valuation.  I will carry the same ideas to defended worms and to
> attacked/defended dragons.

You're welcome to try this but I'll promise that doing it for dragons
will break things horribly.

/Gunnar