[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] influence cleanup - arend_3_11.1a
From: |
Arend Bayer |
Subject: |
[gnugo-devel] influence cleanup - arend_3_11.1a |
Date: |
Wed, 30 Oct 2002 13:12:06 -0500 (EST) |
This is the first of four incremental patches doing some internal cleanup
in influence.c. (Cleaning up the interface to influence.c is probably more
important, but I thought I'd rather start here.)
This one kills the array q->w. It was used for different purposes in
accumulate_influence() and segment_region(), and both are IMHO better
served with a private static variable.
Defintely ugly was however its use in the followup_influence callback
structure. (For those who don't know, this part of the code was written
by myself, so I assume I am free to insult it...) This was used to
implement the following rule:
* An intrusion pattern (from barriers.db) is used for followup influence if
a) the Q-marked stone (the anchor of the pattern) is a saved stone
or directly or diagonally adjacent to one
b) one stone in the pattern is a saved stone
Changing this to the simple rule
* The pattern is used if the anchor is a saved stone
makes the code much cleaner and results in two PASSes, no FAILs in
the regressions.
Arend
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.66
diff -u -r1.66 influence.c
--- engine/influence.c 4 Oct 2002 18:52:35 -0000 1.66
+++ engine/influence.c 30 Oct 2002 15:41:11 -0000
@@ -131,12 +131,12 @@
} \
if (contribution <= INFLUENCE_CUTOFF) \
continue; \
- if (q->w[arg_i][arg_j] == 0.0) { \
+ if (working[arg_i][arg_j] == 0.0) { \
q->queuei[queue_end] = (arg_i); \
q->queuej[queue_end] = (arg_j); \
queue_end++; \
} \
- q->w[arg_i][arg_j] += contribution; \
+ working[arg_i][arg_j] += contribution; \
} } while (0)
#endif
@@ -153,11 +153,21 @@
float inv_attenuation;
float inv_diagonal_damping;
float (*permeability_array)[MAX_BOARD];
-
+
/* Clear the queue. Entry 0 is implicitly (m, n). */
int queue_start = 0;
int queue_end = 1;
+ static float working[MAX_BOARD][MAX_BOARD];
+ static int working_area_initialized = 0;
+
+ if (!working_area_initialized) {
+ for (i = 0; i < board_size; i++)
+ for (j = 0; j < board_size; j++)
+ working[i][j] = 0.0;
+ working_area_initialized = 1;
+ }
+
if (0)
gprintf("Accumulating influence for %s at %m\n",
color_to_string(color), m, n);
@@ -183,9 +193,9 @@
q->queuej[0] = n;
if (color == WHITE)
- q->w[m][n] = q->white_strength[m][n];
+ working[m][n] = q->white_strength[m][n];
else
- q->w[m][n] = q->black_strength[m][n];
+ working[m][n] = q->black_strength[m][n];
/* Spread influence until the stack is empty. */
@@ -199,13 +209,13 @@
continue;
if (0)
gprintf("Picked %m from queue. w=%f start=%d end=%d\n",
- i, j, q->w[i][j], queue_start, queue_end);
+ i, j, working[i][j], queue_start, queue_end);
if (queue_start == 1)
b = 1.0;
else
b = 1.0 / ((i-m)*(i-m) + (j-n)*(j-n));
- current_strength = q->w[i][j] * inv_attenuation;
+ current_strength = working[i][j] * inv_attenuation;
#if !EXPLICIT_LOOP_UNROLLING
/* Try to spread influence in each of the eight directions. */
@@ -267,12 +277,12 @@
if (0)
gprintf(" Spreading %s influence from %m to %m, d=%d\n",
color_to_string(color), i, j, i+di, j+dj, d);
- if (q->w[i+di][j+dj] == 0.0) {
+ if (working[i+di][j+dj] == 0.0) {
q->queuei[queue_end] = i + di;
q->queuej[queue_end] = j + dj;
queue_end++;
}
- q->w[i+di][j+dj] += contribution;
+ working[i+di][j+dj] += contribution;
}
}
#else
@@ -310,17 +320,17 @@
j = q->queuej[k];
if (color == WHITE) {
- if (q->w[i][j] > 1.01 * INFLUENCE_CUTOFF
+ if (working[i][j] > 1.01 * INFLUENCE_CUTOFF
|| q->white_influence[i][j] == 0.0)
- q->white_influence[i][j] += q->w[i][j];
+ q->white_influence[i][j] += working[i][j];
}
else {
- if (q->w[i][j] > 1.01 * INFLUENCE_CUTOFF
+ if (working[i][j] > 1.01 * INFLUENCE_CUTOFF
|| q->black_influence[i][j] == 0.0)
- q->black_influence[i][j] += q->w[i][j];
+ q->black_influence[i][j] += working[i][j];
}
- q->w[i][j] = 0.0;
+ working[i][j] = 0.0;
}
}
@@ -383,7 +393,6 @@
/* Initialize. */
q->white_influence[i][j] = 0.0;
q->black_influence[i][j] = 0.0;
- q->w[i][j] = 0.0;
q->white_attenuation[i][j] = attenuation;
q->black_attenuation[i][j] = attenuation;
q->white_permeability[i][j] = 1.0;
@@ -526,7 +535,7 @@
q->intrusion_counter++;
}
-/* Experimental influence: Comparison of intrusions datas, to sort them. */
+/* Comparison of intrusions datas, to sort them. */
static int
compare_intrusions(const void *p1, const void *p2)
{
@@ -545,11 +554,35 @@
return -1;
}
-/* Experimental influence: This function goes through the list of
- * intrusion sources, and adds the intrusion as influence sources for color.
- * The strength is corrected so that each stone's intrusions sources
- * can have total strength of at most 60%/100% of the strength of the stone.
- * (100% is if q=&followup_influence, 60% otherwise).
+/* It may happen that we have a low intensity influence source at a
+ * blocked intersection (due to an intrusion). This function resets the
+ * permeabilities.
+ */
+static void
+reset_unblocked_blocks(struct influence_data *q)
+{
+ int m, n;
+ for (m = 0; m < board_size; m++)
+ for (n = 0; n < board_size; n++) {
+ if (q->p[m][n] == EMPTY && q->white_strength[m][n] > 0.0
+ && q->white_permeability[m][n] != 1.0) {
+ DEBUG(DEBUG_INFLUENCE, " black block removed from %m\n", m, n);
+ q->white_permeability[m][n] = 1.0;
+ }
+ if (q->p[m][n] == EMPTY && q->black_strength[m][n] > 0.0
+ && q->black_permeability[m][n] != 1.0) {
+ DEBUG(DEBUG_INFLUENCE, " white block removed from %m\n", m, n);
+ q->black_permeability[m][n] = 1.0;
+ }
+ }
+}
+
+
+/* This function goes through the list of intrusion sources, and adds
+ * the intrusion as influence sources for color. The strength is
+ * corrected so that each stone's intrusions sources can have total
+ * strength of at most 60%/100% of the strength of the stone.
+ * (100% is if q == &followup_influence, 60% otherwise).
*/
static void
add_marked_intrusions(struct influence_data *q, int color)
@@ -561,6 +594,7 @@
float correction;
float source_strength;
float allowed_strength;
+
gg_sort(q->intrusions, q->intrusion_counter, sizeof(q->intrusions[0]),
compare_intrusions);
@@ -895,7 +929,6 @@
{
int k;
int t;
- int saved_stone_involved = 0;
struct influence_data *q = data;
UNUSED(color);
@@ -903,22 +936,6 @@
if (!(pattern->class & CLASS_B))
return;
- /* We check first whether a saved stone is involved. */
- for (k = 0; k < pattern->patlen; ++k) /* match each point */
- if (pattern->patn[k].att == ATT_O) {
- /* transform pattern real coordinate */
- int x, y;
- TRANSFORM(pattern->patn[k].x, pattern->patn[k].y, &x, &y, ll);
- x += m;
- y += n;
- if (q->w[x][y] == MARKED)
- saved_stone_involved = 1;
- }
-
- if (!saved_stone_involved)
- return;
-
-
t = AFFINE_TRANSFORM(pattern->movei, pattern->movej, ll, m, n);
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
@@ -1014,24 +1031,7 @@
}
}
}
-
- /* It may happen that we have a low intensity influence source at a
- * blocked intersection (due to an intrusion). Reset the
- * permeability at this point.
- */
- for (m = 0; m < board_size; m++)
- for (n = 0; n < board_size; n++) {
- if (q->p[m][n] == EMPTY && q->white_strength[m][n] > 0.0
- && q->white_permeability[m][n] != 1.0) {
- DEBUG(DEBUG_INFLUENCE, " black block removed from %m\n", m, n);
- q->white_permeability[m][n] = 1.0;
- }
- if (q->p[m][n] == EMPTY && q->black_strength[m][n] > 0.0
- && q->black_permeability[m][n] != 1.0) {
- DEBUG(DEBUG_INFLUENCE, " white block removed from %m\n", m, n);
- q->black_permeability[m][n] = 1.0;
- }
- }
+ reset_unblocked_blocks(q);
}
/* Compute the influence values for both colors, after having made a
@@ -1383,9 +1383,16 @@
int type, int (*segmentation)[MAX_BOARD])
{
int m, n;
+ static char marked[MAX_BOARD][MAX_BOARD];
+
+ /* Reset the markings. */
+ for (m = 0; m < board_size; m++)
+ for (n = 0; n < board_size; n++)
+ marked[m][n] = 0;
+
for (m = 0; m < board_size; m++)
for (n = 0; n < board_size; n++) {
- if (q->w[m][n] == UNMARKED && region_owner(q, m, n) != EMPTY) {
+ if ((!marked[m][n]) && region_owner(q, m, n) != EMPTY) {
/* Found an unlabelled intersection. Use flood filling to find
* the rest of the region.
*/
@@ -1395,7 +1402,7 @@
int queue_end = 1;
int color = region_owner(q, m, n);
q->number_of_regions++;
- q->w[m][n] = MARKED;
+ marked[m][n] = 1;
q->queuei[0] = m;
q->queuej[0] = n;
while (queue_start < queue_end) {
@@ -1413,12 +1420,12 @@
int di = deltai[k];
int dj = deltaj[k];
if (ON_BOARD2(i+di, j+dj)
- && q->w[i+di][j+dj] == UNMARKED
+ && !marked[i+di][j+dj]
&& region_owner(q, i+di, j+dj) == color) {
q->queuei[queue_end] = i+di;
q->queuej[queue_end] = j+dj;
queue_end++;
- q->w[i+di][j+dj] = MARKED;
+ marked[i+di][j+dj] = 1;
}
}
}
@@ -1434,10 +1441,6 @@
color_to_string(color), m, n, size);
}
}
- /* Reset the working area w. */
- for (m = 0; m < board_size; m++)
- for (n = 0; n < board_size; n++)
- q->w[m][n] = UNMARKED;
}
/* Segment the influence map into connected regions of territory,
@@ -1640,8 +1643,6 @@
char saved_stones[BOARDMAX])
{
int i, j;
- int ii;
- int k;
char goal[BOARDMAX];
UNUSED(m);
@@ -1652,20 +1653,11 @@
* and in q->w.
*/
for (i = 0; i < board_size; i++)
- for (j = 0; j < board_size; j++) {
- goal[POS(i,j)] = 0;
- followup_influence.w[i][j] = UNMARKED;
- }
- for (i = 0; i < board_size; i++)
for (j = 0; j < board_size; j++)
- if (saved_stones[POS(i,j)]) {
- ii = POS(i, j);
- goal[ii] = 1;
- followup_influence.w[i][j] = MARKED;
- for (k = 0; k < 8; k++)
- if (board[ii] == board[ii+delta[k]])
- goal[ii+delta[k]] = 1;
- }
+ if (saved_stones[POS(i,j)])
+ goal[POS(i, j)] = 1;
+ else
+ goal[POS(i, j)] = 0;
followup_influence.intrusion_counter = 0;
@@ -1673,34 +1665,11 @@
/* Match B patterns for saved stones. */
matchpat_goal_anchor(followup_influence_callback, color, &barrierspat_db,
&followup_influence, goal, 1);
-
- /* Reset the working area w. */
- for (i = 0; i < board_size; i++)
- for (j = 0; j < board_size; j++)
- followup_influence.w[i][j] = UNMARKED;
/* Now add the intrusions. */
add_marked_intrusions(&followup_influence, color);
- /* It may happen that we have a low intensity influence source at a
- * blocked intersection (due to an intrusion). Reset the
- * permeability at this point.
- */
- for (i = 0; i < board_size; i++)
- for (j = 0; j < board_size; j++) {
- if (followup_influence.p[i][j] == EMPTY
- && followup_influence.white_strength[i][j] > 0.0
- && followup_influence.white_permeability[i][j] != 1.0) {
- DEBUG(DEBUG_INFLUENCE, " black block removed from %m\n", i, j);
- followup_influence.white_permeability[i][j] = 1.0;
- }
- if (followup_influence.p[i][j] == EMPTY
- && followup_influence.black_strength[i][j] > 0.0
- && followup_influence.black_permeability[i][j] != 1.0) {
- DEBUG(DEBUG_INFLUENCE, " white block removed from %m\n", i, j);
- followup_influence.black_permeability[i][j] = 1.0;
- }
- }
+ reset_unblocked_blocks(&followup_influence);
/* Spread influence for new influence sources. */
for (i = 0; i < board_size; i++)
Index: engine/influence.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.h,v
retrieving revision 1.12
diff -u -r1.12 influence.h
--- engine/influence.h 19 Jun 2002 22:30:04 -0000 1.12
+++ engine/influence.h 30 Oct 2002 15:41:11 -0000
@@ -19,12 +19,14 @@
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+#if 0
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "liberty.h"
+#endif
/* Default attenuation coefficient.
* The "TERR_.."-values are used in the influence computations used
@@ -51,10 +53,6 @@
*/
#define NOT_COMPUTED (-2.0 * MAX_BOARD * MAX_BOARD)
-/* Values for the float working area w when used only for marking. */
-#define UNMARKED 0.0
-#define MARKED 1.0
-
/* Territory, moyo, and area are segmented into connected components
* and given a number from the same series. These values are used in
* region_type[][].
@@ -116,7 +114,6 @@
int color_to_move; /* Which color is in turn to move. */
- float w[MAX_BOARD][MAX_BOARD]; /* Working area. */
int queuei[MAX_BOARD * MAX_BOARD]; /* Points receiving influence. */
int queuej[MAX_BOARD * MAX_BOARD];
Index: regression/connection.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/connection.tst,v
retrieving revision 1.37
diff -u -r1.37 connection.tst
--- regression/connection.tst 21 Oct 2002 15:15:20 -0000 1.37
+++ regression/connection.tst 30 Oct 2002 15:41:20 -0000
@@ -314,6 +314,10 @@
95 disconnect O4 P3
#? [1 (N1|N2)]
+loadsgf games/handtalk/handtalk1.sgf 31
+96 same_dragon C16 C13
+#? [0]
+
# Report number of nodes visited by the tactical reading
10000 get_reading_node_counter
#? [0]&
- [gnugo-devel] influence cleanup - arend_3_11.1a,
Arend Bayer <=