[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] intrusions
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] intrusions |
|
Date: |
Thu, 9 Dec 2004 13:14:22 +0100 (CET) |
This patch tries to reduce the problem where gnugo underestimates the danger
of intrusions such as this one:
endgame:840
A B C D E F G H J K L M N O P Q R S T
19 . . . . O . . . . . . . . . . . . . . 19
18 . . O O X X . . X X O . . . . . . . . 18
17 . . O X . . . X O O . O . X O . . . . 17
16 O . O X . . . X O + O . . X . O . . . 16
15 . O X . . . . X X X a , O . . . . . . 15
14 X O X . . . . . X O , . . . . O . . . 14
13 . X . . . . . . X O . . . . . . . . . 13
12 . . . . . . . X O O . . O . O . . O O 12
GNU Go as white doesn't bother to play at "a", basically because there are
two influence blocks next to a, as if white could stop both continuations
of black intrusions at the same time. The solutions works as discussed some
time ago on the list:
+/* This function checks for the situation where an influence source for
+ * the color to move is direclty neighbored by 2 or more influence blocks.
+ * It then removes the least valuable of these blocks, and re-runs the
+ * influence accumulation for this position.
+ */
To estimate the value of a block, I just sum it's territory value with the
territory value of all neighbors. (And re-run territory evaluation after
all blocks are removed.)
Arend
nngs1:27 PASS H2 [H2]
Good.
endgame:840 PASS L15 [L15]
Good, exactly what the patch aimed for.
trevorb:230 FAIL M7 [L5]
partly accidental, real problem is too deep for gnugo
trevorb:900 FAIL E12 [F11]
100% accidental
nngs:930 PASS S8 [S8]
A bit lucky but good.
trevorc:1480 FAIL F6 [A8]
Accidental, highlights problem with Intrusion51b
13x13:43 FAIL B6 [D6]
I think B6 is fine (maybe even better).
gunnar:10 PASS R12 [R12|R14]
A bit accidental but valuation change is improvement.
thrash:14 PASS N17 [N17]
Good.
kgs:110 PASS G13 [G13]
100% accidental.
6 PASS
4 FAIL
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.104
diff -u -p -r1.104 influence.c
--- engine/influence.c 13 Nov 2004 04:46:43 -0000 1.104
+++ engine/influence.c 8 Dec 2004 23:08:09 -0000
@@ -1087,6 +1087,98 @@ find_influence_patterns(struct influence
reset_unblocked_blocks(q);
}
+/* This function checks whether we have two or more adjacent blocks for
+ * influence of color next to pos. If yes, it returns the position of the
+ * least valuable blocks; otherwise, it returns NO_MOVE.
+ */
+static int
+check_double_block(int color, int pos, const struct influence_data *q)
+{
+ int k;
+ int block_neighbors = 0;
+ const float *permeability = ((color == BLACK) ? q->black_permeability :
+ q->white_permeability);
+
+ /* Count neighboring blocks. */
+ for (k = 0; k < 4; k++)
+ if (board[pos + delta[k]] == EMPTY && permeability[pos + delta[k]] == 0.0)
+ block_neighbors++;
+
+ if (block_neighbors >= 2) {
+ /* Search for least valuable block. */
+ float smallest_value = 4.0 * MAX_BOARD * MAX_BOARD;
+ int smallest_block = NO_MOVE;
+ /* We count opponent's territory as positive. */
+ float sign = ((color == WHITE) ? -1.0 : 1.0);
+ for (k = 0; k < 4; k++) {
+ int neighbor = pos + delta[k];
+ if (board[neighbor] == EMPTY && permeability[neighbor] == 0.0) {
+ /* Value is sum of opponents territory at this and all 4 neighboring
+ * intersections.
+ */
+ float this_value = sign * q->territory_value[neighbor];
+ int j;
+ for (j = 0; j < 4; j++)
+ if (ON_BOARD(neighbor + delta[j]))
+ this_value += sign * q->territory_value[neighbor + delta[j]];
+ /* We use an artifical tie breaker to avoid possible platform
+ * dependency.
+ */
+ if (this_value + 0.0005 < smallest_value) {
+ smallest_block = neighbor;
+ smallest_value = this_value;
+ }
+ }
+ }
+ ASSERT1(ON_BOARD1(smallest_block), pos);
+ return smallest_block;
+ }
+ return NO_MOVE;
+}
+
+#define MAX_DOUBLE_BLOCKS 20
+
+
+/* This function checks for the situation where an influence source for
+ * the color to move is direclty neighbored by 2 or more influence blocks.
+ * It then removes the least valuable of these blocks, and re-runs the
+ * influence accumulation for this position.
+ *
+ * See endgame:840 for an example where this is essential.
+ */
+static void
+remove_double_blocks(struct influence_data *q,
+ const char inhibited_sources[BOARDMAX])
+{
+ int ii;
+ float *strength = ((q->color_to_move == WHITE) ? q->white_strength :
+ q->black_strength);
+ int double_blocks[MAX_DOUBLE_BLOCKS];
+ int num_blocks = 0;
+ for (ii = BOARDMIN; ii < BOARDMAX; ii++)
+ if (board[ii] == EMPTY
+ && !(inhibited_sources && inhibited_sources[ii])
+ && strength[ii] > 0.0) {
+ double_blocks[num_blocks] = check_double_block(q->color_to_move, ii, q);
+ if (double_blocks[num_blocks] != NO_MOVE) {
+ num_blocks++;
+ if (num_blocks == MAX_DOUBLE_BLOCKS)
+ break;
+ }
+ }
+ {
+ int k;
+ float *permeability = ((q->color_to_move == BLACK)
+ ? q->black_permeability : q->white_permeability);
+ for (k = 0; k < num_blocks; k++) {
+ DEBUG(DEBUG_INFLUENCE, "Removing block for %s at %1m.\n",
+ q->color_to_move, double_blocks[k]);
+ permeability[double_blocks[k]] = 1.0;
+ accumulate_influence(q, double_blocks[k], q->color_to_move);
+ }
+ }
+}
+
/* Do the real work of influence computation. This is called from
* compute_influence and compute_escape_influence.
@@ -1116,6 +1208,9 @@ do_compute_influence(int color, const ch
}
value_territory(q);
+ remove_double_blocks(q, inhibited_sources);
+
+ value_territory(q);
segment_influence(q);
if ((move == NO_MOVE
Index: regression/atari_atari.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/atari_atari.tst,v
retrieving revision 1.47
diff -u -p -r1.47 atari_atari.tst
--- regression/atari_atari.tst 27 Nov 2004 18:45:11 -0000 1.47
+++ regression/atari_atari.tst 8 Dec 2004 23:08:09 -0000
@@ -123,4 +123,4 @@ play white H5
# See also nngs:1060. Black has no combination attack at R3.
loadsgf games/nngs/gnugo-3.1.18-goku-200201042350.sgf 52
28 combination_attack black
-#? [0]
+#? [0]*
Index: regression/blunder.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/blunder.tst,v
retrieving revision 1.49
diff -u -p -r1.49 blunder.tst
--- regression/blunder.tst 11 Sep 2004 18:55:12 -0000 1.49
+++ regression/blunder.tst 8 Dec 2004 23:08:09 -0000
@@ -161,7 +161,7 @@ loadsgf games/nngs/gnugo-3.4-viking4-200
# This needs a detect_semeai_blunder().
loadsgf games/kisei28_g7.sgf 280
33 reg_genmove white
-#? [!H6|J1]
+#? [!H6|J1]*
# Fills a common liberty in a seki similar to blunder:32.
loadsgf games/kgs/2004-04-28-R-dokuganryu-GnuGoCVS.sgf 302
Index: regression/buzco.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/buzco.tst,v
retrieving revision 1.18
diff -u -p -r1.18 buzco.tst
--- regression/buzco.tst 10 Jul 2003 23:16:39 -0000 1.18
+++ regression/buzco.tst 8 Dec 2004 23:08:09 -0000
@@ -14,7 +14,7 @@ loadsgf games/buzco1.sgf 28
loadsgf games/buzco1.sgf 36
4 reg_genmove black
-#? [D13]*
+#? [D13]
loadsgf games/buzco1.sgf 70
5 reg_genmove black
Index: regression/connection.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/connection.tst,v
retrieving revision 1.79
diff -u -p -r1.79 connection.tst
--- regression/connection.tst 27 Nov 2004 18:45:11 -0000 1.79
+++ regression/connection.tst 8 Dec 2004 23:08:10 -0000
@@ -413,7 +413,7 @@ popgo
loadsgf games/gunnar/gunnar9.sgf 4
115 disconnect D10 J7
-#? [1 H7]
+#? [1 H7]*
# Report number of nodes visited by the tactical reading
10000 get_reading_node_counter
Index: regression/gunnar.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/gunnar.tst,v
retrieving revision 1.45
diff -u -p -r1.45 gunnar.tst
--- regression/gunnar.tst 28 Nov 2004 18:47:31 -0000 1.45
+++ regression/gunnar.tst 8 Dec 2004 23:08:10 -0000
@@ -313,14 +313,14 @@ loadsgf games/gunnar/gunnar13.sgf
loadsgf games/gunnar/gunnar14.sgf
play black B1
55 restricted_genmove white C13 D13 C1
-#? [D13]*
+#? [D13]
# White must find a ko threat. A11 is neither a ko threat, nor worth a
# point.
loadsgf games/gunnar/gunnar15.sgf
play black R1
56 reg_genmove white
-#? [P18|E15|O12|N11|T12|T10|S7|T5]*
+#? [P18|E15|O12|N11|T12|T10|S7|T5]
# No territory to contest around J12. Connect ko at Q19 instead.
loadsgf games/gunnar/gunnar16.sgf
Index: regression/ld_owl.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/ld_owl.tst,v
retrieving revision 1.45
diff -u -p -r1.45 ld_owl.tst
--- regression/ld_owl.tst 4 Dec 2004 19:50:23 -0000 1.45
+++ regression/ld_owl.tst 8 Dec 2004 23:08:10 -0000
@@ -392,11 +392,11 @@ loadsgf games/life_and_death/mixed3.sgf
321 owl_attack D11
#? [2 B12]
322 owl_attack K13
-#? [1 (N11|N13|PASS)]
+#? [1 (N11|N13|PASS)]*
323 owl_defend K13
#? [0]
324 owl_attack L4
-#? [1 N2]
+#? [1 N2]*
# tough under the stones problem from Sensei's Library
loadsgf games/owl47.sgf 5
Index: regression/nngs.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/nngs.tst,v
retrieving revision 1.76
diff -u -p -r1.76 nngs.tst
--- regression/nngs.tst 27 Nov 2004 18:45:11 -0000 1.76
+++ regression/nngs.tst 8 Dec 2004 23:08:10 -0000
@@ -155,7 +155,7 @@ loadsgf games/nngs/Lazarus-gnugo-3.1.17-
loadsgf games/nngs/Lazarus-gnugo-3.1.17-200112301450.sgf 126
380 reg_genmove black
-#? [!H2|S1]
+#? [!H2|S1]*
loadsgf games/nngs/Lazarus-gnugo-3.1.17-200112301450.sgf 152
@@ -488,7 +488,7 @@ loadsgf games/nngs/gnugo-3.1.18-goku-200
# See also atari_atari:28.
loadsgf games/nngs/gnugo-3.1.18-goku-200201042350.sgf 52
1060 reg_genmove white
-#? [H3|F3]
+#? [H3|F3]*
loadsgf games/nngs/gnugo-3.1.18-goku-200201042350.sgf 56
Index: regression/nngs3.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/nngs3.tst,v
retrieving revision 1.64
diff -u -p -r1.64 nngs3.tst
--- regression/nngs3.tst 27 Nov 2004 18:45:11 -0000 1.64
+++ regression/nngs3.tst 8 Dec 2004 23:08:10 -0000
@@ -521,7 +521,7 @@ loadsgf games/nngs/gnugo-3.2-merlin-2002
# We may want to add more moves as acceptable.
loadsgf games/nngs/gnugo-3.2-merlin-200205071828.sgf 224
1090 reg_genmove white
-#? [R7|N9|M8]*
+#? [R7|N9|M8]
# Moved to filllib:41.
Index: regression/reading.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/reading.tst,v
retrieving revision 1.80
diff -u -p -r1.80 reading.tst
--- regression/reading.tst 4 Dec 2004 19:50:23 -0000 1.80
+++ regression/reading.tst 8 Dec 2004 23:08:10 -0000
@@ -861,17 +861,17 @@ popgo
loadsgf games/reading46.sgf
203 attack H9
-#? [1 E9]
+#? [1 E9]*
204 defend H9
#? [1 (C6|E9|G9)]
loadsgf games/reading47.sgf
205 attack G2
-#? [0]
+#? [0]*
loadsgf games/reading47.sgf
206 attack B3
-#? [0]
+#? [0]*
# Report number of nodes visited by the tactical reading
10000 get_reading_node_counter
Index: regression/seki.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/seki.tst,v
retrieving revision 1.17
diff -u -p -r1.17 seki.tst
--- regression/seki.tst 20 Nov 2004 13:20:03 -0000 1.17
+++ regression/seki.tst 8 Dec 2004 23:08:10 -0000
@@ -106,7 +106,7 @@ play white B1
undo
play white C1
112 reg_genmove black
-#? [B1]
+#? [B1]*
loadsgf games/seki06.sgf
Index: regression/semeai.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/semeai.tst,v
retrieving revision 1.64
diff -u -p -r1.64 semeai.tst
--- regression/semeai.tst 4 Dec 2004 19:45:02 -0000 1.64
+++ regression/semeai.tst 8 Dec 2004 23:08:10 -0000
@@ -411,15 +411,15 @@ loadsgf games/semeai/semeai17.sgf 60
loadsgf games/semeai/semeai17.sgf 62
110 analyze_semeai G8 H2
-#? [1 0 (PASS|F3|E1)]*
+#? [1 0 (PASS|F3|E1)]
111 analyze_semeai H2 G8
-#? [1 0 (PASS|F3|E1)]*
+#? [1 0 (PASS|F3|E1)]
loadsgf games/semeai/semeai17.sgf 64
112 analyze_semeai G8 H2
-#? [1 0 PASS]*
+#? [1 0 PASS]
113 analyze_semeai H2 G8
-#? [1 0 PASS]*
+#? [1 0 PASS]
loadsgf games/kgs/yagr-nigiri.sgf 214
116 analyze_semeai F19 F16
@@ -440,7 +440,7 @@ play white H2
# A14 is strictly correct since C19 allows W an unfavorable ko.
loadsgf games/semeai/semeai19.sgf
120 analyze_semeai C18 C19
-#? [1 1 (A14|C19)]
+#? [1 1 (A14|C19)]*
# There is a complication that B18 and C17 are not amalgamated.
# If B plays first C19 gives a favorable ko; A15 allows seki.
@@ -448,20 +448,20 @@ loadsgf games/semeai/semeai19.sgf
# arguably correct.
loadsgf games/semeai/semeai20.sgf
121 analyze_semeai C17 C18
-#? [1 0]
+#? [1 0]*
122 analyze_semeai C18 C17
-#? [2 2 C19]
+#? [2 2 C19]*
# There is also an amalgamation problem here.
loadsgf games/semeai/semeai19.sgf 80
123 analyze_semeai K18 N18
-#? [1 1 M18]
+#? [1 1 M18]*
loadsgf games/verybad.sgf 104
124 analyze_semeai Q16 Q17
#? [1 1 P19]
125 analyze_semeai Q17 Q16
-#? [3 3 T17]
+#? [3 3 T17]*
loadsgf games/verybad.sgf 114
126 analyze_semeai Q16 Q17
@@ -502,7 +502,7 @@ loadsgf games/semeai/semeai17.sgf 52
# Take the ko last.
loadsgf games/verybad.sgf 114
128 restricted_genmove black T15 T17 S17 P19
-#? [!T15]
+#? [!T15]*
########### semeai status tests #################
Index: regression/strategy3.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/strategy3.tst,v
retrieving revision 1.63
diff -u -p -r1.63 strategy3.tst
--- regression/strategy3.tst 20 Nov 2004 13:20:03 -0000 1.63
+++ regression/strategy3.tst 8 Dec 2004 23:08:10 -0000
@@ -78,7 +78,7 @@ loadsgf games/poka.sgf 52
# M4 and N5 are okay. O5 is a bad mistake.
loadsgf games/incident278.sgf 212
116 reg_genmove black
-#? [M4|N5]
+#? [M4|N5]*
# incident 282
loadsgf games/incident278.sgf 252
Index: regression/strategy4.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/strategy4.tst,v
retrieving revision 1.82
diff -u -p -r1.82 strategy4.tst
--- regression/strategy4.tst 27 Nov 2004 18:45:11 -0000 1.82
+++ regression/strategy4.tst 8 Dec 2004 23:08:11 -0000
@@ -40,7 +40,7 @@ loadsgf games/ssstator.sgf 133
# B12, A14, and A12.
loadsgf games/ssstator.sgf 136
157 reg_genmove white
-#? [B14|B13|B12|A14|A12]
+#? [B14|B13|B12|A14|A12]*
# E16 is completely aimless and ineffective.
loadsgf games/strategy38.sgf 51
Index: regression/strategy5.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/strategy5.tst,v
retrieving revision 1.45
diff -u -p -r1.45 strategy5.tst
--- regression/strategy5.tst 29 Nov 2004 04:30:30 -0000 1.45
+++ regression/strategy5.tst 8 Dec 2004 23:08:11 -0000
@@ -170,10 +170,10 @@ loadsgf games/kisei28_g7.sgf 189
loadsgf games/semeai/semeai19.tst 42
292 restricted_genmove black A15 F16 F17 S4 Q3
-#? [F16|F17]
+#? [F16|F17]*
293 reg_genmove white
-#? [F17]
+#? [F17]*
############ End of Tests #################
- [gnugo-devel] intrusions,
Arend Bayer <=