[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] use fixed point arithmetics in accumulat_influence
From: |
Arend Bayer |
Subject: |
[gnugo-devel] use fixed point arithmetics in accumulat_influence |
Date: |
Fri, 29 Nov 2002 00:22:57 +0100 (CET) |
- convert accumulate_influence() to use fixed point integer
My main motivation for this patch was to make GNU Go more suitable
for a submission to SPECint by converting the biggest (computation time
wise) use of floating point to integer. It turned out to be faster
(on my Athlon K6-2 using gcc 2.95.3 -O2 -m486), and so I'd suggest to add this
patch to CVS. (But I have no strong opinion here, see caveat below.)
The patch works by defining GG_ONE = 2^12, and then replacing all
old floating point values by value * GG_ONE. Multiplication then becomes
a * b / GG_ONE (this is optimized by the compiler to a * b >> 12).
The obvious draw-back of this patch is that it will generate overflows
as soon as, say, someone changes the DEFAULT_STRENGTH to 400.0 without
adjusting GG_ONE.
Additional checking of the performance benefit would be welcome. Running
safety.tst at --level 0 should suffice.
Arend
[N.B.: It's actually a non-trivial question _why_ this patch is a
performance improvement. Mixed integer/floating points code could have
the potential to be faster by better using processor pipelines. Probably
the code in #define code1 has simply too many branches depending on
floating point results too make this happen.]
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.67
diff -u -p -r1.67 influence.c
--- engine/influence.c 5 Nov 2002 12:54:23 -0000 1.67
+++ engine/influence.c 28 Nov 2002 23:16:25 -0000
@@ -30,21 +30,20 @@
#include "patterns.h"
#include "gg_utils.h"
-static void add_influence_source(int pos, int color, float strength,
- float attenuation,
- struct influence_data *q);
+static void add_influence_source(int pos, int color, int strength,
+ int attenuation, struct influence_data *q);
static void segment_influence(struct influence_data *q);
static void print_influence(struct influence_data *q,
const char *info_string);
static void print_numeric_influence(struct influence_data *q,
- float values[BOARDMAX],
+ int values[BOARDMAX],
const char *format, int draw_stones,
int mark_epsilon);
static void print_influence_areas(struct influence_data *q);
static void value_territory(struct influence_data *q, int pos, int color);
static void enter_intrusion_source(int source_pos, int strength_pos,
- float strength, float attenuation,
+ int strength, int attenuation,
struct influence_data *q);
static void add_marked_intrusions(struct influence_data *q, int color);
static void print_influence_territory(struct influence_data *q,
@@ -103,12 +102,11 @@ static int debug_influence = NO_MOVE;
* delta_i = I(ii) - m
* delta_j = J(ii) - n
* current_strength combines strength and damping factor
- * b is 1/(square of distance from m,n to i,j) ; or halved
+ * b is (square of distance from m,n to i,j) ; or doubled
* for diagonals
*
- * arg is i + arg_di ; arg_j is j + arg_dj
+ * arg is POS(i + arg_di, j + arg_dj)
* arg_d is 1 for diagonal movement
- *
*/
@@ -116,22 +114,25 @@ static int debug_influence = NO_MOVE;
if (q->p[arg] == EMPTY \
&& ((arg_di)*(delta_i) + (arg_dj)*(delta_j) > 0 \
|| queue_start == 1)) { \
- float contribution; \
- float permeability = permeability_array[ii]; \
+ int contribution; \
+ int permeability = permeability_array[ii]; \
if (arg_d) { \
- permeability *= gg_max(permeability_array[ii + DELTA(arg_di, 0)], \
- permeability_array[ii + DELTA(0, arg_dj)]); \
- if (permeability == 0.0) \
+ permeability = (permeability \
+ * gg_max(permeability_array[ii + DELTA(arg_di, 0)], \
+ permeability_array[ii + DELTA(0, arg_dj)])) \
+ / GG_ONE; \
+ if (permeability == 0) \
continue; \
} \
- contribution = current_strength * permeability; \
+ contribution = (current_strength * permeability) / GG_ONE; \
if (queue_start != 1) { \
int a = (arg_di)*(delta_i) + (arg_dj)*(delta_j); \
- contribution *= (a*a) * b; /* contribution *= cos(phi) */ \
+ contribution *= (a*a); \
+ contribution /= b; /* contribution *= cos(phi) */ \
} \
if (contribution <= INFLUENCE_CUTOFF) \
continue; \
- if (working[arg] == 0.0) { \
+ if (working[arg] == 0) { \
q->queue[queue_end] = (arg); \
queue_end++; \
} \
@@ -150,21 +151,21 @@ accumulate_influence(struct influence_da
#if !EXPLICIT_LOOP_UNROLLING
int d;
#endif
- float b;
- float inv_attenuation;
- float inv_diagonal_damping;
- float (*permeability_array);
+ int b;
+ int attenuation;
+ int diagonal_damping;
+ int *permeability_array;
/* Clear the queue. Entry 0 is implicitly (m, n). */
int queue_start = 0;
int queue_end = 1;
- static float working[BOARDMAX];
+ static int working[BOARDMAX];
static int working_area_initialized = 0;
if (!working_area_initialized) {
for (ii = 0; ii < BOARDMAX; ii++)
- working[ii] = 0.0;
+ working[ii] = 0;
working_area_initialized = 1;
}
@@ -174,14 +175,14 @@ accumulate_influence(struct influence_da
/* Attenuation only depends on the influence origin. */
if (color == WHITE)
- inv_attenuation = 1.0 / q->white_attenuation[pos];
+ attenuation = q->white_attenuation[pos];
else
- inv_attenuation = 1.0 / q->black_attenuation[pos];
+ attenuation = q->black_attenuation[pos];
if (q->is_territorial_influence)
- inv_diagonal_damping = 1.0 / TERR_DIAGONAL_DAMPING;
+ diagonal_damping = TERR_DIAGONAL_DAMPING;
else
- inv_diagonal_damping = 1.0 / DIAGONAL_DAMPING;
+ diagonal_damping = DIAGONAL_DAMPING;
if (color == WHITE)
permeability_array = q->white_permeability;
@@ -199,24 +200,24 @@ accumulate_influence(struct influence_da
/* Spread influence until the stack is empty. */
while (queue_start < queue_end) {
- float current_strength;
+ int current_strength;
int delta_i, delta_j;
ii = q->queue[queue_start];
delta_i = I(ii) - m;
delta_j = J(ii) - n;
queue_start++;
- if (permeability_array[ii] == 0.0)
+ if (permeability_array[ii] == 0)
continue;
if (0)
gprintf("Picked %1m from queue. w=%f start=%d end=%d\n",
- ii, working[ii], queue_start, queue_end);
+ ii, 1.0f * working[ii] / GG_ONE, queue_start, queue_end);
if (queue_start == 1)
- b = 1.0;
+ b = 1;
else
- b = 1.0 / ((delta_i)*(delta_i) + (delta_j)*(delta_j));
+ b = ((delta_i)*(delta_i) + (delta_j)*(delta_j));
- current_strength = working[ii] * inv_attenuation;
+ current_strength = (working[ii] * attenuation) / GG_ONE;
#if !EXPLICIT_LOOP_UNROLLING
/* Try to spread influence in each of the eight directions. */
@@ -297,8 +298,9 @@ accumulate_influence(struct influence_da
code1(deltai[3], deltaj[3], ii + delta[3], 0);
/* Update factors for diagonal movement. */
- b *= 0.5;
- current_strength *= inv_diagonal_damping;
+ b *= 2;
+ current_strength *= diagonal_damping;
+ current_strength /= GG_ONE;
if (ON_BOARD(ii + delta[4]))
code1(deltai[4], deltaj[4], ii + delta[4], 1);
@@ -320,17 +322,17 @@ accumulate_influence(struct influence_da
ii = q->queue[k];
if (color == WHITE) {
- if (working[ii] > 1.01 * INFLUENCE_CUTOFF
- || q->white_influence[ii] == 0.0)
+ if (working[ii] > INFLUENCE_CUTOFF
+ || q->white_influence[ii] == 0)
q->white_influence[ii] += working[ii];
}
else {
- if (working[ii] > 1.01 * INFLUENCE_CUTOFF
- || q->black_influence[ii] == 0.0)
+ if (working[ii] > INFLUENCE_CUTOFF
+ || q->black_influence[ii] == 0)
q->black_influence[ii] += working[ii];
}
- working[ii] = 0.0;
+ working[ii] = 0;
}
}
@@ -366,7 +368,7 @@ init_influence(struct influence_data *q,
char saved_stones[BOARDMAX])
{
int ii;
- float attenuation;
+ int attenuation;
gg_assert(saved_stones != NULL);
@@ -379,10 +381,7 @@ init_influence(struct influence_data *q,
}
else {
q->color_to_move = EMPTY;
- if (q->is_territorial_influence)
- attenuation = 2 * TERR_DEFAULT_ATTENUATION;
- else
- attenuation = 2 * DEFAULT_ATTENUATION;
+ attenuation = DEFAULT_ATTENUATION / 2;
}
q->intrusion_counter = 0;
@@ -390,14 +389,14 @@ init_influence(struct influence_data *q,
for (ii = 0; ii < BOARDMAX; ii++)
if (ON_BOARD(ii)) {
/* Initialize. */
- q->white_influence[ii] = 0.0;
- q->black_influence[ii] = 0.0;
+ q->white_influence[ii] = 0;
+ q->black_influence[ii] = 0;
q->white_attenuation[ii] = attenuation;
q->black_attenuation[ii] = attenuation;
- q->white_permeability[ii] = 1.0;
- q->black_permeability[ii] = 1.0;
- q->white_strength[ii] = 0.0;
- q->black_strength[ii] = 0.0;
+ q->white_permeability[ii] = GG_ONE;
+ q->black_permeability[ii] = GG_ONE;
+ q->white_strength[ii] = 0;
+ q->black_strength[ii] = 0;
q->p[ii] = board[ii];
q->non_territory[ii] = EMPTY;
@@ -420,9 +419,9 @@ init_influence(struct influence_data *q,
|| (DRAGON2(ii).safety == CRITICAL
&& board[ii] == OTHER_COLOR(color))))))) {
if (q->p[ii] == WHITE)
- q->white_permeability[ii] = 0.0;
+ q->white_permeability[ii] = 0;
else
- q->black_permeability[ii] = 0.0;
+ q->black_permeability[ii] = 0;
q->p[ii] = EMPTY;
}
else if (saved_stones[ii] == INFLUENCE_SAVED_STONE
@@ -434,9 +433,9 @@ init_influence(struct influence_data *q,
|| (DRAGON2(ii).safety == CRITICAL
&& board[ii] == color)) {
if (q->p[ii] == WHITE)
- q->black_permeability[ii] = 0.0;
+ q->black_permeability[ii] = 0;
else
- q->white_permeability[ii] = 0.0;
+ q->white_permeability[ii] = 0;
}
/* We need to make an exception to the rules above for
@@ -475,17 +474,17 @@ init_influence(struct influence_data *q,
ASSERT1(dragon[ii].id != -1, ii);
if (q->p[ii] == WHITE) {
if (color == BLACK && DRAGON2(ii).safety == CRITICAL)
- q->white_strength[ii] = 0.0;
+ q->white_strength[ii] = 0;
else
- q->white_strength[ii] = (DEFAULT_STRENGTH
- * strength_map[DRAGON2(ii).safety]);
+ q->white_strength[ii] = DEFAULT_STRENGTH
+ * strength_map[DRAGON2(ii).safety];
}
else if (q->p[ii] == BLACK) {
if (color == WHITE && DRAGON2(ii).safety == CRITICAL)
- q->black_strength[ii] = 0.0;
+ q->black_strength[ii] = 0;
else
- q->black_strength[ii] = (DEFAULT_STRENGTH
- * strength_map[DRAGON2(ii).safety]);
+ q->black_strength[ii] = DEFAULT_STRENGTH
+ * strength_map[DRAGON2(ii).safety];
}
}
}
@@ -498,7 +497,7 @@ init_influence(struct influence_data *q,
* that is stronger than the new one, we do nothing.
*/
static void
-add_influence_source(int pos, int color, float strength, float attenuation,
+add_influence_source(int pos, int color, int strength, int attenuation,
struct influence_data *q)
{
if ((color & WHITE) && (q->white_strength[pos] < strength)) {
@@ -517,7 +516,7 @@ add_influence_source(int pos, int color,
*/
static void
enter_intrusion_source(int source_pos, int strength_pos,
- float strength, float attenuation,
+ int strength, int attenuation,
struct influence_data *q)
{
if (q->intrusion_counter >= MAX_INTRUSIONS) {
@@ -560,15 +559,15 @@ reset_unblocked_blocks(struct influence_
int pos;
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos)) {
- if (q->p[pos] == EMPTY && q->white_strength[pos] > 0.0
- && q->white_permeability[pos] != 1.0) {
+ if (q->p[pos] == EMPTY && q->white_strength[pos] > 0
+ && q->white_permeability[pos] != GG_ONE) {
DEBUG(DEBUG_INFLUENCE, " black block removed from %1m\n", pos);
- q->white_permeability[pos] = 1.0;
+ q->white_permeability[pos] = GG_ONE;
}
- if (q->p[pos] == EMPTY && q->black_strength[pos] > 0.0
- && q->black_permeability[pos] != 1.0) {
+ if (q->p[pos] == EMPTY && q->black_strength[pos] > 0
+ && q->black_permeability[pos] != GG_ONE) {
DEBUG(DEBUG_INFLUENCE, " white block removed from %1m\n", pos);
- q->black_permeability[pos] = 1.0;
+ q->black_permeability[pos] = GG_ONE;
}
}
}
@@ -586,17 +585,17 @@ add_marked_intrusions(struct influence_d
int i;
int j = 0;
int source_pos;
- float strength_sum;
+ int strength_sum;
float correction;
- float source_strength;
- float allowed_strength;
+ int source_strength;
+ int allowed_strength;
gg_sort(q->intrusions, q->intrusion_counter, sizeof(q->intrusions[0]),
compare_intrusions);
/* Go through all intrusion sources. */
for (i = 0; i < q->intrusion_counter; i = j) {
- strength_sum = 0.0;
+ strength_sum = 0;
source_pos = q->intrusions[i].source_pos;
/* "Anonymous" intrusios go in uncorrected. */
if (source_pos == NO_MOVE) {
@@ -605,7 +604,8 @@ add_marked_intrusions(struct influence_d
q->intrusions[j].attenuation, q);
DEBUG(DEBUG_INFLUENCE, "Adding %s intrusion at %1m, value %f\n",
(color == BLACK) ? "black" : "white",
- q->intrusions[j].strength_pos, q->intrusions[j].strength);
+ q->intrusions[j].strength_pos,
+ 1.0f * q->intrusions[j].strength / GG_ONE);
j = i+1;
continue;
}
@@ -627,11 +627,11 @@ add_marked_intrusions(struct influence_d
if (q == &followup_influence)
allowed_strength = source_strength;
else
- allowed_strength = 0.6 * source_strength;
+ allowed_strength = (source_strength * 6) / 10;
if (strength_sum > allowed_strength)
- correction = (allowed_strength / strength_sum);
+ correction = (allowed_strength * GG_ONE) / strength_sum;
else
- correction = 1.0;
+ correction = GG_ONE;
/* Second loop: Add influence sources. */
for (j = i; (j < q->intrusion_counter)
@@ -640,13 +640,15 @@ add_marked_intrusions(struct influence_d
if (j == i || q->intrusions[j].strength_pos
!= q->intrusions[j-1].strength_pos) {
add_influence_source(q->intrusions[j].strength_pos, color,
- correction * q->intrusions[j].strength,
+ (correction * q->intrusions[j].strength) / GG_ONE,
q->intrusions[j].attenuation, q);
DEBUG(DEBUG_INFLUENCE,
"Adding %s intrusion for %1m at %1m, value %f (correction %f)\n",
(color == BLACK) ? "black" : "white", source_pos,
q->intrusions[j].strength_pos,
- correction * q->intrusions[j].strength, correction);
+ (1.0f * (correction * q->intrusions[j].strength / GG_ONE )
+ / GG_ONE),
+ 1.0f * correction / GG_ONE);
}
}
}
@@ -712,9 +714,9 @@ influence_callback(int m, int n, int col
else
blocking_color = OTHER_COLOR(color);
if ((blocking_color == WHITE
- && q->black_permeability[ii] != 0.0)
+ && q->black_permeability[ii] != 0)
|| (blocking_color == BLACK
- && q->white_permeability[ii] != 0.0)) {
+ && q->white_permeability[ii] != 0)) {
something_to_do = 1;
break;
}
@@ -745,8 +747,8 @@ influence_callback(int m, int n, int col
int ii = AFFINE_TRANSFORM(pattern->patn[k].x, pattern->patn[k].y,
ll, m , n);
if (pattern->class & CLASS_E) {
- if ((color == WHITE && q->white_strength[ii] == 0.0)
- || (color == BLACK && q->black_strength[ii] == 0.0))
+ if ((color == WHITE && q->white_strength[ii] == 0)
+ || (color == BLACK && q->black_strength[ii] == 0))
return; /* Match failed. */
}
/* FIXME: This test is probably not necessary any more. */
@@ -758,22 +760,22 @@ influence_callback(int m, int n, int col
/* One test left for class B and t. */
if ((pattern->class & (CLASS_B | CLASS_t))
&& pattern->patn[k].att == ATT_O) {
- if ((color == WHITE && q->white_strength[ii] == 0.0)
- || (color == BLACK && q->black_strength[ii] == 0.0))
+ if ((color == WHITE && q->white_strength[ii] == 0)
+ || (color == BLACK && q->black_strength[ii] == 0))
return; /* Match failed. */
}
if ((pattern->class & (CLASS_A | CLASS_t))
&& pattern->patn[k].att == ATT_X) {
- if ((color == BLACK && q->white_strength[ii] == 0.0)
- || (color == WHITE && q->black_strength[ii] == 0.0))
+ if ((color == BLACK && q->white_strength[ii] == 0)
+ || (color == WHITE && q->black_strength[ii] == 0))
return; /* Match failed. */
}
if (pattern->class & CLASS_D) {
gg_assert(pattern->patn[k].att == ATT_O);
- if ((color == WHITE && q->white_strength[ii] == 0.0)
- || (color == BLACK && q->black_strength[ii] == 0.0))
+ if ((color == WHITE && q->white_strength[ii] == 0)
+ || (color == BLACK && q->black_strength[ii] == 0))
return; /* Match failed. */
}
}
@@ -823,10 +825,11 @@ influence_callback(int m, int n, int col
/* Increase strength if we're computing escape influence. */
if (q == &escape_influence && (pattern->class & CLASS_e))
- add_influence_source(pos, this_color,
- 20 * pattern->value, 1.5, q);
+ add_influence_source(pos, this_color, GG_ONE * 20 * pattern->value,
+ GG_ONE / 1.5, q);
else
- add_influence_source(pos, this_color, pattern->value, 1.5, q);
+ add_influence_source(pos, this_color, GG_ONE * pattern->value,
+ GG_ONE / 1.5, q);
DEBUG(DEBUG_INFLUENCE,
" low intensity influence source at %1m, strength %f, color %C\n",
@@ -838,8 +841,8 @@ influence_callback(int m, int n, int col
* pattern defined strength at *.
*/
if (pattern->class & CLASS_E) {
- add_influence_source(pos, color,
- pattern->value, DEFAULT_ATTENUATION, q);
+ add_influence_source(pos, color, pattern->value * GG_ONE,
+ DEFAULT_ATTENUATION, q);
DEBUG(DEBUG_INFLUENCE,
" extra %C source at %1m, strength %f\n", color,
pos, pattern->value);
@@ -871,28 +874,31 @@ influence_callback(int m, int n, int col
color_to_string(OTHER_COLOR(blocking_color)), ii);
if (pattern->patn[k].att == ATT_comma) {
if (blocking_color == WHITE)
- q->black_permeability[ii] = 0.0;
+ q->black_permeability[ii] = 0;
else
- q->white_permeability[ii] = 0.0;
+ q->white_permeability[ii] = 0;
}
/* Weak barrier at !-marked points. */
else {
- if (blocking_color == WHITE)
- q->black_permeability[ii] *= 0.7;
- else
- q->white_permeability[ii] *= 0.7;
-
+ if (blocking_color == WHITE) {
+ q->black_permeability[ii] *= 7;
+ q->black_permeability[ii] /= 10;
+ }
+ else {
+ q->white_permeability[ii] *= 7;
+ q->white_permeability[ii] /= 10;
+ }
}
}
/* Low intensity influence source for the color in turn to move. */
if (pattern->class & CLASS_B) {
if (q->is_territorial_influence)
- enter_intrusion_source(POS(m, n), ii, pattern->value,
+ enter_intrusion_source(POS(m, n), ii, GG_ONE * pattern->value,
TERR_DEFAULT_ATTENUATION, q);
else
- add_influence_source(ii, color,
- pattern->value, DEFAULT_ATTENUATION, q);
+ add_influence_source(ii, color, GG_ONE * pattern->value,
+ DEFAULT_ATTENUATION, q);
DEBUG(DEBUG_INFLUENCE, " intrusion at %1m\n", ii);
}
}
@@ -962,7 +968,7 @@ followup_influence_callback(int m, int n
ll, m, n);
/* Low intensity influence source for the color in turn to move. */
- enter_intrusion_source(POS(m, n), ii, pattern->value,
+ enter_intrusion_source(POS(m, n), ii, (int) pattern->value * GG_ONE,
TERR_DEFAULT_ATTENUATION, q);
DEBUG(DEBUG_INFLUENCE, " followup for %1m: intrusion at %1m\n",
POS(m, n), ii);
@@ -1010,11 +1016,15 @@ find_influence_patterns(struct influence
int d = delta[k];
if (ON_BOARD(ii + d) && q->p[ii + d] == EMPTY) {
/* Reduce less diagonally. */
- float reduction = (k < 4) ? 0.25 : 0.65;
- if (q->p[ii] == BLACK)
+ int reduction = (k < 4) ? (0.25 * GG_ONE) : (0.65 * GG_ONE);
+ if (q->p[ii] == BLACK) {
q->white_permeability[ii + d] *= reduction;
- else
+ q->white_permeability[ii + d] /= GG_ONE;
+ }
+ else {
q->black_permeability[ii + d] *= reduction;
+ q->black_permeability[ii + d] /= GG_ONE;
+ }
}
}
}
@@ -1050,8 +1060,8 @@ compute_influence(struct influence_data
for (j = 0; j < board_size; j++)
if (no_influence[i][j]) {
q->p[i][j] = EMPTY;
- q->white_strength[i][j] = 0.0;
- q->black_strength[i][j] = 0.0;
+ q->white_strength[i][j] = 0;
+ q->black_strength[i][j] = 0;
q->white_permeability[i][j] = 1.0;
q->black_permeability[i][j] = 1.0;
}
@@ -1067,9 +1077,9 @@ compute_influence(struct influence_data
for (ii = BOARDMIN; ii < BOARDMAX; ii++)
if (ON_BOARD(ii)) {
- if (q->white_strength[ii] > 0.0)
+ if (q->white_strength[ii] > 0)
accumulate_influence(q, ii, WHITE);
- if (q->black_strength[ii] > 0.0)
+ if (q->black_strength[ii] > 0)
accumulate_influence(q, ii, BLACK);
}
@@ -1096,16 +1106,16 @@ compute_influence(struct influence_data
static int
whose_territory(struct influence_data *q, int pos)
{
- float bi = q->black_influence[pos];
- float wi = q->white_influence[pos];
+ int bi = q->black_influence[pos];
+ int wi = q->white_influence[pos];
float terr = q->territory_value[pos];
ASSERT_ON_BOARD1(pos);
- if (bi > 0.0 && wi == 0.0 && terr < -0.95)
+ if (bi > 0 && wi == 0 && terr < -0.95)
return BLACK;
- if (wi > 0.0 && bi == 0.0 && terr > 0.95)
+ if (wi > 0 && bi == 0 && terr > 0.95)
return WHITE;
return EMPTY;
@@ -1118,17 +1128,17 @@ whose_territory(struct influence_data *q
static int
whose_moyo(struct influence_data *q, int pos)
{
- float bi = q->black_influence[pos];
- float wi = q->white_influence[pos];
+ int bi = q->black_influence[pos];
+ int wi = q->white_influence[pos];
int territory_color = whose_territory(q, pos);
if (territory_color != EMPTY)
return territory_color;
- if (bi > 7.0 * wi && bi > 5.0 && wi < 10.0)
+ if (bi > 7 * wi && bi > 5 * GG_ONE && wi < 10 * GG_ONE)
return BLACK;
- if (wi > 7.0 * bi && wi > 5.0 && bi < 10.0)
+ if (wi > 7 * bi && wi > 5 * GG_ONE && bi < 10 * GG_ONE)
return WHITE;
return EMPTY;
@@ -1147,8 +1157,8 @@ whose_moyo(struct influence_data *q, int
static int
whose_moyo_restricted(struct influence_data *q, int pos)
{
- float bi = q->black_influence[pos];
- float wi = q->white_influence[pos];
+ int bi = q->black_influence[pos];
+ int wi = q->white_influence[pos];
int color;
int territory_color = whose_territory(q, pos);
@@ -1160,9 +1170,9 @@ whose_moyo_restricted(struct influence_d
/* default */
if (territory_color != EMPTY)
color = territory_color;
- else if (bi > 10.0 * wi && bi > 10.0 && wi < 10.0)
+ else if (bi > 10 * wi && bi > 10 * GG_ONE && wi < 10 * GG_ONE)
color = BLACK;
- else if (wi > 10.0 * bi && wi > 10.0 && bi < 10.0)
+ else if (wi > 10 * bi && wi > 10 * GG_ONE && bi < 10 * GG_ONE)
color = WHITE;
else
color = EMPTY;
@@ -1185,17 +1195,17 @@ whose_moyo_restricted(struct influence_d
static int
whose_area(struct influence_data *q, int pos)
{
- float bi = q->black_influence[pos];
- float wi = q->white_influence[pos];
+ int bi = q->black_influence[pos];
+ int wi = q->white_influence[pos];
int moyo_color = whose_moyo(q, pos);
if (moyo_color != EMPTY)
return moyo_color;
- if (bi > 3.0 * wi && bi > 1.0 && wi < 40.0)
+ if (bi > 3 * wi && bi > 1 * GG_ONE && wi < 40 * GG_ONE)
return BLACK;
- if (wi > 3.0 * bi && wi > 1.0 && bi < 40.0)
+ if (wi > 3 * bi && wi > 1 * GG_ONE && bi < 40 * GG_ONE)
return WHITE;
return EMPTY;
@@ -1224,7 +1234,7 @@ struct interpolation_data min_infl_for_t
* ( influence of stronger color / min_infl_for_territory(intersection))
*/
struct interpolation_data territory_correction =
- { 5, (float) 0.0, 1.0, {0.0, 0.25, 0.45, 0.65, 0.85, 1.0}};
+ { 5, 0.0, 1.0, {0.0, 0.25, 0.45, 0.65, 0.85, 1.0}};
static void
value_territory(struct influence_data *q, int pos, int color)
@@ -1244,8 +1254,8 @@ value_territory(struct influence_data *q
if (q->p[ii] == EMPTY) {
float diff = 0.0;
if (q->white_influence[ii] + q->black_influence[ii] > 0)
- diff = (q->white_influence[ii] - q->black_influence[ii])
- /(q->white_influence[ii] + q->black_influence[ii]);
+ diff = ((float) (q->white_influence[ii] - q->black_influence[ii]))
+ /(float) (q->white_influence[ii] + q->black_influence[ii]);
first_guess[ii] = diff * diff * diff;
/* If both side have small influence, we have to reduce this value.
@@ -1259,7 +1269,8 @@ value_territory(struct influence_data *q
else
dist_j = gg_min(4, dist_j);
central = (float) 2 * gg_min(dist_i, dist_j) + dist_i + dist_j;
- ratio = gg_max(q->black_influence[ii], q->white_influence[ii])
+ ratio = ((float) gg_max(q->black_influence[ii], q->white_influence[ii])
+ / GG_ONE)
/ gg_interpolate(&min_infl_for_territory, central);
first_guess[ii] *= gg_interpolate(&territory_correction, ratio);
@@ -1296,10 +1307,12 @@ value_territory(struct influence_data *q
/* White territory. */
if (q->p[ii + delta[k]] != WHITE) {
float neighbor_val =
- q->black_permeability[ii + delta[k]]
- * first_guess[ii + delta[k]]
- + (1.0 - q->black_permeability[ii + delta[k]])
- * first_guess[ii];
+ (q->black_permeability[ii + delta[k]]
+ * first_guess[ii + delta[k]])
+ / GG_ONE
+ + ((GG_ONE - q->black_permeability[ii + delta[k]])
+ * first_guess[ii])
+ / GG_ONE;
q->territory_value[ii]
= gg_max(0, gg_min(q->territory_value[ii], neighbor_val));
}
@@ -1308,10 +1321,12 @@ value_territory(struct influence_data *q
/* Black territory. */
if (q->p[ii + delta[k]] != BLACK) {
float neighbor_val =
- q->white_permeability[ii + delta[k]]
- * first_guess[ii + delta[k]]
- + (1 - q->white_permeability[ii + delta[k]])
- * first_guess[ii];
+ (q->white_permeability[ii + delta[k]]
+ * first_guess[ii + delta[k]])
+ / GG_ONE
+ + (GG_ONE - q->white_permeability[ii + delta[k]])
+ * first_guess[ii]
+ / GG_ONE;
q->territory_value[ii]
= gg_min(0, gg_max(q->territory_value[ii], neighbor_val));
}
@@ -1966,8 +1981,8 @@ debug_influence_move(int i, int j)
/* Copy and encode influence data. */
static void
retrieve_influence(struct influence_data *q,
- float white_influence[BOARDMAX],
- float black_influence[BOARDMAX],
+ int white_influence[BOARDMAX],
+ int black_influence[BOARDMAX],
int influence_regions[BOARDMAX])
{
int ii;
@@ -1997,8 +2012,8 @@ retrieve_influence(struct influence_data
*/
void
get_initial_influence(int color, int dragons_known,
- float white_influence[BOARDMAX],
- float black_influence[BOARDMAX],
+ int white_influence[BOARDMAX],
+ int black_influence[BOARDMAX],
int influence_regions[BOARDMAX])
{
compute_initial_influence(color, dragons_known);
@@ -2011,8 +2026,8 @@ get_initial_influence(int color, int dra
void
get_move_influence(int move, int color,
char saved_stones[BOARDMAX],
- float white_influence[BOARDMAX],
- float black_influence[BOARDMAX],
+ int white_influence[BOARDMAX],
+ int black_influence[BOARDMAX],
int influence_regions[BOARDMAX])
{
compute_move_influence(move, color, saved_stones);
@@ -2105,29 +2120,41 @@ print_influence(struct influence_data *q
}
}
+
+char black_stone[8][10] = { "X", " X", " X", " X ", " X ", " X ",
+ " X ", " X "};
+char white_stone[8][10] = { "O", " O", " O", " O ", " O ", " O ",
+ " O ", " O "};
+
/* Print the numerical territory valuation. */
static void
print_influence_territory(struct influence_data *q, const char *info_string)
{
+ int ii;
+
fprintf(stderr, info_string);
- print_numeric_influence(q, q->territory_value, "%5.2f", 5, 0);
+ for (ii = BOARDMIN; ii < BOARDMAX; ii++)
+ if (ON_BOARD(ii)) {
+ if (q->p[ii] == WHITE)
+ fprintf(stderr, white_stone[5]);
+ else if (q->p[ii] == BLACK)
+ fprintf(stderr, black_stone[5]);
+ else {
+ fprintf(stderr, "%5.2f ", q->territory_value[ii]);
+ }
+ }
+ else
+ fprintf(stderr, "\n");
+ fprintf(stderr, "\n\n");
}
-
-char black_stone[8][10] = { "X", " X", " X", " X ", " X ", " X ",
- " X ", " X "};
-char white_stone[8][10] = { "O", " O", " O", " O ", " O ", " O ",
- " O ", " O "};
/* Print numeric influence values.
* If draw_stones is not zero, then it denotes the lenght (in characters)
* of the numeric output fields.
*/
static void
-print_numeric_influence(struct influence_data *q,
- float values[BOARDMAX],
- const char *format,
- int draw_stones,
- int mark_epsilon)
+print_numeric_influence(struct influence_data *q, int values[BOARDMAX],
+ const char *format, int draw_stones, int mark_epsilon)
{
int i, j;
for (i = 0; i < board_size; i++) {
@@ -2138,10 +2165,10 @@ print_numeric_influence(struct influence
else if (draw_stones && q->p[ii] == BLACK)
fprintf(stderr, black_stone[draw_stones]);
else {
- if (mark_epsilon && values[ii] > 0.0 && values[ii] < 1.0)
+ if (mark_epsilon && values[ii] > 0 && values[ii] < GG_ONE)
fprintf(stderr, "eps");
else
- fprintf(stderr, format, values[ii]);
+ fprintf(stderr, format, ((float) values[ii]) / GG_ONE);
fprintf(stderr, " ");
}
}
Index: engine/influence.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.h,v
retrieving revision 1.13
diff -u -p -r1.13 influence.h
--- engine/influence.h 5 Nov 2002 12:54:23 -0000 1.13
+++ engine/influence.h 28 Nov 2002 23:16:25 -0000
@@ -26,25 +26,33 @@
#include "liberty.h"
+/* We use fixed point arithmetics for all internal influence computations.
+ * Everything is stored as (int) GG_ONE * a (with GG_ONE defined in
+ * liberty.h).
+ * [This refers to influence strength, attenuations, permeabilities.
+ * Pattern values (in float) are converted to fixed point as soon as
+ * possible. Territory values are computed via and exported as (float).]
+ */
+
/* Default attenuation coefficient.
* The "TERR_.."-values are used in the influence computations used
* for territory evaluation. (initial_influence with dragons_known,
* move_influence)
*/
-#define DEFAULT_ATTENUATION 3.0
-#define TERR_DEFAULT_ATTENUATION 2.4
+#define DEFAULT_ATTENUATION ((int) (1.0 * GG_ONE / 3.0))
+#define TERR_DEFAULT_ATTENUATION ((int) (1.0 * GG_ONE / 2.4))
/* Extra damping coefficient for spreading influence diagonally. */
-#define DIAGONAL_DAMPING 2.0
-#define TERR_DIAGONAL_DAMPING 1.7
+#define DIAGONAL_DAMPING ((int) (1.0 * GG_ONE / 2.0))
+#define TERR_DIAGONAL_DAMPING ((int) (1.0 * GG_ONE / 1.7))
/* Default strength of the influence from a stone. May be lowered if
* it is unsafe.
*/
-#define DEFAULT_STRENGTH 100.0
+#define DEFAULT_STRENGTH 100 * GG_ONE
/* Smallest amount of influence that we care about distributing. */
-#define INFLUENCE_CUTOFF 0.02
+#define INFLUENCE_CUTOFF (GG_ONE / 50)
/* Value in delta_territory_cache indicating that the value has not
* been computed. Arbitrary but unattainable.
@@ -79,21 +87,21 @@ struct intrusion_data
{
int source_pos; /* Stone from which intrusion originates.*/
int strength_pos; /* Position of the intrusion influence soure. */
- float strength;
- float attenuation;
+ int strength;
+ int attenuation;
};
struct influence_data
{
- float white_influence[BOARDMAX]; /* Accumulated influence. */
- float black_influence[BOARDMAX]; /* Accumulated influence. */
+ int white_influence[BOARDMAX]; /* Accumulated influence. */
+ int black_influence[BOARDMAX]; /* Accumulated influence. */
int p[BOARDMAX]; /* Working copy of board array. */
- float white_strength[BOARDMAX]; /* Strength of influence source. */
- float black_strength[BOARDMAX]; /* Strength of influence source. */
- float white_attenuation[BOARDMAX];
- float black_attenuation[BOARDMAX];
- float white_permeability[BOARDMAX];
- float black_permeability[BOARDMAX];
+ int white_strength[BOARDMAX]; /* Strength of influence source. */
+ int black_strength[BOARDMAX]; /* Strength of influence source. */
+ int white_attenuation[BOARDMAX];
+ int black_attenuation[BOARDMAX];
+ int white_permeability[BOARDMAX];
+ int black_permeability[BOARDMAX];
int territory_segmentation[BOARDMAX];
int moyo_segmentation[BOARDMAX];
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.136
diff -u -p -r1.136 liberty.h
--- engine/liberty.h 21 Nov 2002 00:25:10 -0000 1.136
+++ engine/liberty.h 28 Nov 2002 23:16:31 -0000
@@ -571,6 +571,9 @@ int somewhere(int color, int check_alive
#define INFLUENCE_SAVED_STONE 1
#define INFLUENCE_CAPTURED_STONE 2
+/* This is used for fixed-point integer arithmetic in influence.c. */
+#define GG_ONE (1 << 12)
+
/* These values are used to communicate the status of stones when analyzing
* a move for potentially being a blunder.
*/
@@ -614,12 +617,12 @@ float estimate_score(float *upper, float
void print_initial_influence(int color, int dragons_known);
void print_move_influence(int pos, int color, char saved_stones[BOARDMAX]);
void get_initial_influence(int color, int dragons_known,
- float white_influence[BOARDMAX],
- float black_influence[BOARDMAX],
+ int white_influence[BOARDMAX],
+ int black_influence[BOARDMAX],
int influence_regions[BOARDMAX]);
void get_move_influence(int move, int color, char saved_stones[BOARDMAX],
- float white_influence[BOARDMAX],
- float black_influence[BOARDMAX],
+ int white_influence[BOARDMAX],
+ int black_influence[BOARDMAX],
int influence_regions[BOARDMAX]);
void compute_escape_influence(char goal[BOARDMAX], int color,
char escape_value[BOARDMAX], int dragons_known);
- [gnugo-devel] use fixed point arithmetics in accumulat_influence,
Arend Bayer <=