[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] Patch: Strategic effect for strategic attacks and defenses
From: |
Inge Wallin |
Subject: |
[gnugo-devel] Patch: Strategic effect for strategic attacks and defenses |
Date: |
Sun, 13 Oct 2002 17:41:06 +0200 (MEST) |
Here is a patch that I have wanted to do for a very long time.
Strategic effect is a part of the valuation of a move that is awarded
for two reasons:
a) For connections that connect a weak dragon to a strong
b) For strategic attacks and defenses
This patch only handles the case b) above.
The way this used to work was that a strategic bonus was awarded if we
played near a weak dragon, either our own or the opponents. The
reasoning was that a weak opponent dragon would be further weakened if
we played near it, and our own dragon would be similarly
strengthened. The problem was that this was assumed even though the
move itself did nothing for the strength of the dragon in question.
The way it works after this patch is that the weakness value is
recomputed after the move. The change in weakness is multiplied with
the effective size of the dragon to get the strategic bonus.
Unfortunately, the weakness is not easy to compute after a move is
made, because the weakness value is dependent of so many other
factors, including owl status. There is much to be improved here.
However, the patch below can be thought of as a seed for further
improvements.
I ran the regressions on the changed gnugo and got 13 PASSES and 21
FAILs. However, then I discovered a bug and after I fixed that, some
half of the FAILs had disappeared and a number of new PASSes had
appeared. I didn't have time to rerun it all, but that is the result
I got when I reran a few tests manually (among them strategy and
nngs1).
I analyzed some of the results, and here is what I got:
trevora:220 PASSes, but maybe for the wrong reason.
This test is of the form !B6, i.e to avoid a certain
move. This move is indeed avoided, and the strategic
effect is smaller now. However, it still has a far
too high value, and it leaves too many weaknesses
behind. I think that there are other things wrong
here as well and is worth further investigation.
trevora:530 FAILs, but used to pass by pure luck.
This test used to giva strategic bonus for the dragon
at G8, but the test would have failed if the dragon
had been just one stone smaller (because the strategic
effect would have been smaller).
The real problem is that the owl code only can handle
one attack/defense point. Owl gives G3 as a defense
point for the lower left group at E6, and doesn't see
that the connection at H4 saves the group as well. Of
course, in addition to saving E6, it also saves G8.
I think the owl code should try connections to other
nearby dragons first before trying to live on its
own.
nngs1:50 FAILs, but is almost there
The connection gets a strategic bonus for N10 and P10
as well as for the strategical attack on O9. However,
the stone at R10 is not taken into account although it
obviously is important.
The 3,3-invasion C3 (the chosen move) gets a valuation
of 14.60, which might even be to low.
The problem here is that not all stones that are
affected by the connection are counted (no
amalgamation across a one point jump).
strategy:27 FAILs, but for other reasons
The wrong move F2, has an uncertain owl defense bonus
of 14.33, which is nonsense. The correct move C3 is
the second best move.
strategy:39 FAILs, but partly for other reasons
R6, which is the only move that is valued higher, has
move reason that it owl-attacks R6 and a territorial
value of 23.45, which is doubtful. Also, P16, the
correct move lacks a few followup move reasons, like
the fact that it threatens to cut off and capture
Q13.
endgame:301 PASSes for the wrong reason
The strategic effect that made A3 the move is
indeed gone. However, gnugo still doesn't know that E5
is worth 1 point and the half point that the ko is
worth, somehow disappears in workarounds and
followups. This is worth investigating on its own.
lazarus:16 Properly solved
trevorb:220 Properly solved
trevorb:390 FAILs for other reason
The chosen move, F7, has a valuation of 6 points for
"defends against combination attack on several worms",
which a) does only capture in ko and b) the correct
move also protects against.
The problem here is that atari-atari only generates
one defense point.
trevorb:450 FAILs for other reasons
This move looks strange, but if you look at the
valuation of the move reasons, it is hard to argue
with them.
The correct move F3 has a territorial value of 10.62
points, which might be OK. However, this move is
bigger than that because the opponent can also claim
this part of the board for himself.
I think the problem is a missing reverse followup.
trevorb:660 Properly solved
All in all, for the tests that I investigated, most of them failed for
reasons other than the patch, and many of the PASSes were due to the
patch.
Summary:
- compute_escape() made public
- compute_dragon_weakness() made public
- compute_dragon_weakness_value() enhanced to make recomputing
possible
- dragon_delta_safety(): new function
- use dragon_delta_safety() for valuation of strategic bonus for
strategic attacks and defenses
- minor cleanup of eyes.db
-Inge
================================================================
diff -ur gnugo-3.3.8/engine/combination.c gnugo-3.3.8.iw/engine/combination.c
--- gnugo-3.3.8/engine/combination.c Thu Sep 5 01:19:17 2002
+++ gnugo-3.3.8.iw/engine/combination.c Sun Oct 6 15:53:51 2002
@@ -102,6 +102,7 @@
int k;
int l;
+ /* Loop through all board positions and see if there are double threats. */
for (ii = BOARDMIN; ii < BOARDMAX; ii++) {
int num_a_threatened_groups;
int a_threatened_groups[MAX_THREATENED_STRINGS];
diff -ur gnugo-3.3.8/engine/dragon.c gnugo-3.3.8.iw/engine/dragon.c
--- gnugo-3.3.8/engine/dragon.c Thu Sep 5 01:19:17 2002
+++ gnugo-3.3.8.iw/engine/dragon.c Sat Oct 12 22:02:13 2002
@@ -57,7 +57,6 @@
static int dragon_looks_inessential(int origin);
static int compute_crude_status(int pos);
static void dragon_eye(int pos, struct eye_data[BOARDMAX]);
-static int compute_escape(int pos, int dragon_status_known);
static void compute_surrounding_moyo_sizes(int opposite,
int dragon_status_known);
@@ -1548,7 +1547,7 @@
/* Wrapper to call the function above and compute the escape potential
* for the dragon at (pos).
*/
-static int
+int
compute_escape(int pos, int dragon_status_known)
{
int ii;
@@ -1591,6 +1590,7 @@
return dragon_escape(goal, board[pos], escape_value);
}
+
/*
* Sum up the surrounding moyo sizes for each dragon. Write this into
* dragon2[].moyo if it is smaller than the current entry. If (opposite)
@@ -1652,14 +1652,16 @@
* a dragon. This coefficient * the effective size of the dragon can be
* used to award a strategic penalty for weak dragons.
*/
-static float
-compute_dragon_weakness_value(int d)
+float
+compute_dragon_weakness_value(int d, float extra_territorial_value,
+ float initial_escape_route)
{
float true_genus = (((float) dragon2[d].genus)
+ 0.5 * ((float) dragon2[d].heyes
+ (dragon2[d].lunch != NO_MOVE ? 1.0 : 0.0)));
int origin = dragon2[d].origin;
- float escape_route = (float) dragon2[d].escape_route;
+ float escape_route;
+ float territorial_value;
int dragon_safety = dragon2[d].safety;
int i, j;
@@ -1692,10 +1694,16 @@
* - possible connections to neighbour dragons
*/
- weakness_value[0] = gg_interpolate(&moyo_value2weakness,
- dragon2[d].moyo_territorial_value);
- weakness_value[1] = gg_interpolate(&escape_route2weakness,
- escape_route);
+ territorial_value = (dragon2[d].moyo_territorial_value
+ + extra_territorial_value);
+ weakness_value[0] = gg_interpolate(&moyo_value2weakness, territorial_value);
+
+ if (initial_escape_route == -1.0)
+ escape_route = (float) dragon2[d].escape_route;
+ else
+ escape_route = initial_escape_route;
+ weakness_value[1] = gg_interpolate(&escape_route2weakness, escape_route);
+
weakness_value[2] = gg_interpolate(&genus2weakness, true_genus);
DEBUG(DEBUG_DRAGONS, "Computing weakness of dragon at %1m:\n", origin);
@@ -1704,6 +1712,7 @@
dragon2[d].moyo_territorial_value, weakness_value[0],
escape_route, weakness_value[1], true_genus, weakness_value[2]);
+ /* Sort intermediate weakness values. */
for (i = 0; i < 3; i++)
for (j = i + 1; j < 3; j++)
if (weakness_value[j] < weakness_value[i]) {
@@ -1755,11 +1764,12 @@
* this yields smaller results.
*/
compute_surrounding_moyo_sizes(1, 1);
-
for (d = 0; d < number_of_dragons; d++)
- dragon2[d].weakness = compute_dragon_weakness_value(d);
+ dragon2[d].weakness = compute_dragon_weakness_value(d, 0.0, -1.0);
}
+
+
/*
* Test whether two dragons are the same. Used by autohelpers and elsewhere.
*/
diff -ur gnugo-3.3.8/engine/liberty.h gnugo-3.3.8.iw/engine/liberty.h
--- gnugo-3.3.8/engine/liberty.h Tue Sep 3 16:13:37 2002
+++ gnugo-3.3.8.iw/engine/liberty.h Sat Oct 12 21:56:02 2002
@@ -803,6 +803,10 @@
#define DRAGON(d) dragon[dragon2[d].origin]
+int compute_escape(int pos, int dragon_status_known);
+float compute_dragon_weakness_value(int d, float extra_territorial_value,
+ float initial_escape_route);
+
struct aftermath_data {
int white_captured;
int black_captured;
diff -ur gnugo-3.3.8/engine/value_moves.c gnugo-3.3.8.iw/engine/value_moves.c
--- gnugo-3.3.8/engine/value_moves.c Tue Sep 3 16:13:37 2002
+++ gnugo-3.3.8.iw/engine/value_moves.c Sun Oct 13 15:11:07 2002
@@ -847,6 +847,96 @@
return (1.0 - DRAGON2(dr).weakness);
}
+
+static float
+dragon_delta_safety(int dr, int pos, int color)
+{
+ int dragon_safety = DRAGON2(dr).safety;
+ char saved_stones[BOARDMAX];
+ float weakness;
+ float delta_terri;
+ float followup_value;
+ struct dragon_data save_dragon_data;
+ float escape_route;
+ float retval;
+ int i;
+
+#if 0
+ gprintf("dragon_delta_safety() for dragon %1m, %C move at %1m\n",
+ dr, color, pos);
+#endif
+
+ /* Kludge: If a dragon is dead, we return 1.0 in order not
+ * to try to run away.
+ */
+ if (dragon_safety == DEAD
+ || dragon_safety == INESSENTIAL
+ || dragon_safety == TACTICALLY_DEAD)
+ return 1.0;
+
+ /* When scoring, we don't want to reinforce ALIVE dragons. */
+ if (doing_scoring && dragon_safety == ALIVE)
+ return 1.0;
+
+ weakness = DRAGON2(dr).weakness;
+ memset(saved_stones, 0, BOARDMAX);
+ saved_stones[pos] = INFLUENCE_SAVED_STONE;
+ delta_terri = influence_delta_territory(pos, color, saved_stones,
+ &followup_value);
+
+ /* Add the move at 'pos' to the dragon if the move is the same
+ * color as the dragon. Otherwise find a neighboring dragon and
+ * add to that one.
+ *
+ * FIXME: Do this for real later, but test it first.
+ */
+ save_dragon_data = dragon[pos];
+ if (color == board[dr])
+ dragon[pos] = dragon[dr];
+ else {
+ /* Find a neighbour dragon. */
+ for (i = 0; i < 4; i++) {
+ int pos2 = pos + delta[i];
+
+ if (ON_BOARD1(pos2) && board[pos2] == color) {
+ dragon[pos] = dragon[pos2];
+ break;
+ }
+ }
+ if (i == 4) {
+ /* There was no neighbor. Fake one.
+ * FIXME: This is *real* ugly, but is necessary because
+ * influence_delta_moyo has an assertion for id != 0.
+ */
+ dragon[pos].id = number_of_dragons;
+ }
+ }
+ escape_route = compute_escape(dr, 1);
+ dragon[pos] = save_dragon_data;
+
+#if 0
+ gprintf("delta_terri: %f, escape_route: was %f now %f\n",
+ delta_terri, (float) (DRAGON2(dr).escape_route), escape_route);
+#endif
+ /* The safety value is the negation of the weakness value. */
+ retval = -(compute_dragon_weakness_value(dragon[dr].id,
+ delta_terri, escape_route)
+ - weakness);
+
+ /* If we move on our own dragon, we strengthen it, if we move on the
+ * opponents, we weaken it. */
+ if (color != board[dr])
+ retval = -retval;
+
+#if 0
+ gprintf("dragon_delta_safety result: %f (old weakness: %f)\n",
+ retval, weakness);
+#endif
+
+ return retval;
+}
+
+
/*
* Strategical value of connecting (or cutting) the dragon at (dragona)
* to the dragon at (dragonb). Notice that this function is asymmetric.
@@ -1800,7 +1890,10 @@
float this_value = 0.0;
float tot_value = 0.0;
- /* Strategical value of connecting or cutting dragons. */
+ /* Strategical value of:
+ * - connecting or cutting dragons.
+ * - strategicly attacking or defending dragons.
+ */
static float dragon_value[MAX_DRAGONS];
/* This loop used to be up to next_dragon, but that is not safe
@@ -1871,13 +1964,16 @@
d1 = lunch_dragon[l];
bb = dragons[d1];
- /* FIXME: This value cannot be computed without some
- * measurement of how the actual move affects the dragon.
- * The dragon safety alone is not enough. The question is
- * whether the dragon is threatened by the move or not.
+ /* FIXME: We must take into account the color of the move
+ * and the dragon (see below).
*/
+#if 0
this_value = (dragon[bb].effective_size
* (1.0 - dragon_safety(bb, 0)));
+#else
+ this_value = (dragon_delta_safety(bb, pos, color)
+ * dragon[bb].effective_size);
+#endif
/* If this dragon consists of only one worm and that worm
* can be tactically captured or defended by this move, we
@@ -2136,13 +2232,15 @@
d1 = move_reasons[r].what;
aa = dragons[d1];
- /* FIXME: This value cannot be computed without some
- * measurement of how the actual move affects the dragon. The
- * dragon safety alone is not enough. The question is whether
- * the dragon is threatened by the move or not.
+ /* Check how much the weakness of the dragon is affected by
+ * the move and put a score on that.
*/
- this_value = (dragon[aa].effective_size
- * (1.0 - dragon_safety(aa, 1)));
+ if (color == board[pos])
+ this_value = (dragon_delta_safety(aa, pos, color)
+ * dragon[aa].effective_size);
+ else
+ this_value = -(dragon_delta_safety(aa, pos, color)
+ * dragon[aa].effective_size);
/* To prefer good connections and cuts, we lower this value
* somewhat.
@@ -2241,6 +2339,7 @@
pos, dragon_value[k], aa);
continue;
}
+
/* If the dragon has been owl captured, owl defended, or involved
* in a semeai, we have likewise already counted the points as
* territorial value.
diff -ur gnugo-3.3.8/engine/worm.c gnugo-3.3.8.iw/engine/worm.c
--- gnugo-3.3.8/engine/worm.c Thu Sep 5 01:19:17 2002
+++ gnugo-3.3.8.iw/engine/worm.c Sun Oct 6 13:22:50 2002
@@ -1180,6 +1180,7 @@
if (!is_worm_origin(pos, pos))
continue;
+ /* Report attacks and attack threats on the opponents worms. */
if (board[pos] == OTHER_COLOR(color)) {
for (k = 0; k < MAX_TACTICAL_POINTS; k++) {
if (worm[pos].attack_codes[k] != 0)
@@ -1190,7 +1191,8 @@
worm[pos].attack_threat_codes[k]);
}
}
-
+
+ /* Report defenses and defense threats on our own worms. */
if (board[pos] == color) {
for (k = 0; k < MAX_TACTICAL_POINTS; k++) {
if (worm[pos].defend_codes[k] != 0)
diff -ur gnugo-3.3.8/patterns/eyes.db gnugo-3.3.8.iw/patterns/eyes.db
--- gnugo-3.3.8/patterns/eyes.db Sat Jun 15 17:00:00 2002
+++ gnugo-3.3.8.iw/patterns/eyes.db Fri Oct 11 21:40:56 2002
@@ -622,14 +622,6 @@
Pattern 512
-# FIXME: The correct form of this pattern is
-#
-# |.X>
-# |< X
-# +---
-#
-# but the code towards the end of recognize_eye() can't handle the
-# pattern because there is no '*' or '@'.
|.X>
|< X
- [gnugo-devel] Patch: Strategic effect for strategic attacks and defenses,
Inge Wallin <=
Re: [gnugo-devel] Patch: Strategic effect for strategic attacks and defenses, Arend Bayer, 2002/10/14