Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 or * | |
11 | * (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #include "gnugo.h" | |
25 | ||
26 | #include <stdio.h> | |
27 | #include <stdlib.h> | |
28 | #include <string.h> | |
29 | ||
30 | #include "liberty.h" | |
31 | #include "influence.h" | |
32 | #include "patterns.h" | |
33 | #include "gg_utils.h" | |
34 | ||
35 | static void add_influence_source(int pos, int color, float strength, | |
36 | float attenuation, | |
37 | struct influence_data *q); | |
38 | static void print_influence(const struct influence_data *q, | |
39 | const char *info_string); | |
40 | static void print_numeric_influence(const struct influence_data *q, | |
41 | const float values[BOARDMAX], | |
42 | const char *format, int width, | |
43 | int draw_stones, int mark_epsilon); | |
44 | static void print_influence_areas(const struct influence_data *q); | |
45 | ||
46 | static void value_territory(struct influence_data *q); | |
47 | static void enter_intrusion_source(int source_pos, int strength_pos, | |
48 | float strength, float attenuation, | |
49 | struct influence_data *q); | |
50 | static void add_marked_intrusions(struct influence_data *q); | |
51 | ||
52 | ||
53 | /* Influence computed for the initial position, i.e. before making | |
54 | * some move. | |
55 | */ | |
56 | struct influence_data initial_black_influence; | |
57 | struct influence_data initial_white_influence; | |
58 | ||
59 | /* Influence computed after some move has been made. */ | |
60 | struct influence_data move_influence; | |
61 | struct influence_data followup_influence; | |
62 | ||
63 | /* Influence used for estimation of escape potential. */ | |
64 | static struct influence_data escape_influence; | |
65 | ||
66 | /* Pointer to influence data used during pattern matching. */ | |
67 | static struct influence_data *current_influence = NULL; | |
68 | ||
69 | ||
70 | /* Thresholds values used in the whose_moyo() functions */ | |
71 | static struct moyo_determination_data moyo_data; | |
72 | static struct moyo_determination_data moyo_restricted_data; | |
73 | ||
74 | /* Thresholds value used in the whose_territory() function */ | |
75 | static float territory_determination_value; | |
76 | ||
77 | ||
78 | ||
79 | /* This curve determines how much influence is needed at least to claim | |
80 | * an intersection as territory, in dependence of the "center value". | |
81 | * (In the center, more effort is needed to get territory!) | |
82 | * The center value is at the moment defined as follows: | |
83 | * If d1, d2 are the distance to vertical and horizontal border, resp., | |
84 | * with d1<d2, then | |
85 | * central = 3 * d1 + min(d2, 4) | |
86 | * So this is mainly a function of the distance to the border; the | |
87 | * distance to the second-nearest border gives a small correction of at | |
88 | * most 4. This distinguishes edge and corner positions. | |
89 | * | |
90 | * The values for intersections close to a corner or to the edge have | |
91 | * to be consistent such that standard corner enclosure etc. are | |
92 | * sufficient to claim territory. The center values are more arbitrary | |
93 | * suspect to tuning. | |
94 | */ | |
95 | ||
96 | static struct interpolation_data min_infl_for_territory = | |
97 | { 6, 0.0, 24.0, { 6.0, 15.0, 26.0, 36.0, 45.0, 50.0, 55.0 }}; | |
98 | ||
99 | /* Determines the territory correction factor in dependence of the ratio | |
100 | * ( influence of stronger color / min_infl_for_territory(intersection)) | |
101 | */ | |
102 | static struct interpolation_data territory_correction = | |
103 | { 5, (float) 0.0, 1.0, {0.0, 0.25, 0.45, 0.65, 0.85, 1.0}}; | |
104 | ||
105 | ||
106 | ||
107 | ||
108 | ||
109 | /* If set, print influence map when computing this move. Purely for | |
110 | * debugging. | |
111 | */ | |
112 | static int debug_influence = NO_MOVE; | |
113 | ||
114 | /* Assigns an id to all influence computations for reference in the | |
115 | * delta territory cache. | |
116 | */ | |
117 | static int influence_id = 0; | |
118 | ||
119 | /* This is the core of the influence function. Given the coordinates | |
120 | * and color of an influence source, it radiates the influence | |
121 | * outwards until it hits a barrier or the strength of the influence | |
122 | * falls under a certain threshold. | |
123 | * | |
124 | * The radiation is performed by a breadth first propagation, | |
125 | * implemented by means of an internal queue. | |
126 | * | |
127 | * Since this function has turned out be one of the bottlenecks, loop | |
128 | * unrolling makes a noticeable performance difference. It does, | |
129 | * however, make the code much harder to read and maintain. Therefore | |
130 | * we include both the original and the unrolled versions. | |
131 | */ | |
132 | ||
133 | #define EXPLICIT_LOOP_UNROLLING 1 | |
134 | ||
135 | #if EXPLICIT_LOOP_UNROLLING | |
136 | /* In addition to the parameters, this macro expects | |
137 | * m,n = original source of influence | |
138 | * ii = point influence is being spread from | |
139 | * delta_i = I(ii) - m | |
140 | * delta_j = J(ii) - n | |
141 | * current_strength combines strength and damping factor | |
142 | * b is 1/(square of distance from m,n to i,j) ; or halved | |
143 | * for diagonals | |
144 | * | |
145 | * arg is i + arg_di ; arg_j is j + arg_dj | |
146 | * arg_d is 1 for diagonal movement | |
147 | * | |
148 | */ | |
149 | ||
150 | ||
151 | #define code1(arg_di, arg_dj, arg, arg_d) do { \ | |
152 | if (!q->safe[arg] \ | |
153 | && ((arg_di)*(delta_i) + (arg_dj)*(delta_j) > 0 \ | |
154 | || queue_start == 1)) { \ | |
155 | float contribution; \ | |
156 | float permeability = permeability_array[ii]; \ | |
157 | if (arg_d) { \ | |
158 | permeability *= gg_max(permeability_array[ii + DELTA(arg_di, 0)], \ | |
159 | permeability_array[ii + DELTA(0, arg_dj)]); \ | |
160 | if (permeability == 0.0) \ | |
161 | continue; \ | |
162 | } \ | |
163 | contribution = current_strength * permeability; \ | |
164 | if (queue_start != 1) { \ | |
165 | int a = (arg_di)*(delta_i) + (arg_dj)*(delta_j); \ | |
166 | contribution *= (a*a) * b; /* contribution *= cos(phi) */ \ | |
167 | } \ | |
168 | if (contribution <= INFLUENCE_CUTOFF) \ | |
169 | continue; \ | |
170 | if (working[arg] == 0.0) { \ | |
171 | q->queue[queue_end] = (arg); \ | |
172 | queue_end++; \ | |
173 | } \ | |
174 | working[arg] += contribution; \ | |
175 | } } while (0) | |
176 | #endif | |
177 | ||
178 | ||
179 | static void | |
180 | accumulate_influence(struct influence_data *q, int pos, int color) | |
181 | { | |
182 | int ii; | |
183 | int m = I(pos); | |
184 | int n = J(pos); | |
185 | int k; | |
186 | #if !EXPLICIT_LOOP_UNROLLING | |
187 | int d; | |
188 | #endif | |
189 | float b; | |
190 | float inv_attenuation; | |
191 | float inv_diagonal_damping; | |
192 | float *permeability_array; | |
193 | ||
194 | /* Clear the queue. Entry 0 is implicitly (m, n). */ | |
195 | int queue_start = 0; | |
196 | int queue_end = 1; | |
197 | ||
198 | static float working[BOARDMAX]; | |
199 | static int working_area_initialized = 0; | |
200 | ||
201 | if (!working_area_initialized) { | |
202 | for (ii = 0; ii < BOARDMAX; ii++) | |
203 | working[ii] = 0.0; | |
204 | working_area_initialized = 1; | |
205 | } | |
206 | ||
207 | if (0) | |
208 | gprintf("Accumulating influence for %s at %m\n", | |
209 | color_to_string(color), m, n); | |
210 | ||
211 | /* Attenuation only depends on the influence origin. */ | |
212 | if (color == WHITE) | |
213 | inv_attenuation = 1.0 / q->white_attenuation[pos]; | |
214 | else | |
215 | inv_attenuation = 1.0 / q->black_attenuation[pos]; | |
216 | ||
217 | if (q->is_territorial_influence) | |
218 | inv_diagonal_damping = 1.0 / TERR_DIAGONAL_DAMPING; | |
219 | else | |
220 | inv_diagonal_damping = 1.0 / DIAGONAL_DAMPING; | |
221 | ||
222 | if (color == WHITE) | |
223 | permeability_array = q->white_permeability; | |
224 | else | |
225 | permeability_array = q->black_permeability; | |
226 | ||
227 | /* We put the original source into slot 0. */ | |
228 | q->queue[0] = pos; | |
229 | ||
230 | if (color == WHITE) | |
231 | working[pos] = q->white_strength[pos]; | |
232 | else | |
233 | working[pos] = q->black_strength[pos]; | |
234 | ||
235 | ||
236 | /* Spread influence until the stack is empty. */ | |
237 | while (queue_start < queue_end) { | |
238 | float current_strength; | |
239 | int delta_i, delta_j; | |
240 | ||
241 | ii = q->queue[queue_start]; | |
242 | delta_i = I(ii) - m; | |
243 | delta_j = J(ii) - n; | |
244 | queue_start++; | |
245 | if (permeability_array[ii] == 0.0) | |
246 | continue; | |
247 | if (0) | |
248 | gprintf("Picked %1m from queue. w=%f start=%d end=%d\n", | |
249 | ii, working[ii], queue_start, queue_end); | |
250 | if (queue_start == 1) | |
251 | b = 1.0; | |
252 | else | |
253 | b = 1.0 / ((delta_i)*(delta_i) + (delta_j)*(delta_j)); | |
254 | ||
255 | current_strength = working[ii] * inv_attenuation; | |
256 | ||
257 | #if !EXPLICIT_LOOP_UNROLLING | |
258 | /* Try to spread influence in each of the eight directions. */ | |
259 | for (d = 0; d < 8; d++) { | |
260 | int di = deltai[d]; | |
261 | int dj = deltaj[d]; | |
262 | int d_ii = delta[d]; | |
263 | ||
264 | /* Verify that (ii + d_ii) is | |
265 | * 1. Inside the board. | |
266 | * 2. Not occupied. | |
267 | * 3. Directed outwards. For the origin all directions are outwards. | |
268 | */ | |
269 | if (ON_BOARD(ii + d_ii) | |
270 | && (!q->safe[ii + d_ii]) | |
271 | && (di*(delta_i) + dj*(delta_j) > 0 | |
272 | || queue_start == 1)) { | |
273 | ||
274 | float contribution; | |
275 | float permeability = permeability_array[ii]; | |
276 | float dfactor; | |
277 | float inv_damping; | |
278 | ||
279 | /* Now compute the damping of the influence. | |
280 | * First we have the permeability at the point we are | |
281 | * spreading from. For diagonal movement we also take the | |
282 | * permeability of the vertices we are "passing by" into | |
283 | * account. | |
284 | */ | |
285 | if (d > 3) { /* diagonal movement */ | |
286 | permeability *= gg_max(permeability_array[ii + DELTA(di, 0)], | |
287 | permeability_array[ii + DELTA(0, dj)]); | |
288 | inv_damping = inv_diagonal_damping; | |
289 | dfactor = 0.5; | |
290 | } | |
291 | else { | |
292 | inv_damping = 1.0; | |
293 | dfactor = 1.0; | |
294 | } | |
295 | ||
296 | if (permeability == 0.0) | |
297 | continue; | |
298 | ||
299 | contribution = permeability * current_strength * inv_damping; | |
300 | ||
301 | /* Finally direction dependent damping. */ | |
302 | if (ii != pos) { | |
303 | int a = di*(delta_i) + dj*(delta_j); | |
304 | gg_assert(a > 0); | |
305 | contribution *= (a*a) * b * dfactor; | |
306 | } | |
307 | ||
308 | /* Stop spreading influence if the contribution becomes too low. */ | |
309 | if (contribution <= INFLUENCE_CUTOFF) | |
310 | continue; | |
311 | ||
312 | /* If no influence here before, add the point to the queue for | |
313 | * further spreading. | |
314 | */ | |
315 | if (0) | |
316 | gprintf(" Spreading %s influence from %1m to %1m, d=%d\n", | |
317 | color_to_string(color), ii, ii + d_ii, d); | |
318 | if (working[ii + d_ii] == 0.0) { | |
319 | q->queue[queue_end] = ii + d_ii; | |
320 | queue_end++; | |
321 | } | |
322 | working[ii + d_ii] += contribution; | |
323 | } | |
324 | } | |
325 | #else | |
326 | if (ON_BOARD(ii + delta[0])) | |
327 | code1(deltai[0], deltaj[0], ii + delta[0], 0); | |
328 | if (ON_BOARD(ii + delta[1])) | |
329 | code1(deltai[1], deltaj[1], ii + delta[1], 0); | |
330 | if (ON_BOARD(ii + delta[2])) | |
331 | code1(deltai[2], deltaj[2], ii + delta[2], 0); | |
332 | if (ON_BOARD(ii + delta[3])) | |
333 | code1(deltai[3], deltaj[3], ii + delta[3], 0); | |
334 | ||
335 | /* Update factors for diagonal movement. */ | |
336 | b *= 0.5; | |
337 | current_strength *= inv_diagonal_damping; | |
338 | ||
339 | if (ON_BOARD(ii + delta[4])) | |
340 | code1(deltai[4], deltaj[4], ii + delta[4], 1); | |
341 | if (ON_BOARD(ii + delta[5])) | |
342 | code1(deltai[5], deltaj[5], ii + delta[5], 1); | |
343 | if (ON_BOARD(ii + delta[6])) | |
344 | code1(deltai[6], deltaj[6], ii + delta[6], 1); | |
345 | if (ON_BOARD(ii + delta[7])) | |
346 | code1(deltai[7], deltaj[7], ii + delta[7], 1); | |
347 | #endif | |
348 | } | |
349 | ||
350 | /* Add the values in the working area to the accumulated influence | |
351 | * and simultaneously reset the working area. We know that all | |
352 | * influenced points were stored in the queue, so we just traverse | |
353 | * it. | |
354 | */ | |
355 | for (k = 0; k < queue_end; k++) { | |
356 | ii = q->queue[k]; | |
357 | ||
358 | if (color == WHITE) { | |
359 | if (working[ii] > 1.01 * INFLUENCE_CUTOFF | |
360 | || q->white_influence[ii] == 0.0) | |
361 | q->white_influence[ii] += working[ii]; | |
362 | } | |
363 | else { | |
364 | if (working[ii] > 1.01 * INFLUENCE_CUTOFF | |
365 | || q->black_influence[ii] == 0.0) | |
366 | q->black_influence[ii] += working[ii]; | |
367 | } | |
368 | ||
369 | working[ii] = 0.0; | |
370 | } | |
371 | } | |
372 | ||
373 | ||
374 | ||
375 | /* Initialize the influence_data structure. */ | |
376 | ||
377 | static void | |
378 | init_influence(struct influence_data *q, | |
379 | const signed char safe_stones[BOARDMAX], | |
380 | const float strength[BOARDMAX]) | |
381 | { | |
382 | int ii; | |
383 | float attenuation; | |
384 | ||
385 | /* Initialisation of some global positional values, based on | |
386 | * game stage. | |
387 | */ | |
388 | if (cosmic_gnugo) { | |
389 | float t; | |
390 | if ((board_size != 19) || (movenum <= 2) || ((movenum / 2) % 2)) | |
391 | cosmic_importance = 0.0; | |
392 | else { | |
393 | cosmic_importance = 1.0 - (movenum / 150.0)*(movenum / 150.0); | |
394 | cosmic_importance = gg_max(0.0, cosmic_importance); | |
395 | } | |
396 | ||
397 | t = cosmic_importance; | |
398 | ||
399 | moyo_data.influence_balance = t * 15.0 + (1.0-t) * 5.0; | |
400 | moyo_data.my_influence_minimum = t * 5.0 + (1.0-t) * 5.0; | |
401 | moyo_data.opp_influence_maximum = t * 30.0 + (1.0-t) * 30.0; | |
402 | ||
403 | /* we use the same values for moyo and moyo_restricted */ | |
404 | moyo_restricted_data = moyo_data; | |
405 | ||
406 | territory_determination_value = t * 0.95 + (1.0-t) * 0.95; | |
407 | ||
408 | min_infl_for_territory.values[0] = t * 6.0 + (1.0-t) * 10.0; | |
409 | min_infl_for_territory.values[1] = t * 10.0 + (1.0-t) * 15.0; | |
410 | min_infl_for_territory.values[2] = t * 20.0 + (1.0-t) * 15.0; | |
411 | min_infl_for_territory.values[3] = t * 20.0 + (1.0-t) * 20.0; | |
412 | min_infl_for_territory.values[4] = t * 20.0 + (1.0-t) * 20.0; | |
413 | min_infl_for_territory.values[5] = t * 15.0 + (1.0-t) * 15.0; | |
414 | min_infl_for_territory.values[6] = t * 10.0 + (1.0-t) * 15.0; | |
415 | } | |
416 | else { | |
417 | /* non-cosmic values */ | |
418 | cosmic_importance = 0.0; | |
419 | ||
420 | moyo_data.influence_balance = 7.0; | |
421 | moyo_data.my_influence_minimum = 5.0; | |
422 | moyo_data.opp_influence_maximum = 10.0; | |
423 | ||
424 | moyo_restricted_data.influence_balance = 10.0; | |
425 | moyo_restricted_data.my_influence_minimum = 10.0; | |
426 | moyo_restricted_data.opp_influence_maximum = 10.0; | |
427 | ||
428 | territory_determination_value = 0.95; | |
429 | ||
430 | min_infl_for_territory.values[0] = 6.0; | |
431 | min_infl_for_territory.values[1] = 15.0; | |
432 | min_infl_for_territory.values[2] = 26.0; | |
433 | min_infl_for_territory.values[3] = 36.0; | |
434 | min_infl_for_territory.values[4] = 45.0; | |
435 | min_infl_for_territory.values[5] = 50.0; | |
436 | min_infl_for_territory.values[6] = 55.0; | |
437 | } | |
438 | ||
439 | if (q->is_territorial_influence) | |
440 | attenuation = TERR_DEFAULT_ATTENUATION; | |
441 | else | |
442 | attenuation = 2 * DEFAULT_ATTENUATION; | |
443 | ||
444 | q->intrusion_counter = 0; | |
445 | ||
446 | /* Remember this for later. */ | |
447 | memcpy(q->safe, safe_stones, BOARDMAX * sizeof(*safe_stones)); | |
448 | q->captured = black_captured - white_captured; | |
449 | ||
450 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
451 | if (ON_BOARD(ii)) { | |
452 | /* Initialize. */ | |
453 | q->white_influence[ii] = 0.0; | |
454 | q->black_influence[ii] = 0.0; | |
455 | q->white_attenuation[ii] = attenuation; | |
456 | q->black_attenuation[ii] = attenuation; | |
457 | q->white_permeability[ii] = 1.0; | |
458 | q->black_permeability[ii] = 1.0; | |
459 | q->white_strength[ii] = 0.0; | |
460 | q->black_strength[ii] = 0.0; | |
461 | q->non_territory[ii] = EMPTY; | |
462 | ||
463 | if (IS_STONE(board[ii])) { | |
464 | if (!safe_stones[ii]) { | |
465 | if (board[ii] == WHITE) | |
466 | q->white_permeability[ii] = 0.0; | |
467 | else | |
468 | q->black_permeability[ii] = 0.0; | |
469 | } | |
470 | else { | |
471 | if (board[ii] == WHITE) { | |
472 | if (strength) | |
473 | q->white_strength[ii] = strength[ii]; | |
474 | else | |
475 | q->white_strength[ii] = DEFAULT_STRENGTH; | |
476 | q->black_permeability[ii] = 0.0; | |
477 | } | |
478 | else { | |
479 | if (strength) | |
480 | q->black_strength[ii] = strength[ii]; | |
481 | else | |
482 | q->black_strength[ii] = DEFAULT_STRENGTH; | |
483 | q->white_permeability[ii] = 0.0; | |
484 | } | |
485 | } | |
486 | } | |
487 | else | |
488 | /* Ideally, safe_stones[] should always be zero for empty | |
489 | * intersections. This is currently, however, sometimes not true | |
490 | * when an inessential worm gets captured. So we revise this | |
491 | * in our private copy here. | |
492 | */ | |
493 | q->safe[ii] = 0; | |
494 | } | |
495 | } | |
496 | ||
497 | ||
498 | /* Adds an influence source at position pos with prescribed strength | |
499 | * and attenuation. color can be BLACK, WHITE or both. If there | |
500 | * already exists an influence source of the respective color at pos | |
501 | * that is stronger than the new one, we do nothing. | |
502 | */ | |
503 | static void | |
504 | add_influence_source(int pos, int color, float strength, float attenuation, | |
505 | struct influence_data *q) | |
506 | { | |
507 | if ((color & WHITE) && (q->white_strength[pos] < strength)) { | |
508 | q->white_strength[pos] = strength; | |
509 | q->white_attenuation[pos] = attenuation; | |
510 | } | |
511 | ||
512 | if ((color & BLACK) && (q->black_strength[pos] < strength)) { | |
513 | q->black_strength[pos] = strength; | |
514 | q->black_attenuation[pos] = attenuation; | |
515 | } | |
516 | } | |
517 | ||
518 | /* Adds an intrusion as an entry in the list q->intrusions. */ | |
519 | static void | |
520 | enter_intrusion_source(int source_pos, int strength_pos, | |
521 | float strength, float attenuation, | |
522 | struct influence_data *q) | |
523 | { | |
524 | if (q->intrusion_counter >= MAX_INTRUSIONS) { | |
525 | DEBUG(DEBUG_INFLUENCE, "intrusion list exhausted\n"); | |
526 | return; | |
527 | } | |
528 | q->intrusions[q->intrusion_counter].source_pos = source_pos; | |
529 | q->intrusions[q->intrusion_counter].strength_pos = strength_pos; | |
530 | q->intrusions[q->intrusion_counter].strength = strength; | |
531 | q->intrusions[q->intrusion_counter].attenuation = attenuation; | |
532 | q->intrusion_counter++; | |
533 | } | |
534 | ||
535 | /* Comparison of intrusions datas, to sort them. */ | |
536 | static int | |
537 | compare_intrusions(const void *p1, const void *p2) | |
538 | { | |
539 | const struct intrusion_data *intr1 = p1; | |
540 | const struct intrusion_data *intr2 = p2; | |
541 | if (intr1->source_pos - intr2->source_pos != 0) | |
542 | return (intr1->source_pos - intr2->source_pos); | |
543 | else if (intr1->strength_pos - intr2->strength_pos != 0) | |
544 | return (intr1->strength_pos - intr2->strength_pos); | |
545 | else if (intr1->strength > intr2->strength) | |
546 | return 1; | |
547 | else | |
548 | return -1; | |
549 | } | |
550 | ||
551 | /* It may happen that we have a low intensity influence source at a | |
552 | * blocked intersection (due to an intrusion). This function resets the | |
553 | * permeabilities. | |
554 | */ | |
555 | static void | |
556 | reset_unblocked_blocks(struct influence_data *q) | |
557 | { | |
558 | int pos; | |
559 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
560 | if (ON_BOARD(pos)) { | |
561 | if (!q->safe[pos] && q->white_strength[pos] > 0.0 | |
562 | && q->white_permeability[pos] != 1.0) { | |
563 | DEBUG(DEBUG_INFLUENCE, " black block removed from %1m\n", pos); | |
564 | q->white_permeability[pos] = 1.0; | |
565 | } | |
566 | if (!q->safe[pos] && q->black_strength[pos] > 0.0 | |
567 | && q->black_permeability[pos] != 1.0) { | |
568 | DEBUG(DEBUG_INFLUENCE, " white block removed from %1m\n", pos); | |
569 | q->black_permeability[pos] = 1.0; | |
570 | } | |
571 | } | |
572 | } | |
573 | ||
574 | ||
575 | /* This function goes through the list of intrusion sources, and adds | |
576 | * the intrusion as influence sources for color. The strength is | |
577 | * corrected so that each stone's intrusions sources can have total | |
578 | * strength of at most 60%/100% of the strength of the stone. | |
579 | * (100% is if q == &followup_influence, 60% otherwise). | |
580 | */ | |
581 | static void | |
582 | add_marked_intrusions(struct influence_data *q) | |
583 | { | |
584 | int i; | |
585 | int j = 0; | |
586 | int source_pos; | |
587 | float strength_sum; | |
588 | float correction; | |
589 | float source_strength; | |
590 | float allowed_strength; | |
591 | int color = q->color_to_move; | |
592 | ||
593 | gg_sort(q->intrusions, q->intrusion_counter, sizeof(q->intrusions[0]), | |
594 | compare_intrusions); | |
595 | ||
596 | /* Go through all intrusion sources. */ | |
597 | for (i = 0; i < q->intrusion_counter; i = j) { | |
598 | strength_sum = 0.0; | |
599 | source_pos = q->intrusions[i].source_pos; | |
600 | /* "Anonymous" intrusios go in uncorrected. */ | |
601 | if (source_pos == NO_MOVE) { | |
602 | add_influence_source(q->intrusions[i].strength_pos, color, | |
603 | q->intrusions[j].strength, | |
604 | q->intrusions[j].attenuation, q); | |
605 | DEBUG(DEBUG_INFLUENCE, "Adding %s intrusion at %1m, value %f\n", | |
606 | (color == BLACK) ? "black" : "white", | |
607 | q->intrusions[j].strength_pos, q->intrusions[j].strength); | |
608 | j = i+1; | |
609 | continue; | |
610 | } | |
611 | if (color == BLACK) | |
612 | source_strength = q->black_strength[source_pos]; | |
613 | else | |
614 | source_strength = q->white_strength[source_pos]; | |
615 | ||
616 | /* First loop: Determine correction factor. */ | |
617 | for (j = i; (j < q->intrusion_counter) | |
618 | && (q->intrusions[j].source_pos == source_pos); j++) { | |
619 | /* Of identical strength positions, only take strongest value. */ | |
620 | if (j == i | |
621 | || q->intrusions[j].strength_pos != q->intrusions[j-1].strength_pos) | |
622 | strength_sum += q->intrusions[j].strength; | |
623 | } | |
624 | if (q == &followup_influence) | |
625 | allowed_strength = source_strength; | |
626 | else | |
627 | allowed_strength = 0.6 * source_strength; | |
628 | if (strength_sum > allowed_strength) | |
629 | correction = (allowed_strength / strength_sum); | |
630 | else | |
631 | correction = 1.0; | |
632 | ||
633 | /* Second loop: Add influence sources. */ | |
634 | for (j = i; (j < q->intrusion_counter) | |
635 | && (q->intrusions[j].source_pos == source_pos); j++) { | |
636 | /* Of identical strenght positions, only take strongest value. */ | |
637 | if (j == i || q->intrusions[j].strength_pos | |
638 | != q->intrusions[j-1].strength_pos) { | |
639 | add_influence_source(q->intrusions[j].strength_pos, color, | |
640 | correction * q->intrusions[j].strength, | |
641 | q->intrusions[j].attenuation, q); | |
642 | DEBUG(DEBUG_INFLUENCE, | |
643 | "Adding %s intrusion for %1m at %1m, value %f (correction %f)\n", | |
644 | (color == BLACK) ? "black" : "white", source_pos, | |
645 | q->intrusions[j].strength_pos, | |
646 | correction * q->intrusions[j].strength, correction); | |
647 | } | |
648 | } | |
649 | } | |
650 | } | |
651 | ||
652 | /* Callback for the matched patterns in influence.db and barriers.db. | |
653 | * The pattern classes used here are: | |
654 | * A - Barrier pattern, where O plays first and X tries to block influence. | |
655 | * D - Barrier pattern, where O plays first and O tries to block influence. | |
656 | * B - Intrusion patterns, adding a low intensity influence source. | |
657 | * E - Enhance patterns, FIXME: document this one! | |
658 | * t - Non-territory patterns, marking vertices as not territory. | |
659 | * I - Invasion patterns, adding a low intensity influence source. | |
660 | * e - Escape bonus. Used together with I to increase the value substantially | |
661 | * if escape influence is being computed. | |
662 | * | |
663 | * Classes A, D, and B are matched with color as O, and it is assumed | |
664 | * that O is in turn to move. Classes E and I are matched with either | |
665 | * color as O. | |
666 | */ | |
667 | static void | |
668 | influence_callback(int anchor, int color, struct pattern *pattern, int ll, | |
669 | void *data) | |
670 | { | |
671 | int pos = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); | |
672 | int k; | |
673 | struct influence_data *q = data; | |
674 | ||
675 | /* We also ignore enhancement patterns in territorial influence. */ | |
676 | if ((pattern->class & CLASS_E) && q->is_territorial_influence) | |
677 | return; | |
678 | ||
679 | /* Don't use invasion (I) patterns when scoring. */ | |
680 | if (doing_scoring && (pattern->class & CLASS_I)) | |
681 | return; | |
682 | ||
683 | /* Loop through pattern elements to see if an A or D pattern | |
684 | * can possibly have any effect. If not we can skip evaluating | |
685 | * constraint and/or helper. | |
686 | */ | |
687 | if (pattern->class & (CLASS_A | CLASS_D)) { | |
688 | int something_to_do = 0; | |
689 | gg_assert(q->is_territorial_influence); | |
690 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ | |
691 | int blocking_color; | |
692 | int ii; | |
693 | /* The order of elements is: All commas, all "!", then other. */ | |
694 | if (pattern->patn[k].att != ATT_comma | |
695 | && pattern->patn[k].att != ATT_not) | |
696 | break; | |
697 | ||
698 | ii = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); | |
699 | ||
700 | if (pattern->class & CLASS_D) | |
701 | blocking_color = color; | |
702 | else | |
703 | blocking_color = OTHER_COLOR(color); | |
704 | if ((blocking_color == WHITE | |
705 | && q->black_permeability[ii] != 0.0) | |
706 | || (blocking_color == BLACK | |
707 | && q->white_permeability[ii] != 0.0)) { | |
708 | something_to_do = 1; | |
709 | break; | |
710 | } | |
711 | } | |
712 | if (!something_to_do) | |
713 | return; | |
714 | } | |
715 | ||
716 | /* Require that all O stones in the pattern have non-zero influence | |
717 | * strength for patterns of type D, E, B, t, and all X stones have | |
718 | * non-zero strength for patterns of type A and t. | |
719 | * | |
720 | * Patterns also having class s are an exception from this rule. | |
721 | */ | |
722 | if ((pattern->class & (CLASS_D | CLASS_A | CLASS_B | CLASS_E | CLASS_t)) | |
723 | && !(pattern->class & CLASS_s)) { | |
724 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ | |
725 | int ii = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); | |
726 | if (pattern->patn[k].att == ATT_O) { | |
727 | if ((pattern->class & (CLASS_B | CLASS_t | CLASS_E | CLASS_D)) | |
728 | && ((color == WHITE && q->white_strength[ii] == 0.0) | |
729 | || (color == BLACK && q->black_strength[ii] == 0.0))) | |
730 | return; | |
731 | } | |
732 | else if (pattern->patn[k].att == ATT_X) { | |
733 | if ((pattern->class & (CLASS_A | CLASS_t)) | |
734 | && ((color == BLACK && q->white_strength[ii] == 0.0) | |
735 | || (color == WHITE && q->black_strength[ii] == 0.0))) | |
736 | return; /* Match failed. */ | |
737 | } | |
738 | } | |
739 | } | |
740 | ||
741 | /* If the pattern has a constraint, call the autohelper to see | |
742 | * if the pattern must be rejected. | |
743 | */ | |
744 | if ((pattern->autohelper_flag & HAVE_CONSTRAINT) | |
745 | && !pattern->autohelper(ll, pos, color, 0)) | |
746 | return; | |
747 | ||
748 | DEBUG(DEBUG_INFLUENCE, "influence pattern '%s'+%d matched at %1m\n", | |
749 | pattern->name, ll, anchor); | |
750 | ||
751 | /* For t patterns, everything happens in the action. */ | |
752 | if ((pattern->class & CLASS_t) | |
753 | && (pattern->autohelper_flag & HAVE_ACTION)) { | |
754 | pattern->autohelper(ll, pos, color, INFLUENCE_CALLBACK); | |
755 | return; | |
756 | } | |
757 | ||
758 | /* For I patterns, add a low intensity, both colored, influence | |
759 | * source at *. | |
760 | */ | |
761 | if (pattern->class & CLASS_I) { | |
762 | int this_color = EMPTY; | |
763 | float strength; | |
764 | float attenuation; | |
765 | ||
766 | if (q->color_to_move == EMPTY || (pattern->class & CLASS_s)) | |
767 | this_color = BLACK | WHITE; | |
768 | else if (q->color_to_move != color) | |
769 | this_color = q->color_to_move; | |
770 | ||
771 | if (cosmic_gnugo) { | |
772 | float t = 0.15 + (1.0 - cosmic_importance); | |
773 | t = gg_min(1.0, t); | |
774 | t = gg_max(0.0, t); | |
775 | strength = t * pattern->value; | |
776 | attenuation = 1.6; | |
777 | } | |
778 | else { | |
779 | strength = pattern->value; | |
780 | attenuation = 1.5; | |
781 | } | |
782 | ||
783 | /* Increase strength if we're computing escape influence. */ | |
784 | if (!q->is_territorial_influence && (pattern->class & CLASS_e)) | |
785 | add_influence_source(pos, this_color, 20 * strength, attenuation, q); | |
786 | else | |
787 | add_influence_source(pos, this_color, strength, attenuation, q); | |
788 | ||
789 | DEBUG(DEBUG_INFLUENCE, | |
790 | " low intensity influence source at %1m, strength %f, color %C\n", | |
791 | pos, strength, this_color); | |
792 | return; | |
793 | } | |
794 | ||
795 | /* For E patterns, add a new influence source of the same color and | |
796 | * pattern defined strength at *. | |
797 | */ | |
798 | if (pattern->class & CLASS_E) { | |
799 | add_influence_source(pos, color, pattern->value, DEFAULT_ATTENUATION, q); | |
800 | DEBUG(DEBUG_INFLUENCE, | |
801 | " extra %C source at %1m, strength %f\n", color, | |
802 | pos, pattern->value); | |
803 | return; | |
804 | } | |
805 | ||
806 | /* For B patterns add intrusions sources at "!" points. */ | |
807 | if (pattern->class & CLASS_B) { | |
808 | float strength; | |
809 | if (cosmic_gnugo) { | |
810 | float t = 0.15 + (1.0 - cosmic_importance); | |
811 | t = gg_min(1.0, t); | |
812 | t = gg_max(0.0, t); | |
813 | strength = t * pattern->value; | |
814 | } | |
815 | else | |
816 | strength = pattern->value; | |
817 | ||
818 | for (k = 0; k < pattern->patlen; ++k) /* match each point */ | |
819 | if (pattern->patn[k].att == ATT_not) { | |
820 | /* transform pattern real coordinate */ | |
821 | int ii = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); | |
822 | ||
823 | /* Low intensity influence source for the color in turn to move. */ | |
824 | if (q->is_territorial_influence) | |
825 | enter_intrusion_source(anchor, ii, strength, | |
826 | TERR_DEFAULT_ATTENUATION, q); | |
827 | else | |
828 | add_influence_source(ii, color, strength, DEFAULT_ATTENUATION, q); | |
829 | DEBUG(DEBUG_INFLUENCE, " intrusion at %1m\n", ii); | |
830 | } | |
831 | return; | |
832 | } | |
833 | ||
834 | ||
835 | gg_assert(pattern->class & (CLASS_D | CLASS_A)); | |
836 | /* For A, D patterns, add blocks for all "," or "!" points. */ | |
837 | for (k = 0; k < pattern->patlen; ++k) { /* match each point */ | |
838 | if (pattern->patn[k].att == ATT_comma | |
839 | || pattern->patn[k].att == ATT_not) { | |
840 | /* transform pattern real coordinate */ | |
841 | int ii = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); | |
842 | int blocking_color; | |
843 | if (pattern->class & CLASS_D) | |
844 | blocking_color = color; | |
845 | else | |
846 | blocking_color = OTHER_COLOR(color); | |
847 | DEBUG(DEBUG_INFLUENCE, " barrier for %s influence at %1m\n", | |
848 | color_to_string(OTHER_COLOR(blocking_color)), ii); | |
849 | if (pattern->patn[k].att == ATT_comma) { | |
850 | if (blocking_color == WHITE) | |
851 | q->black_permeability[ii] = 0.0; | |
852 | else | |
853 | q->white_permeability[ii] = 0.0; | |
854 | } | |
855 | /* Weak barrier at !-marked points. */ | |
856 | else { | |
857 | if (blocking_color == WHITE) | |
858 | q->black_permeability[ii] *= 0.7; | |
859 | else | |
860 | q->white_permeability[ii] *= 0.7; | |
861 | ||
862 | } | |
863 | } | |
864 | } | |
865 | } | |
866 | ||
867 | /* Callback for matched barriers patterns in followup influence. | |
868 | * This adds an intrusion source for all B patterns in barriers.db for | |
869 | * the color that has made a move if all the following conditions are | |
870 | * fulfilled: | |
871 | * - the anchor ("Q") is adjacent (directly or diagonally) to a "saved stone" | |
872 | * (this is ensured by matchpat before calling back here) | |
873 | * - at least one of the O stones in the pattern is a saved stone. | |
874 | * - the usual pattern constraint ("; oplay_attack_either(...)") is fulfilled | |
875 | * - the pattern action (typically ">return (!xplay_attack(...))") returns | |
876 | * true if called with parameter action = FOLLOWUP_INFLUENCE_CALLBACK. | |
877 | * "Saved stones" are: the move played + tactically rescued stones + stones | |
878 | * in a critcal dragon brought to life by this move | |
879 | */ | |
880 | static void | |
881 | followup_influence_callback(int anchor, int color, struct pattern *pattern, | |
882 | int ll, void *data) | |
883 | { | |
884 | int k; | |
885 | int t; | |
886 | struct influence_data *q = data; | |
887 | UNUSED(color); | |
888 | ||
889 | /* We use only B patterns in followup influence. */ | |
890 | if (!(pattern->class & CLASS_B)) | |
891 | return; | |
892 | ||
893 | t = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); | |
894 | ||
895 | /* If the pattern has a constraint, call the autohelper to see | |
896 | * if the pattern must be rejected. | |
897 | */ | |
898 | if (pattern->autohelper_flag & HAVE_CONSTRAINT | |
899 | && !pattern->autohelper(ll, t, color, 0)) | |
900 | return; | |
901 | ||
902 | /* Actions in B patterns are used as followup specific constraints. */ | |
903 | if ((pattern->autohelper_flag & HAVE_ACTION) | |
904 | && !pattern->autohelper(ll, t, color, FOLLOWUP_INFLUENCE_CALLBACK)) | |
905 | return; | |
906 | ||
907 | DEBUG(DEBUG_INFLUENCE, "influence pattern '%s'+%d matched at %1m\n", | |
908 | pattern->name, ll, anchor); | |
909 | ||
910 | for (k = 0; k < pattern->patlen; ++k) /* match each point */ | |
911 | if (pattern->patn[k].att == ATT_not) { | |
912 | /* transform pattern real coordinate */ | |
913 | int ii = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); | |
914 | ||
915 | /* Low intensity influence source for the color in turn to move. */ | |
916 | enter_intrusion_source(anchor, ii, pattern->value, | |
917 | TERR_DEFAULT_ATTENUATION, q); | |
918 | DEBUG(DEBUG_INFLUENCE, " followup for %1m: intrusion at %1m\n", | |
919 | anchor, ii); | |
920 | } | |
921 | } | |
922 | ||
923 | /* Called from actions for t patterns. Marks (pos) as not being | |
924 | * territory for (color). | |
925 | */ | |
926 | void | |
927 | influence_mark_non_territory(int pos, int color) | |
928 | { | |
929 | DEBUG(DEBUG_INFLUENCE, " non-territory for %C at %1m\n", color, pos); | |
930 | current_influence->non_territory[pos] |= color; | |
931 | } | |
932 | ||
933 | /* Erases all territory for color at (pos), and all directly neighboring | |
934 | * fields. | |
935 | */ | |
936 | void | |
937 | influence_erase_territory(struct influence_data *q, int pos, int color) | |
938 | { | |
939 | int k; | |
940 | ASSERT1((color == WHITE && q->territory_value[pos] >= 0.0) | |
941 | || (color == BLACK && q->territory_value[pos] <= 0.0), pos); | |
942 | ||
943 | current_influence = q; | |
944 | ||
945 | q->territory_value[pos] = 0.0; | |
946 | influence_mark_non_territory(pos, color); | |
947 | for (k = 0; k < 4; k++) { | |
948 | if (ON_BOARD(pos + delta[k])) { | |
949 | q->territory_value[pos + delta[k]] = 0.0; | |
950 | influence_mark_non_territory(pos + delta[k], color); | |
951 | } | |
952 | } | |
953 | } | |
954 | ||
955 | /* Match the patterns in influence.db and barriers.db in order to add: | |
956 | * - influence barriers, | |
957 | * - extra influence sources at possible invasion and intrusion points, and | |
958 | * - extra influence induced by strong positions. | |
959 | * Reduce permeability around each living stone. | |
960 | * Reset permeability to 1.0 at intrusion points. | |
961 | */ | |
962 | static void | |
963 | find_influence_patterns(struct influence_data *q) | |
964 | { | |
965 | int ii; | |
966 | ||
967 | current_influence = q; | |
968 | matchpat(influence_callback, ANCHOR_COLOR, &influencepat_db, q, NULL); | |
969 | if (q->color_to_move != EMPTY) | |
970 | matchpat(influence_callback, q->color_to_move, &barrierspat_db, q, NULL); | |
971 | ||
972 | if (q->is_territorial_influence) | |
973 | add_marked_intrusions(q); | |
974 | ||
975 | /* Additionally, we introduce a weaker kind of barriers around living | |
976 | * stones. | |
977 | */ | |
978 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
979 | if (ON_BOARD(ii) && !q->safe[ii]) { | |
980 | int k; | |
981 | float black_reduction = 1.0; | |
982 | float white_reduction = 1.0; | |
983 | for (k = 0; k < 8; k++) { | |
984 | int d = delta[k]; | |
985 | if (IS_STONE(board[ii + d]) && q->safe[ii + d]) { | |
986 | /* Reduce less diagonally. */ | |
987 | float reduction = (k < 4) ? 0.25 : 0.65; | |
988 | if (board[ii + d] == BLACK) | |
989 | white_reduction *= reduction; | |
990 | else | |
991 | black_reduction *= reduction; | |
992 | } | |
993 | else if (IS_STONE(board[ii + d]) && !q->safe[ii + d]) { | |
994 | if (board[ii + d] == BLACK) | |
995 | white_reduction = -100.0; | |
996 | else | |
997 | black_reduction = -100.0; | |
998 | } | |
999 | } | |
1000 | if (black_reduction > 0.0) | |
1001 | q->black_permeability[ii] *= black_reduction; | |
1002 | if (white_reduction > 0.0) | |
1003 | q->white_permeability[ii] *= white_reduction; | |
1004 | } | |
1005 | ||
1006 | reset_unblocked_blocks(q); | |
1007 | } | |
1008 | ||
1009 | /* This function checks whether we have two or more adjacent blocks for | |
1010 | * influence of color next to pos. If yes, it returns the position of the | |
1011 | * least valuable blocks; otherwise, it returns NO_MOVE. | |
1012 | */ | |
1013 | static int | |
1014 | check_double_block(int color, int pos, const struct influence_data *q) | |
1015 | { | |
1016 | int k; | |
1017 | int block_neighbors = 0; | |
1018 | const float *permeability = ((color == BLACK) ? q->black_permeability : | |
1019 | q->white_permeability); | |
1020 | ||
1021 | /* Count neighboring blocks. */ | |
1022 | for (k = 0; k < 4; k++) | |
1023 | if (board[pos + delta[k]] == EMPTY && permeability[pos + delta[k]] == 0.0) | |
1024 | block_neighbors++; | |
1025 | ||
1026 | if (block_neighbors >= 2) { | |
1027 | /* Search for least valuable block. */ | |
1028 | float smallest_value = 4.0 * MAX_BOARD * MAX_BOARD; | |
1029 | int smallest_block = NO_MOVE; | |
1030 | /* We count opponent's territory as positive. */ | |
1031 | float sign = ((color == WHITE) ? -1.0 : 1.0); | |
1032 | for (k = 0; k < 4; k++) { | |
1033 | int neighbor = pos + delta[k]; | |
1034 | if (board[neighbor] == EMPTY && permeability[neighbor] == 0.0) { | |
1035 | /* Value is sum of opponents territory at this and all 4 neighboring | |
1036 | * intersections. | |
1037 | */ | |
1038 | float this_value = sign * q->territory_value[neighbor]; | |
1039 | int j; | |
1040 | for (j = 0; j < 4; j++) | |
1041 | if (ON_BOARD(neighbor + delta[j])) | |
1042 | this_value += sign * q->territory_value[neighbor + delta[j]]; | |
1043 | /* We use an artifical tie breaker to avoid possible platform | |
1044 | * dependency. | |
1045 | */ | |
1046 | if (this_value + 0.0005 < smallest_value) { | |
1047 | smallest_block = neighbor; | |
1048 | smallest_value = this_value; | |
1049 | } | |
1050 | } | |
1051 | } | |
1052 | ASSERT1(ON_BOARD1(smallest_block), pos); | |
1053 | return smallest_block; | |
1054 | } | |
1055 | return NO_MOVE; | |
1056 | } | |
1057 | ||
1058 | #define MAX_DOUBLE_BLOCKS 20 | |
1059 | ||
1060 | ||
1061 | /* This function checks for the situation where an influence source for | |
1062 | * the color to move is direclty neighbored by 2 or more influence blocks. | |
1063 | * It then removes the least valuable of these blocks, and re-runs the | |
1064 | * influence accumulation for this position. | |
1065 | * | |
1066 | * See endgame:840 for an example where this is essential. | |
1067 | */ | |
1068 | static void | |
1069 | remove_double_blocks(struct influence_data *q, | |
1070 | const signed char inhibited_sources[BOARDMAX]) | |
1071 | { | |
1072 | int ii; | |
1073 | float *strength = ((q->color_to_move == WHITE) ? q->white_strength : | |
1074 | q->black_strength); | |
1075 | int double_blocks[MAX_DOUBLE_BLOCKS]; | |
1076 | int num_blocks = 0; | |
1077 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1078 | if (board[ii] == EMPTY | |
1079 | && !(inhibited_sources && inhibited_sources[ii]) | |
1080 | && strength[ii] > 0.0) { | |
1081 | double_blocks[num_blocks] = check_double_block(q->color_to_move, ii, q); | |
1082 | if (double_blocks[num_blocks] != NO_MOVE) { | |
1083 | num_blocks++; | |
1084 | if (num_blocks == MAX_DOUBLE_BLOCKS) | |
1085 | break; | |
1086 | } | |
1087 | } | |
1088 | { | |
1089 | int k; | |
1090 | float *permeability = ((q->color_to_move == BLACK) | |
1091 | ? q->black_permeability : q->white_permeability); | |
1092 | for (k = 0; k < num_blocks; k++) { | |
1093 | DEBUG(DEBUG_INFLUENCE, "Removing block for %s at %1m.\n", | |
1094 | color_to_string(q->color_to_move), double_blocks[k]); | |
1095 | permeability[double_blocks[k]] = 1.0; | |
1096 | accumulate_influence(q, double_blocks[k], q->color_to_move); | |
1097 | } | |
1098 | } | |
1099 | } | |
1100 | ||
1101 | ||
1102 | /* Do the real work of influence computation. This is called from | |
1103 | * compute_influence and compute_escape_influence. | |
1104 | * | |
1105 | * q->is_territorial_influence and q->color_to_move must be set by the caller. | |
1106 | */ | |
1107 | static void | |
1108 | do_compute_influence(const signed char safe_stones[BOARDMAX], | |
1109 | const signed char inhibited_sources[BOARDMAX], | |
1110 | const float strength[BOARDMAX], struct influence_data *q, | |
1111 | int move, const char *trace_message) | |
1112 | { | |
1113 | int ii; | |
1114 | init_influence(q, safe_stones, strength); | |
1115 | ||
1116 | modify_depth_values(stackp - 1); | |
1117 | find_influence_patterns(q); | |
1118 | modify_depth_values(1 - stackp); | |
1119 | ||
1120 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1121 | if (ON_BOARD(ii) && !(inhibited_sources && inhibited_sources[ii])) { | |
1122 | if (q->white_strength[ii] > 0.0) | |
1123 | accumulate_influence(q, ii, WHITE); | |
1124 | if (q->black_strength[ii] > 0.0) | |
1125 | accumulate_influence(q, ii, BLACK); | |
1126 | } | |
1127 | ||
1128 | value_territory(q); | |
1129 | remove_double_blocks(q, inhibited_sources); | |
1130 | ||
1131 | value_territory(q); | |
1132 | ||
1133 | if ((move == NO_MOVE | |
1134 | && (printmoyo & PRINTMOYO_INITIAL_INFLUENCE)) | |
1135 | || (debug_influence && move == debug_influence)) | |
1136 | print_influence(q, trace_message); | |
1137 | } | |
1138 | ||
1139 | ||
1140 | /* Compute the influence values for both colors. | |
1141 | * | |
1142 | * The caller must | |
1143 | * - set up the board[] state | |
1144 | * - mark safe stones with INFLUENCE_SAFE_STONE, dead stones with 0 | |
1145 | * - mark stones newly saved by a move with INFLUENCE_SAVED_STONE | |
1146 | * (this is relevant if the influence_data *q is reused to compute | |
1147 | * a followup value for this move). | |
1148 | * | |
1149 | * Results will be stored in q. | |
1150 | * | |
1151 | * (move) has no effects except toggling debugging. Set it to -1 | |
1152 | * for no debug output at all (otherwise it will be controlled by | |
1153 | * the -m command line option). | |
1154 | * | |
1155 | * It is assumed that color is in turn to move. (This affects the | |
1156 | * barrier patterns (class A, D) and intrusions (class B)). Color | |
1157 | */ | |
1158 | ||
1159 | void | |
1160 | compute_influence(int color, const signed char safe_stones[BOARDMAX], | |
1161 | const float strength[BOARDMAX], struct influence_data *q, | |
1162 | int move, const char *trace_message) | |
1163 | { | |
1164 | int save_debug = debug; | |
1165 | VALGRIND_MAKE_WRITABLE(q, sizeof(*q)); | |
1166 | ||
1167 | q->is_territorial_influence = 1; | |
1168 | q->color_to_move = color; | |
1169 | ||
1170 | /* Turn off DEBUG_INFLUENCE for influence computations we are not | |
1171 | * interested in. | |
1172 | */ | |
1173 | if ((move == NO_MOVE | |
1174 | && !(printmoyo & PRINTMOYO_INITIAL_INFLUENCE)) | |
1175 | || (move != NO_MOVE && move != debug_influence)) | |
1176 | debug = debug &~ DEBUG_INFLUENCE; | |
1177 | ||
1178 | influence_id++; | |
1179 | q->id = influence_id; | |
1180 | ||
1181 | do_compute_influence(safe_stones, NULL, strength, | |
1182 | q, move, trace_message); | |
1183 | ||
1184 | debug = save_debug; | |
1185 | } | |
1186 | ||
1187 | /* Return the color of the territory at (pos). If it's territory for | |
1188 | * neither color, EMPTY is returned. | |
1189 | */ | |
1190 | int | |
1191 | whose_territory(const struct influence_data *q, int pos) | |
1192 | { | |
1193 | float bi = q->black_influence[pos]; | |
1194 | float wi = q->white_influence[pos]; | |
1195 | float terr = q->territory_value[pos]; | |
1196 | ||
1197 | ASSERT_ON_BOARD1(pos); | |
1198 | ||
1199 | if (bi > 0.0 && wi == 0.0 && terr < -territory_determination_value) | |
1200 | return BLACK; | |
1201 | if (wi > 0.0 && bi == 0.0 && terr > territory_determination_value) | |
1202 | return WHITE; | |
1203 | ||
1204 | return EMPTY; | |
1205 | } | |
1206 | ||
1207 | ||
1208 | /* Return the color who has a moyo at (pos). If neither color has a | |
1209 | * moyo there, EMPTY is returned. The definition of moyo in terms of the | |
1210 | * influences is totally ad hoc. | |
1211 | */ | |
1212 | int | |
1213 | whose_moyo(const struct influence_data *q, int pos) | |
1214 | { | |
1215 | float bi = q->black_influence[pos]; | |
1216 | float wi = q->white_influence[pos]; | |
1217 | ||
1218 | int territory_color = whose_territory(q, pos); | |
1219 | if (territory_color != EMPTY) | |
1220 | return territory_color; | |
1221 | ||
1222 | if (bi > moyo_data.influence_balance * wi | |
1223 | && bi > moyo_data.my_influence_minimum | |
1224 | && wi < moyo_data.opp_influence_maximum) | |
1225 | return BLACK; | |
1226 | if (wi > moyo_data.influence_balance * bi | |
1227 | && wi > moyo_data.my_influence_minimum | |
1228 | && bi < moyo_data.opp_influence_maximum) | |
1229 | return WHITE; | |
1230 | ||
1231 | return EMPTY; | |
1232 | } | |
1233 | ||
1234 | /* Return the color who has a moyo at (pos). If neither color has a | |
1235 | * moyo there, EMPTY is returned. | |
1236 | * The definition of moyo in terms of the influences is totally ad | |
1237 | * hoc. | |
1238 | * | |
1239 | * It has a slightly different definition of moyo than whose_moyo. | |
1240 | */ | |
1241 | int | |
1242 | whose_moyo_restricted(const struct influence_data *q, int pos) | |
1243 | { | |
1244 | float bi = q->black_influence[pos]; | |
1245 | float wi = q->white_influence[pos]; | |
1246 | ||
1247 | int territory_color = whose_territory(q, pos); | |
1248 | ||
1249 | /* default */ | |
1250 | if (territory_color != EMPTY) | |
1251 | return territory_color; | |
1252 | else if (bi > moyo_restricted_data.influence_balance * wi | |
1253 | && bi > moyo_restricted_data.my_influence_minimum | |
1254 | && wi < moyo_restricted_data.opp_influence_maximum) | |
1255 | return BLACK; | |
1256 | else if (wi > moyo_restricted_data.influence_balance * bi | |
1257 | && wi > moyo_restricted_data.my_influence_minimum | |
1258 | && bi < moyo_restricted_data.opp_influence_maximum) | |
1259 | return WHITE; | |
1260 | else | |
1261 | return EMPTY; | |
1262 | } | |
1263 | ||
1264 | ||
1265 | /* Return the color who has dominating influence ("area") at (pos). | |
1266 | * If neither color dominates the influence there, EMPTY is returned. | |
1267 | * The definition of area in terms of the influences is totally ad | |
1268 | * hoc. | |
1269 | */ | |
1270 | int | |
1271 | whose_area(const struct influence_data *q, int pos) | |
1272 | { | |
1273 | float bi = q->black_influence[pos]; | |
1274 | float wi = q->white_influence[pos]; | |
1275 | ||
1276 | int moyo_color = whose_moyo(q, pos); | |
1277 | if (moyo_color != EMPTY) | |
1278 | return moyo_color; | |
1279 | ||
1280 | if (bi > 3.0 * wi && bi > 1.0 && wi < 40.0) | |
1281 | return BLACK; | |
1282 | ||
1283 | if (wi > 3.0 * bi && wi > 1.0 && bi < 40.0) | |
1284 | return WHITE; | |
1285 | ||
1286 | return EMPTY; | |
1287 | } | |
1288 | ||
1289 | ||
1290 | static void | |
1291 | value_territory(struct influence_data *q) | |
1292 | { | |
1293 | int ii; | |
1294 | int dist_i, dist_j; | |
1295 | float central; | |
1296 | float first_guess[BOARDMAX]; | |
1297 | float ratio; | |
1298 | int k; | |
1299 | ||
1300 | memset(first_guess, 0, BOARDMAX*sizeof(float)); | |
1301 | memset(q->territory_value, 0, BOARDMAX*sizeof(float)); | |
1302 | /* First loop: guess territory directly from influence. */ | |
1303 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1304 | if (ON_BOARD(ii) | |
1305 | && !q->safe[ii]) { | |
1306 | float diff = 0.0; | |
1307 | if (q->white_influence[ii] + q->black_influence[ii] > 0) | |
1308 | diff = (q->white_influence[ii] - q->black_influence[ii]) | |
1309 | / (q->white_influence[ii] + q->black_influence[ii]); | |
1310 | first_guess[ii] = diff * diff * diff; | |
1311 | ||
1312 | /* If both side have small influence, we have to reduce this value. | |
1313 | * What we consider "small influence" depends on how central this | |
1314 | * intersection lies. | |
1315 | * | |
1316 | * The values of central on an 11x11 board become: | |
1317 | * | |
1318 | * 4 5 6 7 7 7 7 7 6 5 4 | |
1319 | * 5 8 9 10 10 10 10 10 9 8 5 | |
1320 | * 6 9 12 13 13 13 13 13 12 9 6 | |
1321 | * 7 10 13 16 16 16 16 16 13 10 7 | |
1322 | * 7 10 13 16 17 17 17 16 13 10 7 | |
1323 | * 7 10 13 16 17 18 17 16 13 10 7 | |
1324 | * 7 10 13 16 17 17 17 16 13 10 7 | |
1325 | * 7 10 13 16 16 16 16 16 13 10 7 | |
1326 | * 6 9 12 13 13 13 13 13 12 9 6 | |
1327 | * 5 8 9 10 10 10 10 10 9 8 5 | |
1328 | * 4 5 6 7 7 7 7 7 6 5 4 | |
1329 | */ | |
1330 | dist_i = gg_min(I(ii), board_size - I(ii) - 1); | |
1331 | dist_j = gg_min(J(ii), board_size - J(ii) - 1); | |
1332 | if (dist_i > dist_j) | |
1333 | dist_i = gg_min(4, dist_i); | |
1334 | else | |
1335 | dist_j = gg_min(4, dist_j); | |
1336 | central = (float) 2 * gg_min(dist_i, dist_j) + dist_i + dist_j; | |
1337 | ratio = gg_max(q->black_influence[ii], q->white_influence[ii]) | |
1338 | / gg_interpolate(&min_infl_for_territory, central); | |
1339 | ||
1340 | /* Do not make this adjustment when scoring unless both | |
1341 | * players have non-zero influence. | |
1342 | */ | |
1343 | if (doing_scoring && (q->black_influence[ii] == 0.0 | |
1344 | || q->white_influence[ii] == 0.0)) | |
1345 | ratio = 1.0; | |
1346 | ||
1347 | first_guess[ii] *= gg_interpolate(&territory_correction, ratio); | |
1348 | ||
1349 | /* Dead stone, upgrade to territory. Notice that this is not | |
1350 | * the point for a prisoner, which is added later. Instead | |
1351 | * this is to make sure that the vertex is not regarded as | |
1352 | * moyo or area. Also notice that the non-territory | |
1353 | * degradation below may over-rule this decision. | |
1354 | */ | |
1355 | if (board[ii] == BLACK) | |
1356 | first_guess[ii] = 1.0; | |
1357 | else if (board[ii] == WHITE) | |
1358 | first_guess[ii] = -1.0; | |
1359 | q->territory_value[ii] = first_guess[ii]; | |
1360 | } | |
1361 | ||
1362 | /* Second loop: Correct according to neighbour vertices. Each territory | |
1363 | * value is degraded to the minimum value of its neighbors (unless this | |
1364 | * neighbor has reduced permeability for the opponent's influence). | |
1365 | */ | |
1366 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1367 | if (ON_BOARD(ii) | |
1368 | /* Do not overrule dead stone territory above. | |
1369 | * FIXME: This does not do what it claims to do. Correcting it | |
1370 | * seems to break some tests, though. | |
1371 | */ | |
1372 | && !q->safe[ii]) { | |
1373 | /* Loop over all neighbors. */ | |
1374 | for (k = 0; k < 4; k++) { | |
1375 | if (!ON_BOARD(ii + delta[k])) | |
1376 | continue; | |
1377 | if (q->territory_value[ii] > 0.0) { | |
1378 | /* White territory. */ | |
1379 | if (!q->safe[ii + delta[k]]) { | |
1380 | float neighbor_val = | |
1381 | q->black_permeability[ii + delta[k]] | |
1382 | * first_guess[ii + delta[k]] | |
1383 | + (1.0 - q->black_permeability[ii + delta[k]]) | |
1384 | * first_guess[ii]; | |
1385 | q->territory_value[ii] | |
1386 | = gg_max(0, gg_min(q->territory_value[ii], neighbor_val)); | |
1387 | } | |
1388 | } | |
1389 | else { | |
1390 | /* Black territory. */ | |
1391 | if (!q->safe[ii + delta[k]]) { | |
1392 | float neighbor_val = | |
1393 | q->white_permeability[ii + delta[k]] | |
1394 | * first_guess[ii + delta[k]] | |
1395 | + (1 - q->white_permeability[ii + delta[k]]) | |
1396 | * first_guess[ii]; | |
1397 | q->territory_value[ii] | |
1398 | = gg_min(0, gg_max(q->territory_value[ii], neighbor_val)); | |
1399 | } | |
1400 | } | |
1401 | } | |
1402 | } | |
1403 | ||
1404 | /* Third loop: Nonterritory patterns, points for prisoners. */ | |
1405 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1406 | if (ON_BOARD(ii) | |
1407 | && !q->safe[ii]) { | |
1408 | /* If marked as non-territory for the color currently owning | |
1409 | * it, reset the territory value. | |
1410 | */ | |
1411 | if (q->territory_value[ii] > 0.0 | |
1412 | && (q->non_territory[ii] & WHITE)) | |
1413 | q->territory_value[ii] = 0.0; | |
1414 | ||
1415 | if (q->territory_value[ii] < 0.0 | |
1416 | && (q->non_territory[ii] & BLACK)) | |
1417 | q->territory_value[ii] = 0.0; | |
1418 | ||
1419 | /* Dead stone, add one to the territory value. */ | |
1420 | if (board[ii] == BLACK) | |
1421 | q->territory_value[ii] += 1.0; | |
1422 | else if (board[ii] == WHITE) | |
1423 | q->territory_value[ii] -= 1.0; | |
1424 | } | |
1425 | } | |
1426 | ||
1427 | ||
1428 | /* Segment the influence map into connected regions of territory, | |
1429 | * moyo, or area. What to segment on is determined by the the function | |
1430 | * pointer region_owner. The segmentation is performed for both | |
1431 | * colors. The connected regions may include stones of the own color, | |
1432 | * but only empty intersections (and dead opponent stones) count | |
1433 | * toward the region size. | |
1434 | */ | |
1435 | static void | |
1436 | segment_region(struct influence_data *q, owner_function_ptr region_owner, | |
1437 | struct moyo_data *regions) | |
1438 | { | |
1439 | int ii; | |
1440 | static signed char marked[BOARDMAX]; | |
1441 | regions->number = 0; | |
1442 | ||
1443 | /* Reset the markings. */ | |
1444 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
1445 | marked[ii] = 0; | |
1446 | regions->segmentation[ii] = 0; | |
1447 | } | |
1448 | ||
1449 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1450 | if (ON_BOARD(ii) | |
1451 | && !marked[ii] | |
1452 | && region_owner(q, ii) != EMPTY) { | |
1453 | /* Found an unlabelled intersection. Use flood filling to find | |
1454 | * the rest of the region. | |
1455 | */ | |
1456 | int size = 0; | |
1457 | float terr_val = 0.0; | |
1458 | int queue_start = 0; | |
1459 | int queue_end = 1; | |
1460 | int color = region_owner(q, ii); | |
1461 | regions->number++; | |
1462 | marked[ii] = 1; | |
1463 | q->queue[0] = ii; | |
1464 | while (queue_start < queue_end) { | |
1465 | int tt = q->queue[queue_start]; | |
1466 | int k; | |
1467 | queue_start++; | |
1468 | if (!q->safe[tt] || board[tt] != color) { | |
1469 | size++; | |
1470 | if (q->is_territorial_influence) | |
1471 | terr_val += gg_abs(q->territory_value[tt]); | |
1472 | } | |
1473 | regions->segmentation[tt] = regions->number; | |
1474 | for (k = 0; k < 4; k++) { | |
1475 | int d = delta[k]; | |
1476 | if (ON_BOARD(tt + d) | |
1477 | && !marked[tt + d] | |
1478 | && region_owner(q, tt + d) == color) { | |
1479 | q->queue[queue_end] = tt + d; | |
1480 | queue_end++; | |
1481 | marked[tt + d] = 1; | |
1482 | } | |
1483 | } | |
1484 | } | |
1485 | regions->size[regions->number] = size; | |
1486 | regions->territorial_value[regions->number] = terr_val; | |
1487 | regions->owner[regions->number] = color; | |
1488 | } | |
1489 | } | |
1490 | ||
1491 | ||
1492 | ||
1493 | /* Export a territory segmentation. */ | |
1494 | void | |
1495 | influence_get_territory_segmentation(struct influence_data *q, | |
1496 | struct moyo_data *moyos) | |
1497 | { | |
1498 | segment_region(q, whose_territory, moyos); | |
1499 | } | |
1500 | ||
1501 | ||
1502 | /* Export the territory valuation at an intersection from initial_influence; | |
1503 | * it is given from (color)'s point of view. | |
1504 | */ | |
1505 | float | |
1506 | influence_territory(const struct influence_data *q, int pos, int color) | |
1507 | { | |
1508 | if (color == WHITE) | |
1509 | return q->territory_value[pos]; | |
1510 | else | |
1511 | return -q->territory_value[pos]; | |
1512 | } | |
1513 | ||
1514 | int | |
1515 | influence_considered_lively(const struct influence_data *q, int pos) | |
1516 | { | |
1517 | int color = board[pos]; | |
1518 | ASSERT1(IS_STONE(color), pos); | |
1519 | return (q->safe[pos] | |
1520 | && ((color == WHITE && q->white_strength[pos] > 0) | |
1521 | || (color == BLACK && q->black_strength[pos] > 0))); | |
1522 | } | |
1523 | ||
1524 | ||
1525 | /* Compute a followup influence. It is assumed that the stones that | |
1526 | * deserve a followup have been marked INFLUENCE_SAVED_STONE in | |
1527 | * base->safe. | |
1528 | */ | |
1529 | void | |
1530 | compute_followup_influence(const struct influence_data *base, | |
1531 | struct influence_data *q, | |
1532 | int move, const char *trace_message) | |
1533 | { | |
1534 | int ii; | |
1535 | signed char goal[BOARDMAX]; | |
1536 | /* This is the color that will get a followup value. */ | |
1537 | int color = OTHER_COLOR(base->color_to_move); | |
1538 | int save_debug = debug; | |
1539 | ||
1540 | memcpy(q, base, sizeof(*q)); | |
1541 | ASSERT1(IS_STONE(q->color_to_move), move); | |
1542 | q->color_to_move = color; | |
1543 | ||
1544 | /* We mark the saved stones and their neighbors in the goal array. | |
1545 | */ | |
1546 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1547 | if (ON_BOARD(ii)) { | |
1548 | if (q->safe[ii] == INFLUENCE_SAVED_STONE) | |
1549 | goal[ii] = 1; | |
1550 | else | |
1551 | goal[ii] = 0; | |
1552 | } | |
1553 | ||
1554 | ||
1555 | /* Turn off DEBUG_INFLUENCE for influence computations we are not | |
1556 | * interested in. | |
1557 | */ | |
1558 | if ((move == NO_MOVE | |
1559 | && !(printmoyo & PRINTMOYO_INITIAL_INFLUENCE)) | |
1560 | || (move != debug_influence)) | |
1561 | debug = debug &~ DEBUG_INFLUENCE; | |
1562 | ||
1563 | q->intrusion_counter = 0; | |
1564 | current_influence = q; | |
1565 | /* Match B patterns for saved stones. */ | |
1566 | matchpat_goal_anchor(followup_influence_callback, color, &barrierspat_db, | |
1567 | q, goal, 1); | |
1568 | ||
1569 | debug = save_debug; | |
1570 | ||
1571 | /* Now add the intrusions. */ | |
1572 | add_marked_intrusions(q); | |
1573 | ||
1574 | reset_unblocked_blocks(q); | |
1575 | ||
1576 | /* Spread influence for new influence sources. */ | |
1577 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1578 | if (ON_BOARD(ii)) | |
1579 | if ((color == BLACK | |
1580 | && q->black_strength[ii] > base->black_strength[ii]) | |
1581 | || (color == WHITE | |
1582 | && q->white_strength[ii] > base->white_strength[ii])) | |
1583 | accumulate_influence(q, ii, color); | |
1584 | ||
1585 | value_territory(q); | |
1586 | ||
1587 | if (debug_influence && debug_influence == move) | |
1588 | print_influence(q, trace_message); | |
1589 | } | |
1590 | ||
1591 | ||
1592 | /* Compute influence based escape values and return them in the | |
1593 | * escape_value array. | |
1594 | */ | |
1595 | ||
1596 | void | |
1597 | compute_escape_influence(int color, const signed char safe_stones[BOARDMAX], | |
1598 | const signed char goal[BOARDMAX], | |
1599 | const float strength[BOARDMAX], | |
1600 | signed char escape_value[BOARDMAX]) | |
1601 | { | |
1602 | int k; | |
1603 | int ii; | |
1604 | int save_debug = debug; | |
1605 | ||
1606 | /* IMPORTANT: The caching relies on the fact that safe_stones[] and | |
1607 | * strength[] will currently always be identical for identical board[] | |
1608 | * states. Better check for these, too. | |
1609 | */ | |
1610 | static int cached_board[BOARDMAX]; | |
1611 | static signed char escape_values[BOARDMAX][2]; | |
1612 | static int active_caches[2] = {0, 0}; | |
1613 | ||
1614 | int cache_number = (color == WHITE); | |
1615 | ||
1616 | VALGRIND_MAKE_WRITABLE(&escape_influence, sizeof(escape_influence)); | |
1617 | ||
1618 | if (!goal) { | |
1619 | /* Encode the values of color and dragons_known into an integer | |
1620 | * between 0 and 3. | |
1621 | */ | |
1622 | int board_was_cached = 1; | |
1623 | ||
1624 | /* Notice that we compare the out of board markers as well, in | |
1625 | * case the board size should have changed between calls. | |
1626 | */ | |
1627 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
1628 | if (cached_board[ii] != board[ii]) { | |
1629 | cached_board[ii] = board[ii]; | |
1630 | board_was_cached = 0; | |
1631 | } | |
1632 | } | |
1633 | ||
1634 | if (!board_was_cached) | |
1635 | for (k = 0; k < 2; k++) | |
1636 | active_caches[k] = 0; | |
1637 | ||
1638 | if (active_caches[cache_number]) { | |
1639 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1640 | if (ON_BOARD(ii)) | |
1641 | escape_value[ii] = escape_values[ii][cache_number]; | |
1642 | ||
1643 | return; | |
1644 | } | |
1645 | } | |
1646 | ||
1647 | /* Use enhance pattern and higher attenuation for escape influence. */ | |
1648 | escape_influence.is_territorial_influence = 0; | |
1649 | escape_influence.color_to_move = EMPTY; | |
1650 | ||
1651 | /* Turn off DEBUG_INFLUENCE unless we are specifically interested in | |
1652 | * escape computations. | |
1653 | */ | |
1654 | if (!(debug & DEBUG_ESCAPE)) | |
1655 | debug &= ~DEBUG_INFLUENCE; | |
1656 | ||
1657 | do_compute_influence(safe_stones, goal, strength, | |
1658 | &escape_influence, -1, NULL); | |
1659 | ||
1660 | debug = save_debug; | |
1661 | ||
1662 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1663 | if (ON_BOARD(ii)) { | |
1664 | if (whose_moyo(&escape_influence, ii) == color) | |
1665 | escape_value[ii] = 4; | |
1666 | else if (whose_area(&escape_influence, ii) == color) | |
1667 | escape_value[ii] = 2; | |
1668 | else if (whose_area(&escape_influence, ii) == EMPTY) { | |
1669 | if (goal) { | |
1670 | escape_value[ii] = 0; | |
1671 | ||
1672 | if (!goal[ii]) { | |
1673 | int goal_proximity = 0; | |
1674 | ||
1675 | for (k = 0; k < 8; k++) { | |
1676 | if (ON_BOARD(ii + delta[k])) { | |
1677 | goal_proximity += 2 * goal[ii + delta[k]]; | |
1678 | if (k < 4 && ON_BOARD(ii + 2 * delta[k])) | |
1679 | goal_proximity += goal[ii + delta[k]]; | |
1680 | } | |
1681 | else | |
1682 | goal_proximity += 1; | |
1683 | } | |
1684 | ||
1685 | if (goal_proximity < 6) | |
1686 | escape_value[ii] = 1; | |
1687 | } | |
1688 | } | |
1689 | else | |
1690 | escape_value[ii] = 1; | |
1691 | } | |
1692 | else | |
1693 | escape_value[ii] = 0; | |
1694 | } | |
1695 | ||
1696 | if (0 && (debug & DEBUG_ESCAPE) && verbose > 0) | |
1697 | print_influence(&escape_influence, "escape influence"); | |
1698 | ||
1699 | if (!goal) { | |
1700 | /* Save the computed values in the cache. */ | |
1701 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1702 | if (ON_BOARD(ii)) | |
1703 | escape_values[ii][cache_number] = escape_value[ii]; | |
1704 | active_caches[cache_number] = 1; | |
1705 | } | |
1706 | } | |
1707 | ||
1708 | ||
1709 | /* Cache of delta_territory_values. */ | |
1710 | static float delta_territory_cache[BOARDMAX]; | |
1711 | static float followup_territory_cache[BOARDMAX]; | |
1712 | static Hash_data delta_territory_cache_hash[BOARDMAX]; | |
1713 | static int territory_cache_position_number = -1; | |
1714 | static int territory_cache_influence_id = -1; | |
1715 | static int territory_cache_color = -1; | |
1716 | ||
1717 | /* We cache territory computations. This avoids unnecessary re-computations | |
1718 | * when review_move_reasons is run a second time for the endgame patterns. | |
1719 | * | |
1720 | * (*base) points to the initial_influence data that would be used | |
1721 | * to make the territory computation against. | |
1722 | */ | |
1723 | int | |
1724 | retrieve_delta_territory_cache(int pos, int color, float *move_value, | |
1725 | float *followup_value, | |
1726 | const struct influence_data *base, | |
1727 | Hash_data safety_hash) | |
1728 | { | |
1729 | ASSERT_ON_BOARD1(pos); | |
1730 | ASSERT1(IS_STONE(color), pos); | |
1731 | ||
1732 | /* We check whether the color, the board position, or the base influence | |
1733 | * data has changed since the cache entry got entered. | |
1734 | */ | |
1735 | if (territory_cache_position_number == position_number | |
1736 | && territory_cache_color == color | |
1737 | && territory_cache_influence_id == base->id | |
1738 | && delta_territory_cache[pos] != NOT_COMPUTED) { | |
1739 | int i; | |
1740 | for (i = 0; i < NUM_HASHVALUES; i++) | |
1741 | if (delta_territory_cache_hash[pos].hashval[i] | |
1742 | != safety_hash.hashval[i]) | |
1743 | return 0; | |
1744 | *move_value = delta_territory_cache[pos]; | |
1745 | *followup_value = followup_territory_cache[pos]; | |
1746 | if (0) | |
1747 | gprintf("%1m: retrieved territory value from cache: %f, %f\n", pos, | |
1748 | *move_value, *followup_value); | |
1749 | return 1; | |
1750 | } | |
1751 | return 0; | |
1752 | } | |
1753 | ||
1754 | void | |
1755 | store_delta_territory_cache(int pos, int color, | |
1756 | float move_value, float followup_value, | |
1757 | const struct influence_data *base, | |
1758 | Hash_data safety_hash) | |
1759 | { | |
1760 | int i; | |
1761 | ||
1762 | ASSERT_ON_BOARD1(pos); | |
1763 | ASSERT1(IS_STONE(color), pos); | |
1764 | ||
1765 | if (territory_cache_position_number != position_number | |
1766 | || territory_cache_color != color | |
1767 | || territory_cache_influence_id != base->id) { | |
1768 | int ii; | |
1769 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1770 | delta_territory_cache[ii] = NOT_COMPUTED; | |
1771 | territory_cache_position_number = position_number; | |
1772 | territory_cache_influence_id = base->id; | |
1773 | territory_cache_color = color; | |
1774 | if (0) | |
1775 | gprintf("Cleared delta territory cache.\n"); | |
1776 | } | |
1777 | delta_territory_cache[pos] = move_value; | |
1778 | followup_territory_cache[pos] = followup_value; | |
1779 | for (i = 0; i < NUM_HASHVALUES; i++) | |
1780 | delta_territory_cache_hash[pos].hashval[i] = safety_hash.hashval[i]; | |
1781 | if (0) | |
1782 | gprintf("%1m: Stored delta territory cache: %f, %f\n", pos, move_value, | |
1783 | followup_value); | |
1784 | } | |
1785 | ||
1786 | /* Compute the difference in territory between two influence data, | |
1787 | * from the point of view of (color). | |
1788 | * (move) is only passed for debugging output. | |
1789 | */ | |
1790 | float | |
1791 | influence_delta_territory(const struct influence_data *base, | |
1792 | const struct influence_data *q, int color, | |
1793 | int move) | |
1794 | { | |
1795 | int ii; | |
1796 | float total_delta = 0.0; | |
1797 | float this_delta; | |
1798 | ASSERT_ON_BOARD1(move); | |
1799 | ASSERT1(IS_STONE(color), move); | |
1800 | ||
1801 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1802 | if (ON_BOARD(ii)) { | |
1803 | float new_value = q->territory_value[ii]; | |
1804 | float old_value = base->territory_value[ii]; | |
1805 | this_delta = new_value - old_value; | |
1806 | /* Negate values if we are black. */ | |
1807 | if (color == BLACK) { | |
1808 | new_value = -new_value; | |
1809 | old_value = -old_value; | |
1810 | this_delta = -this_delta; | |
1811 | } | |
1812 | ||
1813 | if (move != -1 | |
1814 | && (this_delta > 0.02 || -this_delta > 0.02)) | |
1815 | DEBUG(DEBUG_TERRITORY, | |
1816 | " %1m: - %1m territory change %f (%f -> %f)\n", | |
1817 | move, ii, this_delta, old_value, new_value); | |
1818 | total_delta += this_delta; | |
1819 | } | |
1820 | ||
1821 | /* Finally, captured stones: */ | |
1822 | this_delta = q->captured - base->captured; | |
1823 | if (color == BLACK) | |
1824 | this_delta = -this_delta; | |
1825 | if (move != -1 | |
1826 | && this_delta != 0.0) | |
1827 | DEBUG(DEBUG_TERRITORY, " %1m: - captured stones %f\n", | |
1828 | move, this_delta); | |
1829 | total_delta += this_delta; | |
1830 | ||
1831 | return total_delta; | |
1832 | } | |
1833 | ||
1834 | ||
1835 | /* Estimate the score. A positive value means white is ahead. The | |
1836 | * score is estimated influence data *q, which must have been | |
1837 | * computed in advance. | |
1838 | */ | |
1839 | float | |
1840 | influence_score(const struct influence_data *q, int use_chinese_rules) | |
1841 | { | |
1842 | float score = 0.0; | |
1843 | int ii; | |
1844 | ||
1845 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1846 | if (ON_BOARD(ii)) | |
1847 | score += q->territory_value[ii]; | |
1848 | ||
1849 | if (use_chinese_rules) | |
1850 | score += stones_on_board(WHITE) - stones_on_board(BLACK) + komi + handicap; | |
1851 | else | |
1852 | score += black_captured - white_captured + komi; | |
1853 | ||
1854 | return score; | |
1855 | } | |
1856 | ||
1857 | ||
1858 | /* Uses initial_influence to estimate the game advancement (fuseki, | |
1859 | * chuban, yose) returned as a value between 0.0 (start) and 1.0 (game | |
1860 | * over) | |
1861 | */ | |
1862 | float | |
1863 | game_status(int color) | |
1864 | { | |
1865 | struct influence_data *iq = INITIAL_INFLUENCE(color); | |
1866 | struct influence_data *oq = OPPOSITE_INFLUENCE(color); | |
1867 | int count = 0; | |
1868 | int ii; | |
1869 | ||
1870 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1871 | if (ON_BOARD(ii)) { | |
1872 | if (iq->safe[ii]) | |
1873 | count += WEIGHT_TERRITORY; | |
1874 | else if (whose_territory(iq, ii) != EMPTY | |
1875 | && whose_territory(oq, ii) != EMPTY) | |
1876 | count += WEIGHT_TERRITORY; | |
1877 | else if (whose_moyo(oq, ii) != EMPTY) | |
1878 | count += WEIGHT_MOYO; | |
1879 | else if (whose_area(oq, ii) != EMPTY) | |
1880 | count += WEIGHT_AREA; | |
1881 | } | |
1882 | ||
1883 | return (float) count / (WEIGHT_TERRITORY * board_size * board_size); | |
1884 | } | |
1885 | ||
1886 | ||
1887 | /* Print the influence map when we have computed influence for the | |
1888 | * move at (i, j). | |
1889 | */ | |
1890 | void | |
1891 | debug_influence_move(int move) | |
1892 | { | |
1893 | debug_influence = move; | |
1894 | } | |
1895 | ||
1896 | ||
1897 | /* One more way to export influence data. This should only be used | |
1898 | * for debugging. | |
1899 | */ | |
1900 | void | |
1901 | get_influence(const struct influence_data *q, | |
1902 | float white_influence[BOARDMAX], | |
1903 | float black_influence[BOARDMAX], | |
1904 | float white_strength[BOARDMAX], | |
1905 | float black_strength[BOARDMAX], | |
1906 | float white_attenuation[BOARDMAX], | |
1907 | float black_attenuation[BOARDMAX], | |
1908 | float white_permeability[BOARDMAX], | |
1909 | float black_permeability[BOARDMAX], | |
1910 | float territory_value[BOARDMAX], | |
1911 | int influence_regions[BOARDMAX], | |
1912 | int non_territory[BOARDMAX]) | |
1913 | { | |
1914 | int ii; | |
1915 | ||
1916 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
1917 | white_influence[ii] = q->white_influence[ii]; | |
1918 | black_influence[ii] = q->black_influence[ii]; | |
1919 | white_strength[ii] = q->white_strength[ii]; | |
1920 | black_strength[ii] = q->black_strength[ii]; | |
1921 | white_attenuation[ii] = q->white_attenuation[ii]; | |
1922 | black_attenuation[ii] = q->black_attenuation[ii]; | |
1923 | white_permeability[ii] = q->white_permeability[ii]; | |
1924 | black_permeability[ii] = q->black_permeability[ii]; | |
1925 | territory_value[ii] = q->territory_value[ii]; | |
1926 | non_territory[ii] = q->non_territory[ii]; | |
1927 | ||
1928 | if (board[ii] == EMPTY) { | |
1929 | if (whose_territory(q, ii) == WHITE) | |
1930 | influence_regions[ii] = 3; | |
1931 | else if (whose_territory(q, ii) == BLACK) | |
1932 | influence_regions[ii] = -3; | |
1933 | else if (whose_moyo(q, ii) == WHITE) | |
1934 | influence_regions[ii] = 2; | |
1935 | else if (whose_moyo(q, ii) == BLACK) | |
1936 | influence_regions[ii] = -2; | |
1937 | else if (whose_area(q, ii) == WHITE) | |
1938 | influence_regions[ii] = 1; | |
1939 | else if (whose_area(q, ii) == BLACK) | |
1940 | influence_regions[ii] = -1; | |
1941 | else | |
1942 | influence_regions[ii] = 0; | |
1943 | } | |
1944 | else if (board[ii] == WHITE) | |
1945 | influence_regions[ii] = 4; | |
1946 | else if (board[ii] == BLACK) | |
1947 | influence_regions[ii] = -4; | |
1948 | } | |
1949 | } | |
1950 | ||
1951 | ||
1952 | ||
1953 | /* Print influence for debugging purposes, according to | |
1954 | * printmoyo bitmap (controlled by -m command line option). | |
1955 | */ | |
1956 | void | |
1957 | print_influence(const struct influence_data *q, const char *info_string) | |
1958 | { | |
1959 | if (printmoyo & PRINTMOYO_ATTENUATION) { | |
1960 | /* Print the attenuation values. */ | |
1961 | fprintf(stderr, "white attenuation (%s):\n", info_string); | |
1962 | print_numeric_influence(q, q->white_attenuation, "%3.2f", 3, 0, 0); | |
1963 | fprintf(stderr, "black attenuation (%s):\n", info_string); | |
1964 | print_numeric_influence(q, q->black_attenuation, "%3.2f", 3, 0, 0); | |
1965 | } | |
1966 | ||
1967 | if (printmoyo & PRINTMOYO_PERMEABILITY) { | |
1968 | /* Print the white permeability values. */ | |
1969 | fprintf(stderr, "white permeability:\n"); | |
1970 | print_numeric_influence(q, q->white_permeability, "%3.1f", 3, 0, 0); | |
1971 | ||
1972 | /* Print the black permeability values. */ | |
1973 | fprintf(stderr, "black permeability:\n"); | |
1974 | print_numeric_influence(q, q->black_permeability, "%3.1f", 3, 0, 0); | |
1975 | } | |
1976 | ||
1977 | if (printmoyo & PRINTMOYO_STRENGTH) { | |
1978 | /* Print the strength values. */ | |
1979 | fprintf(stderr, "white strength:\n"); | |
1980 | if (q->is_territorial_influence) | |
1981 | print_numeric_influence(q, q->white_strength, "%5.1f", 5, 0, 0); | |
1982 | else | |
1983 | print_numeric_influence(q, q->white_strength, "%3.0f", 3, 0, 1); | |
1984 | fprintf(stderr, "black strength:\n"); | |
1985 | if (q->is_territorial_influence) | |
1986 | print_numeric_influence(q, q->black_strength, "%5.1f", 5, 0, 0); | |
1987 | else | |
1988 | print_numeric_influence(q, q->black_strength, "%3.0f", 3, 0, 1); | |
1989 | } | |
1990 | ||
1991 | if (printmoyo & PRINTMOYO_NUMERIC_INFLUENCE) { | |
1992 | /* Print the white influence values. */ | |
1993 | fprintf(stderr, "white influence (%s):\n", info_string); | |
1994 | print_numeric_influence(q, q->white_influence, "%5.1f", 5, 1, 0); | |
1995 | /* Print the black influence values. */ | |
1996 | fprintf(stderr, "black influence (%s):\n", info_string); | |
1997 | print_numeric_influence(q, q->black_influence, "%5.1f", 5, 1, 0); | |
1998 | } | |
1999 | ||
2000 | if (printmoyo & PRINTMOYO_PRINT_INFLUENCE) { | |
2001 | fprintf(stderr, "influence regions (%s):\n", info_string); | |
2002 | print_influence_areas(q); | |
2003 | } | |
2004 | if (printmoyo & PRINTMOYO_VALUE_TERRITORY) { | |
2005 | fprintf(stderr, "territory (%s)", info_string); | |
2006 | print_numeric_influence(q, q->territory_value, "%5.2f", 5, 1, 0); | |
2007 | } | |
2008 | } | |
2009 | ||
2010 | ||
2011 | ||
2012 | /* | |
2013 | * Print numeric influence values. | |
2014 | */ | |
2015 | static void | |
2016 | print_numeric_influence(const struct influence_data *q, | |
2017 | const float values[BOARDMAX], | |
2018 | const char *format, int width, | |
2019 | int draw_stones, int mark_epsilon) | |
2020 | { | |
2021 | int i, j; | |
2022 | char ch; | |
2023 | char format_stone[20]; | |
2024 | ||
2025 | memset(format_stone, ' ', 20); | |
2026 | format_stone[(width + 1) / 2] = '%'; | |
2027 | format_stone[(width + 3) / 2] = 'c'; | |
2028 | format_stone[width + 2] = 0; | |
2029 | ||
2030 | fprintf(stderr, " "); | |
2031 | for (i = 0, ch = 'A'; i < board_size; i++, ch++) { | |
2032 | if (ch == 'I') | |
2033 | ch++; | |
2034 | fprintf(stderr, format_stone, ch); | |
2035 | } | |
2036 | fprintf(stderr, "\n"); | |
2037 | ||
2038 | for (i = 0; i < board_size; i++) { | |
2039 | int ii = board_size - i; | |
2040 | fprintf(stderr, "%2d ", ii); | |
2041 | for (j = 0; j < board_size; j++) { | |
2042 | int ii = POS(i, j); | |
2043 | if (draw_stones && q->safe[ii]) { | |
2044 | if (board[ii] == WHITE) | |
2045 | fprintf(stderr, format_stone, 'O'); | |
2046 | else | |
2047 | fprintf(stderr, format_stone, 'X'); | |
2048 | } | |
2049 | else { | |
2050 | if (mark_epsilon && values[ii] > 0.0 && values[ii] < 1.0) | |
2051 | fprintf(stderr, "eps"); | |
2052 | else | |
2053 | fprintf(stderr, format, values[ii]); | |
2054 | fprintf(stderr, " "); | |
2055 | } | |
2056 | } | |
2057 | fprintf(stderr, "%2d\n", ii); | |
2058 | } | |
2059 | ||
2060 | fprintf(stderr, " "); | |
2061 | for (i = 0, ch = 'A'; i < board_size; i++, ch++) { | |
2062 | if (ch == 'I') | |
2063 | ch++; | |
2064 | fprintf(stderr, format_stone, ch); | |
2065 | } | |
2066 | fprintf(stderr, "\n"); | |
2067 | } | |
2068 | ||
2069 | /* Draw colored board illustrating territory, moyo, and area. */ | |
2070 | static void | |
2071 | print_influence_areas(const struct influence_data *q) | |
2072 | { | |
2073 | int ii; | |
2074 | start_draw_board(); | |
2075 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
2076 | if (ON_BOARD(ii)) { | |
2077 | int c = EMPTY; | |
2078 | int color = GG_COLOR_BLACK; | |
2079 | if (q->safe[ii]) { | |
2080 | color = GG_COLOR_BLACK; | |
2081 | if (board[ii] == WHITE) | |
2082 | c = 'O'; | |
2083 | else | |
2084 | c = 'X'; | |
2085 | } | |
2086 | else if (whose_territory(q, ii) == WHITE) { | |
2087 | c = 'o'; | |
2088 | color = GG_COLOR_CYAN; | |
2089 | } | |
2090 | else if (whose_territory(q, ii) == BLACK) { | |
2091 | c = 'x'; | |
2092 | color = GG_COLOR_CYAN; | |
2093 | } | |
2094 | else if (whose_moyo(q, ii) == WHITE) { | |
2095 | c = 'o'; | |
2096 | color = GG_COLOR_YELLOW; | |
2097 | } | |
2098 | else if (whose_moyo(q, ii) == BLACK) { | |
2099 | c = 'x'; | |
2100 | color = GG_COLOR_YELLOW; | |
2101 | } | |
2102 | else if (whose_area(q, ii) == WHITE) { | |
2103 | c = 'o'; | |
2104 | color = GG_COLOR_RED; | |
2105 | } | |
2106 | else if (whose_area(q, ii) == BLACK) { | |
2107 | c = 'x'; | |
2108 | color = GG_COLOR_RED; | |
2109 | } | |
2110 | draw_color_char(I(ii), J(ii), c, color); | |
2111 | } | |
2112 | end_draw_board(); | |
2113 | } | |
2114 | ||
2115 | ||
2116 | /* | |
2117 | * Local Variables: | |
2118 | * tab-width: 8 | |
2119 | * c-basic-offset: 2 | |
2120 | * End: | |
2121 | */ | |
2122 |