[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] connections reevaluated
|
From: |
Arend Bayer |
|
Subject: |
Re: [gnugo-devel] connections reevaluated |
|
Date: |
Mon, 18 Nov 2002 16:19:47 +0100 (CET) |
This is a version of arend_3_12.4 with small revisions.
I have looked in big detail at the PASSes and FAILs (27 vs 17), and where
as there remain a few problems, I am now more convinced that it is a
good improvement.
I see only 5 of the 17 FAILs as a problem in the valuation.
The biggest improvements are due to
- avoiding ridiculously high connection values for huge but
STRONGLY_ALIVE dragons.
- Connections to a single, unimportant but ALIVE stone no longer
give a benefit.
- Connections from a critical dragon to another are now simply ignored.
This seems to be the best guess for me: It is automatically checked
whether such a move owl_does_defend the dragon, and I don't think
we should overrule owl if it thinks it doesn't help.
This could certainly be refined.
Arend
(I have a patch pending for some of the "bad test" cases.)
PASS:
trevora:290 probably lucky
trevora:420 good.
strategy:22 improved
neurogo:11 (almost) properly solved
dniwog:7 properly solved
lazarus:4 improved
trevorb:740 improved
nngs:420 partly luck
nngs:490 improved, partly luck
trevorc:170 properly solved
trevorc:590 properly solved
strategy3:136 improved, somewhat lucky
global:7 improved
arend:23 properly solved
13x13:12 propely solved
13x13:15 improved, partly lucky
strategy4:200 Very random (There is an incorrect rejection of S18 as
blunder.) Actual change is however a good one.
nngs2:290 luck
nngs2:550 bad test
nngs3:320 very good
nngs3:730 good
nngs3:800 properly solved
nngs3:1150 properly solved
strategy5:226 improved
century2002:160 improved
ninestones:150 ok
tactics1:10 ok
FAIL:
("unlucky" admits some responsibility)
strategy:20 'Q11', got 'C18' bad, but partly unlucky.
strategy:40 'E5|M11', got 'R6' bad (weakness of F5 far too low: 0.12)
trevorb:790 'K6|K5', got 'A6 bad test
trvorb:840 '!D12', got 'D12' solved by arend_3_12.6
nngs:1280 'D13', got 'J12' previous valuation pretty non-sense
(owl doesn't see that D13 trivially defends B18 with ko.)
nngs:1860 '!L7|D19', got 'D19' accidental (valuation improved)
trevorc:1580 'C8', got 'A4' accidental (valuation improved)
strategy3:119 'D9|J3', got 'B13' accidental (pretty bad owl result)
global:5 'O4', got 'F5' unlucky
arend:9 'S17', got 'S15' accidental
(valuations for S15 duplicated)
(also maybe this test is bad, S17 is a little tricky if white
replies at R15)
13x13:40 'K13', got 'L11' bad
nngs2:140 'P5', got 'Q6' acceptable and accidental
nngs3:310 'C5|B5', got 'B7' ok
| Error in test: C5 is occupied
nngs3:400 'N13', got 'Q15' bad, somehwat unlucky
nngs3:830 '!N13', got 'N13' valuation improved
nngs3:1170 'B1', got 'B7' bad owl results (how on earth
can B1 be an owl defense for B5??)
Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.87
diff -u -p -r1.87 dragon.c
--- engine/dragon.c 14 Oct 2002 15:41:07 -0000 1.87
+++ engine/dragon.c 16 Nov 2002 00:00:42 -0000
@@ -1950,64 +1950,33 @@ struct interpolation_data escape_route2w
struct interpolation_data genus2weakness =
{ 6, 0.0, 3.0, {1.0, 0.95, 0.8, 0.5, 0.2, 0.1, 0.0}};
-/* This function tries to guess a coefficient measuring the weakness of
- * 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
+crude_dragon_weakness(int safety, struct eyevalue *genus, int has_lunch,
+ float moyo_value, float escape_route)
{
/* FIXME: We lose information when constructing true_genus. This
* code can be improved.
*/
- struct eyevalue *genus = &dragon2[d].genus;
float true_genus = 0.5 * (max_eyes(genus) + min_eyes(genus)
- + (dragon2[d].lunch != NO_MOVE));
- int origin = dragon2[d].origin;
- float escape_route = (float) dragon2[d].escape_route;
- int dragon_safety = dragon2[d].safety;
- int i, j;
-
+ + (has_lunch != 0));
float weakness_value[3];
float weakness;
+ int i, j;
- if (dragon_safety == INVINCIBLE || dragon_safety == INESSENTIAL)
+ if (safety == INVINCIBLE || safety == INESSENTIAL)
return 0.0;
- if (dragon_safety == TACTICALLY_DEAD)
- return 1.0;
-
- if (dragon_safety == DEAD)
+ if (safety == TACTICALLY_DEAD || safety == DEAD || safety == CRITICAL)
return 1.0;
- if (dragon_safety == CRITICAL)
- return 0.9;
-
- /* Possible ingredients for the computation:
- * '+' means currently used, '-' means not (yet?) used
- * - pre-owl moyo_size
- * + post-owl moyo_size and its territory value!
- * + escape factor
- * + number of eyes
- * - minus number of vital attack moves?
- * + from owl:
- * + attack certain?
- * - number of owl nodes
- * - maybe reading shadow?
- * + threat to attack?
- * - 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);
+ weakness_value[0] = gg_interpolate(&moyo_value2weakness, moyo_value);
+ 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);
DEBUG(DEBUG_DRAGONS,
" moyo value %f -> %f, escape %f -> %f, eyes %f -> %f,",
- dragon2[d].moyo_territorial_value, weakness_value[0],
- escape_route, weakness_value[1], true_genus, weakness_value[2]);
+ moyo_value, weakness_value[0],
+ escape_route, weakness_value[1],
+ true_genus, weakness_value[2]);
for (i = 0; i < 3; i++)
for (j = i + 1; j < 3; j++)
@@ -2023,6 +1992,43 @@ compute_dragon_weakness_value(int d)
weakness = gg_min(0.7 * weakness_value[0] + 0.3 * weakness_value[1],
1.3 * weakness_value[0]);
+ gg_assert(weakness >= 0.0 && weakness <= 1.0);
+
+ return weakness;
+}
+
+/* This function tries to guess a coefficient measuring the weakness of
+ * 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)
+{
+ int origin = dragon2[d].origin;
+ float weakness;
+
+ /* Possible ingredients for the computation:
+ * '+' means currently used, '-' means not (yet?) used
+ * - pre-owl moyo_size
+ * + post-owl moyo_size and its territory value
+ * + escape factor
+ * + number of eyes
+ * - minus number of vital attack moves?
+ * + from owl:
+ * + attack certain?
+ * - number of owl nodes
+ * - maybe reading shadow?
+ * + threat to attack?
+ * - possible connections to neighbour dragons
+ */
+
+ DEBUG(DEBUG_DRAGONS, "Computing weakness of dragon at %1m:\n", origin);
+
+ weakness = crude_dragon_weakness(dragon2[d].safety, &dragon2[d].genus,
+ dragon2[d].lunch != NO_MOVE,
+ dragon2[d].moyo_territorial_value,
+ (float) dragon2[d].escape_route);
+
/* Now corrections due to (uncertain) owl results resp. owl threats. */
if (!dragon[origin].owl_attack_certain)
weakness += gg_min(0.25 * (1.0 - weakness), 0.25 * weakness);
@@ -2037,9 +2043,9 @@ compute_dragon_weakness_value(int d)
weakness = 1.0;
DEBUG(DEBUG_DRAGONS, " result: %f.\n", weakness);
-
return weakness;
}
+
/* This function has to be called _after_ the owl analysis and the
* subsequent re-run of the influence code.
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.77
diff -u -p -r1.77 gnugo.h
--- engine/gnugo.h 14 Nov 2002 16:49:53 -0000 1.77
+++ engine/gnugo.h 16 Nov 2002 00:00:44 -0000
@@ -476,7 +476,6 @@ void make_worms(void);
/* dragon.c */
void make_dragons(int color, int stop_before_owl, int save_verbose);
-void compute_refined_dragon_weaknesses(void);
void initialize_dragon_data(void);
void show_dragons(void);
int crude_status(int pos);
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.132
diff -u -p -r1.132 liberty.h
--- engine/liberty.h 15 Nov 2002 15:12:45 -0000 1.132
+++ engine/liberty.h 16 Nov 2002 00:00:49 -0000
@@ -351,6 +351,10 @@ void restore_depth_values(void);
int safe_move(int move, int color);
void join_dragons(int d1, int d2);
int dragon_escape(char goal[BOARDMAX], int color, char escape_value[BOARDMAX]);
+void compute_refined_dragon_weaknesses(void);
+struct eyevalue;
+float crude_dragon_weakness(int safety, struct eyevalue *genus, int has_lunch,
+ float moyo_value, float escape_route);
int is_same_dragon(int d1, int d2);
int are_neighbor_dragons(int d1, int d2);
int first_worm_in_dragon(int w);
Index: engine/move_reasons.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.c,v
retrieving revision 1.101
diff -u -p -r1.101 move_reasons.c
--- engine/move_reasons.c 12 Nov 2002 17:59:56 -0000 1.101
+++ engine/move_reasons.c 16 Nov 2002 00:00:56 -0000
@@ -1990,10 +1990,9 @@ scale_randomness(int pos, float scaling)
* the strategic effect.
*/
float
-strategic_effective_size(int pos)
+strategic_effective_size(float effective_size)
{
- float eff = dragon[pos].effective_size;
- return ((15.0 * eff) / (15.0 + eff));
+ return ((15.0 * effective_size) / (15.0 + effective_size));
}
/*
Index: engine/move_reasons.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.h,v
retrieving revision 1.26
diff -u -p -r1.26 move_reasons.h
--- engine/move_reasons.h 14 Oct 2002 17:43:27 -0000 1.26
+++ engine/move_reasons.h 16 Nov 2002 00:00:57 -0000
@@ -203,7 +203,7 @@ void mark_changed_dragon(int pos, int co
int move_reason_type, char changed_stones[BOARDMAX],
float *effective_size);
-float strategic_effective_size(int pos);
+float strategic_effective_size(float effective_size);
/*
* Local Variables:
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.65
diff -u -p -r1.65 value_moves.c
--- engine/value_moves.c 20 Oct 2002 10:40:45 -0000 1.65
+++ engine/value_moves.c 16 Nov 2002 00:01:09 -0000
@@ -1,4 +1,4 @@
-/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ \hline
* This is GNU GO, a Go program. Contact address@hidden, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* *
@@ -898,77 +898,27 @@ dragon_weakness(int dr, int ignore_dead_
* + max(connection_value(C, A), connection_value(C, B))
*
* The parameter 'margin' is the margin by which we are ahead.
- * If this exceeds 20 points we use the cautious impact values,
- * which value connections more. This is because we can afford
- * to waste a move making sure of safety. If the margin is between
- * 0 and 20 points we interpret linearly between the two sets of
- * impact values.
+ * If this exceeds 20 points we value connections more. This is because
+ * we can afford to waste a move making sure of safety.
*/
-/* Values higher than 1.0 to give connections a bonus over other vital
- * moves.
- */
-static float impact_values[10][10] = {
-/* (dragonb) DEAD ALIV CRIT INES TACT WEAK WE_A SEKI STRO INVI */
-/* DEAD */ {0.0, 0.9, 0.0, 0.0, 0.0, 0.8, 0.85,0.8, 0.95,1.0 },
-/* ALIVE */ {0.0, 0.08,0.05,0.0, 0.0, 0.05,0.07,0.05,0.09,0.1 },
-/* CRITICAL */ {0.0, 1.04,0.85,0.0, 0.0, 0.75,0.9, 0.85,1.08,1.1 },
-/* INESSENTIAL */ {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 },
-/* TACT. DEAD */ {0.0, 0.9, 0.0, 0.0, 0.0, 0.8, 0.85,0.8, 0.95,1.0 },
-/* WEAK */ {0.1, 0.6, 0.25,0.0, 0.0, 0.2, 0.25,0.25,0.65,0.65},
-/* WEAK ALIVE */ {0.0, 0.4, 0.3, 0.0, 0.0, 0.15,0.2, 0.2 ,0.45,0.45},
-/* SEKI */ {0.0, 0.2, 0.15,0.0, 0.0, 0.1, 0.15,0.2, 0.25,0.3 },
-/* STR. ALIVE */ {0.0, 0.01,0.01,0.0, 0.0, 0.01,0.01,0.01,0.01,0.01},
-/* INVINCIBLE */ {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 }};
-/* (dragona) */
-
-static float cautious_impact_values[10][10] = {
-/* (dragonb) DEAD ALIV CRIT INES TACT WEAK WE_A SEKI STRO INVI */
-/* DEAD */ {0.3, 0.9, 0.0, 0.0, 0.0, 0.8, 0.85,0.8, 0.95,1.0 },
-/* ALIVE */ {0.0, 0.2, 0.05,0.0, 0.0, 0.1,0.15, 0.10,0.2 ,0.2 },
-/* CRITICAL */ {0.0, 1.04,0.85,0.0, 0.0, 0.75,0.9, 0.85,1.08,1.1 },
-/* INESSENTIAL */ {0.1, 0.6, 0.0, 0.0, 0.0, 0.3, 0.5, 0.5, 0.6, 0.6 },
-/* TACT. DEAD */ {0.2, 0.9, 0.0, 0.0, 0.0, 0.8, 0.85,0.8, 0.95,1.0 },
-/* WEAK */ {0.1, 0.6, 0.25,0.0, 0.0, 0.2, 0.25,0.25,0.65,0.65},
-/* WEAK ALIVE */ {0.0, 0.4, 0.3, 0.0, 0.0, 0.2, 0.2, 0.2 ,0.45,0.45},
-/* SEKI */ {0.0, 0.2, 0.15,0.0, 0.0, 0.1, 0.15,0.2, 0.25,0.3 },
-/* STR. ALIVE */ {0.0, 0.02,0.01,0.0, 0.0, 0.01,0.01,0.01,0.02,0.02},
-/* INVINCIBLE */ {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 }};
-/* (dragona) */
-
static float
connection_value(int dragona, int dragonb, int tt, float margin)
{
- int safety1 = DRAGON2(dragona).safety;
- int safety2 = DRAGON2(dragonb).safety;
- /* FIXME: We lose information when constructing true_genus. This
- * code can be improved.
- */
- struct eyevalue *genus1 = &DRAGON2(dragona).genus;
- struct eyevalue *genus2 = &DRAGON2(dragonb).genus;
- int true_genus1 = max_eyes(genus1) + min_eyes(genus1);
- int true_genus2 = max_eyes(genus2) + min_eyes(genus2);
- float impact;
-
- /* If the connected dragon gets sufficient eyespace to live on its
- * own, although neither of the unconnected ones did, we simulate
- * this by upgrading the safety of the second dragon to ALIVE.
- */
- if (true_genus1 < 4 && true_genus2 < 4) {
- if (true_genus1 + true_genus2 >= 4
- || (true_genus1 + true_genus2 >= 3
- && (DRAGON2(dragona).heye == tt
- || DRAGON2(dragonb).heye == tt)))
- safety2 = ALIVE;
- }
-
- /* If the b dragon is critical but has genus 0 and no moyo, we
- * assume it doesn't help dragon a to connect to b.
- */
- if (safety2 == CRITICAL && true_genus2 == 0
- && DRAGON2(dragonb).moyo_size_pre_owl == 0)
- return 0.0;
-
+ struct dragon_data2* da = &DRAGON2(dragona);
+ struct dragon_data2* db = &DRAGON2(dragonb);
+ float sizea = dragon[dragona].effective_size;
+ float sizeb = dragon[dragonb].effective_size;
+ int safetya = da->safety;
+ int safetyb = db->safety;
+ float crude_weakness_a
+ = crude_dragon_weakness(da->safety, &da->genus, da->lunch != NO_MOVE,
+ da->moyo_territorial_value,
+ (float) da->escape_route);
+ float crude_weakness_sum;
+ struct eyevalue genus_sum;
+ float terr_val = move[tt].territorial_value;
+ float return_value;
/* When scoring, we want to be restrictive with reinforcement moves
* inside own territory. Thus if both dragons are weakly_alive,
@@ -976,37 +926,71 @@ connection_value(int dragona, int dragon
*
* Notice that this requires that the territorial value is computed
* before the strategical value.
+ *
+ * FIXME: Shouldn't it be sufficient to check this for dragon a?
*/
- if (doing_scoring && move[tt].territorial_value < 0.0) {
- if ((safety1 == WEAKLY_ALIVE
- || safety1 == ALIVE
- || safety1 == STRONGLY_ALIVE
- || safety1 == INVINCIBLE)
- && (safety2 == WEAKLY_ALIVE
- || safety2 == ALIVE
- || safety2 == STRONGLY_ALIVE
- || safety2 == INVINCIBLE))
+ if (doing_scoring && terr_val < 0.0) {
+ if ((safetya == WEAKLY_ALIVE
+ || safetya == ALIVE
+ || safetya == STRONGLY_ALIVE
+ || safetya == INVINCIBLE)
+ && (safetyb == WEAKLY_ALIVE
+ || safetyb == ALIVE
+ || safetyb == STRONGLY_ALIVE
+ || safetyb == INVINCIBLE))
return 0.0;
}
- if (doing_scoring || margin < 0.0)
- impact = impact_values[safety1][safety2];
- else if (margin > 20.0)
- impact = cautious_impact_values[safety1][safety2];
- else
- impact = (0.05 * margin * cautious_impact_values[safety1][safety2]
- + (1 - 0.05 * margin) * impact_values[safety1][safety2]);
-
+ if (crude_weakness_a == 0.0
+ || dragon[dragona].status == CRITICAL
+ || dragon[dragona].status == DEAD)
+ return 0.0;
+ if (terr_val < 0.0)
+ terr_val = 0.0;
- /* Trying to connect an inessential string to something else with a
- * self atari is almost certainly worthless.
+ add_eyevalues(&da->genus, &db->genus, &genus_sum);
+ /* FIXME: There is currently no sane way to take the escape values
+ * into account. Hence we simply pretend they do not change.
+ *
+ * FIXME: terr_val is a very crude approximation to the expected
+ * increase in moyo size. It's especially way off if the move at (tt)
+ * (owl) defends some stones.
*/
- if (impact > 0.0
- && safety1 == INESSENTIAL
- && is_self_atari(tt, board[dragona]))
- impact = 0.0;
-
- return impact * 2.0 * dragon[dragona].effective_size;
+ crude_weakness_sum
+ = crude_dragon_weakness(safetyb, &genus_sum,
+ (da->lunch != NO_MOVE || db->lunch != NO_MOVE),
+ da->moyo_territorial_value
+ + db->moyo_territorial_value
+ + terr_val,
+ (float) da->escape_route);
+
+ if (safetya == CRITICAL)
+ return_value = 2.1 * (1.0 - 0.5 * crude_weakness_sum) * sizea;
+ else {
+ /* The old burden is the burden of defending dragon a. */
+ float old_burden = 2.0 * crude_weakness_a
+ * strategic_effective_size(sizea);
+
+ /* The new burden is the burden of defending new joint dragon; but
+ * we share this burden proportionally with the other dragon.
+ */
+ float new_burden = 2.0 * crude_weakness_sum
+ * strategic_effective_size(sizea + sizeb)
+ * sizea / (sizea + sizeb);
+
+ return_value = 1.05 * (old_burden - new_burden);
+ }
+
+ if (return_value < 0.0)
+ return_value = 0.0;
+
+ /* If ahead, give extra bonus to connections. */
+ if (margin > 20.0)
+ margin = 20.0;
+ if (margin > 0.0)
+ return_value *= 1.0 + 0.02 * margin;
+
+ return return_value;
}
@@ -1940,7 +1924,8 @@ estimate_strategical_value(int pos, int
* alone is not enough. The question is whether the dragon is
* threatened or defended by the move or not.
*/
- this_value = (1.8 * strategic_effective_size(bb)
+ this_value = (1.8 * strategic_effective_size(dragon[bb]
+ .effective_size)
* dragon_weakness(bb, 0));
/* If this dragon consists of only one worm and that worm
@@ -2210,7 +2195,8 @@ estimate_strategical_value(int pos, int
* dragon safety alone is not enough. The question is whether
* the dragon is threatened by the move or not.
*/
- this_value = (1.8 * strategic_effective_size(aa)
+ this_value = (1.8 * strategic_effective_size(dragon[aa]
+ .effective_size)
* dragon_weakness(aa, 1));
/* No strategical attack value is awarded if the dragon at (aa)