/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 by the Free Software Foundation. *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation - version 3 or *
* (at your option) any later version. *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License in file COPYING for more details. *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
static void add_influence_source(int pos
, int color
, float strength
,
struct influence_data
*q
);
static void print_influence(const struct influence_data
*q
,
const char *info_string
);
static void print_numeric_influence(const struct influence_data
*q
,
const float values
[BOARDMAX
],
const char *format
, int width
,
int draw_stones
, int mark_epsilon
);
static void print_influence_areas(const struct influence_data
*q
);
static void value_territory(struct influence_data
*q
);
static void enter_intrusion_source(int source_pos
, int strength_pos
,
float strength
, float attenuation
,
struct influence_data
*q
);
static void add_marked_intrusions(struct influence_data
*q
);
/* Influence computed for the initial position, i.e. before making
struct influence_data initial_black_influence
;
struct influence_data initial_white_influence
;
/* Influence computed after some move has been made. */
struct influence_data move_influence
;
struct influence_data followup_influence
;
/* Influence used for estimation of escape potential. */
static struct influence_data escape_influence
;
/* Pointer to influence data used during pattern matching. */
static struct influence_data
*current_influence
= NULL
;
/* Thresholds values used in the whose_moyo() functions */
static struct moyo_determination_data moyo_data
;
static struct moyo_determination_data moyo_restricted_data
;
/* Thresholds value used in the whose_territory() function */
static float territory_determination_value
;
/* This curve determines how much influence is needed at least to claim
* an intersection as territory, in dependence of the "center value".
* (In the center, more effort is needed to get territory!)
* The center value is at the moment defined as follows:
* If d1, d2 are the distance to vertical and horizontal border, resp.,
* central = 3 * d1 + min(d2, 4)
* So this is mainly a function of the distance to the border; the
* distance to the second-nearest border gives a small correction of at
* most 4. This distinguishes edge and corner positions.
* The values for intersections close to a corner or to the edge have
* to be consistent such that standard corner enclosure etc. are
* sufficient to claim territory. The center values are more arbitrary
static struct interpolation_data min_infl_for_territory
=
{ 6, 0.0, 24.0, { 6.0, 15.0, 26.0, 36.0, 45.0, 50.0, 55.0 }};
/* Determines the territory correction factor in dependence of the ratio
* ( influence of stronger color / min_infl_for_territory(intersection))
static struct interpolation_data territory_correction
=
{ 5, (float) 0.0, 1.0, {0.0, 0.25, 0.45, 0.65, 0.85, 1.0}};
/* If set, print influence map when computing this move. Purely for
static int debug_influence
= NO_MOVE
;
/* Assigns an id to all influence computations for reference in the
static int influence_id
= 0;
/* This is the core of the influence function. Given the coordinates
* and color of an influence source, it radiates the influence
* outwards until it hits a barrier or the strength of the influence
* falls under a certain threshold.
* The radiation is performed by a breadth first propagation,
* implemented by means of an internal queue.
* Since this function has turned out be one of the bottlenecks, loop
* unrolling makes a noticeable performance difference. It does,
* however, make the code much harder to read and maintain. Therefore
* we include both the original and the unrolled versions.
#define EXPLICIT_LOOP_UNROLLING 1
#if EXPLICIT_LOOP_UNROLLING
/* In addition to the parameters, this macro expects
* m,n = original source of influence
* ii = point influence is being spread from
* current_strength combines strength and damping factor
* b is 1/(square of distance from m,n to i,j) ; or halved
* arg is i + arg_di ; arg_j is j + arg_dj
* arg_d is 1 for diagonal movement
#define code1(arg_di, arg_dj, arg, arg_d) do { \
&& ((arg_di)*(delta_i) + (arg_dj)*(delta_j) > 0 \
|| queue_start == 1)) { \
float permeability = permeability_array[ii]; \
permeability *= gg_max(permeability_array[ii + DELTA(arg_di, 0)], \
permeability_array[ii + DELTA(0, arg_dj)]); \
if (permeability == 0.0) \
contribution = current_strength * permeability; \
if (queue_start != 1) { \
int a = (arg_di)*(delta_i) + (arg_dj)*(delta_j); \
contribution *= (a*a) * b; /* contribution *= cos(phi) */ \
if (contribution <= INFLUENCE_CUTOFF) \
if (working[arg] == 0.0) { \
q->queue[queue_end] = (arg); \
working[arg] += contribution; \
accumulate_influence(struct influence_data
*q
, int pos
, int color
)
#if !EXPLICIT_LOOP_UNROLLING
float inv_diagonal_damping
;
float *permeability_array
;
/* Clear the queue. Entry 0 is implicitly (m, n). */
static float working
[BOARDMAX
];
static int working_area_initialized
= 0;
if (!working_area_initialized
) {
for (ii
= 0; ii
< BOARDMAX
; ii
++)
working_area_initialized
= 1;
gprintf("Accumulating influence for %s at %m\n",
color_to_string(color
), m
, n
);
/* Attenuation only depends on the influence origin. */
inv_attenuation
= 1.0 / q
->white_attenuation
[pos
];
inv_attenuation
= 1.0 / q
->black_attenuation
[pos
];
if (q
->is_territorial_influence
)
inv_diagonal_damping
= 1.0 / TERR_DIAGONAL_DAMPING
;
inv_diagonal_damping
= 1.0 / DIAGONAL_DAMPING
;
permeability_array
= q
->white_permeability
;
permeability_array
= q
->black_permeability
;
/* We put the original source into slot 0. */
working
[pos
] = q
->white_strength
[pos
];
working
[pos
] = q
->black_strength
[pos
];
/* Spread influence until the stack is empty. */
while (queue_start
< queue_end
) {
ii
= q
->queue
[queue_start
];
if (permeability_array
[ii
] == 0.0)
gprintf("Picked %1m from queue. w=%f start=%d end=%d\n",
ii
, working
[ii
], queue_start
, queue_end
);
b
= 1.0 / ((delta_i
)*(delta_i
) + (delta_j
)*(delta_j
));
current_strength
= working
[ii
] * inv_attenuation
;
#if !EXPLICIT_LOOP_UNROLLING
/* Try to spread influence in each of the eight directions. */
for (d
= 0; d
< 8; d
++) {
/* Verify that (ii + d_ii) is
* 3. Directed outwards. For the origin all directions are outwards.
&& (di
*(delta_i
) + dj
*(delta_j
) > 0
float permeability
= permeability_array
[ii
];
/* Now compute the damping of the influence.
* First we have the permeability at the point we are
* spreading from. For diagonal movement we also take the
* permeability of the vertices we are "passing by" into
if (d
> 3) { /* diagonal movement */
permeability
*= gg_max(permeability_array
[ii
+ DELTA(di
, 0)],
permeability_array
[ii
+ DELTA(0, dj
)]);
inv_damping
= inv_diagonal_damping
;
contribution
= permeability
* current_strength
* inv_damping
;
/* Finally direction dependent damping. */
int a
= di
*(delta_i
) + dj
*(delta_j
);
contribution
*= (a
*a
) * b
* dfactor
;
/* Stop spreading influence if the contribution becomes too low. */
if (contribution
<= INFLUENCE_CUTOFF
)
/* If no influence here before, add the point to the queue for
gprintf(" Spreading %s influence from %1m to %1m, d=%d\n",
color_to_string(color
), ii
, ii
+ d_ii
, d
);
if (working
[ii
+ d_ii
] == 0.0) {
q
->queue
[queue_end
] = ii
+ d_ii
;
working
[ii
+ d_ii
] += contribution
;
if (ON_BOARD(ii
+ delta
[0]))
code1(deltai
[0], deltaj
[0], ii
+ delta
[0], 0);
if (ON_BOARD(ii
+ delta
[1]))
code1(deltai
[1], deltaj
[1], ii
+ delta
[1], 0);
if (ON_BOARD(ii
+ delta
[2]))
code1(deltai
[2], deltaj
[2], ii
+ delta
[2], 0);
if (ON_BOARD(ii
+ delta
[3]))
code1(deltai
[3], deltaj
[3], ii
+ delta
[3], 0);
/* Update factors for diagonal movement. */
current_strength
*= inv_diagonal_damping
;
if (ON_BOARD(ii
+ delta
[4]))
code1(deltai
[4], deltaj
[4], ii
+ delta
[4], 1);
if (ON_BOARD(ii
+ delta
[5]))
code1(deltai
[5], deltaj
[5], ii
+ delta
[5], 1);
if (ON_BOARD(ii
+ delta
[6]))
code1(deltai
[6], deltaj
[6], ii
+ delta
[6], 1);
if (ON_BOARD(ii
+ delta
[7]))
code1(deltai
[7], deltaj
[7], ii
+ delta
[7], 1);
/* Add the values in the working area to the accumulated influence
* and simultaneously reset the working area. We know that all
* influenced points were stored in the queue, so we just traverse
for (k
= 0; k
< queue_end
; k
++) {
if (working
[ii
] > 1.01 * INFLUENCE_CUTOFF
|| q
->white_influence
[ii
] == 0.0)
q
->white_influence
[ii
] += working
[ii
];
if (working
[ii
] > 1.01 * INFLUENCE_CUTOFF
|| q
->black_influence
[ii
] == 0.0)
q
->black_influence
[ii
] += working
[ii
];
/* Initialize the influence_data structure. */
init_influence(struct influence_data
*q
,
const signed char safe_stones
[BOARDMAX
],
const float strength
[BOARDMAX
])
/* Initialisation of some global positional values, based on
if ((board_size
!= 19) || (movenum
<= 2) || ((movenum
/ 2) % 2))
cosmic_importance
= 1.0 - (movenum
/ 150.0)*(movenum
/ 150.0);
cosmic_importance
= gg_max(0.0, cosmic_importance
);
moyo_data
.influence_balance
= t
* 15.0 + (1.0-t
) * 5.0;
moyo_data
.my_influence_minimum
= t
* 5.0 + (1.0-t
) * 5.0;
moyo_data
.opp_influence_maximum
= t
* 30.0 + (1.0-t
) * 30.0;
/* we use the same values for moyo and moyo_restricted */
moyo_restricted_data
= moyo_data
;
territory_determination_value
= t
* 0.95 + (1.0-t
) * 0.95;
min_infl_for_territory
.values
[0] = t
* 6.0 + (1.0-t
) * 10.0;
min_infl_for_territory
.values
[1] = t
* 10.0 + (1.0-t
) * 15.0;
min_infl_for_territory
.values
[2] = t
* 20.0 + (1.0-t
) * 15.0;
min_infl_for_territory
.values
[3] = t
* 20.0 + (1.0-t
) * 20.0;
min_infl_for_territory
.values
[4] = t
* 20.0 + (1.0-t
) * 20.0;
min_infl_for_territory
.values
[5] = t
* 15.0 + (1.0-t
) * 15.0;
min_infl_for_territory
.values
[6] = t
* 10.0 + (1.0-t
) * 15.0;
moyo_data
.influence_balance
= 7.0;
moyo_data
.my_influence_minimum
= 5.0;
moyo_data
.opp_influence_maximum
= 10.0;
moyo_restricted_data
.influence_balance
= 10.0;
moyo_restricted_data
.my_influence_minimum
= 10.0;
moyo_restricted_data
.opp_influence_maximum
= 10.0;
territory_determination_value
= 0.95;
min_infl_for_territory
.values
[0] = 6.0;
min_infl_for_territory
.values
[1] = 15.0;
min_infl_for_territory
.values
[2] = 26.0;
min_infl_for_territory
.values
[3] = 36.0;
min_infl_for_territory
.values
[4] = 45.0;
min_infl_for_territory
.values
[5] = 50.0;
min_infl_for_territory
.values
[6] = 55.0;
if (q
->is_territorial_influence
)
attenuation
= TERR_DEFAULT_ATTENUATION
;
attenuation
= 2 * DEFAULT_ATTENUATION
;
q
->intrusion_counter
= 0;
/* Remember this for later. */
memcpy(q
->safe
, safe_stones
, BOARDMAX
* sizeof(*safe_stones
));
q
->captured
= black_captured
- white_captured
;
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
q
->white_influence
[ii
] = 0.0;
q
->black_influence
[ii
] = 0.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
->non_territory
[ii
] = EMPTY
;
if (IS_STONE(board
[ii
])) {
q
->white_permeability
[ii
] = 0.0;
q
->black_permeability
[ii
] = 0.0;
if (board
[ii
] == WHITE
) {
q
->white_strength
[ii
] = strength
[ii
];
q
->white_strength
[ii
] = DEFAULT_STRENGTH
;
q
->black_permeability
[ii
] = 0.0;
q
->black_strength
[ii
] = strength
[ii
];
q
->black_strength
[ii
] = DEFAULT_STRENGTH
;
q
->white_permeability
[ii
] = 0.0;
/* Ideally, safe_stones[] should always be zero for empty
* intersections. This is currently, however, sometimes not true
* when an inessential worm gets captured. So we revise this
* in our private copy here.
/* Adds an influence source at position pos with prescribed strength
* and attenuation. color can be BLACK, WHITE or both. If there
* already exists an influence source of the respective color at pos
* that is stronger than the new one, we do nothing.
add_influence_source(int pos
, int color
, float strength
, float attenuation
,
struct influence_data
*q
)
if ((color
& WHITE
) && (q
->white_strength
[pos
] < strength
)) {
q
->white_strength
[pos
] = strength
;
q
->white_attenuation
[pos
] = attenuation
;
if ((color
& BLACK
) && (q
->black_strength
[pos
] < strength
)) {
q
->black_strength
[pos
] = strength
;
q
->black_attenuation
[pos
] = attenuation
;
/* Adds an intrusion as an entry in the list q->intrusions. */
enter_intrusion_source(int source_pos
, int strength_pos
,
float strength
, float attenuation
,
struct influence_data
*q
)
if (q
->intrusion_counter
>= MAX_INTRUSIONS
) {
DEBUG(DEBUG_INFLUENCE
, "intrusion list exhausted\n");
q
->intrusions
[q
->intrusion_counter
].source_pos
= source_pos
;
q
->intrusions
[q
->intrusion_counter
].strength_pos
= strength_pos
;
q
->intrusions
[q
->intrusion_counter
].strength
= strength
;
q
->intrusions
[q
->intrusion_counter
].attenuation
= attenuation
;
/* Comparison of intrusions datas, to sort them. */
compare_intrusions(const void *p1
, const void *p2
)
const struct intrusion_data
*intr1
= p1
;
const struct intrusion_data
*intr2
= p2
;
if (intr1
->source_pos
- intr2
->source_pos
!= 0)
return (intr1
->source_pos
- intr2
->source_pos
);
else if (intr1
->strength_pos
- intr2
->strength_pos
!= 0)
return (intr1
->strength_pos
- intr2
->strength_pos
);
else if (intr1
->strength
> intr2
->strength
)
/* It may happen that we have a low intensity influence source at a
* blocked intersection (due to an intrusion). This function resets the
reset_unblocked_blocks(struct influence_data
*q
)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (!q
->safe
[pos
] && q
->white_strength
[pos
] > 0.0
&& q
->white_permeability
[pos
] != 1.0) {
DEBUG(DEBUG_INFLUENCE
, " black block removed from %1m\n", pos
);
q
->white_permeability
[pos
] = 1.0;
if (!q
->safe
[pos
] && q
->black_strength
[pos
] > 0.0
&& q
->black_permeability
[pos
] != 1.0) {
DEBUG(DEBUG_INFLUENCE
, " white block removed from %1m\n", pos
);
q
->black_permeability
[pos
] = 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).
add_marked_intrusions(struct influence_data
*q
)
int color
= q
->color_to_move
;
gg_sort(q
->intrusions
, q
->intrusion_counter
, sizeof(q
->intrusions
[0]),
/* Go through all intrusion sources. */
for (i
= 0; i
< q
->intrusion_counter
; i
= j
) {
source_pos
= q
->intrusions
[i
].source_pos
;
/* "Anonymous" intrusios go in uncorrected. */
if (source_pos
== NO_MOVE
) {
add_influence_source(q
->intrusions
[i
].strength_pos
, color
,
q
->intrusions
[j
].strength
,
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
);
source_strength
= q
->black_strength
[source_pos
];
source_strength
= q
->white_strength
[source_pos
];
/* First loop: Determine correction factor. */
for (j
= i
; (j
< q
->intrusion_counter
)
&& (q
->intrusions
[j
].source_pos
== source_pos
); j
++) {
/* Of identical strength positions, only take strongest value. */
|| q
->intrusions
[j
].strength_pos
!= q
->intrusions
[j
-1].strength_pos
)
strength_sum
+= q
->intrusions
[j
].strength
;
if (q
== &followup_influence
)
allowed_strength
= source_strength
;
allowed_strength
= 0.6 * source_strength
;
if (strength_sum
> allowed_strength
)
correction
= (allowed_strength
/ strength_sum
);
/* Second loop: Add influence sources. */
for (j
= i
; (j
< q
->intrusion_counter
)
&& (q
->intrusions
[j
].source_pos
== source_pos
); j
++) {
/* Of identical strenght positions, only take strongest value. */
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
,
q
->intrusions
[j
].attenuation
, q
);
"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
);
/* Callback for the matched patterns in influence.db and barriers.db.
* The pattern classes used here are:
* A - Barrier pattern, where O plays first and X tries to block influence.
* D - Barrier pattern, where O plays first and O tries to block influence.
* B - Intrusion patterns, adding a low intensity influence source.
* E - Enhance patterns, FIXME: document this one!
* t - Non-territory patterns, marking vertices as not territory.
* I - Invasion patterns, adding a low intensity influence source.
* e - Escape bonus. Used together with I to increase the value substantially
* if escape influence is being computed.
* Classes A, D, and B are matched with color as O, and it is assumed
* that O is in turn to move. Classes E and I are matched with either
influence_callback(int anchor
, int color
, struct pattern
*pattern
, int ll
,
int pos
= AFFINE_TRANSFORM(pattern
->move_offset
, ll
, anchor
);
struct influence_data
*q
= data
;
/* We also ignore enhancement patterns in territorial influence. */
if ((pattern
->class & CLASS_E
) && q
->is_territorial_influence
)
/* Don't use invasion (I) patterns when scoring. */
if (doing_scoring
&& (pattern
->class & CLASS_I
))
/* Loop through pattern elements to see if an A or D pattern
* can possibly have any effect. If not we can skip evaluating
* constraint and/or helper.
if (pattern
->class & (CLASS_A
| CLASS_D
)) {
gg_assert(q
->is_territorial_influence
);
for (k
= 0; k
< pattern
->patlen
; ++k
) { /* match each point */
/* The order of elements is: All commas, all "!", then other. */
if (pattern
->patn
[k
].att
!= ATT_comma
&& pattern
->patn
[k
].att
!= ATT_not
)
ii
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
if (pattern
->class & CLASS_D
)
blocking_color
= OTHER_COLOR(color
);
if ((blocking_color
== WHITE
&& q
->black_permeability
[ii
] != 0.0)
|| (blocking_color
== BLACK
&& q
->white_permeability
[ii
] != 0.0)) {
/* Require that all O stones in the pattern have non-zero influence
* strength for patterns of type D, E, B, t, and all X stones have
* non-zero strength for patterns of type A and t.
* Patterns also having class s are an exception from this rule.
if ((pattern
->class & (CLASS_D
| CLASS_A
| CLASS_B
| CLASS_E
| CLASS_t
))
&& !(pattern
->class & CLASS_s
)) {
for (k
= 0; k
< pattern
->patlen
; ++k
) { /* match each point */
int ii
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
if (pattern
->patn
[k
].att
== ATT_O
) {
if ((pattern
->class & (CLASS_B
| CLASS_t
| CLASS_E
| CLASS_D
))
&& ((color
== WHITE
&& q
->white_strength
[ii
] == 0.0)
|| (color
== BLACK
&& q
->black_strength
[ii
] == 0.0)))
else if (pattern
->patn
[k
].att
== ATT_X
) {
if ((pattern
->class & (CLASS_A
| CLASS_t
))
&& ((color
== BLACK
&& q
->white_strength
[ii
] == 0.0)
|| (color
== WHITE
&& q
->black_strength
[ii
] == 0.0)))
return; /* Match failed. */
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
if ((pattern
->autohelper_flag
& HAVE_CONSTRAINT
)
&& !pattern
->autohelper(ll
, pos
, color
, 0))
DEBUG(DEBUG_INFLUENCE
, "influence pattern '%s'+%d matched at %1m\n",
pattern
->name
, ll
, anchor
);
/* For t patterns, everything happens in the action. */
if ((pattern
->class & CLASS_t
)
&& (pattern
->autohelper_flag
& HAVE_ACTION
)) {
pattern
->autohelper(ll
, pos
, color
, INFLUENCE_CALLBACK
);
/* For I patterns, add a low intensity, both colored, influence
if (pattern
->class & CLASS_I
) {
if (q
->color_to_move
== EMPTY
|| (pattern
->class & CLASS_s
))
this_color
= BLACK
| WHITE
;
else if (q
->color_to_move
!= color
)
this_color
= q
->color_to_move
;
float t
= 0.15 + (1.0 - cosmic_importance
);
strength
= t
* pattern
->value
;
strength
= pattern
->value
;
/* Increase strength if we're computing escape influence. */
if (!q
->is_territorial_influence
&& (pattern
->class & CLASS_e
))
add_influence_source(pos
, this_color
, 20 * strength
, attenuation
, q
);
add_influence_source(pos
, this_color
, strength
, attenuation
, q
);
" low intensity influence source at %1m, strength %f, color %C\n",
pos
, strength
, this_color
);
/* For E patterns, add a new influence source of the same color and
* pattern defined strength at *.
if (pattern
->class & CLASS_E
) {
add_influence_source(pos
, color
, pattern
->value
, DEFAULT_ATTENUATION
, q
);
" extra %C source at %1m, strength %f\n", color
,
/* For B patterns add intrusions sources at "!" points. */
if (pattern
->class & CLASS_B
) {
float t
= 0.15 + (1.0 - cosmic_importance
);
strength
= t
* pattern
->value
;
strength
= pattern
->value
;
for (k
= 0; k
< pattern
->patlen
; ++k
) /* match each point */
if (pattern
->patn
[k
].att
== ATT_not
) {
/* transform pattern real coordinate */
int ii
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
/* Low intensity influence source for the color in turn to move. */
if (q
->is_territorial_influence
)
enter_intrusion_source(anchor
, ii
, strength
,
TERR_DEFAULT_ATTENUATION
, q
);
add_influence_source(ii
, color
, strength
, DEFAULT_ATTENUATION
, q
);
DEBUG(DEBUG_INFLUENCE
, " intrusion at %1m\n", ii
);
gg_assert(pattern
->class & (CLASS_D
| CLASS_A
));
/* For A, D patterns, add blocks for all "," or "!" points. */
for (k
= 0; k
< pattern
->patlen
; ++k
) { /* match each point */
if (pattern
->patn
[k
].att
== ATT_comma
|| pattern
->patn
[k
].att
== ATT_not
) {
/* transform pattern real coordinate */
int ii
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
if (pattern
->class & CLASS_D
)
blocking_color
= OTHER_COLOR(color
);
DEBUG(DEBUG_INFLUENCE
, " barrier for %s influence at %1m\n",
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
->white_permeability
[ii
] = 0.0;
/* Weak barrier at !-marked points. */
if (blocking_color
== WHITE
)
q
->black_permeability
[ii
] *= 0.7;
q
->white_permeability
[ii
] *= 0.7;
/* Callback for matched barriers patterns in followup influence.
* This adds an intrusion source for all B patterns in barriers.db for
* the color that has made a move if all the following conditions are
* - the anchor ("Q") is adjacent (directly or diagonally) to a "saved stone"
* (this is ensured by matchpat before calling back here)
* - at least one of the O stones in the pattern is a saved stone.
* - the usual pattern constraint ("; oplay_attack_either(...)") is fulfilled
* - the pattern action (typically ">return (!xplay_attack(...))") returns
* true if called with parameter action = FOLLOWUP_INFLUENCE_CALLBACK.
* "Saved stones" are: the move played + tactically rescued stones + stones
* in a critcal dragon brought to life by this move
followup_influence_callback(int anchor
, int color
, struct pattern
*pattern
,
struct influence_data
*q
= data
;
/* We use only B patterns in followup influence. */
if (!(pattern
->class & CLASS_B
))
t
= AFFINE_TRANSFORM(pattern
->move_offset
, ll
, anchor
);
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
if (pattern
->autohelper_flag
& HAVE_CONSTRAINT
&& !pattern
->autohelper(ll
, t
, color
, 0))
/* Actions in B patterns are used as followup specific constraints. */
if ((pattern
->autohelper_flag
& HAVE_ACTION
)
&& !pattern
->autohelper(ll
, t
, color
, FOLLOWUP_INFLUENCE_CALLBACK
))
DEBUG(DEBUG_INFLUENCE
, "influence pattern '%s'+%d matched at %1m\n",
pattern
->name
, ll
, anchor
);
for (k
= 0; k
< pattern
->patlen
; ++k
) /* match each point */
if (pattern
->patn
[k
].att
== ATT_not
) {
/* transform pattern real coordinate */
int ii
= AFFINE_TRANSFORM(pattern
->patn
[k
].offset
, ll
, anchor
);
/* Low intensity influence source for the color in turn to move. */
enter_intrusion_source(anchor
, ii
, pattern
->value
,
TERR_DEFAULT_ATTENUATION
, q
);
DEBUG(DEBUG_INFLUENCE
, " followup for %1m: intrusion at %1m\n",
/* Called from actions for t patterns. Marks (pos) as not being
influence_mark_non_territory(int pos
, int color
)
DEBUG(DEBUG_INFLUENCE
, " non-territory for %C at %1m\n", color
, pos
);
current_influence
->non_territory
[pos
] |= color
;
/* Erases all territory for color at (pos), and all directly neighboring
influence_erase_territory(struct influence_data
*q
, int pos
, int color
)
ASSERT1((color
== WHITE
&& q
->territory_value
[pos
] >= 0.0)
|| (color
== BLACK
&& q
->territory_value
[pos
] <= 0.0), pos
);
q
->territory_value
[pos
] = 0.0;
influence_mark_non_territory(pos
, color
);
for (k
= 0; k
< 4; k
++) {
if (ON_BOARD(pos
+ delta
[k
])) {
q
->territory_value
[pos
+ delta
[k
]] = 0.0;
influence_mark_non_territory(pos
+ delta
[k
], color
);
/* Match the patterns in influence.db and barriers.db in order to add:
* - extra influence sources at possible invasion and intrusion points, and
* - extra influence induced by strong positions.
* Reduce permeability around each living stone.
* Reset permeability to 1.0 at intrusion points.
find_influence_patterns(struct influence_data
*q
)
matchpat(influence_callback
, ANCHOR_COLOR
, &influencepat_db
, q
, NULL
);
if (q
->color_to_move
!= EMPTY
)
matchpat(influence_callback
, q
->color_to_move
, &barrierspat_db
, q
, NULL
);
if (q
->is_territorial_influence
)
add_marked_intrusions(q
);
/* Additionally, we introduce a weaker kind of barriers around living
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (ON_BOARD(ii
) && !q
->safe
[ii
]) {
float black_reduction
= 1.0;
float white_reduction
= 1.0;
for (k
= 0; k
< 8; k
++) {
if (IS_STONE(board
[ii
+ d
]) && q
->safe
[ii
+ d
]) {
/* Reduce less diagonally. */
float reduction
= (k
< 4) ? 0.25 : 0.65;
if (board
[ii
+ d
] == BLACK
)
white_reduction
*= reduction
;
black_reduction
*= reduction
;
else if (IS_STONE(board
[ii
+ d
]) && !q
->safe
[ii
+ d
]) {
if (board
[ii
+ d
] == BLACK
)
white_reduction
= -100.0;
black_reduction
= -100.0;
if (black_reduction
> 0.0)
q
->black_permeability
[ii
] *= black_reduction
;
if (white_reduction
> 0.0)
q
->white_permeability
[ii
] *= white_reduction
;
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.
check_double_block(int color
, int pos
, const struct influence_data
*q
)
const float *permeability
= ((color
== BLACK
) ? q
->black_permeability
:
/* Count neighboring blocks. */
if (board
[pos
+ delta
[k
]] == EMPTY
&& permeability
[pos
+ delta
[k
]] == 0.0)
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
float this_value
= sign
* q
->territory_value
[neighbor
];
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
if (this_value
+ 0.0005 < smallest_value
) {
smallest_block
= neighbor
;
smallest_value
= this_value
;
ASSERT1(ON_BOARD1(smallest_block
), pos
);
#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.
remove_double_blocks(struct influence_data
*q
,
const signed char inhibited_sources
[BOARDMAX
])
float *strength
= ((q
->color_to_move
== WHITE
) ? q
->white_strength
:
int double_blocks
[MAX_DOUBLE_BLOCKS
];
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
&& !(inhibited_sources
&& inhibited_sources
[ii
])
double_blocks
[num_blocks
] = check_double_block(q
->color_to_move
, ii
, q
);
if (double_blocks
[num_blocks
] != NO_MOVE
) {
if (num_blocks
== MAX_DOUBLE_BLOCKS
)
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",
color_to_string(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.
* q->is_territorial_influence and q->color_to_move must be set by the caller.
do_compute_influence(const signed char safe_stones
[BOARDMAX
],
const signed char inhibited_sources
[BOARDMAX
],
const float strength
[BOARDMAX
], struct influence_data
*q
,
int move
, const char *trace_message
)
init_influence(q
, safe_stones
, strength
);
modify_depth_values(stackp
- 1);
find_influence_patterns(q
);
modify_depth_values(1 - stackp
);
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (ON_BOARD(ii
) && !(inhibited_sources
&& inhibited_sources
[ii
])) {
if (q
->white_strength
[ii
] > 0.0)
accumulate_influence(q
, ii
, WHITE
);
if (q
->black_strength
[ii
] > 0.0)
accumulate_influence(q
, ii
, BLACK
);
remove_double_blocks(q
, inhibited_sources
);
&& (printmoyo
& PRINTMOYO_INITIAL_INFLUENCE
))
|| (debug_influence
&& move
== debug_influence
))
print_influence(q
, trace_message
);
/* Compute the influence values for both colors.
* - set up the board[] state
* - mark safe stones with INFLUENCE_SAFE_STONE, dead stones with 0
* - mark stones newly saved by a move with INFLUENCE_SAVED_STONE
* (this is relevant if the influence_data *q is reused to compute
* a followup value for this move).
* Results will be stored in q.
* (move) has no effects except toggling debugging. Set it to -1
* for no debug output at all (otherwise it will be controlled by
* the -m command line option).
* It is assumed that color is in turn to move. (This affects the
* barrier patterns (class A, D) and intrusions (class B)). Color
compute_influence(int color
, const signed char safe_stones
[BOARDMAX
],
const float strength
[BOARDMAX
], struct influence_data
*q
,
int move
, const char *trace_message
)
VALGRIND_MAKE_WRITABLE(q
, sizeof(*q
));
q
->is_territorial_influence
= 1;
q
->color_to_move
= color
;
/* Turn off DEBUG_INFLUENCE for influence computations we are not
&& !(printmoyo
& PRINTMOYO_INITIAL_INFLUENCE
))
|| (move
!= NO_MOVE
&& move
!= debug_influence
))
debug
= debug
&~ DEBUG_INFLUENCE
;
do_compute_influence(safe_stones
, NULL
, strength
,
/* Return the color of the territory at (pos). If it's territory for
* neither color, EMPTY is returned.
whose_territory(const struct influence_data
*q
, int pos
)
float bi
= q
->black_influence
[pos
];
float wi
= q
->white_influence
[pos
];
float terr
= q
->territory_value
[pos
];
if (bi
> 0.0 && wi
== 0.0 && terr
< -territory_determination_value
)
if (wi
> 0.0 && bi
== 0.0 && terr
> territory_determination_value
)
/* Return the color who has a moyo at (pos). If neither color has a
* moyo there, EMPTY is returned. The definition of moyo in terms of the
* influences is totally ad hoc.
whose_moyo(const struct influence_data
*q
, int pos
)
float bi
= q
->black_influence
[pos
];
float wi
= q
->white_influence
[pos
];
int territory_color
= whose_territory(q
, pos
);
if (territory_color
!= EMPTY
)
if (bi
> moyo_data
.influence_balance
* wi
&& bi
> moyo_data
.my_influence_minimum
&& wi
< moyo_data
.opp_influence_maximum
)
if (wi
> moyo_data
.influence_balance
* bi
&& wi
> moyo_data
.my_influence_minimum
&& bi
< moyo_data
.opp_influence_maximum
)
/* Return the color who has a moyo at (pos). If neither color has a
* moyo there, EMPTY is returned.
* The definition of moyo in terms of the influences is totally ad
* It has a slightly different definition of moyo than whose_moyo.
whose_moyo_restricted(const struct influence_data
*q
, int pos
)
float bi
= q
->black_influence
[pos
];
float wi
= q
->white_influence
[pos
];
int territory_color
= whose_territory(q
, pos
);
if (territory_color
!= EMPTY
)
else if (bi
> moyo_restricted_data
.influence_balance
* wi
&& bi
> moyo_restricted_data
.my_influence_minimum
&& wi
< moyo_restricted_data
.opp_influence_maximum
)
else if (wi
> moyo_restricted_data
.influence_balance
* bi
&& wi
> moyo_restricted_data
.my_influence_minimum
&& bi
< moyo_restricted_data
.opp_influence_maximum
)
/* Return the color who has dominating influence ("area") at (pos).
* If neither color dominates the influence there, EMPTY is returned.
* The definition of area in terms of the influences is totally ad
whose_area(const struct influence_data
*q
, int pos
)
float bi
= q
->black_influence
[pos
];
float wi
= q
->white_influence
[pos
];
int moyo_color
= whose_moyo(q
, pos
);
if (bi
> 3.0 * wi
&& bi
> 1.0 && wi
< 40.0)
if (wi
> 3.0 * bi
&& wi
> 1.0 && bi
< 40.0)
value_territory(struct influence_data
*q
)
float first_guess
[BOARDMAX
];
memset(first_guess
, 0, BOARDMAX
*sizeof(float));
memset(q
->territory_value
, 0, BOARDMAX
*sizeof(float));
/* First loop: guess territory directly from influence. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
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
]);
first_guess
[ii
] = diff
* diff
* diff
;
/* If both side have small influence, we have to reduce this value.
* What we consider "small influence" depends on how central this
* The values of central on an 11x11 board become:
* 5 8 9 10 10 10 10 10 9 8 5
* 6 9 12 13 13 13 13 13 12 9 6
* 7 10 13 16 16 16 16 16 13 10 7
* 7 10 13 16 17 17 17 16 13 10 7
* 7 10 13 16 17 18 17 16 13 10 7
* 7 10 13 16 17 17 17 16 13 10 7
* 7 10 13 16 16 16 16 16 13 10 7
* 6 9 12 13 13 13 13 13 12 9 6
* 5 8 9 10 10 10 10 10 9 8 5
dist_i
= gg_min(I(ii
), board_size
- I(ii
) - 1);
dist_j
= gg_min(J(ii
), board_size
- J(ii
) - 1);
dist_i
= gg_min(4, dist_i
);
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
])
/ gg_interpolate(&min_infl_for_territory
, central
);
/* Do not make this adjustment when scoring unless both
* players have non-zero influence.
if (doing_scoring
&& (q
->black_influence
[ii
] == 0.0
|| q
->white_influence
[ii
] == 0.0))
first_guess
[ii
] *= gg_interpolate(&territory_correction
, ratio
);
/* Dead stone, upgrade to territory. Notice that this is not
* the point for a prisoner, which is added later. Instead
* this is to make sure that the vertex is not regarded as
* moyo or area. Also notice that the non-territory
* degradation below may over-rule this decision.
else if (board
[ii
] == WHITE
)
q
->territory_value
[ii
] = first_guess
[ii
];
/* Second loop: Correct according to neighbour vertices. Each territory
* value is degraded to the minimum value of its neighbors (unless this
* neighbor has reduced permeability for the opponent's influence).
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
/* Do not overrule dead stone territory above.
* FIXME: This does not do what it claims to do. Correcting it
* seems to break some tests, though.
/* Loop over all neighbors. */
for (k
= 0; k
< 4; k
++) {
if (!ON_BOARD(ii
+ delta
[k
]))
if (q
->territory_value
[ii
] > 0.0) {
if (!q
->safe
[ii
+ delta
[k
]]) {
q
->black_permeability
[ii
+ delta
[k
]]
* first_guess
[ii
+ delta
[k
]]
+ (1.0 - q
->black_permeability
[ii
+ delta
[k
]])
= gg_max(0, gg_min(q
->territory_value
[ii
], neighbor_val
));
if (!q
->safe
[ii
+ delta
[k
]]) {
q
->white_permeability
[ii
+ delta
[k
]]
* first_guess
[ii
+ delta
[k
]]
+ (1 - q
->white_permeability
[ii
+ delta
[k
]])
= gg_min(0, gg_max(q
->territory_value
[ii
], neighbor_val
));
/* Third loop: Nonterritory patterns, points for prisoners. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
/* If marked as non-territory for the color currently owning
* it, reset the territory value.
if (q
->territory_value
[ii
] > 0.0
&& (q
->non_territory
[ii
] & WHITE
))
q
->territory_value
[ii
] = 0.0;
if (q
->territory_value
[ii
] < 0.0
&& (q
->non_territory
[ii
] & BLACK
))
q
->territory_value
[ii
] = 0.0;
/* Dead stone, add one to the territory value. */
q
->territory_value
[ii
] += 1.0;
else if (board
[ii
] == WHITE
)
q
->territory_value
[ii
] -= 1.0;
/* Segment the influence map into connected regions of territory,
* moyo, or area. What to segment on is determined by the the function
* pointer region_owner. The segmentation is performed for both
* colors. The connected regions may include stones of the own color,
* but only empty intersections (and dead opponent stones) count
* toward the region size.
segment_region(struct influence_data
*q
, owner_function_ptr region_owner
,
struct moyo_data
*regions
)
static signed char marked
[BOARDMAX
];
/* Reset the markings. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++) {
regions
->segmentation
[ii
] = 0;
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
&& region_owner(q
, ii
) != EMPTY
) {
/* Found an unlabelled intersection. Use flood filling to find
* the rest of the region.
int color
= region_owner(q
, ii
);
while (queue_start
< queue_end
) {
int tt
= q
->queue
[queue_start
];
if (!q
->safe
[tt
] || board
[tt
] != color
) {
if (q
->is_territorial_influence
)
terr_val
+= gg_abs(q
->territory_value
[tt
]);
regions
->segmentation
[tt
] = regions
->number
;
for (k
= 0; k
< 4; k
++) {
&& region_owner(q
, tt
+ d
) == color
) {
q
->queue
[queue_end
] = tt
+ d
;
regions
->size
[regions
->number
] = size
;
regions
->territorial_value
[regions
->number
] = terr_val
;
regions
->owner
[regions
->number
] = color
;
/* Export a territory segmentation. */
influence_get_territory_segmentation(struct influence_data
*q
,
segment_region(q
, whose_territory
, moyos
);
/* Export the territory valuation at an intersection from initial_influence;
* it is given from (color)'s point of view.
influence_territory(const struct influence_data
*q
, int pos
, int color
)
return q
->territory_value
[pos
];
return -q
->territory_value
[pos
];
influence_considered_lively(const struct influence_data
*q
, int pos
)
ASSERT1(IS_STONE(color
), pos
);
&& ((color
== WHITE
&& q
->white_strength
[pos
] > 0)
|| (color
== BLACK
&& q
->black_strength
[pos
] > 0)));
/* Compute a followup influence. It is assumed that the stones that
* deserve a followup have been marked INFLUENCE_SAVED_STONE in
compute_followup_influence(const struct influence_data
*base
,
struct influence_data
*q
,
int move
, const char *trace_message
)
signed char goal
[BOARDMAX
];
/* This is the color that will get a followup value. */
int color
= OTHER_COLOR(base
->color_to_move
);
memcpy(q
, base
, sizeof(*q
));
ASSERT1(IS_STONE(q
->color_to_move
), move
);
q
->color_to_move
= color
;
/* We mark the saved stones and their neighbors in the goal array.
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (q
->safe
[ii
] == INFLUENCE_SAVED_STONE
)
/* Turn off DEBUG_INFLUENCE for influence computations we are not
&& !(printmoyo
& PRINTMOYO_INITIAL_INFLUENCE
))
|| (move
!= debug_influence
))
debug
= debug
&~ DEBUG_INFLUENCE
;
q
->intrusion_counter
= 0;
/* Match B patterns for saved stones. */
matchpat_goal_anchor(followup_influence_callback
, color
, &barrierspat_db
,
/* Now add the intrusions. */
add_marked_intrusions(q
);
reset_unblocked_blocks(q
);
/* Spread influence for new influence sources. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
&& q
->black_strength
[ii
] > base
->black_strength
[ii
])
&& q
->white_strength
[ii
] > base
->white_strength
[ii
]))
accumulate_influence(q
, ii
, color
);
if (debug_influence
&& debug_influence
== move
)
print_influence(q
, trace_message
);
/* Compute influence based escape values and return them in the
compute_escape_influence(int color
, const signed char safe_stones
[BOARDMAX
],
const signed char goal
[BOARDMAX
],
const float strength
[BOARDMAX
],
signed char escape_value
[BOARDMAX
])
/* IMPORTANT: The caching relies on the fact that safe_stones[] and
* strength[] will currently always be identical for identical board[]
* states. Better check for these, too.
static int cached_board
[BOARDMAX
];
static signed char escape_values
[BOARDMAX
][2];
static int active_caches
[2] = {0, 0};
int cache_number
= (color
== WHITE
);
VALGRIND_MAKE_WRITABLE(&escape_influence
, sizeof(escape_influence
));
/* Encode the values of color and dragons_known into an integer
int board_was_cached
= 1;
/* Notice that we compare the out of board markers as well, in
* case the board size should have changed between calls.
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++) {
if (cached_board
[ii
] != board
[ii
]) {
cached_board
[ii
] = board
[ii
];
if (active_caches
[cache_number
]) {
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
escape_value
[ii
] = escape_values
[ii
][cache_number
];
/* Use enhance pattern and higher attenuation for escape influence. */
escape_influence
.is_territorial_influence
= 0;
escape_influence
.color_to_move
= EMPTY
;
/* Turn off DEBUG_INFLUENCE unless we are specifically interested in
if (!(debug
& DEBUG_ESCAPE
))
debug
&= ~DEBUG_INFLUENCE
;
do_compute_influence(safe_stones
, goal
, strength
,
&escape_influence
, -1, NULL
);
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (whose_moyo(&escape_influence
, ii
) == color
)
else if (whose_area(&escape_influence
, ii
) == color
)
else if (whose_area(&escape_influence
, ii
) == EMPTY
) {
for (k
= 0; k
< 8; k
++) {
if (ON_BOARD(ii
+ delta
[k
])) {
goal_proximity
+= 2 * goal
[ii
+ delta
[k
]];
if (k
< 4 && ON_BOARD(ii
+ 2 * delta
[k
]))
goal_proximity
+= goal
[ii
+ delta
[k
]];
if (0 && (debug
& DEBUG_ESCAPE
) && verbose
> 0)
print_influence(&escape_influence
, "escape influence");
/* Save the computed values in the cache. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
escape_values
[ii
][cache_number
] = escape_value
[ii
];
active_caches
[cache_number
] = 1;
/* Cache of delta_territory_values. */
static float delta_territory_cache
[BOARDMAX
];
static float followup_territory_cache
[BOARDMAX
];
static Hash_data delta_territory_cache_hash
[BOARDMAX
];
static int territory_cache_position_number
= -1;
static int territory_cache_influence_id
= -1;
static int territory_cache_color
= -1;
/* We cache territory computations. This avoids unnecessary re-computations
* when review_move_reasons is run a second time for the endgame patterns.
* (*base) points to the initial_influence data that would be used
* to make the territory computation against.
retrieve_delta_territory_cache(int pos
, int color
, float *move_value
,
const struct influence_data
*base
,
ASSERT1(IS_STONE(color
), pos
);
/* We check whether the color, the board position, or the base influence
* data has changed since the cache entry got entered.
if (territory_cache_position_number
== position_number
&& territory_cache_color
== color
&& territory_cache_influence_id
== base
->id
&& delta_territory_cache
[pos
] != NOT_COMPUTED
) {
for (i
= 0; i
< NUM_HASHVALUES
; i
++)
if (delta_territory_cache_hash
[pos
].hashval
[i
]
!= safety_hash
.hashval
[i
])
*move_value
= delta_territory_cache
[pos
];
*followup_value
= followup_territory_cache
[pos
];
gprintf("%1m: retrieved territory value from cache: %f, %f\n", pos
,
*move_value
, *followup_value
);
store_delta_territory_cache(int pos
, int color
,
float move_value
, float followup_value
,
const struct influence_data
*base
,
ASSERT1(IS_STONE(color
), pos
);
if (territory_cache_position_number
!= position_number
|| territory_cache_color
!= color
|| territory_cache_influence_id
!= base
->id
) {
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
delta_territory_cache
[ii
] = NOT_COMPUTED
;
territory_cache_position_number
= position_number
;
territory_cache_influence_id
= base
->id
;
territory_cache_color
= color
;
gprintf("Cleared delta territory cache.\n");
delta_territory_cache
[pos
] = move_value
;
followup_territory_cache
[pos
] = followup_value
;
for (i
= 0; i
< NUM_HASHVALUES
; i
++)
delta_territory_cache_hash
[pos
].hashval
[i
] = safety_hash
.hashval
[i
];
gprintf("%1m: Stored delta territory cache: %f, %f\n", pos
, move_value
,
/* Compute the difference in territory between two influence data,
* from the point of view of (color).
* (move) is only passed for debugging output.
influence_delta_territory(const struct influence_data
*base
,
const struct influence_data
*q
, int color
,
ASSERT1(IS_STONE(color
), move
);
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
float new_value
= q
->territory_value
[ii
];
float old_value
= base
->territory_value
[ii
];
this_delta
= new_value
- old_value
;
/* Negate values if we are black. */
this_delta
= -this_delta
;
&& (this_delta
> 0.02 || -this_delta
> 0.02))
" %1m: - %1m territory change %f (%f -> %f)\n",
move
, ii
, this_delta
, old_value
, new_value
);
total_delta
+= this_delta
;
/* Finally, captured stones: */
this_delta
= q
->captured
- base
->captured
;
this_delta
= -this_delta
;
DEBUG(DEBUG_TERRITORY
, " %1m: - captured stones %f\n",
total_delta
+= this_delta
;
/* Estimate the score. A positive value means white is ahead. The
* score is estimated influence data *q, which must have been
influence_score(const struct influence_data
*q
, int use_chinese_rules
)
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
score
+= q
->territory_value
[ii
];
score
+= stones_on_board(WHITE
) - stones_on_board(BLACK
) + komi
+ handicap
;
score
+= black_captured
- white_captured
+ komi
;
/* Uses initial_influence to estimate the game advancement (fuseki,
* chuban, yose) returned as a value between 0.0 (start) and 1.0 (game
struct influence_data
*iq
= INITIAL_INFLUENCE(color
);
struct influence_data
*oq
= OPPOSITE_INFLUENCE(color
);
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
count
+= WEIGHT_TERRITORY
;
else if (whose_territory(iq
, ii
) != EMPTY
&& whose_territory(oq
, ii
) != EMPTY
)
count
+= WEIGHT_TERRITORY
;
else if (whose_moyo(oq
, ii
) != EMPTY
)
else if (whose_area(oq
, ii
) != EMPTY
)
return (float) count
/ (WEIGHT_TERRITORY
* board_size
* board_size
);
/* Print the influence map when we have computed influence for the
debug_influence_move(int move
)
/* One more way to export influence data. This should only be used
get_influence(const struct influence_data
*q
,
float white_influence
[BOARDMAX
],
float black_influence
[BOARDMAX
],
float white_strength
[BOARDMAX
],
float black_strength
[BOARDMAX
],
float white_attenuation
[BOARDMAX
],
float black_attenuation
[BOARDMAX
],
float white_permeability
[BOARDMAX
],
float black_permeability
[BOARDMAX
],
float territory_value
[BOARDMAX
],
int influence_regions
[BOARDMAX
],
int non_territory
[BOARDMAX
])
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++) {
white_influence
[ii
] = q
->white_influence
[ii
];
black_influence
[ii
] = q
->black_influence
[ii
];
white_strength
[ii
] = q
->white_strength
[ii
];
black_strength
[ii
] = q
->black_strength
[ii
];
white_attenuation
[ii
] = q
->white_attenuation
[ii
];
black_attenuation
[ii
] = q
->black_attenuation
[ii
];
white_permeability
[ii
] = q
->white_permeability
[ii
];
black_permeability
[ii
] = q
->black_permeability
[ii
];
territory_value
[ii
] = q
->territory_value
[ii
];
non_territory
[ii
] = q
->non_territory
[ii
];
if (board
[ii
] == EMPTY
) {
if (whose_territory(q
, ii
) == WHITE
)
influence_regions
[ii
] = 3;
else if (whose_territory(q
, ii
) == BLACK
)
influence_regions
[ii
] = -3;
else if (whose_moyo(q
, ii
) == WHITE
)
influence_regions
[ii
] = 2;
else if (whose_moyo(q
, ii
) == BLACK
)
influence_regions
[ii
] = -2;
else if (whose_area(q
, ii
) == WHITE
)
influence_regions
[ii
] = 1;
else if (whose_area(q
, ii
) == BLACK
)
influence_regions
[ii
] = -1;
influence_regions
[ii
] = 0;
else if (board
[ii
] == WHITE
)
influence_regions
[ii
] = 4;
else if (board
[ii
] == BLACK
)
influence_regions
[ii
] = -4;
/* Print influence for debugging purposes, according to
* printmoyo bitmap (controlled by -m command line option).
print_influence(const struct influence_data
*q
, const char *info_string
)
if (printmoyo
& PRINTMOYO_ATTENUATION
) {
/* Print the attenuation values. */
fprintf(stderr
, "white attenuation (%s):\n", info_string
);
print_numeric_influence(q
, q
->white_attenuation
, "%3.2f", 3, 0, 0);
fprintf(stderr
, "black attenuation (%s):\n", info_string
);
print_numeric_influence(q
, q
->black_attenuation
, "%3.2f", 3, 0, 0);
if (printmoyo
& PRINTMOYO_PERMEABILITY
) {
/* Print the white permeability values. */
fprintf(stderr
, "white permeability:\n");
print_numeric_influence(q
, q
->white_permeability
, "%3.1f", 3, 0, 0);
/* Print the black permeability values. */
fprintf(stderr
, "black permeability:\n");
print_numeric_influence(q
, q
->black_permeability
, "%3.1f", 3, 0, 0);
if (printmoyo
& PRINTMOYO_STRENGTH
) {
/* Print the strength values. */
fprintf(stderr
, "white strength:\n");
if (q
->is_territorial_influence
)
print_numeric_influence(q
, q
->white_strength
, "%5.1f", 5, 0, 0);
print_numeric_influence(q
, q
->white_strength
, "%3.0f", 3, 0, 1);
fprintf(stderr
, "black strength:\n");
if (q
->is_territorial_influence
)
print_numeric_influence(q
, q
->black_strength
, "%5.1f", 5, 0, 0);
print_numeric_influence(q
, q
->black_strength
, "%3.0f", 3, 0, 1);
if (printmoyo
& PRINTMOYO_NUMERIC_INFLUENCE
) {
/* Print the white influence values. */
fprintf(stderr
, "white influence (%s):\n", info_string
);
print_numeric_influence(q
, q
->white_influence
, "%5.1f", 5, 1, 0);
/* Print the black influence values. */
fprintf(stderr
, "black influence (%s):\n", info_string
);
print_numeric_influence(q
, q
->black_influence
, "%5.1f", 5, 1, 0);
if (printmoyo
& PRINTMOYO_PRINT_INFLUENCE
) {
fprintf(stderr
, "influence regions (%s):\n", info_string
);
print_influence_areas(q
);
if (printmoyo
& PRINTMOYO_VALUE_TERRITORY
) {
fprintf(stderr
, "territory (%s)", info_string
);
print_numeric_influence(q
, q
->territory_value
, "%5.2f", 5, 1, 0);
* Print numeric influence values.
print_numeric_influence(const struct influence_data
*q
,
const float values
[BOARDMAX
],
const char *format
, int width
,
int draw_stones
, int mark_epsilon
)
memset(format_stone
, ' ', 20);
format_stone
[(width
+ 1) / 2] = '%';
format_stone
[(width
+ 3) / 2] = 'c';
format_stone
[width
+ 2] = 0;
for (i
= 0, ch
= 'A'; i
< board_size
; i
++, ch
++) {
fprintf(stderr
, format_stone
, ch
);
for (i
= 0; i
< board_size
; i
++) {
fprintf(stderr
, "%2d ", ii
);
for (j
= 0; j
< board_size
; j
++) {
if (draw_stones
&& q
->safe
[ii
]) {
fprintf(stderr
, format_stone
, 'O');
fprintf(stderr
, format_stone
, 'X');
if (mark_epsilon
&& values
[ii
] > 0.0 && values
[ii
] < 1.0)
fprintf(stderr
, format
, values
[ii
]);
fprintf(stderr
, "%2d\n", ii
);
for (i
= 0, ch
= 'A'; i
< board_size
; i
++, ch
++) {
fprintf(stderr
, format_stone
, ch
);
/* Draw colored board illustrating territory, moyo, and area. */
print_influence_areas(const struct influence_data
*q
)
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
int color
= GG_COLOR_BLACK
;
else if (whose_territory(q
, ii
) == WHITE
) {
else if (whose_territory(q
, ii
) == BLACK
) {
else if (whose_moyo(q
, ii
) == WHITE
) {
else if (whose_moyo(q
, ii
) == BLACK
) {
else if (whose_area(q
, ii
) == WHITE
) {
else if (whose_area(q
, ii
) == BLACK
) {
draw_color_char(I(ii
), J(ii
), c
, color
);