[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] connections reevaluated
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] connections reevaluated |
|
Date: |
Mon, 11 Nov 2002 17:29:45 +0100 (CET) |
This patch makes the connection valuation closer to a before move/after
move analysis. It is similar to inge_3_10.2, and in particular the idea
to use the territorial value of the move as a guess for the change in
moyo size is borrowed from Inge.
To estimate the value of connecting dragon A to dragon B, we compare the
weakness of dragon A to the weakness of the dragon A+B. As we do not
have available all the information used in compute_dragon_weakness_value(),
I've broken out compute_crude_dragon_weakness(), which only uses
the genus, the lunch, the moyo size and the escape route.
For dragon A+B, we e.g. assume it has moyo size
(moyo size of A + moyo size of B + territorial value of move).
The territorial vale is sometimes way bigger than the real change in moyo
size, and maybe it is worth it to actually compute the new moyo size
according to the same rules as it is done at stackp==0. (This causes a few
but not many of the FAILs.)
The breakage is quite big, and looks positive. But given the big change
in behaviour, I suggest being a bit more careful, and I have started
a twogtp match.
Arend
Breakage (patch against CVS of a few days ago, compared to the same CVS)
32 new PASSes, 17 new FAILs
./regress.sh . trevora.tst
220 unexpected PASS!
420 unexpected PASS!
./regress.sh . strategy.tst
7 unexpected FAIL: Correct 'S19', got 'T15'
40 unexpected FAIL: Correct 'E5|M11', got 'R6'
./regress.sh . neurogo.tst
11 unexpected PASS!
./regress.sh . rosebud.tst
1 unexpected PASS!
./regress.sh . viking.tst
1: new fail (PASS in CVS)
./regress.sh . ego.tst
4 unexpected PASS!
8 unexpected PASS!
./regress.sh . dniwog.tst
7 unexpected PASS!
./regress.sh . lazarus.tst
4 unexpected PASS!
./regress.sh . trevorb.tst
130 unexpected PASS!
740 unexpected PASS!
./regress.sh . nicklas1.tst
1207 unexpected PASS!
./regress.sh . nicklas4.tst
1201 unexpected FAIL: Correct 'Q9', got 'S7'
./regress.sh . nicklas5.tst
804 unexpected PASS!
./regress.sh . nngs.tst
420 unexpected PASS!
900 unexpected FAIL: Correct 'Q15', got 'S14'
1280 unexpected FAIL: Correct 'D13', got 'J12'
1955 unexpected PASS!
./regress.sh . trevorc.tst
170 unexpected PASS!
230 unexpected PASS!
590 unexpected PASS!
820 unexpected FAIL: Correct 'A6', got 'B12'
1080 unexpected FAIL: Correct '!L8|K10|K9', got 'L8'
./regress.sh . global.tst
7 unexpected PASS!
./regress.sh . arend.tst
9 unexpected FAIL: Correct 'S17', got 'S15'
23 unexpected PASS!
./regress.sh . 13x13.tst
7 unexpected PASS!
12 unexpected PASS!
15 unexpected PASS!
41 unexpected PASS!
52 unexpected PASS!
./regress.sh . trevord.tst
500 unexpected PASS!
1070 unexpected PASS!
./regress.sh . strategy4.tst
163 unexpected FAIL: Correct 'O7|P8', got 'N8'
200 unexpected PASS!
./regress.sh . nngs2.tst
140 unexpected FAIL: Correct 'P5', got 'Q6'
./regress.sh . nngs3.tst
230 unexpected PASS!
310 unexpected FAIL: Correct 'C5|B5', got 'B7'
320 unexpected PASS!
400 unexpected FAIL: Correct 'N13', got 'Q15'
730 unexpected PASS!
830 unexpected FAIL: Correct '!N13', got 'N13'
840 unexpected PASS!
1080 unexpected FAIL: Correct '!H7', got 'H7'
1170 unexpected FAIL: Correct 'B1', got 'B7'
./regress.sh . strategy5.tst
226 unexpected PASS!
./regress.sh . century2002.tst
85 unexpected FAIL: Correct 'N9', got 'Q7'
150 unexpected PASS!
160 unexpected PASS!
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 11 Nov 2002 16:05:14 -0000
@@ -1950,6 +1950,50 @@ 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}};
+float
+compute_crude_dragon_weakness(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.
+ */
+ float true_genus = 0.5 * (max_eyes(genus) + min_eyes(genus)
+ + (has_lunch != 0));
+ float weakness_value[3];
+ float weakness;
+
+ int i, j;
+
+ 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,
+ " moyo value %f -> %f, escape %f -> %f, eyes %f -> %f,",
+ 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++)
+ if (weakness_value[j] < weakness_value[i]) {
+ float tmp = weakness_value[i];
+ weakness_value[i] = weakness_value[j];
+ weakness_value[j] = tmp;
+ }
+
+ /* The overall weakness is mostly, but not completely determined by the
+ * best value found so far:
+ */
+ 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.
@@ -1957,35 +2001,24 @@ struct interpolation_data genus2weakness
static float
compute_dragon_weakness_value(int d)
{
- /* 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;
- float weakness_value[3];
float weakness;
if (dragon_safety == INVINCIBLE || dragon_safety == INESSENTIAL)
return 0.0;
if (dragon_safety == TACTICALLY_DEAD)
return 1.0;
-
if (dragon_safety == DEAD)
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!
+ * + post-owl moyo_size and its territory value
* + escape factor
* + number of eyes
* - minus number of vital attack moves?
@@ -1997,31 +2030,12 @@ compute_dragon_weakness_value(int d)
* - 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[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]);
-
- for (i = 0; i < 3; i++)
- for (j = i + 1; j < 3; j++)
- if (weakness_value[j] < weakness_value[i]) {
- float tmp = weakness_value[i];
- weakness_value[i] = weakness_value[j];
- weakness_value[j] = tmp;
- }
- /* The overall weakness is mostly, but not completely determined by the
- * best value found so far:
- */
- weakness = gg_min(0.7 * weakness_value[0] + 0.3 * weakness_value[1],
- 1.3 * weakness_value[0]);
+ weakness = compute_crude_dragon_weakness(&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)
@@ -2037,9 +2051,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.72
diff -u -p -r1.72 gnugo.h
--- engine/gnugo.h 14 Oct 2002 17:02:57 -0000 1.72
+++ engine/gnugo.h 11 Nov 2002 16:05:17 -0000
@@ -468,7 +468,6 @@ void make_worms(int save_verbose);
/* 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.129
diff -u -p -r1.129 liberty.h
--- engine/liberty.h 23 Oct 2002 18:32:35 -0000 1.129
+++ engine/liberty.h 11 Nov 2002 16:05:22 -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 compute_crude_dragon_weakness(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.100
diff -u -p -r1.100 move_reasons.c
--- engine/move_reasons.c 14 Oct 2002 17:43:27 -0000 1.100
+++ engine/move_reasons.c 11 Nov 2002 16:05:29 -0000
@@ -1988,10 +1988,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 11 Nov 2002 16:05:30 -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 11 Nov 2002 16:05:42 -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,29 @@ 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
+ = compute_crude_dragon_weakness(&da->genus, da->lunch != NO_MOVE,
+ da->moyo_territorial_value,
+ (float) da->escape_route);
+ float crude_weakness_sum;
+ struct eyevalue genus_sum;
+ float old_burden;
+ float new_burden;
+ 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 +928,68 @@ 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 (safetya == INESSENTIAL || safetya == INVINCIBLE)
+ return 0.0;
+
+ if (terr_val < 0.0)
+ terr_val = 0.0;
+ 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 it does 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.
+ */
+ crude_weakness_sum
+ = compute_crude_dragon_weakness(&genus_sum,
+ (da->lunch != NO_MOVE
+ || db->lunch != NO_MOVE),
+ da->moyo_territorial_value
+ + db->moyo_territorial_value
+ + terr_val,
+ (float) da->escape_route);
+ /* The old burden is the burden of defending dragon a. */
+ old_burden = 2.0 * crude_weakness_a * strategic_effective_size(sizea);
- /* Trying to connect an inessential string to something else with a
- * self atari is almost certainly worthless.
+ /* The new burden is the burden of defending new joint dragon; but
+ * we share this burden proportionally with the other dragon.
*/
- if (impact > 0.0
- && safety1 == INESSENTIAL
- && is_self_atari(tt, board[dragona]))
- impact = 0.0;
-
- return impact * 2.0 * dragon[dragona].effective_size;
+ new_burden = 2.0 * crude_weakness_sum
+ * strategic_effective_size(sizea + sizeb)
+ * sizea / (sizea + sizeb);
+
+ return_value = 1.1 * (old_burden - new_burden);
+
+ /* This assertion should be valid as long as
+ * - crude_weakness_sum is not worse than crude_weakness_a
+ * - strategic_effective_size(x)/x is a decreasing function
+ */
+ gg_assert(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 +1923,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 +2194,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)
- [gnugo-devel] connections reevaluated,
Arend Bayer <=