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 | #include <math.h> | |
30 | ||
31 | #include "liberty.h" | |
32 | #include "gg_utils.h" | |
33 | #include "move_reasons.h" | |
34 | ||
35 | ||
36 | /* Count how many distinct strings are (solidly) connected by the move | |
37 | * at (pos). Add a bonus for strings with few liberties. Also add | |
38 | * bonus for opponent strings put in atari or removed and for own | |
39 | * strings in atari adjacent to removed opponent strings. | |
40 | * | |
41 | * The parameter to_move should be set when color is the color to | |
42 | * move. (This function is called for both colors.) | |
43 | */ | |
44 | static int | |
45 | move_connects_strings(int pos, int color, int to_move) | |
46 | { | |
47 | int ss[4]; | |
48 | int strings = 0; | |
49 | int own_strings = 0; | |
50 | int k, l; | |
51 | int fewlibs = 0; | |
52 | ||
53 | for (k = 0; k < 4; k++) { | |
54 | int ii = pos + delta[k]; | |
55 | int origin; | |
56 | ||
57 | if (!ON_BOARD(ii) || board[ii] == EMPTY) | |
58 | continue; | |
59 | ||
60 | origin = find_origin(ii); | |
61 | ||
62 | for (l = 0; l < strings; l++) | |
63 | if (ss[l] == origin) | |
64 | break; | |
65 | ||
66 | if (l == strings) { | |
67 | ss[strings] = origin; | |
68 | strings++; | |
69 | } | |
70 | } | |
71 | ||
72 | for (k = 0; k < strings; k++) { | |
73 | if (worm[ss[k]].invincible) | |
74 | continue; | |
75 | if (board[ss[k]] == color) { | |
76 | int newlibs = approxlib(pos, color, MAXLIBS, NULL); | |
77 | own_strings++; | |
78 | if (newlibs >= countlib(ss[k])) { | |
79 | if (countlib(ss[k]) <= 4) | |
80 | fewlibs++; | |
81 | if (countlib(ss[k]) <= 2) | |
82 | fewlibs++; | |
83 | } | |
84 | } | |
85 | else { | |
86 | if (countlib(ss[k]) <= 2) | |
87 | fewlibs++; | |
88 | if (countlib(ss[k]) <= 1 && to_move) { | |
89 | int dummy[MAXCHAIN]; | |
90 | fewlibs++; | |
91 | fewlibs += chainlinks2(ss[k], dummy, 1); | |
92 | } | |
93 | } | |
94 | } | |
95 | ||
96 | /* Do some thresholding. */ | |
97 | if (fewlibs > 4) | |
98 | fewlibs = 4; | |
99 | if (to_move && is_ko(pos, color, NULL) && fewlibs > 1) | |
100 | fewlibs = 1; | |
101 | if (fewlibs == 0 && own_strings == 1) | |
102 | own_strings = 0; | |
103 | ||
104 | return own_strings + fewlibs; | |
105 | } | |
106 | ||
107 | /* Find saved dragons and worms, then call blunder_size(). */ | |
108 | static float | |
109 | value_moves_get_blunder_size(int move, int color) | |
110 | { | |
111 | signed char saved_dragons[BOARDMAX]; | |
112 | signed char saved_worms[BOARDMAX]; | |
113 | signed char safe_stones[BOARDMAX]; | |
114 | ||
115 | get_saved_dragons(move, saved_dragons); | |
116 | get_saved_worms(move, saved_worms); | |
117 | ||
118 | mark_safe_stones(color, move, saved_dragons, saved_worms, safe_stones); | |
119 | ||
120 | return blunder_size(move, color, NULL, safe_stones); | |
121 | } | |
122 | ||
123 | static int | |
124 | value_moves_confirm_safety(int move, int color) | |
125 | { | |
126 | return (value_moves_get_blunder_size(move, color) == 0.0); | |
127 | } | |
128 | ||
129 | ||
130 | /* Test all moves which defend, attack, connect or cut to see if they | |
131 | * also attack or defend some other worm. | |
132 | * | |
133 | * FIXME: We would like to see whether an arbitrary move works to cut | |
134 | * or connect something else too. | |
135 | */ | |
136 | ||
137 | static void | |
138 | find_more_attack_and_defense_moves(int color) | |
139 | { | |
140 | int unstable_worms[MAX_WORMS]; | |
141 | int N = 0; /* number of unstable worms */ | |
142 | int ii; | |
143 | int k; | |
144 | int other = OTHER_COLOR(color); | |
145 | int cursor_at_start_of_line; | |
146 | ||
147 | TRACE("\nLooking for additional attack and defense moves. Trying moves ...\n"); | |
148 | ||
149 | /* Identify the unstable worms and store them in a list. */ | |
150 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
151 | if (IS_STONE(board[ii]) | |
152 | && worm[ii].origin == ii | |
153 | && worm[ii].attack_codes[0] != 0 | |
154 | && worm[ii].defense_codes[0] != 0) { | |
155 | unstable_worms[N] = ii; | |
156 | N++; | |
157 | } | |
158 | } | |
159 | ||
160 | /* To avoid horizon effects, we temporarily increase the depth values. */ | |
161 | increase_depth_values(); | |
162 | ||
163 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
164 | if (board[ii] != EMPTY) | |
165 | continue; | |
166 | ||
167 | /* Don't consider send-two-return-one moves here. */ | |
168 | if (send_two_return_one(ii, color)) | |
169 | continue; | |
170 | ||
171 | for (k = 0; k < MAX_REASONS; k++) { | |
172 | int r = move[ii].reason[k]; | |
173 | ||
174 | if (r < 0) | |
175 | break; | |
176 | ||
177 | if (move_reasons[r].type == ATTACK_MOVE | |
178 | || move_reasons[r].type == ATTACK_MOVE_GOOD_KO | |
179 | || move_reasons[r].type == ATTACK_MOVE_BAD_KO | |
180 | || move_reasons[r].type == DEFEND_MOVE | |
181 | || move_reasons[r].type == DEFEND_MOVE_GOOD_KO | |
182 | || move_reasons[r].type == DEFEND_MOVE_BAD_KO | |
183 | || move_reasons[r].type == CONNECT_MOVE | |
184 | || move_reasons[r].type == CUT_MOVE) | |
185 | break; | |
186 | /* FIXME: Add code for EITHER_MOVE and ALL_MOVE here. */ | |
187 | } | |
188 | ||
189 | if (k == MAX_REASONS || move[ii].reason[k] == -1) | |
190 | continue; | |
191 | ||
192 | /* Try the move at (ii) and see what happens. */ | |
193 | cursor_at_start_of_line = 0; | |
194 | TRACE("%1m ", ii); | |
195 | if (trymove(ii, color, "find_more_attack_and_defense_moves", NO_MOVE)) { | |
196 | for (k = 0; k < N; k++) { | |
197 | int aa = unstable_worms[k]; | |
198 | ||
199 | /* string of our color, see if there still is an attack, | |
200 | * unless we already know the move works as defense move. | |
201 | */ | |
202 | if (board[aa] == color | |
203 | && !defense_move_reason_known(ii, unstable_worms[k])) { | |
204 | int acode = attack(aa, NULL); | |
205 | if (acode < worm[aa].attack_codes[0]) { | |
206 | /* Maybe attack() doesn't find the attack. Try to | |
207 | * attack with the stored attack move. | |
208 | */ | |
209 | int defense_works = 1; | |
210 | ||
211 | if (trymove(worm[aa].attack_points[0], other, | |
212 | "find_more_attack_and_defense_moves", 0)) { | |
213 | if (!board[aa]) | |
214 | defense_works = 0; | |
215 | else { | |
216 | int this_acode = REVERSE_RESULT(find_defense(aa, NULL)); | |
217 | if (this_acode > acode) { | |
218 | acode = this_acode; | |
219 | if (acode >= worm[aa].attack_codes[0]) | |
220 | defense_works = 0; | |
221 | } | |
222 | } | |
223 | popgo(); | |
224 | } | |
225 | ||
226 | if (defense_works) { | |
227 | if (!cursor_at_start_of_line) | |
228 | TRACE("\n"); | |
229 | TRACE("%ofound extra point of defense of %1m at %1m code %d\n", | |
230 | aa, ii, REVERSE_RESULT(acode)); | |
231 | cursor_at_start_of_line = 1; | |
232 | add_defense_move(ii, aa, REVERSE_RESULT(acode)); | |
233 | } | |
234 | } | |
235 | } | |
236 | ||
237 | /* string of opponent color, see if there still is a defense, | |
238 | * unless we already know the move works as attack move. | |
239 | */ | |
240 | if (board[aa] == other | |
241 | && !attack_move_reason_known(ii, unstable_worms[k])) { | |
242 | ||
243 | int dcode = find_defense(aa, NULL); | |
244 | if (dcode < worm[aa].defense_codes[0]) { | |
245 | /* Maybe find_defense() doesn't find the defense. Try to | |
246 | * defend with the stored defense move. | |
247 | * | |
248 | * Another option is maybe there is no attack anymore | |
249 | * (e.g. we pushed the worm into seki), find_defense() | |
250 | * could easily fail in that case. | |
251 | */ | |
252 | int attack_works = 1; | |
253 | ||
254 | if (attack(aa, NULL) >= worm[aa].attack_codes[0]) { | |
255 | if (trymove(worm[aa].defense_points[0], other, | |
256 | "find_more_attack_and_defense_moves", 0)) { | |
257 | int this_dcode = REVERSE_RESULT(attack(aa, NULL)); | |
258 | if (this_dcode > dcode) { | |
259 | dcode = this_dcode; | |
260 | if (dcode >= worm[aa].defense_codes[0]) | |
261 | attack_works = 0; | |
262 | } | |
263 | popgo(); | |
264 | } | |
265 | } | |
266 | else | |
267 | attack_works = 0; | |
268 | ||
269 | if (attack_works) { | |
270 | if (!cursor_at_start_of_line) | |
271 | TRACE("\n"); | |
272 | TRACE("%ofound extra point of attack of %1m at %1m code %d\n", | |
273 | aa, ii, REVERSE_RESULT(dcode)); | |
274 | cursor_at_start_of_line = 1; | |
275 | add_attack_move(ii, aa, REVERSE_RESULT(dcode)); | |
276 | } | |
277 | } | |
278 | } | |
279 | } | |
280 | popgo(); | |
281 | } | |
282 | } | |
283 | ||
284 | TRACE("\n"); | |
285 | decrease_depth_values(); | |
286 | } | |
287 | ||
288 | ||
289 | /* Do the real job of find_more_owl_attack_and_defense_moves() with given | |
290 | * move reason at given position and for given target (`what'). This | |
291 | * function is used from induce_secondary_move_reasons() for upgrading | |
292 | * one specific move reason only. | |
293 | */ | |
294 | static void | |
295 | do_find_more_owl_attack_and_defense_moves(int color, int pos, | |
296 | int move_reason_type, int what) | |
297 | { | |
298 | int k; | |
299 | int dd1 = NO_MOVE; | |
300 | int dd2 = NO_MOVE; | |
301 | int save_verbose; | |
302 | ||
303 | gg_assert(stackp == 0); | |
304 | ||
305 | /* Never consider moves of the send-two-return-one type here. */ | |
306 | if (send_two_return_one(pos, color)) | |
307 | return; | |
308 | ||
309 | /* Never consider moves playing into snapback here. */ | |
310 | if (playing_into_snapback(pos, color)) | |
311 | return; | |
312 | ||
313 | save_verbose = verbose; | |
314 | if (verbose > 0) | |
315 | verbose --; | |
316 | ||
317 | if (move_reason_type == STRATEGIC_ATTACK_MOVE | |
318 | || move_reason_type == STRATEGIC_DEFEND_MOVE) | |
319 | dd1 = what; | |
320 | else if (move_reason_type == ATTACK_MOVE | |
321 | || move_reason_type == ATTACK_MOVE_GOOD_KO | |
322 | || move_reason_type == ATTACK_MOVE_BAD_KO | |
323 | || move_reason_type == DEFEND_MOVE | |
324 | || move_reason_type == DEFEND_MOVE_GOOD_KO | |
325 | || move_reason_type == DEFEND_MOVE_BAD_KO | |
326 | || move_reason_type == VITAL_EYE_MOVE) | |
327 | dd1 = what; | |
328 | else if (move_reason_type == CONNECT_MOVE) { | |
329 | int worm1 = conn_worm1[what]; | |
330 | int worm2 = conn_worm2[what]; | |
331 | ||
332 | dd1 = dragon[worm1].origin; | |
333 | dd2 = dragon[worm2].origin; | |
334 | if (dd1 == dd2) | |
335 | dd2 = NO_MOVE; | |
336 | } | |
337 | else { | |
338 | verbose = save_verbose; | |
339 | return; | |
340 | } | |
341 | ||
342 | for (k = 0; k < 2; k++) { | |
343 | int dd = (k == 0 ? dd1 : dd2); | |
344 | ||
345 | if (dd == NO_MOVE) | |
346 | continue; | |
347 | ||
348 | /* Don't care about inessential dragons. */ | |
349 | if (DRAGON2(dd).safety == INESSENTIAL) | |
350 | continue; | |
351 | ||
352 | if (DRAGON2(dd).owl_status != CRITICAL) | |
353 | continue; | |
354 | ||
355 | if ((move_reason_type == STRATEGIC_ATTACK_MOVE | |
356 | || move_reason_type == ATTACK_MOVE | |
357 | || move_reason_type == ATTACK_MOVE_GOOD_KO | |
358 | || move_reason_type == ATTACK_MOVE_BAD_KO | |
359 | || (move_reason_type == VITAL_EYE_MOVE | |
360 | && board[dd] == OTHER_COLOR(color))) | |
361 | && !owl_attack_move_reason_known(pos, dd)) { | |
362 | int kworm = NO_MOVE; | |
363 | int acode = owl_does_attack(pos, dd, &kworm); | |
364 | ||
365 | if (acode >= DRAGON2(dd).owl_attack_code) { | |
366 | add_owl_attack_move(pos, dd, kworm, acode); | |
367 | if (save_verbose) | |
368 | gprintf("Move at %1m upgraded to owl attack on %1m (%s).\n", | |
369 | pos, dd, result_to_string(acode)); | |
370 | } | |
371 | } | |
372 | ||
373 | if ((move_reason_type == STRATEGIC_DEFEND_MOVE | |
374 | || move_reason_type == CONNECT_MOVE | |
375 | || move_reason_type == DEFEND_MOVE | |
376 | || move_reason_type == DEFEND_MOVE_GOOD_KO | |
377 | || move_reason_type == DEFEND_MOVE_BAD_KO | |
378 | || (move_reason_type == VITAL_EYE_MOVE | |
379 | && board[dd] == color)) | |
380 | && !owl_defense_move_reason_known(pos, dd)) { | |
381 | int kworm = NO_MOVE; | |
382 | /* FIXME: Better use owl_connection_defend() for CONNECT_MOVE ? */ | |
383 | int dcode = owl_does_defend(pos, dd, &kworm); | |
384 | ||
385 | if (dcode >= DRAGON2(dd).owl_defense_code) { | |
386 | if (dcode == LOSS) | |
387 | add_loss_move(pos, dd, kworm); | |
388 | else | |
389 | add_owl_defense_move(pos, dd, dcode); | |
390 | if (save_verbose) | |
391 | gprintf("Move at %1m upgraded to owl defense for %1m (%s).\n", | |
392 | pos, dd, result_to_string(dcode)); | |
393 | } | |
394 | } | |
395 | } | |
396 | ||
397 | verbose = save_verbose; | |
398 | } | |
399 | ||
400 | ||
401 | ||
402 | /* Try whether the move at (pos) for (color) is also an owl attack on | |
403 | * (target). (dist) is the distance to the dragon, and is used for a | |
404 | * safety heuristic: distant moves are only accepted if they kill within | |
405 | * few owl nodes. | |
406 | */ | |
407 | static void | |
408 | try_large_scale_owl_attack(int pos, int color, int target, int dist) | |
409 | { | |
410 | int owl_nodes_before; | |
411 | int owl_nodes_used; | |
412 | int kworm = NO_MOVE; | |
413 | int acode; | |
414 | int save_verbose = verbose; | |
415 | int save_owl_node_limit = owl_node_limit; | |
416 | ||
417 | ASSERT1(board[target] == OTHER_COLOR(color), pos); | |
418 | ASSERT1(!owl_attack_move_reason_known(pos, target), pos); | |
419 | DEBUG(DEBUG_LARGE_SCALE, "Trying large scale move %1m on %1m\n", pos, target); | |
420 | ||
421 | /* To avoid horizon effects, we temporarily increase | |
422 | * the depth values to find the large scale attacks. | |
423 | */ | |
424 | increase_depth_values(); | |
425 | ||
426 | /* To reduce the amount of aji allowed for large scale | |
427 | * attacks, we reduce the owl limit to 350 nodes for | |
428 | * attacks at distance <= 1, and 150 nodes for attacks at | |
429 | * distance >= 2. | |
430 | */ | |
431 | if (dist <= 1) | |
432 | owl_node_limit *= 0.35; | |
433 | else | |
434 | owl_node_limit *= 0.15; | |
435 | ||
436 | if (DRAGON2(target).owl_attack_node_count < owl_node_limit) { | |
437 | if (verbose > 0) | |
438 | verbose--; | |
439 | ||
440 | owl_nodes_before = get_owl_node_counter(); | |
441 | acode = owl_does_attack(pos, target, &kworm); | |
442 | owl_nodes_used = get_owl_node_counter() - owl_nodes_before; | |
443 | ||
444 | if (acode >= DRAGON2(target).owl_attack_code | |
445 | && acode == WIN) { | |
446 | add_owl_attack_move(pos, target, kworm, acode); | |
447 | DEBUG(DEBUG_LARGE_SCALE | DEBUG_MOVE_REASONS, | |
448 | "Move at %1m owl-attacks %1m on a large scale(%s).\n", | |
449 | pos, target, result_to_string(acode)); | |
450 | } | |
451 | else | |
452 | DEBUG(DEBUG_LARGE_SCALE, | |
453 | "Move at %1m isn't a clean large scale attack on %1m (%s).\n", | |
454 | pos, target, result_to_string(acode)); | |
455 | ||
456 | DEBUG(DEBUG_LARGE_SCALE, " owl nodes used = %d, dist = %d\n", | |
457 | owl_nodes_used, dist); | |
458 | /* Restore settings. */ | |
459 | verbose = save_verbose; | |
460 | } | |
461 | decrease_depth_values(); | |
462 | owl_node_limit = save_owl_node_limit; | |
463 | } | |
464 | ||
465 | ||
466 | #define MAXIMUM_LARGE_SCALE_DIST 3 | |
467 | ||
468 | /* Test all the moves to see whether they can owl-attack a specific | |
469 | * dragon on a large scale . Tested moves are | |
470 | * 1. Moves that already have a move reason. | |
471 | * 2. Are not too far away. | |
472 | * The distance used is the Manhattan distance, and the maximum | |
473 | * distance is MAXIMUM_LARGE_SCALE_DIST. | |
474 | */ | |
475 | static void | |
476 | find_large_scale_owl_attacks_on_dragon(int color, int target) | |
477 | { | |
478 | int x, y; | |
479 | int x_min = board_size; | |
480 | int x_max = 0; | |
481 | int y_min = board_size; | |
482 | int y_max = 0; | |
483 | int dist; | |
484 | ||
485 | ASSERT1(board[target] == OTHER_COLOR(color), target); | |
486 | ||
487 | /* Find the physical extension of the dragon. */ | |
488 | for (x = 0; x < board_size; x++) | |
489 | for (y = 0; y < board_size; y++) { | |
490 | if (is_same_dragon(target, POS(x, y))) { | |
491 | if (x < x_min) | |
492 | x_min = x; | |
493 | if (x > x_max) | |
494 | x_max = x; | |
495 | if (y < y_min) | |
496 | y_min = y; | |
497 | if (y > y_max) | |
498 | y_max = y; | |
499 | } | |
500 | } | |
501 | ASSERT1(x_min <= x_max && y_min <= y_max, target); | |
502 | ||
503 | /* Try to find large scale attacks. | |
504 | * We do this by first trying to find attacks at dist = 0, then | |
505 | * dist = 1, etc., up to MAXIMUM_LARGE_SCALE_DIST. | |
506 | */ | |
507 | for (dist = 0; dist <= MAXIMUM_LARGE_SCALE_DIST; dist++) | |
508 | for (x = gg_max(x_min - dist, 0); | |
509 | x <= gg_min(x_max + dist, board_size - 1); x++) | |
510 | for (y = gg_max(y_min - dist, 0); | |
511 | y <= gg_min(y_max + dist, board_size - 1); y++) { | |
512 | int pos = POS(x, y); | |
513 | ASSERT1(ON_BOARD2(x, y), pos); | |
514 | ||
515 | if (board[pos] == EMPTY) { | |
516 | int a, b, dx, dy; | |
517 | a = abs(x - x_min); | |
518 | b = abs(x - x_max); | |
519 | dx = gg_min(a, b); | |
520 | a = abs(y - y_min); | |
521 | b = abs(y - y_max); | |
522 | dy = gg_min(a, b); | |
523 | ||
524 | if (gg_max(dx, dy) == dist | |
525 | && move[pos].reason[0] >= 0 | |
526 | && !owl_attack_move_reason_known(pos, target)) | |
527 | /* Maximum Manhatan distance, move reason known but no owl | |
528 | * attack yet. | |
529 | */ | |
530 | try_large_scale_owl_attack(pos, color, target, dist); | |
531 | ||
532 | } | |
533 | } | |
534 | } | |
535 | ||
536 | ||
537 | /* Try large scale owl attacks against all enemy dragons that are | |
538 | * small (size <= 6) and critical. | |
539 | */ | |
540 | static void | |
541 | find_large_scale_owl_attack_moves(int color) | |
542 | { | |
543 | int d; | |
544 | ||
545 | DEBUG(DEBUG_LARGE_SCALE, "\nTrying to find large scale attack moves.\n"); | |
546 | for (d = 0; d < number_of_dragons; d++) { | |
547 | int target = dragon2[d].origin; | |
548 | if (dragon[target].color == OTHER_COLOR(color) | |
549 | && dragon[target].size <= 6 | |
550 | && dragon[target].status == CRITICAL | |
551 | && dragon2[d].owl_status == CRITICAL) { | |
552 | DEBUG(DEBUG_LARGE_SCALE, "Small critical dragon found at %1m\n", target); | |
553 | find_large_scale_owl_attacks_on_dragon(color, target); | |
554 | } | |
555 | } | |
556 | } | |
557 | ||
558 | /* Test certain moves to see whether they (too) can owl-attack or | |
559 | * defend an owl critical dragon. Tested moves are | |
560 | * 1. Strategical attacks or defenses for the dragon. | |
561 | * 2. Vital eye points for the dragon. | |
562 | * 3. Tactical attacks or defenses for a part of the dragon. | |
563 | * 4. Moves connecting the dragon to something else. | |
564 | */ | |
565 | static void | |
566 | find_more_owl_attack_and_defense_moves(int color) | |
567 | { | |
568 | int pos, pos2; | |
569 | int k; | |
570 | int dd = NO_MOVE; | |
571 | int worth_trying; | |
572 | int save_verbose; | |
573 | struct eye_data *our_eyes; | |
574 | struct eye_data *your_eyes; | |
575 | struct vital_eye_points *our_vital_points; | |
576 | struct vital_eye_points *your_vital_points; | |
577 | ||
578 | if (verbose) | |
579 | gprintf("\nTrying to upgrade strategical attack and defense moves.\n"); | |
580 | ||
581 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
582 | if (!ON_BOARD(pos)) | |
583 | continue; | |
584 | ||
585 | for (k = 0; k < MAX_REASONS; k++) { | |
586 | int r = move[pos].reason[k]; | |
587 | if (r < 0) | |
588 | break; | |
589 | ||
590 | do_find_more_owl_attack_and_defense_moves(color, pos, | |
591 | move_reasons[r].type, | |
592 | move_reasons[r].what); | |
593 | } | |
594 | } | |
595 | ||
596 | if (verbose) | |
597 | gprintf("\nTrying vital eye moves as owl attacks.\n"); | |
598 | if (color == WHITE) { | |
599 | our_eyes = white_eye; | |
600 | your_eyes = black_eye; | |
601 | our_vital_points = white_vital_points; | |
602 | your_vital_points = black_vital_points; | |
603 | } | |
604 | else { | |
605 | our_eyes = black_eye; | |
606 | your_eyes = white_eye; | |
607 | our_vital_points = black_vital_points; | |
608 | your_vital_points = white_vital_points; | |
609 | } | |
610 | ||
611 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
612 | if (!ON_BOARD(pos)) | |
613 | continue; | |
614 | if (our_eyes[pos].origin == pos | |
615 | && our_vital_points[pos].defense_points[0] != NO_MOVE) { | |
616 | int k, dr; | |
617 | find_eye_dragons(pos, our_eyes, color, &dr, 1); | |
618 | for (k = 0; k < MAX_EYE_ATTACKS; k++) { | |
619 | int move = our_vital_points[pos].defense_points[k]; | |
620 | if (move == NO_MOVE) | |
621 | break; | |
622 | do_find_more_owl_attack_and_defense_moves(color, move, | |
623 | VITAL_EYE_MOVE, dr); | |
624 | } | |
625 | } | |
626 | if (your_eyes[pos].origin == pos | |
627 | && your_vital_points[pos].attack_points[0] != NO_MOVE) { | |
628 | int k, dr; | |
629 | find_eye_dragons(pos, your_eyes, OTHER_COLOR(color), &dr, 1); | |
630 | for (k = 0; k < MAX_EYE_ATTACKS; k++) { | |
631 | int move = your_vital_points[pos].attack_points[k]; | |
632 | if (move == NO_MOVE) | |
633 | break; | |
634 | do_find_more_owl_attack_and_defense_moves(color, move, | |
635 | VITAL_EYE_MOVE, dr); | |
636 | } | |
637 | } | |
638 | } | |
639 | ||
640 | save_verbose = verbose; | |
641 | if (verbose > 0) | |
642 | verbose--; | |
643 | ||
644 | /* If two critical dragons are adjacent, test whether a move to owl | |
645 | * attack or defend one also is effective on the other. | |
646 | */ | |
647 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
648 | if (IS_STONE(board[pos]) | |
649 | && dragon[pos].origin == pos | |
650 | && DRAGON2(pos).owl_status == CRITICAL) { | |
651 | for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) { | |
652 | if (board[pos2] != EMPTY) | |
653 | continue; | |
654 | worth_trying = 0; | |
655 | for (k = 0; k < MAX_REASONS; k++) { | |
656 | int r = move[pos2].reason[k]; | |
657 | ||
658 | if (r < 0) | |
659 | break; | |
660 | if (move_reasons[r].type == OWL_ATTACK_MOVE | |
661 | || move_reasons[r].type == OWL_ATTACK_MOVE_GOOD_KO | |
662 | || move_reasons[r].type == OWL_ATTACK_MOVE_BAD_KO | |
663 | || move_reasons[r].type == OWL_DEFEND_MOVE | |
664 | || move_reasons[r].type == OWL_DEFEND_MOVE_GOOD_KO | |
665 | || move_reasons[r].type == OWL_DEFEND_MOVE_BAD_KO) { | |
666 | dd = move_reasons[r].what; | |
667 | if (are_neighbor_dragons(dd, pos)) { | |
668 | worth_trying = 1; | |
669 | break; | |
670 | } | |
671 | } | |
672 | /* else ... | |
673 | FIXME: what about the new OWL_ATTACK_MOVE_GAIN codes ? | |
674 | */ | |
675 | } | |
676 | ||
677 | if (worth_trying) { | |
678 | if (board[pos] == color | |
679 | && !owl_defense_move_reason_known(pos2, pos)) { | |
680 | int kworm = NO_MOVE; | |
681 | int dcode = owl_does_defend(pos2, pos, &kworm); | |
682 | if (dcode >= DRAGON2(pos).owl_defense_code) { | |
683 | if (dcode == LOSS) | |
684 | add_loss_move(pos2, pos, kworm); | |
685 | else | |
686 | add_owl_defense_move(pos2, pos, dcode); | |
687 | if (save_verbose) | |
688 | gprintf("Move at %1m also owl defends %1m (%s).\n", | |
689 | pos2, pos, result_to_string(dcode)); | |
690 | } | |
691 | ||
692 | } | |
693 | else if (board[pos] != color | |
694 | && !owl_attack_move_reason_known(pos2, pos)) { | |
695 | int kworm = NO_MOVE; | |
696 | int acode = owl_does_attack(pos2, pos, &kworm); | |
697 | if (acode >= DRAGON2(pos).owl_attack_code) { | |
698 | add_owl_attack_move(pos2, pos, kworm, acode); | |
699 | if (save_verbose) | |
700 | gprintf("Move at %1m also owl attacks %1m (%s).\n", | |
701 | pos2, pos, result_to_string(acode)); | |
702 | } | |
703 | } | |
704 | } | |
705 | } | |
706 | } | |
707 | } | |
708 | ||
709 | verbose = save_verbose; | |
710 | } | |
711 | ||
712 | /* Tests whether the potential semeai move at (pos) with details given via | |
713 | * (*reason) works, and adds a semeai move if applicable. | |
714 | */ | |
715 | static void | |
716 | try_potential_semeai_move(int pos, int color, struct move_reason *reason) | |
717 | { | |
718 | int dr1 = semeai_target1[reason->what]; | |
719 | int dr2 = semeai_target2[reason->what]; | |
720 | int resulta, resultb, certain, old_certain; | |
721 | ASSERT1(IS_STONE(board[dr1]), pos); | |
722 | switch (reason->type) { | |
723 | case POTENTIAL_SEMEAI_ATTACK: | |
724 | owl_analyze_semeai_after_move(pos, color, dr1, dr2, | |
725 | &resulta, &resultb, NULL, | |
726 | 1, &certain, 0); | |
727 | old_certain = DRAGON2(dr1).semeai_attack_certain; | |
728 | break; | |
729 | case POTENTIAL_SEMEAI_DEFENSE: | |
730 | old_certain = DRAGON2(dr1).semeai_defense_certain; | |
731 | /* In this case other dragon gets to move first after forced move. */ | |
732 | owl_analyze_semeai_after_move(pos, color, dr2, dr1, | |
733 | &resulta, &resultb, NULL, | |
734 | 1, &certain, 0); | |
735 | break; | |
736 | default: | |
737 | ASSERT1(0, pos); | |
738 | } | |
739 | if (resulta == 0 && resultb == 0 | |
740 | && (certain || !old_certain)) { | |
741 | add_semeai_move(pos, dr1); | |
742 | DEBUG(DEBUG_SEMEAI, | |
743 | "Potential semeai move at %1m for dragon at %1m is real\n", | |
744 | pos, dr1); | |
745 | } | |
746 | else | |
747 | DEBUG(DEBUG_MOVE_REASONS, "Potential semeai move at %1m for %1m discarded\n", | |
748 | pos, dr1); | |
749 | } | |
750 | ||
751 | /* This functions tests all potential semeai attack moves whether they work, | |
752 | * provided that there is at least one other move reasons stored for the | |
753 | * relevant position. | |
754 | */ | |
755 | static void | |
756 | find_more_semeai_moves(int color) | |
757 | { | |
758 | int pos; | |
759 | int save_verbose = verbose; | |
760 | ||
761 | if (verbose > 0) | |
762 | verbose--; | |
763 | ||
764 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
765 | int k, r; | |
766 | int potential_semeai_move_found = 0; | |
767 | int other_move_reason_found = 0; | |
768 | ||
769 | if (!ON_BOARD1(pos)) | |
770 | continue; | |
771 | for (k = 0; k < MAX_REASONS; k++) { | |
772 | r = move[pos].reason[k]; | |
773 | if (r < 0) | |
774 | break; | |
775 | switch (move_reasons[r].type) { | |
776 | case POTENTIAL_SEMEAI_ATTACK: | |
777 | case POTENTIAL_SEMEAI_DEFENSE: | |
778 | potential_semeai_move_found = 1; | |
779 | break; | |
780 | default: | |
781 | other_move_reason_found = 1; | |
782 | } | |
783 | } | |
784 | if ((r < 0 || k == MAX_REASONS) | |
785 | && !other_move_reason_found) | |
786 | continue; | |
787 | if (!potential_semeai_move_found) | |
788 | continue; | |
789 | ||
790 | for (k = 0; k < MAX_REASONS; k++) { | |
791 | int r = move[pos].reason[k]; | |
792 | if (r < 0) | |
793 | break; | |
794 | if (move_reasons[r].type == POTENTIAL_SEMEAI_ATTACK | |
795 | || move_reasons[r].type == POTENTIAL_SEMEAI_DEFENSE) | |
796 | try_potential_semeai_move(pos, color, &(move_reasons[r])); | |
797 | } | |
798 | } | |
799 | verbose = save_verbose; | |
800 | } | |
801 | ||
802 | ||
803 | /* | |
804 | * Any move that captures or defends a worm also potentially connects | |
805 | * or cuts the surrounding strings. Find these secondary move reasons | |
806 | * and verify them by connection reading. | |
807 | * | |
808 | * We also let an owl attack count as a strategical defense of our | |
809 | * neighbors of the owl attacked dragon. We only do this for | |
810 | * tactically safe dragons, however, because otherwise the effects of | |
811 | * capturing have already been taken into account elsewhere. | |
812 | * | |
813 | * Also, connecting moves played on inhibited points possibly remove | |
814 | * nearby connection inhibitions like in following example : | |
815 | * | |
816 | * .OX. The * move connects _all_ O stones together, not only | |
817 | * O... the 2 lower ones. | |
818 | * XO*O | |
819 | * X.X. | |
820 | * | |
821 | */ | |
822 | ||
823 | static void | |
824 | induce_secondary_move_reasons(int color) | |
825 | { | |
826 | int pos; | |
827 | int k; | |
828 | int i, j; | |
829 | int aa; | |
830 | ||
831 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
832 | if (!ON_BOARD(pos)) | |
833 | continue; | |
834 | ||
835 | for (k = 0; k < MAX_REASONS; k++) { | |
836 | int r = move[pos].reason[k]; | |
837 | ||
838 | if (r < 0) | |
839 | break; | |
840 | ||
841 | if (move_reasons[r].type == ATTACK_MOVE | |
842 | || move_reasons[r].type == DEFEND_MOVE) { | |
843 | int attack_move; | |
844 | int color_to_move; | |
845 | int num_adj, adjs[MAXCHAIN]; | |
846 | ||
847 | aa = move_reasons[r].what; | |
848 | ||
849 | if (move_reasons[r].type == ATTACK_MOVE) { | |
850 | attack_move = 1; | |
851 | color_to_move = OTHER_COLOR(board[aa]); | |
852 | } | |
853 | else { | |
854 | attack_move = 0; | |
855 | color_to_move = board[aa]; | |
856 | } | |
857 | ||
858 | if (worm[aa].defense_codes[0] == 0) | |
859 | continue; /* No defense. */ | |
860 | ||
861 | /* Don't care about inessential dragons. */ | |
862 | if (DRAGON2(aa).safety == INESSENTIAL) | |
863 | continue; | |
864 | ||
865 | /* | |
866 | * If this is a defense move and the defense is futile for | |
867 | * strategical reasons, we shouldn't induce a cutting move | |
868 | * reason. | |
869 | * | |
870 | * FIXME: We may want to revise this policy. | |
871 | */ | |
872 | if (!attack_move && !move[pos].move_safety) | |
873 | continue; | |
874 | ||
875 | num_adj = extended_chainlinks(aa, adjs, 1); | |
876 | ||
877 | for (i = 0; i < num_adj; i++) { | |
878 | for (j = i+1; j < num_adj; j++) { | |
879 | int adj1 = adjs[i]; | |
880 | int adj2 = adjs[j]; | |
881 | ||
882 | if (board[adj1] != board[adj2]) | |
883 | continue; | |
884 | if (attack_move | |
885 | && board[adj1] != board[aa] | |
886 | && !disconnect(adj1, adj2, NULL)) | |
887 | continue; | |
888 | if (!attack_move | |
889 | && board[adj1] != board[aa] | |
890 | && !string_connect(adj1, adj2, NULL)) | |
891 | continue; | |
892 | if (attack_move | |
893 | && board[adj1] == board[aa]) | |
894 | continue; | |
895 | if (!attack_move | |
896 | && board[adj1] == board[aa] | |
897 | && !disconnect(adj1, adj2, NULL)) | |
898 | continue; | |
899 | ||
900 | if (trymove(pos, color_to_move, "induce_secondary_move_reasons", | |
901 | aa)) { | |
902 | if (attack_move | |
903 | && board[adj1] != board[aa] | |
904 | && !disconnect(adj1, adj2, NULL)) { | |
905 | popgo(); | |
906 | DEBUG(DEBUG_MOVE_REASONS, | |
907 | "Connection move at %1m induced for %1m/%1m due to attack of %1m\n", | |
908 | pos, adj1, adj2, aa); | |
909 | add_connection_move(pos, adj1, adj2); | |
910 | do_find_more_owl_attack_and_defense_moves(color, pos, CONNECT_MOVE, | |
911 | find_connection(adj1, adj2)); | |
912 | } | |
913 | else if (!attack_move | |
914 | && board[adj1] != board[aa] | |
915 | && !string_connect(adj1, adj2, NULL)) { | |
916 | popgo(); | |
917 | DEBUG(DEBUG_MOVE_REASONS, | |
918 | "Cut move at %1m induced for %1m/%1m due to defense of %1m\n", | |
919 | pos, adj1, adj2, aa); | |
920 | add_cut_move(pos, adj1, adj2); | |
921 | } | |
922 | else if (!attack_move | |
923 | && board[adj1] == board[aa] | |
924 | && !disconnect(adj1, adj2, NULL)) { | |
925 | popgo(); | |
926 | DEBUG(DEBUG_MOVE_REASONS, | |
927 | "Connection move at %1m induced for %1m/%1m due to defense of %1m\n", | |
928 | pos, adj1, adj2, aa); | |
929 | add_connection_move(pos, adj1, adj2); | |
930 | do_find_more_owl_attack_and_defense_moves(color, pos, CONNECT_MOVE, | |
931 | find_connection(adj1, adj2)); | |
932 | } | |
933 | else | |
934 | popgo(); | |
935 | } | |
936 | } | |
937 | } | |
938 | ||
939 | /* Strategical attack move reason is induced for moves that | |
940 | * defend neighbor strings of weak opponent dragons a. We | |
941 | * only count strings that are large (more than three stones) | |
942 | * or adjoin at least two non-dead non-single-stone opponent | |
943 | * dragons. | |
944 | */ | |
945 | if (!attack_move) { | |
946 | int strategically_valuable = (worm[aa].size > 3); | |
947 | signed char neighbor_dragons[BOARDMAX]; | |
948 | ||
949 | memset(neighbor_dragons, 0, sizeof(neighbor_dragons)); | |
950 | ||
951 | if (!strategically_valuable) { | |
952 | int num_dragons = 0; | |
953 | ||
954 | for (i = 0; i < num_adj; i++) { | |
955 | int origin = dragon[adjs[i]].origin; | |
956 | ||
957 | if (board[origin] != color_to_move | |
958 | && neighbor_dragons[origin] != 1 | |
959 | && dragon[origin].size > 1 | |
960 | && dragon[origin].status != DEAD) { | |
961 | if (++num_dragons == 2) { | |
962 | strategically_valuable = 1; | |
963 | break; | |
964 | } | |
965 | ||
966 | neighbor_dragons[origin] = 1; | |
967 | } | |
968 | } | |
969 | } | |
970 | ||
971 | if (strategically_valuable) { | |
972 | for (i = 0; i < num_adj; i++) { | |
973 | int origin = dragon[adjs[i]].origin; | |
974 | ||
975 | if (board[origin] != color_to_move | |
976 | && neighbor_dragons[origin] != 2 | |
977 | && dragon[origin].status != DEAD | |
978 | && dragon_weak(origin)) { | |
979 | DEBUG(DEBUG_MOVE_REASONS, | |
980 | "Strategical attack move at %1m induced for %1m due to defense of %1m\n", | |
981 | pos, origin, aa); | |
982 | add_strategical_attack_move(pos, origin); | |
983 | do_find_more_owl_attack_and_defense_moves(color, pos, | |
984 | STRATEGIC_ATTACK_MOVE, | |
985 | origin); | |
986 | ||
987 | neighbor_dragons[origin] = 2; | |
988 | } | |
989 | } | |
990 | } | |
991 | } | |
992 | } | |
993 | else if (move_reasons[r].type == OWL_ATTACK_MOVE) { | |
994 | aa = move_reasons[r].what; | |
995 | for (i = 0; i < DRAGON2(aa).neighbors; i++) { | |
996 | int bb = dragon2[DRAGON2(aa).adjacent[i]].origin; | |
997 | if (dragon[bb].color == color && worm[bb].attack_codes[0] == 0 | |
998 | && !DRAGON2(bb).semeais) { | |
999 | add_strategical_defense_move(pos, bb); | |
1000 | do_find_more_owl_attack_and_defense_moves(color, pos, | |
1001 | STRATEGIC_DEFEND_MOVE, | |
1002 | bb); | |
1003 | DEBUG(DEBUG_MOVE_REASONS, "Strategic defense at %1m induced for %1m due to owl attack on %1m\n", | |
1004 | pos, bb, aa); | |
1005 | } | |
1006 | } | |
1007 | } | |
1008 | else if (move_reasons[r].type == CONNECT_MOVE | |
1009 | && cut_possible(pos, OTHER_COLOR(color))) { | |
1010 | int worm1 = conn_worm1[move_reasons[r].what]; | |
1011 | int worm2 = conn_worm2[move_reasons[r].what]; | |
1012 | int pos2; | |
1013 | for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) { | |
1014 | if (ON_BOARD(pos2) && board[pos2] == EMPTY | |
1015 | && cut_possible(pos2, OTHER_COLOR(color)) | |
1016 | && square_dist(pos, pos2) <= 5) { | |
1017 | for (j = 0; j < 8; j++) { | |
1018 | int pos3 = pos2 + delta[j]; | |
1019 | if (ON_BOARD(pos3) && board[pos3] == color | |
1020 | && !is_same_worm(pos3, worm1) | |
1021 | && !is_same_worm(pos3, worm2)) { | |
1022 | if (trymove(pos, color, "induce_secondary_move_reasons-B", | |
1023 | worm1)) { | |
1024 | int break1 = disconnect(pos3, worm1, NULL); | |
1025 | int break2 = disconnect(pos3, worm2, NULL); | |
1026 | popgo(); | |
1027 | ||
1028 | if (!break1) { | |
1029 | add_connection_move(pos, pos3, worm1); | |
1030 | do_find_more_owl_attack_and_defense_moves(color, pos, CONNECT_MOVE, | |
1031 | find_connection(pos3, worm1)); | |
1032 | DEBUG(DEBUG_MOVE_REASONS, "Connection at %1m induced for %1m/%1m due to connection at %1m/%1m\n", | |
1033 | pos, worm1, worm2, pos3, worm1); | |
1034 | } | |
1035 | ||
1036 | if (!break2) { | |
1037 | add_connection_move(pos, pos3, worm2); | |
1038 | do_find_more_owl_attack_and_defense_moves(color, pos, CONNECT_MOVE, | |
1039 | find_connection(pos3, worm2)); | |
1040 | DEBUG(DEBUG_MOVE_REASONS, "Connection at %1m induced for %1m/%1m due to connection at %1m/%1m\n", | |
1041 | pos, worm1, worm2, pos3, worm2); | |
1042 | } | |
1043 | } | |
1044 | } | |
1045 | } | |
1046 | } | |
1047 | } | |
1048 | } | |
1049 | } | |
1050 | } | |
1051 | } | |
1052 | ||
1053 | ||
1054 | /* Examine the strategical and tactical safety of the moves. This is | |
1055 | * used to decide whether or not the stone should generate influence | |
1056 | * when the move is evaluated. The idea is to avoid overestimating the | |
1057 | * value of strategically unsafe defense moves and connections of dead | |
1058 | * dragons. This sets the move.move_safety field. | |
1059 | */ | |
1060 | static void | |
1061 | examine_move_safety(int color) | |
1062 | { | |
1063 | int pos; | |
1064 | int k; | |
1065 | ||
1066 | start_timer(3); | |
1067 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1068 | int safety = 0; | |
1069 | int tactical_safety = 0; | |
1070 | if (!ON_BOARD(pos)) | |
1071 | continue; | |
1072 | tactical_safety = is_known_safe_move(pos); | |
1073 | ||
1074 | for (k = 0; k < MAX_REASONS; k++) { | |
1075 | int r = move[pos].reason[k]; | |
1076 | int type; | |
1077 | int what; | |
1078 | ||
1079 | if (r == -1) | |
1080 | break; | |
1081 | type = move_reasons[r].type; | |
1082 | what = move_reasons[r].what; | |
1083 | switch (type) { | |
1084 | case CUT_MOVE: | |
1085 | /* We don't trust cut moves, unless some other move reason | |
1086 | * indicates they are safe. | |
1087 | */ | |
1088 | break; | |
1089 | case OWL_DEFEND_MOVE: | |
1090 | case OWL_DEFEND_MOVE_GOOD_KO: | |
1091 | case OWL_DEFEND_MOVE_BAD_KO: | |
1092 | case OWL_DEFEND_MOVE_LOSS: | |
1093 | { | |
1094 | int ii; | |
1095 | for (ii = first_worm_in_dragon(what); ii != NO_MOVE; | |
1096 | ii = next_worm_in_dragon(ii)) { | |
1097 | if (!play_connect_n(color, 0, 1, pos, ii, pos)) | |
1098 | break; | |
1099 | } | |
1100 | if (ii != NO_MOVE) { | |
1101 | tactical_safety = 1; | |
1102 | safety = 1; | |
1103 | } | |
1104 | break; | |
1105 | } | |
1106 | case SEMEAI_MOVE: | |
1107 | case MY_ATARI_ATARI_MOVE: | |
1108 | case YOUR_ATARI_ATARI_MOVE: | |
1109 | case EITHER_MOVE: /* FIXME: More advanced handling? */ | |
1110 | tactical_safety = 1; | |
1111 | safety = 1; | |
1112 | break; | |
1113 | case ALL_MOVE: | |
1114 | /* We don't trust these, unless some other move reason | |
1115 | * indicates safety. | |
1116 | */ | |
1117 | break; | |
1118 | case EXPAND_TERRITORY_MOVE: | |
1119 | case EXPAND_MOYO_MOVE: | |
1120 | case INVASION_MOVE: /* A real invasion should be safe. | |
1121 | A sacrifice is something else.*/ | |
1122 | safety = 1; | |
1123 | break; | |
1124 | case ATTACK_MOVE: | |
1125 | case ATTACK_MOVE_GOOD_KO: | |
1126 | case ATTACK_MOVE_BAD_KO: | |
1127 | case OWL_ATTACK_MOVE: | |
1128 | case OWL_ATTACK_MOVE_GOOD_KO: | |
1129 | case OWL_ATTACK_MOVE_BAD_KO: | |
1130 | case OWL_ATTACK_MOVE_GAIN: | |
1131 | { | |
1132 | int aa = NO_MOVE; | |
1133 | int bb = NO_MOVE; | |
1134 | int size; | |
1135 | int m; | |
1136 | int our_color_neighbors; | |
1137 | ||
1138 | if (type == ATTACK_MOVE | |
1139 | || type == ATTACK_MOVE_GOOD_KO | |
1140 | || type == ATTACK_MOVE_BAD_KO) { | |
1141 | aa = what; | |
1142 | size = worm[aa].effective_size; | |
1143 | } | |
1144 | else if (type == OWL_ATTACK_MOVE_GAIN) { | |
1145 | aa = either_data[what].what2; | |
1146 | size = worm[aa].effective_size; | |
1147 | } | |
1148 | else { | |
1149 | aa = what; | |
1150 | size = dragon[aa].effective_size; | |
1151 | } | |
1152 | ||
1153 | /* No worries if we catch something big. */ | |
1154 | if (size >= 8) { | |
1155 | tactical_safety = 1; | |
1156 | safety = 1; | |
1157 | break; | |
1158 | } | |
1159 | ||
1160 | /* If the victim has multiple neighbor dragons of our | |
1161 | * color, we leave it to the connection move reason to | |
1162 | * determine safety. | |
1163 | * | |
1164 | * The exception is an owl_attack where we only require | |
1165 | * one neighbor to be alive. | |
1166 | */ | |
1167 | our_color_neighbors = 0; | |
1168 | if (type == ATTACK_MOVE | |
1169 | || type == ATTACK_MOVE_GOOD_KO | |
1170 | || type == ATTACK_MOVE_BAD_KO) { | |
1171 | /* We could use the same code as for OWL_ATTACK_MOVE | |
1172 | * below if we were certain that the capturable string | |
1173 | * had not been amalgamated with a living dragon. | |
1174 | */ | |
1175 | int num_adj, adjs[MAXCHAIN]; | |
1176 | ||
1177 | num_adj = chainlinks(aa, adjs); | |
1178 | for (m = 0; m < num_adj; m++) { | |
1179 | int adj = adjs[m]; | |
1180 | ||
1181 | if (board[adj] == color) { | |
1182 | /* Check whether this string is part of the same | |
1183 | * dragon as an earlier string. We only want to | |
1184 | * count distinct neighbor dragons. | |
1185 | */ | |
1186 | int n; | |
1187 | ||
1188 | for (n = 0; n < m; n++) | |
1189 | if (dragon[adjs[n]].id == dragon[adj].id) | |
1190 | break; | |
1191 | if (n == m) { | |
1192 | /* New dragon. */ | |
1193 | our_color_neighbors++; | |
1194 | bb = adj; | |
1195 | } | |
1196 | } | |
1197 | } | |
1198 | } | |
1199 | else { | |
1200 | for (m = 0; m < DRAGON2(aa).neighbors; m++) | |
1201 | if (DRAGON(DRAGON2(aa).adjacent[m]).color == color) { | |
1202 | our_color_neighbors++; | |
1203 | bb = dragon2[DRAGON2(aa).adjacent[m]].origin; | |
1204 | if (dragon[bb].status == ALIVE) { | |
1205 | tactical_safety = 1; | |
1206 | safety = 1; | |
1207 | } | |
1208 | } | |
1209 | } | |
1210 | ||
1211 | if (our_color_neighbors > 1) | |
1212 | break; | |
1213 | ||
1214 | /* It may happen in certain positions that no neighbor of | |
1215 | * our color is found. The working hypothesis is that | |
1216 | * the move is safe then. One example is a position like | |
1217 | * | |
1218 | * ----+ | |
1219 | * OX.X| | |
1220 | * OOX.| | |
1221 | * OOX| | |
1222 | * OO| | |
1223 | * | |
1224 | * where the top right stone only has friendly neighbors | |
1225 | * but can be attacked. | |
1226 | * | |
1227 | * As a further improvement, we also look for a friendly | |
1228 | * dragon adjacent to the considered move. | |
1229 | */ | |
1230 | ||
1231 | for (m = 0; m < 4; m++) { | |
1232 | int d = delta[m]; | |
1233 | if (board[pos+d] == color) { | |
1234 | bb = pos + d; | |
1235 | break; | |
1236 | } | |
1237 | } | |
1238 | ||
1239 | if (bb == NO_MOVE) { | |
1240 | tactical_safety = 1; | |
1241 | safety = 1; | |
1242 | break; | |
1243 | } | |
1244 | ||
1245 | /* If the attacker is thought to be alive, we trust that | |
1246 | * sentiment. | |
1247 | */ | |
1248 | if (dragon[bb].status == ALIVE) { | |
1249 | tactical_safety = 1; | |
1250 | safety = 1; | |
1251 | break; | |
1252 | } | |
1253 | ||
1254 | /* It remains the possibility that what we have captured | |
1255 | * is just a nakade shape. Ask the owl code whether this | |
1256 | * move saves our attacking dragon. | |
1257 | * | |
1258 | * FIXME: Might need to involve semeai code too here. | |
1259 | */ | |
1260 | if (owl_does_defend(pos, bb, NULL)) { | |
1261 | tactical_safety = 1; | |
1262 | safety = 1; | |
1263 | } | |
1264 | break; | |
1265 | } | |
1266 | case DEFEND_MOVE: | |
1267 | case DEFEND_MOVE_GOOD_KO: | |
1268 | case DEFEND_MOVE_BAD_KO: | |
1269 | { | |
1270 | int aa = what; | |
1271 | ||
1272 | if (dragon[aa].status == ALIVE) | |
1273 | /* It would be better if this never happened, but it does | |
1274 | * sometimes. The owl reading can be very slow then. | |
1275 | */ | |
1276 | safety = 1; | |
1277 | ||
1278 | else if (!play_connect_n(color, 0, 1, pos, aa, pos) | |
1279 | && owl_does_defend(pos, aa, NULL)) | |
1280 | safety = 1; | |
1281 | break; | |
1282 | } | |
1283 | ||
1284 | case ATTACK_THREAT: | |
1285 | case DEFEND_THREAT: | |
1286 | break; | |
1287 | ||
1288 | case CONNECT_MOVE: | |
1289 | { | |
1290 | int worm1 = conn_worm1[move_reasons[r].what]; | |
1291 | int worm2 = conn_worm2[move_reasons[r].what]; | |
1292 | int aa = dragon[worm1].origin; | |
1293 | int bb = dragon[worm2].origin; | |
1294 | ||
1295 | if (aa == bb) | |
1296 | continue; | |
1297 | ||
1298 | if (DRAGON2(aa).owl_status == ALIVE | |
1299 | || DRAGON2(bb).owl_status == ALIVE) { | |
1300 | tactical_safety = 1; | |
1301 | safety = 1; | |
1302 | } | |
1303 | else if ((DRAGON2(aa).owl_status == UNCHECKED | |
1304 | && dragon[aa].crude_status == ALIVE) | |
1305 | || (DRAGON2(bb).owl_status == UNCHECKED | |
1306 | && dragon[bb].crude_status == ALIVE)) { | |
1307 | tactical_safety = 1; | |
1308 | safety = 1; | |
1309 | } | |
1310 | else if (owl_connection_defends(pos, aa, bb)) { | |
1311 | tactical_safety = 1; | |
1312 | safety = 1; | |
1313 | } | |
1314 | break; | |
1315 | } | |
1316 | } | |
1317 | if (safety == 1 && (tactical_safety == 1 || safe_move(pos, color))) | |
1318 | break; | |
1319 | } | |
1320 | ||
1321 | if (safety == 1 && (tactical_safety || safe_move(pos, color))) | |
1322 | move[pos].move_safety = 1; | |
1323 | else | |
1324 | move[pos].move_safety = 0; | |
1325 | ||
1326 | time_report(3, " examine_move_safety: ", pos, 1.0); | |
1327 | } | |
1328 | } | |
1329 | ||
1330 | ||
1331 | /* | |
1332 | * Returns the pre-computed weakness of a dragon, with corrections | |
1333 | * according to ignore_dead_dragons. | |
1334 | * | |
1335 | * FIXME: Important to test more exactly how effective a strategical | |
1336 | * attack or defense of a weak dragon is. This can be done by | |
1337 | * measuring escape factor and moyo size after the move and | |
1338 | * compare with the old values. Also necessary to test whether | |
1339 | * an attack or defense of a critical dragon is effective. | |
1340 | * Notice that this wouldn't exactly go into this function but | |
1341 | * rather where it's called. | |
1342 | */ | |
1343 | ||
1344 | float | |
1345 | dragon_weakness(int dr, int ignore_dead_dragons) | |
1346 | { | |
1347 | int dragon_safety = DRAGON2(dr).safety; | |
1348 | ||
1349 | /* Kludge: If a dragon is dead, we return 1.0 in order not | |
1350 | * to try to run away. | |
1351 | */ | |
1352 | if (ignore_dead_dragons | |
1353 | && (dragon_safety == DEAD | |
1354 | || dragon_safety == INESSENTIAL | |
1355 | || dragon_safety == TACTICALLY_DEAD)) | |
1356 | return 0.0; | |
1357 | ||
1358 | /* When scoring, we don't want to reinforce ALIVE dragons. */ | |
1359 | if (doing_scoring && dragon_safety == ALIVE) | |
1360 | return 0.0; | |
1361 | ||
1362 | return DRAGON2(dr).weakness; | |
1363 | } | |
1364 | ||
1365 | /* | |
1366 | * Strategical value of connecting (or cutting) the dragon at (dragona) | |
1367 | * to the dragon at (dragonb). Notice that this function is asymmetric. | |
1368 | * This is because connection_value(a, b) is intended to measure the | |
1369 | * strategical value on the a dragon from a connection to the b dragon. | |
1370 | * | |
1371 | * Consider the following position: | |
1372 | * +---------+ | |
1373 | * |XXO.O.OXX| | |
1374 | * |.XOOOOOX.| | |
1375 | * |XXXX.XXXX| | |
1376 | * |.XOOXOOX.| | |
1377 | * |XXO.X.O.X| | |
1378 | * |OOOXXXOOO| | |
1379 | * |..OOOOO..| | |
1380 | * |.........| | |
1381 | * +---------+ | |
1382 | * | |
1383 | * X has three dragons, one invincible to the left (A), one critical to | |
1384 | * the right (B), and one dead in the center (C). The move at the cutting | |
1385 | * point has three move reasons: | |
1386 | * connect A and B | |
1387 | * connect A and C | |
1388 | * connect B and C | |
1389 | * | |
1390 | * The strategical value on A of either connection is of course zero, | |
1391 | * since it's very unconditionally alive. The strategical value on B is | |
1392 | * high when it's connected to A but small (at least should be) from the | |
1393 | * connection to C. Similarly for dragon C. In effect the total | |
1394 | * strategical value of this move is computed as: | |
1395 | * | |
1396 | * max(connection_value(A, B), connection_value(A, C)) | |
1397 | * + max(connection_value(B, A), connection_value(B, C)) | |
1398 | * + max(connection_value(C, A), connection_value(C, B)) | |
1399 | * | |
1400 | * The parameter 'margin' is the margin by which we are ahead. | |
1401 | * If this exceeds 20 points we value connections more. This is because | |
1402 | * we can afford to waste a move making sure of safety. | |
1403 | */ | |
1404 | ||
1405 | static float | |
1406 | connection_value(int dragona, int dragonb, int tt, float margin) | |
1407 | { | |
1408 | struct dragon_data2 *da = &DRAGON2(dragona); | |
1409 | struct dragon_data2 *db = &DRAGON2(dragonb); | |
1410 | float sizea = da->strategic_size; | |
1411 | float sizeb = db->strategic_size; | |
1412 | int safetya = da->safety; | |
1413 | int safetyb = db->safety; | |
1414 | float crude_weakness_a | |
1415 | = crude_dragon_weakness(da->safety, &da->genus, da->lunch != NO_MOVE, | |
1416 | da->moyo_territorial_value, | |
1417 | (float) da->escape_route); | |
1418 | float crude_weakness_sum; | |
1419 | struct eyevalue genus_sum; | |
1420 | float terr_val = move[tt].territorial_value; | |
1421 | float return_value; | |
1422 | ||
1423 | if (margin > 20.0) | |
1424 | margin = 20.0; | |
1425 | ||
1426 | /* When scoring, we want to be restrictive with reinforcement moves. | |
1427 | * Thus if both dragons are alive, strongly alive, or invincible, no | |
1428 | * bonus is awarded. | |
1429 | * | |
1430 | * FIXME: Shouldn't it be sufficient to check this for dragon a? | |
1431 | */ | |
1432 | if (doing_scoring) { | |
1433 | if ((safetya == ALIVE | |
1434 | || safetya == STRONGLY_ALIVE | |
1435 | || safetya == INVINCIBLE) | |
1436 | && (safetyb == ALIVE | |
1437 | || safetyb == STRONGLY_ALIVE | |
1438 | || safetyb == INVINCIBLE)) | |
1439 | return 0.0; | |
1440 | } | |
1441 | ||
1442 | if (safetyb == INESSENTIAL) | |
1443 | return 0.0; | |
1444 | ||
1445 | if (crude_weakness_a == 0.0 | |
1446 | || dragon[dragona].status == DEAD) | |
1447 | return 0.0; | |
1448 | if (terr_val < 0.0) | |
1449 | terr_val = 0.0; | |
1450 | ||
1451 | add_eyevalues(&da->genus, &db->genus, &genus_sum); | |
1452 | /* FIXME: There is currently no sane way to take the escape values | |
1453 | * into account. Hence we simply pretend they do not change. | |
1454 | * | |
1455 | * FIXME: terr_val is a very crude approximation to the expected | |
1456 | * increase in moyo size. It's especially way off if the move at (tt) | |
1457 | * (owl) defends some stones. | |
1458 | */ | |
1459 | crude_weakness_sum | |
1460 | = crude_dragon_weakness(safetyb, &genus_sum, | |
1461 | (da->lunch != NO_MOVE || db->lunch != NO_MOVE), | |
1462 | da->moyo_territorial_value | |
1463 | + db->moyo_territorial_value | |
1464 | + terr_val, | |
1465 | (float) da->escape_route); | |
1466 | ||
1467 | /* Kludge: For a CRITICAL dragon, we use the usual effective | |
1468 | * size and give a strategic effect bigger than 2.0 * effective size. | |
1469 | * This is to match the "strategic bonus computation" in | |
1470 | * estimate_strategical_value(). This prefers connection moves that | |
1471 | * owl defend a dragon to other owl defense move. | |
1472 | */ | |
1473 | if (dragon[dragona].status == CRITICAL) { | |
1474 | float bonus = (0.4 - 0.3 * crude_weakness_sum) * sizea; | |
1475 | ||
1476 | if (bonus < 0.0) | |
1477 | bonus = 0.0; | |
1478 | ||
1479 | /* If ahead, give extra bonus to connections. */ | |
1480 | if (margin > 0.0 && bonus > 0.0) | |
1481 | bonus *= 1.0 + 0.05 * margin; | |
1482 | return_value = 2.0 * sizea + bonus; | |
1483 | } | |
1484 | else { | |
1485 | float old_burden = 2.0 * crude_weakness_a * soft_cap(sizea, 15.0); | |
1486 | ||
1487 | /* The new burden is the burden of defending new joint dragon; but | |
1488 | * we share this burden proportionally with the other dragon. | |
1489 | */ | |
1490 | float new_burden = 2.0 * crude_weakness_sum * soft_cap(sizea + sizeb, 15.0) | |
1491 | * sizea / (sizea + sizeb); | |
1492 | ||
1493 | return_value = 1.05 * (old_burden - new_burden); | |
1494 | /* If ahead, give extra bonus to connections. */ | |
1495 | if (margin > 0.0) | |
1496 | return_value *= 1.0 + 0.02 * margin; | |
1497 | } | |
1498 | ||
1499 | if (return_value < 0.0) | |
1500 | return_value = 0.0; | |
1501 | ||
1502 | return return_value; | |
1503 | } | |
1504 | ||
1505 | ||
1506 | /* | |
1507 | * This function computes the shape factor, which multiplies | |
1508 | * the score of a move. We take the largest positive contribution | |
1509 | * to shape and add 1 for each additional positive contribution found. | |
1510 | * Then we take the largest negative contribution to shape, and | |
1511 | * add 1 for each additional negative contribution. The resulting | |
1512 | * number is raised to the power 1.05. | |
1513 | * | |
1514 | * The rationale behind this complicated scheme is that every | |
1515 | * shape point is very significant. If two shape contributions | |
1516 | * with values (say) 5 and 3 are found, the second contribution | |
1517 | * should be devalued to 1. Otherwise the engine is too difficult to | |
1518 | * tune since finding multiple contributions to shape can cause | |
1519 | * significant overvaluing of a move. | |
1520 | */ | |
1521 | ||
1522 | static float | |
1523 | compute_shape_factor(int pos) | |
1524 | { | |
1525 | float exponent = move[pos].maxpos_shape - move[pos].maxneg_shape; | |
1526 | ||
1527 | ASSERT_ON_BOARD1(pos); | |
1528 | if (move[pos].numpos_shape > 1) | |
1529 | exponent += move[pos].numpos_shape - 1; | |
1530 | if (move[pos].numneg_shape > 1) | |
1531 | exponent -= move[pos].numneg_shape - 1; | |
1532 | return pow(1.05, exponent); | |
1533 | } | |
1534 | ||
1535 | ||
1536 | /* | |
1537 | * Usually the value of attacking a worm is twice its effective size, | |
1538 | * but when evaluating certain move reasons we need to adjust this to | |
1539 | * take effects on neighbors into account, e.g. for an attack_either | |
1540 | * move reason. This does not apply to the attack and defense move | |
1541 | * reasons, however, because then the neighbors already have separate | |
1542 | * attack or defense move reasons (if such apply). | |
1543 | * | |
1544 | * If the worm has an adjacent (friendly) dead dragon we add its | |
1545 | * value. At least one of the surrounding dragons must be alive. | |
1546 | * If not, the worm must produce an eye of sufficient size, and that | |
1547 | * should't be accounted for here. As a guess, we suppose that | |
1548 | * a critical dragon is alive for our purpose here. | |
1549 | * | |
1550 | * On the other hand if it has an adjacent critical worm, and | |
1551 | * if (pos) does not defend that worm, we subtract the value of the | |
1552 | * worm, since (pos) may be defended by attacking that worm. We make at | |
1553 | * most one adjustment of each type. | |
1554 | */ | |
1555 | ||
1556 | static float | |
1557 | adjusted_worm_attack_value(int pos, int ww) | |
1558 | { | |
1559 | int num_adj; | |
1560 | int adjs[MAXCHAIN]; | |
1561 | int has_live_neighbor = 0; | |
1562 | float adjusted_value = 2 * worm[ww].effective_size; | |
1563 | float adjustment_up = 0.0; | |
1564 | float adjustment_down = 0.0; | |
1565 | int s; | |
1566 | ||
1567 | num_adj = chainlinks(ww, adjs); | |
1568 | for (s = 0; s < num_adj; s++) { | |
1569 | int adj = adjs[s]; | |
1570 | ||
1571 | if (dragon[adj].status != DEAD) | |
1572 | has_live_neighbor = 1; | |
1573 | ||
1574 | if (dragon[adj].status == DEAD | |
1575 | && 2*dragon[adj].effective_size > adjustment_up) | |
1576 | adjustment_up = 2*dragon[adj].effective_size; | |
1577 | ||
1578 | if (worm[adj].attack_codes[0] != 0 | |
1579 | && !does_defend(pos, adj) | |
1580 | && 2*worm[adj].effective_size > adjustment_down) | |
1581 | adjustment_down = 2*worm[adj].effective_size; | |
1582 | } | |
1583 | ||
1584 | if (has_live_neighbor) | |
1585 | adjusted_value += adjustment_up; | |
1586 | adjusted_value -= adjustment_down; | |
1587 | ||
1588 | /* It can happen that the adjustment down was larger than the effective | |
1589 | * size we started with. In this case we simply return 0.0. (This means | |
1590 | * we ignore the respective EITHER_MOVE reason.) | |
1591 | */ | |
1592 | if (adjusted_value > 0.0) | |
1593 | return adjusted_value; | |
1594 | else | |
1595 | return 0.0; | |
1596 | } | |
1597 | ||
1598 | ||
1599 | /* The new (3.2) territorial evaluation overvalues moves creating a new | |
1600 | * group in the opponent's sphere of influence. The influence module cannot | |
1601 | * see that the opponent will gain by attacking the new (probably weak) | |
1602 | * group. | |
1603 | * This function uses some heuristics to estimate the strategic penalty | |
1604 | * of invasion moves, and moves that try to run away with a group of size | |
1605 | * 1 in front of opponent's strength. | |
1606 | */ | |
1607 | static float | |
1608 | strategic_penalty(int pos, int color) | |
1609 | { | |
1610 | int k; | |
1611 | float ret_val; | |
1612 | ||
1613 | /* We try to detect support from an alive friendly stone by checking | |
1614 | * whether all neighboring intersections belong to the opponent's moyo. | |
1615 | */ | |
1616 | for (k = 0; k < 4; k++) | |
1617 | if (board[pos + delta[k]] == EMPTY | |
1618 | && whose_area(OPPOSITE_INFLUENCE(color), pos + delta[k]) | |
1619 | != OTHER_COLOR(color)) | |
1620 | return 0.0; | |
1621 | if (whose_area(OPPOSITE_INFLUENCE(color), pos) != OTHER_COLOR(color)) | |
1622 | return 0.0; | |
1623 | ||
1624 | for (k = 0; k < MAX_REASONS; k++) { | |
1625 | int r = move[pos].reason[k]; | |
1626 | if (r < 0) | |
1627 | break; | |
1628 | /* We assume that invasion moves can only have the move reasons listed | |
1629 | * below. | |
1630 | * | |
1631 | * FIXME: EXPAND_TERRITORY should always be connected to our own | |
1632 | * stones. Remove later when that change is done. | |
1633 | */ | |
1634 | switch (move_reasons[r].type) { | |
1635 | #if 0 | |
1636 | case EXPAND_TERRITORY_MOVE: | |
1637 | #endif | |
1638 | case EXPAND_MOYO_MOVE: | |
1639 | case STRATEGIC_ATTACK_MOVE: | |
1640 | case INVASION_MOVE: | |
1641 | continue; | |
1642 | /* If we find a tactical defense move, we just test whether it concerns | |
1643 | * a single-stone-dragon; if not, we stop, if yes, we let the necessary | |
1644 | * tests be made in the OWL_DEFEND_MOVE case. | |
1645 | */ | |
1646 | case DEFEND_MOVE: | |
1647 | { | |
1648 | int target = move_reasons[r].what; | |
1649 | if (dragon[target].size > 1) | |
1650 | return 0.0; | |
1651 | continue; | |
1652 | } | |
1653 | /* An owl defense of a single stone might be a stupid attempt to run | |
1654 | * away with an unimportant (kikashi like) stone. We assume this is the | |
1655 | * case if this single stone has a strong hostile direct neighbor. | |
1656 | */ | |
1657 | case OWL_DEFEND_MOVE: | |
1658 | { | |
1659 | int target = move_reasons[r].what; | |
1660 | int has_strong_neighbor = 0; | |
1661 | int has_weak_neighbor = 0; | |
1662 | int i; | |
1663 | /* We award no penalty for running away with a cutting stone. */ | |
1664 | if (dragon[target].size > 1 | |
1665 | || worm[target].cutstone > 0 | |
1666 | || worm[target].cutstone2 > 0) | |
1667 | return 0.0; | |
1668 | /* Third line moves (or lower) are ok -- they try to live, not run | |
1669 | * away. | |
1670 | */ | |
1671 | if (edge_distance(pos) < 3) | |
1672 | return 0.0; | |
1673 | ||
1674 | for (i = 0; i < 4; i++) | |
1675 | if (board[target + delta[i]] == OTHER_COLOR(color)) { | |
1676 | if (dragon[target + delta[i]].size == 1) { | |
1677 | has_weak_neighbor = 1; | |
1678 | break; | |
1679 | } | |
1680 | switch (DRAGON2(target + delta[i]).safety) { | |
1681 | case INVINCIBLE: | |
1682 | case STRONGLY_ALIVE: | |
1683 | has_strong_neighbor = 1; | |
1684 | break; | |
1685 | case ALIVE: | |
1686 | if (DRAGON2(target + delta[i]).weakness > 0.4) | |
1687 | has_weak_neighbor = 1; | |
1688 | break; | |
1689 | default: | |
1690 | has_weak_neighbor = 1; | |
1691 | } | |
1692 | } | |
1693 | if (has_weak_neighbor || (!has_strong_neighbor)) | |
1694 | return 0.0; | |
1695 | else | |
1696 | continue; | |
1697 | } | |
1698 | default: | |
1699 | return 0.0; | |
1700 | } | |
1701 | } | |
1702 | ||
1703 | /* We have to make a guess how much the point where we want to play | |
1704 | * is dominated by the opponent. The territorial valuation is a | |
1705 | * good try here. | |
1706 | */ | |
1707 | ret_val = influence_territory(INITIAL_INFLUENCE(OTHER_COLOR(color)), | |
1708 | pos, OTHER_COLOR(color)); | |
1709 | ret_val *= 12.0; | |
1710 | ret_val = gg_max(0.0, ret_val); | |
1711 | return ret_val; | |
1712 | } | |
1713 | ||
1714 | ||
1715 | /* True if pos is adjacent to a nondead stone of the given color. This | |
1716 | * function can be called when stackp>0 but the result is given for | |
1717 | * the position when stackp==0. It also checks for nondead stones two | |
1718 | * steps away from pos if a move by color at pos cannot be cut off | |
1719 | * from that stone. | |
1720 | * | |
1721 | * FIXME: Move this somewhere more generally accessible, probably | |
1722 | * utils.c | |
1723 | */ | |
1724 | int | |
1725 | adjacent_to_nondead_stone(int pos, int color) | |
1726 | { | |
1727 | int k; | |
1728 | ||
1729 | int stack[MAXSTACK]; | |
1730 | int move_color[MAXSTACK]; | |
1731 | int saved_stackp = stackp; | |
1732 | int result = 0; | |
1733 | ||
1734 | while (stackp > 0) { | |
1735 | get_move_from_stack(stackp - 1, &stack[stackp - 1], | |
1736 | &move_color[stackp - 1]); | |
1737 | popgo(); | |
1738 | } | |
1739 | ||
1740 | if (trymove(pos, color, NULL, EMPTY)) { | |
1741 | for (k = 0; k < 12; k++) { | |
1742 | int pos2; | |
1743 | if (k < 8) | |
1744 | pos2 = pos + delta[k]; | |
1745 | else if (ON_BOARD(pos + delta[k - 8])) | |
1746 | pos2 = pos + 2 * delta[k - 8]; | |
1747 | else | |
1748 | continue; | |
1749 | ||
1750 | if (ON_BOARD(pos2) | |
1751 | && worm[pos2].color == color | |
1752 | && dragon[pos2].status != DEAD | |
1753 | && !disconnect(pos, pos2, NULL)) { | |
1754 | result = 1; | |
1755 | break; | |
1756 | } | |
1757 | } | |
1758 | popgo(); | |
1759 | } | |
1760 | ||
1761 | while (stackp < saved_stackp) | |
1762 | tryko(stack[stackp], move_color[stackp], NULL); | |
1763 | ||
1764 | return result; | |
1765 | } | |
1766 | ||
1767 | static int | |
1768 | max_lunch_eye_value(int pos) | |
1769 | { | |
1770 | int min; | |
1771 | int probable; | |
1772 | int max; | |
1773 | ||
1774 | estimate_lunch_eye_value(pos, &min, &probable, &max, 0); | |
1775 | return max; | |
1776 | } | |
1777 | ||
1778 | /* | |
1779 | * Estimate the direct territorial value of a move at (pos) by (color). | |
1780 | */ | |
1781 | static void | |
1782 | estimate_territorial_value(int pos, int color, float our_score, | |
1783 | int disable_delta_territory_cache) | |
1784 | { | |
1785 | int other = OTHER_COLOR(color); | |
1786 | int k; | |
1787 | int aa = NO_MOVE; | |
1788 | int bb = NO_MOVE; | |
1789 | ||
1790 | float this_value = 0.0; | |
1791 | float tot_value = 0.0; | |
1792 | float secondary_value = 0.0; | |
1793 | ||
1794 | int does_block = 0; | |
1795 | signed char safe_stones[BOARDMAX]; | |
1796 | float strength[BOARDMAX]; | |
1797 | ||
1798 | set_strength_data(OTHER_COLOR(color), safe_stones, strength); | |
1799 | ||
1800 | for (k = 0; k < MAX_REASONS; k++) { | |
1801 | int r = move[pos].reason[k]; | |
1802 | if (r < 0) | |
1803 | break; | |
1804 | if (move_reasons[r].status & TERRITORY_REDUNDANT) | |
1805 | continue; | |
1806 | ||
1807 | this_value = 0.0; | |
1808 | switch (move_reasons[r].type) { | |
1809 | case ATTACK_MOVE: | |
1810 | case ATTACK_MOVE_GOOD_KO: | |
1811 | case ATTACK_MOVE_BAD_KO: | |
1812 | aa = move_reasons[r].what; | |
1813 | ||
1814 | ASSERT1(board[aa] != color, aa); | |
1815 | ||
1816 | /* Defenseless stone. */ | |
1817 | if (worm[aa].defense_codes[0] == 0) { | |
1818 | DEBUG(DEBUG_MOVE_REASONS, | |
1819 | " %1m: %f (secondary) - attack on %1m (defenseless)\n", | |
1820 | pos, worm[aa].effective_size, aa); | |
1821 | secondary_value += worm[aa].effective_size; | |
1822 | does_block = 1; | |
1823 | break; | |
1824 | } | |
1825 | ||
1826 | this_value = 2 * worm[aa].effective_size; | |
1827 | ||
1828 | /* If the stones are dead, there is only a secondary value in | |
1829 | * capturing them tactically as well. | |
1830 | */ | |
1831 | if (dragon[aa].status == DEAD) { | |
1832 | DEBUG(DEBUG_MOVE_REASONS, | |
1833 | " %1m: %f (secondary) - attack on %1m (dead)\n", | |
1834 | pos, 0.2 * this_value, aa); | |
1835 | secondary_value += 0.2 * this_value; | |
1836 | does_block = 1; | |
1837 | break; | |
1838 | } | |
1839 | ||
1840 | /* Mark the string as captured, for evaluation in the influence code. */ | |
1841 | mark_changed_string(aa, safe_stones, strength, 0); | |
1842 | TRACE(" %1m: attack on worm %1m\n", pos, aa); | |
1843 | ||
1844 | /* FIXME: How much should we reduce the value for ko attacks? */ | |
1845 | if (move_reasons[r].type == ATTACK_MOVE) | |
1846 | this_value = 0.0; | |
1847 | else if (move_reasons[r].type == ATTACK_MOVE_GOOD_KO) { | |
1848 | this_value *= 0.3; | |
1849 | TRACE(" %1m: -%f - attack on worm %1m only with good ko\n", | |
1850 | pos, this_value, aa); | |
1851 | } | |
1852 | else if (move_reasons[r].type == ATTACK_MOVE_BAD_KO) { | |
1853 | this_value *= 0.5; | |
1854 | TRACE(" %1m: -%f - attack on worm %1m only with bad ko\n", | |
1855 | pos, this_value, aa); | |
1856 | } | |
1857 | ||
1858 | tot_value -= this_value; | |
1859 | does_block = 1; | |
1860 | break; | |
1861 | ||
1862 | case DEFEND_MOVE: | |
1863 | case DEFEND_MOVE_GOOD_KO: | |
1864 | case DEFEND_MOVE_BAD_KO: | |
1865 | aa = move_reasons[r].what; | |
1866 | ||
1867 | ASSERT1(board[aa] == color, aa); | |
1868 | ||
1869 | /* | |
1870 | * Estimate value | |
1871 | */ | |
1872 | this_value = 2 * worm[aa].effective_size; | |
1873 | ||
1874 | /* If the stones are dead, we use the convention that | |
1875 | * defending them has a strategical value rather than | |
1876 | * territorial. Admittedly this make more sense for attacks on | |
1877 | * dead stones. | |
1878 | */ | |
1879 | if (dragon[aa].status == DEAD) { | |
1880 | DEBUG(DEBUG_MOVE_REASONS, | |
1881 | " %1m: %f (secondary) - defense of %1m (dead)\n", | |
1882 | pos, 0.2 * this_value, aa); | |
1883 | secondary_value += 0.2 * this_value; | |
1884 | break; | |
1885 | } | |
1886 | ||
1887 | if (DRAGON2(aa).owl_status == CRITICAL | |
1888 | && (owl_defense_move_reason_known(pos, aa) | |
1889 | < defense_move_reason_known(pos, aa)) | |
1890 | && !semeai_move_reason_known(pos, aa)) { | |
1891 | DEBUG(DEBUG_MOVE_REASONS, | |
1892 | " %1m: %f (secondary) - ineffective defense of %1m (critical)\n", | |
1893 | pos, 0.2 * this_value, aa); | |
1894 | secondary_value += 0.2 * this_value; | |
1895 | break; | |
1896 | } | |
1897 | ||
1898 | /* Mark the string as saved, for evaluation in the influence code. */ | |
1899 | mark_changed_string(aa, safe_stones, strength, INFLUENCE_SAVED_STONE); | |
1900 | TRACE(" %1m: defense of worm %1m\n", pos, aa); | |
1901 | ||
1902 | /* FIXME: How much should we reduce the value for ko defenses? */ | |
1903 | if (move_reasons[r].type == DEFEND_MOVE) | |
1904 | this_value = 0.0; | |
1905 | else if (move_reasons[r].type == DEFEND_MOVE_GOOD_KO) { | |
1906 | this_value *= 0.3; | |
1907 | TRACE(" %1m: -%f - defense of worm %1m with good ko\n", | |
1908 | pos, this_value, aa); | |
1909 | } | |
1910 | else if (move_reasons[r].type == DEFEND_MOVE_BAD_KO) { | |
1911 | this_value *= 0.5; | |
1912 | TRACE(" %1m: -%f - defense of worm %1m with bad ko\n", | |
1913 | pos, this_value, aa); | |
1914 | } | |
1915 | ||
1916 | tot_value -= this_value; | |
1917 | ||
1918 | /* If a move tactically defends an owl critical string, but | |
1919 | * this move is not listed as an owl defense, it probably is | |
1920 | * ineffective. The 0.45 factor is chosen so that even in | |
1921 | * combination with bad ko it still has a positive net impact. | |
1922 | */ | |
1923 | if (DRAGON2(aa).owl_status == CRITICAL | |
1924 | && (owl_defense_move_reason_known(pos, aa) | |
1925 | < defense_move_reason_known(pos, aa))) { | |
1926 | this_value = 0.45 * (2 * worm[aa].effective_size); | |
1927 | TRACE(" %1m: -%f - suspected ineffective defense of worm %1m\n", | |
1928 | pos, this_value, aa); | |
1929 | tot_value -= this_value; | |
1930 | } | |
1931 | ||
1932 | does_block = 1; | |
1933 | break; | |
1934 | ||
1935 | case ATTACK_THREAT: | |
1936 | aa = move_reasons[r].what; | |
1937 | ||
1938 | /* Make sure this is a threat to attack opponent stones. */ | |
1939 | ASSERT1(board[aa] == other, aa); | |
1940 | ||
1941 | if (dragon[aa].status == DEAD) { | |
1942 | DEBUG(DEBUG_MOVE_REASONS, | |
1943 | " %1m: 0.0 - threatens to capture %1m (dead)\n", pos, aa); | |
1944 | break; | |
1945 | } | |
1946 | ||
1947 | /* The followup value of a move threatening to attack (aa) | |
1948 | * is twice its effective size, with adjustments. If the | |
1949 | * worm has an adjacent (friendly) dead dragon we add its | |
1950 | * value. On the other hand if it has an adjacent critical | |
1951 | * worm, and if (pos) does not defend that worm, we subtract | |
1952 | * the value of the worm, since (aa) may be defended by | |
1953 | * attacking that worm. We make at most one adjustment | |
1954 | * of each type. | |
1955 | * | |
1956 | * No followup value is awarded if the defense move is a threat | |
1957 | * back on our move because we're likely to end in gote then, | |
1958 | * unless the move is unsafe anyway and played as a ko threat. | |
1959 | * | |
1960 | * FIXME: It might be possible that parts of the dragon | |
1961 | * can be cut in the process of capturing the (aa) | |
1962 | * worm. In that case, not the entire size of the | |
1963 | * adjacent dead dragon should be counted as a positive | |
1964 | * adjustment. However, it seems difficult to do this | |
1965 | * analysis, and in most cases it won't apply, so we | |
1966 | * leave it as it is for now. | |
1967 | * | |
1968 | * FIXME: The same analysis should be applied to | |
1969 | * DEFEND_THREAT, | |
1970 | * ATTACK_EITHER_MOVE, DEFEND_BOTH_MOVE. It should be | |
1971 | * broken out as separate functions and dealt with in | |
1972 | * a structured manner. | |
1973 | */ | |
1974 | ||
1975 | if (trymove(pos, color, "estimate_territorial_value-A", NO_MOVE)) { | |
1976 | int adjs[MAXCHAIN]; | |
1977 | float adjusted_value = 2 * worm[aa].effective_size; | |
1978 | float adjustment_up = 0.0; | |
1979 | float adjustment_down = 0.0; | |
1980 | int s; | |
1981 | int num_adj; | |
1982 | int defense_move; | |
1983 | ||
1984 | /* In rare cases it may happen that the trymove() above | |
1985 | * actually removed the string at aa. | |
1986 | */ | |
1987 | if (board[aa] == EMPTY) | |
1988 | num_adj = 0; | |
1989 | else | |
1990 | num_adj = chainlinks(aa, adjs); | |
1991 | ||
1992 | /* No followup value if string can be defended with threat | |
1993 | * against our move. An exception to this is when our move | |
1994 | * isn't safe anyway and we play this only for the followup | |
1995 | * value, typically as a ko threat. Though, "suspicious" owl | |
1996 | * defenses (move_safety != 1) are still tested for possible | |
1997 | * backfires. | |
1998 | * | |
1999 | * This rule may be overwritten with patterns. See pattern | |
2000 | * Sente22 and related test trevord:950 for an example. | |
2001 | * | |
2002 | * FIXME: This is somewhat halfhearted since only one defense | |
2003 | * move is tested. | |
2004 | */ | |
2005 | if (!is_known_good_attack_threat(pos, aa) | |
2006 | && board[aa] != EMPTY | |
2007 | && (move[pos].move_safety == 1 | |
2008 | || adjacent_to_nondead_stone(pos, color) | |
2009 | || owl_defense_move_reason_known(pos, -1)) | |
2010 | && find_defense(aa, &defense_move) == WIN | |
2011 | && defense_move != NO_MOVE) { | |
2012 | int bad_followup; | |
2013 | int attack_move; | |
2014 | ||
2015 | if (attack(pos, &attack_move) != WIN) { | |
2016 | int i; | |
2017 | ||
2018 | if (trymove(defense_move, other, | |
2019 | "estimate_territorial_value-b", NO_MOVE)) { | |
2020 | if (board[pos] == EMPTY || attack(pos, NULL) != 0) { | |
2021 | popgo(); | |
2022 | popgo(); | |
2023 | break; | |
2024 | } | |
2025 | ||
2026 | /* Now check all `ATTACK_MOVE' reasons for this same | |
2027 | * move. If the defense against current threat makes a | |
2028 | * string attacked by this move defendable, we reduce | |
2029 | * the followup. | |
2030 | * | |
2031 | * Adjustments done later are concerned with current | |
2032 | * dragon states. Here we actually try to check if | |
2033 | * opponent's reply to our move will have a followup in | |
2034 | * turn. | |
2035 | */ | |
2036 | for (i = 0; i < MAX_REASONS; i++) { | |
2037 | int reason = move[pos].reason[i]; | |
2038 | int attacked_string; | |
2039 | if (reason < 0) | |
2040 | break; | |
2041 | ||
2042 | attacked_string = move_reasons[reason].what; | |
2043 | if (move_reasons[reason].type == ATTACK_MOVE | |
2044 | && board[attacked_string] == other) { | |
2045 | int defense_code = find_defense(attacked_string, NULL); | |
2046 | double down_coefficient = 0.0; | |
2047 | ||
2048 | switch (defense_code) { | |
2049 | case WIN: | |
2050 | down_coefficient = 2.0; | |
2051 | break; | |
2052 | ||
2053 | case KO_A: | |
2054 | down_coefficient = 2.0 * 0.5; | |
2055 | break; | |
2056 | ||
2057 | case KO_B: | |
2058 | down_coefficient = 2.0 * 0.7; | |
2059 | break; | |
2060 | } | |
2061 | ||
2062 | if (adjustment_down | |
2063 | < (worm[attacked_string].effective_size | |
2064 | * down_coefficient)) { | |
2065 | adjustment_down = (worm[attacked_string].effective_size | |
2066 | * down_coefficient); | |
2067 | } | |
2068 | } | |
2069 | } | |
2070 | ||
2071 | popgo(); | |
2072 | } | |
2073 | } | |
2074 | else { | |
2075 | /* Our move is attackable to begin with. However, maybe | |
2076 | * the attack is not sufficient to defend opponent's | |
2077 | * string? | |
2078 | */ | |
2079 | if (trymove(attack_move, other, | |
2080 | "estimate_territorial_value-c", NO_MOVE)) { | |
2081 | if (attack(aa, NULL) == 0) { | |
2082 | /* It is sufficient, no followup. */ | |
2083 | popgo(); | |
2084 | popgo(); | |
2085 | break; | |
2086 | } | |
2087 | ||
2088 | popgo(); | |
2089 | } | |
2090 | ||
2091 | /* Heuristically reduce the followup, since our string | |
2092 | * will be still attackable if opponent defends his | |
2093 | * string. | |
2094 | */ | |
2095 | adjustment_down = 2 * countstones(pos); | |
2096 | } | |
2097 | ||
2098 | bad_followup = 0; | |
2099 | for (s = 0; s < num_adj; s++) { | |
2100 | int lib; | |
2101 | if (countlib(adjs[s]) == 1) { | |
2102 | findlib(adjs[s], 1, &lib); | |
2103 | if (trymove(lib, other, | |
2104 | "estimate_territorial_value-d", NO_MOVE)) { | |
2105 | if (!attack(aa, NULL) | |
2106 | && (board[pos] == EMPTY || attack(pos, NULL) != 0)) { | |
2107 | popgo(); | |
2108 | bad_followup = 1; | |
2109 | break; | |
2110 | } | |
2111 | popgo(); | |
2112 | } | |
2113 | } | |
2114 | } | |
2115 | if (bad_followup) { | |
2116 | popgo(); | |
2117 | break; | |
2118 | } | |
2119 | } | |
2120 | ||
2121 | for (s = 0; s < num_adj; s++) { | |
2122 | int adj = adjs[s]; | |
2123 | ||
2124 | if (same_string(pos, adj)) | |
2125 | continue; | |
2126 | if (dragon[adj].color == color | |
2127 | && dragon[adj].status == DEAD | |
2128 | && 2*dragon[adj].effective_size > adjustment_up) | |
2129 | adjustment_up = 2*dragon[adj].effective_size; | |
2130 | if (dragon[adj].color == color | |
2131 | && attack(adj, NULL) | |
2132 | && 2*worm[adj].effective_size > adjustment_down) | |
2133 | adjustment_down = 2*worm[adj].effective_size; | |
2134 | } | |
2135 | ||
2136 | popgo(); | |
2137 | ||
2138 | /* No followup if the string is not substantial. */ | |
2139 | { | |
2140 | int save_verbose = verbose; | |
2141 | if (verbose > 0) | |
2142 | verbose --; | |
2143 | if (move[pos].move_safety == 0 | |
2144 | && !owl_substantial(aa)) { | |
2145 | verbose = save_verbose; | |
2146 | break; | |
2147 | } | |
2148 | verbose = save_verbose; | |
2149 | } | |
2150 | ||
2151 | adjusted_value += adjustment_up; | |
2152 | adjusted_value -= adjustment_down; | |
2153 | if (adjusted_value > 0.0) { | |
2154 | add_followup_value(pos, adjusted_value); | |
2155 | TRACE(" %1m: %f (followup) - threatens to capture %1m\n", | |
2156 | pos, adjusted_value, aa); | |
2157 | } | |
2158 | } | |
2159 | break; | |
2160 | ||
2161 | case DEFEND_THREAT: | |
2162 | aa = move_reasons[r].what; | |
2163 | ||
2164 | /* Make sure this is a threat to defend our stones. */ | |
2165 | ASSERT1(board[aa] == color, aa); | |
2166 | ||
2167 | /* We don't trust tactical defense threats as ko threats, unless | |
2168 | * the move is safe. | |
2169 | */ | |
2170 | if (move[pos].move_safety == 0) | |
2171 | break; | |
2172 | ||
2173 | /* No followup value if string can be attacked with threat | |
2174 | * against our move. An exception to this is when our move | |
2175 | * isn't safe anyway and we play this only for the followup | |
2176 | * value, typically as a ko threat. | |
2177 | * | |
2178 | * FIXME: This is somewhat halfhearted since only one attack | |
2179 | * move is tested. | |
2180 | */ | |
2181 | if (trymove(pos, color, "estimate_territorial_value-A", NO_MOVE)) { | |
2182 | int attack_move; | |
2183 | if (move[pos].move_safety == 1 | |
2184 | && attack(aa, &attack_move) == WIN | |
2185 | && attack_move != NO_MOVE) { | |
2186 | if (trymove(attack_move, other, | |
2187 | "estimate_territorial_value-b", NO_MOVE)) { | |
2188 | if (board[pos] == EMPTY || attack(pos, NULL) != 0) { | |
2189 | popgo(); | |
2190 | popgo(); | |
2191 | break; | |
2192 | } | |
2193 | popgo(); | |
2194 | } | |
2195 | } | |
2196 | popgo(); | |
2197 | } | |
2198 | ||
2199 | add_followup_value(pos, 2 * worm[aa].effective_size); | |
2200 | ||
2201 | TRACE(" %1m: %f (followup) - threatens to defend %1m\n", | |
2202 | pos, 2 * worm[aa].effective_size, aa); | |
2203 | ||
2204 | break; | |
2205 | ||
2206 | case UNCERTAIN_OWL_DEFENSE: | |
2207 | /* This move reason is valued as a strategical value. */ | |
2208 | break; | |
2209 | ||
2210 | case CUT_MOVE: | |
2211 | case EXPAND_MOYO_MOVE: | |
2212 | case EXPAND_TERRITORY_MOVE: | |
2213 | case INVASION_MOVE: | |
2214 | does_block = 1; | |
2215 | break; | |
2216 | ||
2217 | case CONNECT_MOVE: | |
2218 | /* This used to always set does_block=1, but there is no | |
2219 | * guarantee that a connection move is strategically safe. See | |
2220 | * for example gunnar:72. | |
2221 | */ | |
2222 | if (move[pos].move_safety) | |
2223 | does_block = 1; | |
2224 | break; | |
2225 | ||
2226 | case STRATEGIC_ATTACK_MOVE: | |
2227 | case STRATEGIC_DEFEND_MOVE: | |
2228 | /* Do not trust these when we are scoring. Maybe we shouldn't | |
2229 | * trust them otherwise either but require them to be | |
2230 | * accompanied by e.g. an EXPAND move reason. | |
2231 | */ | |
2232 | if (!doing_scoring) | |
2233 | does_block = 1; | |
2234 | break; | |
2235 | ||
2236 | case SEMEAI_THREAT: | |
2237 | aa = move_reasons[r].what; | |
2238 | ||
2239 | /* threaten to win the semeai as a ko threat */ | |
2240 | add_followup_value(pos, 2 * dragon[aa].effective_size); | |
2241 | TRACE(" %1m: %f (followup) - threatens to win semeai for %1m\n", | |
2242 | pos, 2 * dragon[aa].effective_size, aa); | |
2243 | break; | |
2244 | ||
2245 | case SEMEAI_MOVE: | |
2246 | case OWL_ATTACK_MOVE: | |
2247 | case OWL_ATTACK_MOVE_GOOD_KO: | |
2248 | case OWL_ATTACK_MOVE_BAD_KO: | |
2249 | case OWL_ATTACK_MOVE_GAIN: | |
2250 | case OWL_DEFEND_MOVE: | |
2251 | case OWL_DEFEND_MOVE_GOOD_KO: | |
2252 | case OWL_DEFEND_MOVE_BAD_KO: | |
2253 | case OWL_DEFEND_MOVE_LOSS: | |
2254 | ||
2255 | if (move_reasons[r].type == OWL_ATTACK_MOVE_GAIN | |
2256 | || move_reasons[r].type == OWL_DEFEND_MOVE_LOSS) { | |
2257 | aa = either_data[move_reasons[r].what].what1; | |
2258 | bb = either_data[move_reasons[r].what].what2; | |
2259 | } | |
2260 | else { | |
2261 | aa = move_reasons[r].what; | |
2262 | bb = NO_MOVE; | |
2263 | } | |
2264 | ||
2265 | /* If the dragon is a single ko stone, the owl code currently | |
2266 | * won't detect that the owl attack is conditional. As a | |
2267 | * workaround we deduct 0.5 points for the move here, but only | |
2268 | * if the move is a liberty of the string. | |
2269 | */ | |
2270 | if (dragon[aa].size == 1 | |
2271 | && is_ko_point(aa) | |
2272 | && liberty_of_string(pos, aa)) { | |
2273 | TRACE(" %1m: -0.5 - penalty for ko stone %1m (workaround)\n", | |
2274 | pos, aa); | |
2275 | tot_value -= 0.5; | |
2276 | } | |
2277 | ||
2278 | /* Mark the affected dragon for use in the territory analysis. */ | |
2279 | mark_changed_dragon(pos, color, aa, bb, move_reasons[r].type, | |
2280 | safe_stones, strength, &this_value); | |
2281 | this_value *= 2.0; | |
2282 | ||
2283 | TRACE(" %1m: owl attack/defend for %1m\n", pos, aa); | |
2284 | ||
2285 | /* FIXME: How much should we reduce the value for ko attacks? */ | |
2286 | if (move_reasons[r].type == OWL_ATTACK_MOVE | |
2287 | || move_reasons[r].type == OWL_DEFEND_MOVE | |
2288 | || move_reasons[r].type == SEMEAI_MOVE) | |
2289 | this_value = 0.0; | |
2290 | else if (move_reasons[r].type == OWL_ATTACK_MOVE_GOOD_KO | |
2291 | || move_reasons[r].type == OWL_DEFEND_MOVE_GOOD_KO) { | |
2292 | this_value *= 0.3; | |
2293 | TRACE(" %1m: -%f - owl attack/defense of %1m only with good ko\n", | |
2294 | pos, this_value, aa); | |
2295 | } | |
2296 | else if (move_reasons[r].type == OWL_ATTACK_MOVE_BAD_KO | |
2297 | || move_reasons[r].type == OWL_DEFEND_MOVE_BAD_KO) { | |
2298 | this_value *= 0.5; | |
2299 | TRACE(" %1m: -%f - owl attack/defense of %1m only with bad ko\n", | |
2300 | pos, this_value, aa); | |
2301 | } | |
2302 | else if (move_reasons[r].type == OWL_ATTACK_MOVE_GAIN | |
2303 | || move_reasons[r].type == OWL_DEFEND_MOVE_LOSS) { | |
2304 | this_value = 0.0; | |
2305 | } | |
2306 | ||
2307 | tot_value -= this_value; | |
2308 | ||
2309 | /* If the dragon is a single string which can be tactically | |
2310 | * attacked, but this owl attack does not attack tactically, it | |
2311 | * can be suspected to leave some unnecessary aji or even be an | |
2312 | * owl misread. Therefore we give it a small penalty to favor | |
2313 | * the moves which do attack tactically as well. | |
2314 | * | |
2315 | * One example is manyfaces:2 where the single stone S15 can be | |
2316 | * tactically attacked at S16 but where 3.3.2 finds additional | |
2317 | * owl attacks at R14 (clearly ineffective) and T15 (might work, | |
2318 | * but leaves huge amounts of aji). | |
2319 | */ | |
2320 | if ((move_reasons[r].type == OWL_ATTACK_MOVE | |
2321 | || move_reasons[r].type == OWL_ATTACK_MOVE_GOOD_KO | |
2322 | || move_reasons[r].type == OWL_ATTACK_MOVE_BAD_KO) | |
2323 | && dragon[aa].size == worm[aa].size | |
2324 | && worm[aa].attack_codes[0] == WIN | |
2325 | && worm[aa].defense_codes[0] != 0 | |
2326 | && attack_move_reason_known(pos, aa) != WIN) { | |
2327 | if (large_scale) | |
2328 | this_value = (2.0 + 0.05 * (2 * worm[aa].effective_size)); | |
2329 | else | |
2330 | this_value = 0.05 * (2 * worm[aa].effective_size); | |
2331 | TRACE(" %1m: -%f - suspected ineffective owl attack of worm %1m\n", | |
2332 | pos, this_value, aa); | |
2333 | tot_value -= this_value; | |
2334 | } | |
2335 | ||
2336 | does_block = 1; | |
2337 | break; | |
2338 | ||
2339 | case OWL_ATTACK_THREAT: | |
2340 | aa = move_reasons[r].what; | |
2341 | ||
2342 | if (dragon[aa].status == DEAD) { | |
2343 | DEBUG(DEBUG_MOVE_REASONS, | |
2344 | " %1m: 0.0 - threatens to owl attack %1m (dead)\n", pos, aa); | |
2345 | break; | |
2346 | } | |
2347 | ||
2348 | /* The followup value of a move threatening to attack (aa) is | |
2349 | * twice its effective size, unless it has an adjacent | |
2350 | * (friendly) critical dragon. In that case it's probably a | |
2351 | * mistake to make the threat since it can defend itself with | |
2352 | * profit. | |
2353 | * | |
2354 | * FIXME: We probably need to verify that the critical dragon is | |
2355 | * substantial enough that capturing it saves the threatened | |
2356 | * dragon. | |
2357 | */ | |
2358 | { | |
2359 | float value = 2 * dragon[aa].effective_size; | |
2360 | int s; | |
2361 | ||
2362 | for (s = 0; s < DRAGON2(aa).neighbors; s++) { | |
2363 | int d = DRAGON2(aa).adjacent[s]; | |
2364 | int adj = dragon2[d].origin; | |
2365 | ||
2366 | if (dragon[adj].color == color | |
2367 | && dragon[adj].status == CRITICAL | |
2368 | && dragon2[d].safety != INESSENTIAL | |
2369 | && !owl_defense_move_reason_known(pos, adj)) | |
2370 | value = 0.0; | |
2371 | } | |
2372 | ||
2373 | if (value > 0.0) { | |
2374 | add_followup_value(pos, value); | |
2375 | TRACE(" %1m: %f (followup) - threatens to owl attack %1m\n", | |
2376 | pos, value, aa); | |
2377 | } | |
2378 | } | |
2379 | break; | |
2380 | ||
2381 | case OWL_DEFEND_THREAT: | |
2382 | aa = move_reasons[r].what; | |
2383 | ||
2384 | add_followup_value(pos, 2 * dragon[aa].effective_size); | |
2385 | TRACE(" %1m: %f (followup) - threatens to owl defend %1m\n", | |
2386 | pos, 2 * dragon[aa].effective_size, aa); | |
2387 | break; | |
2388 | ||
2389 | case OWL_PREVENT_THREAT: | |
2390 | /* A move attacking a dragon whose defense can be threatened. | |
2391 | */ | |
2392 | aa = move_reasons[r].what; | |
2393 | ||
2394 | if (dragon[aa].status != DEAD) { | |
2395 | DEBUG(DEBUG_MOVE_REASONS, | |
2396 | " %1m: 0.0 - prevent defense threat (dragon is not dead)\n", | |
2397 | pos); | |
2398 | break; | |
2399 | } | |
2400 | ||
2401 | /* If the opponent just added a stone to a dead dragon, then | |
2402 | * attack it. If we are ahead, add a safety move here, at most | |
2403 | * half the margin of victory. | |
2404 | * | |
2405 | * This does not apply if we are doing scoring. | |
2406 | */ | |
2407 | if (!doing_scoring | |
2408 | && is_same_dragon(get_last_opponent_move(color), aa)) { | |
2409 | this_value = 1.5 * dragon[aa].effective_size; | |
2410 | TRACE(" %1m: %f - attack last move played, although it seems dead\n", | |
2411 | pos, this_value); | |
2412 | tot_value += this_value * attack_dragon_weight; | |
2413 | } | |
2414 | else if (!doing_scoring && our_score > 0.0) { | |
2415 | /* tm - devalued this bonus (3.1.17) */ | |
2416 | this_value = gg_min(0.9 * dragon[aa].effective_size, | |
2417 | our_score/2.0 - board_size/2.0 - 1.0); | |
2418 | this_value = gg_max(this_value, 0); | |
2419 | TRACE(" %1m: %f - attack %1m, although it seems dead, as we are ahead\n", | |
2420 | pos, this_value, aa); | |
2421 | tot_value += this_value * attack_dragon_weight; | |
2422 | } | |
2423 | else { | |
2424 | ||
2425 | add_reverse_followup_value(pos, 2 * dragon[aa].effective_size); | |
2426 | if (board[aa] == color) | |
2427 | TRACE(" %1m: %f (reverse followup) - prevent threat to attack %1m\n", | |
2428 | pos, 2 * dragon[aa].effective_size, aa); | |
2429 | else | |
2430 | TRACE(" %1m: %f (reverse followup) - prevent threat to defend %1m\n", | |
2431 | pos, 2 * dragon[aa].effective_size, aa); | |
2432 | } | |
2433 | break; | |
2434 | ||
2435 | case MY_ATARI_ATARI_MOVE: | |
2436 | /* Add 1.0 to compensate for -1.0 penalty because the move is | |
2437 | * thought to be a sacrifice. | |
2438 | */ | |
2439 | this_value = move_reasons[r].what + 1.0; | |
2440 | tot_value += this_value; | |
2441 | TRACE(" %1m: %f - combination attack kills one of several worms\n", | |
2442 | pos, this_value); | |
2443 | break; | |
2444 | ||
2445 | case YOUR_ATARI_ATARI_MOVE: | |
2446 | /* Set does_block to force territorial valuation of the move. | |
2447 | * That way we can prefer defenses against combination attacks | |
2448 | * on dame points instead of inside territory. | |
2449 | */ | |
2450 | does_block = 1; | |
2451 | this_value = move_reasons[r].what; | |
2452 | tot_value += this_value; | |
2453 | TRACE(" %1m: %f - defends against combination attack on several worms\n", | |
2454 | pos, this_value); | |
2455 | break; | |
2456 | } | |
2457 | } | |
2458 | ||
2459 | /* Currently no difference in the valuation between blocking and | |
2460 | * expanding moves. | |
2461 | */ | |
2462 | this_value = 0.0; | |
2463 | ||
2464 | mark_inessential_stones(OTHER_COLOR(color), safe_stones); | |
2465 | ||
2466 | if (move[pos].move_safety == 1 | |
2467 | && (is_known_safe_move(pos) || safe_move(pos, color) != 0)) { | |
2468 | safe_stones[pos] = INFLUENCE_SAVED_STONE; | |
2469 | strength[pos] = DEFAULT_STRENGTH; | |
2470 | if (0) | |
2471 | TRACE(" %1m: is a safe move\n", pos); | |
2472 | } | |
2473 | else { | |
2474 | TRACE(" %1m: not a safe move\n", pos); | |
2475 | safe_stones[pos] = 0; | |
2476 | strength[pos] = 0.0; | |
2477 | } | |
2478 | ||
2479 | /* We don't check for move safety here. This enables a territorial | |
2480 | * evaluation for sacrifice moves that enable a break-through (or | |
2481 | * an owl defense). | |
2482 | */ | |
2483 | if (does_block | |
2484 | && tryko(pos, color, "estimate_territorial_value")) { | |
2485 | Hash_data safety_hash = goal_to_hashvalue(safe_stones); | |
2486 | if (disable_delta_territory_cache | |
2487 | || !retrieve_delta_territory_cache(pos, color, &this_value, | |
2488 | &move[pos].influence_followup_value, | |
2489 | OPPOSITE_INFLUENCE(color), | |
2490 | safety_hash)) { | |
2491 | ||
2492 | compute_influence(OTHER_COLOR(color), safe_stones, strength, | |
2493 | &move_influence, pos, "after move"); | |
2494 | increase_depth_values(); | |
2495 | break_territories(OTHER_COLOR(color), &move_influence, 0, pos); | |
2496 | decrease_depth_values(); | |
2497 | this_value = influence_delta_territory(OPPOSITE_INFLUENCE(color), | |
2498 | &move_influence, color, pos); | |
2499 | compute_followup_influence(&move_influence, &followup_influence, | |
2500 | pos, "followup"); | |
2501 | ||
2502 | if (this_value != 0.0) | |
2503 | TRACE("%1m: %f - change in territory\n", pos, this_value); | |
2504 | else | |
2505 | DEBUG(DEBUG_MOVE_REASONS, "%1m: 0.00 - change in territory\n", pos); | |
2506 | move[pos].influence_followup_value | |
2507 | = influence_delta_territory(&move_influence, &followup_influence, | |
2508 | color, pos); | |
2509 | store_delta_territory_cache(pos, color, this_value, | |
2510 | move[pos].influence_followup_value, | |
2511 | OPPOSITE_INFLUENCE(color), safety_hash); | |
2512 | } | |
2513 | else { | |
2514 | if (this_value != 0.0) | |
2515 | TRACE("%1m: %f - change in territory (cached)\n", pos, this_value); | |
2516 | else | |
2517 | DEBUG(DEBUG_MOVE_REASONS, | |
2518 | "%1m: 0.00 - change in territory (cached)\n", pos); | |
2519 | } | |
2520 | popgo(); | |
2521 | ||
2522 | } | |
2523 | ||
2524 | tot_value += this_value; | |
2525 | ||
2526 | /* Test if min_territory or max_territory values constrain the | |
2527 | * delta_territory value. | |
2528 | */ | |
2529 | if (tot_value < move[pos].min_territory | |
2530 | && move[pos].min_territory > 0) { | |
2531 | tot_value = move[pos].min_territory; | |
2532 | TRACE(" %1m: %f - revised to meet minimum territory value\n", | |
2533 | pos, tot_value); | |
2534 | } | |
2535 | if (tot_value > move[pos].max_territory) { | |
2536 | tot_value = move[pos].max_territory; | |
2537 | TRACE(" %1m: %f - revised to meet maximum territory value\n", | |
2538 | pos, tot_value); | |
2539 | } | |
2540 | ||
2541 | move[pos].territorial_value = tot_value; | |
2542 | move[pos].secondary_value += secondary_value; | |
2543 | } | |
2544 | ||
2545 | ||
2546 | /* | |
2547 | * Estimate the strategical value of a move at (pos). | |
2548 | */ | |
2549 | static void | |
2550 | estimate_strategical_value(int pos, int color, float our_score, | |
2551 | int use_thrashing_dragon_heuristics) | |
2552 | { | |
2553 | int k; | |
2554 | int l; | |
2555 | int aa = NO_MOVE; | |
2556 | int bb = NO_MOVE; | |
2557 | float aa_value = 0.0; | |
2558 | float bb_value = 0.0; | |
2559 | ||
2560 | float this_value = 0.0; | |
2561 | float tot_value = 0.0; | |
2562 | ||
2563 | /* Strategical value of connecting or cutting dragons. */ | |
2564 | float dragon_value[BOARDMAX]; | |
2565 | ||
2566 | for (aa = BOARDMIN; aa < BOARDMAX; aa++) | |
2567 | dragon_value[aa] = 0.0; | |
2568 | ||
2569 | for (k = 0; k < MAX_REASONS; k++) { | |
2570 | int r = move[pos].reason[k]; | |
2571 | if (r < 0) | |
2572 | break; | |
2573 | if (move_reasons[r].status & STRATEGICALLY_REDUNDANT) | |
2574 | continue; | |
2575 | ||
2576 | this_value = 0.0; | |
2577 | switch (move_reasons[r].type) { | |
2578 | case ATTACK_MOVE: | |
2579 | case ATTACK_MOVE_GOOD_KO: | |
2580 | case ATTACK_MOVE_BAD_KO: | |
2581 | case DEFEND_MOVE: | |
2582 | case DEFEND_MOVE_GOOD_KO: | |
2583 | case DEFEND_MOVE_BAD_KO: | |
2584 | aa = move_reasons[r].what; | |
2585 | ||
2586 | /* Defenseless stone */ | |
2587 | if (worm[aa].defense_codes[0] == 0) | |
2588 | break; | |
2589 | ||
2590 | if (doing_scoring && dragon[aa].status == DEAD) | |
2591 | break; | |
2592 | ||
2593 | /* FIXME: This is totally ad hoc, just guessing the value of | |
2594 | * potential cutting points. | |
2595 | * FIXME: When worm[aa].cutstone2 == 1 we should probably add | |
2596 | * a followup value. | |
2597 | */ | |
2598 | if (worm[aa].cutstone2 > 1 && !worm[aa].inessential) { | |
2599 | double ko_factor = 1; | |
2600 | if (move_reasons[r].type == ATTACK_MOVE_GOOD_KO | |
2601 | || move_reasons[r].type == DEFEND_MOVE_GOOD_KO) { | |
2602 | ko_factor = 0.6; | |
2603 | } | |
2604 | else if (move_reasons[r].type == ATTACK_MOVE_BAD_KO | |
2605 | || move_reasons[r].type == DEFEND_MOVE_BAD_KO) { | |
2606 | ko_factor = 0.4; | |
2607 | } | |
2608 | this_value = 10.0 * (worm[aa].cutstone2 - 1) * ko_factor; | |
2609 | TRACE(" %1m: %f - %1m cutstone\n", pos, this_value, aa); | |
2610 | } | |
2611 | ||
2612 | tot_value += this_value; | |
2613 | ||
2614 | /* If the string is a lunch for a weak dragon, the attack or | |
2615 | * defense has a strategical value. This can be valued along | |
2616 | * the same lines as strategic_attack/strategic_defend. | |
2617 | * | |
2618 | * No points are awarded if the lunch is an inessential dragon | |
2619 | * or worm. | |
2620 | */ | |
2621 | if (DRAGON2(aa).safety == INESSENTIAL | |
2622 | || worm[aa].inessential) | |
2623 | break; | |
2624 | ||
2625 | /* If the lunch has no potential to create eyes, no points. */ | |
2626 | if (max_lunch_eye_value(aa) == 0) | |
2627 | break; | |
2628 | ||
2629 | /* Can't use k in this loop too. */ | |
2630 | for (l = 0; l < next_lunch; l++) | |
2631 | if (lunch_worm[l] == aa) { | |
2632 | bb = lunch_dragon[l]; | |
2633 | ||
2634 | /* FIXME: This value cannot be computed without some measurement | |
2635 | * of how the actual move affects the dragon. The dragon safety | |
2636 | * alone is not enough. The question is whether the dragon is | |
2637 | * threatened or defended by the move or not. | |
2638 | */ | |
2639 | this_value = 1.8 * soft_cap(DRAGON2(bb).strategic_size, 15.0) | |
2640 | * dragon_weakness(bb, 0); | |
2641 | ||
2642 | /* If this dragon consists of only one worm and that worm | |
2643 | * can be tactically captured or defended by this move, we | |
2644 | * have already counted the points as territorial value, | |
2645 | * unless it's assumed to be dead. | |
2646 | */ | |
2647 | if (dragon[bb].status != DEAD | |
2648 | && dragon[bb].size == worm[bb].size | |
2649 | && (attack_move_reason_known(pos, bb) | |
2650 | || defense_move_reason_known(pos, bb))) | |
2651 | this_value = 0.0; | |
2652 | ||
2653 | /* If this dragon can be tactically attacked and the move | |
2654 | * does not defend or attack, no points. | |
2655 | */ | |
2656 | if (worm[bb].attack_codes[0] != 0 | |
2657 | && ((color == board[bb] && !does_defend(pos, bb)) | |
2658 | || (color == OTHER_COLOR(board[bb]) | |
2659 | && !does_attack(pos, bb)))) | |
2660 | this_value = 0.0; | |
2661 | ||
2662 | /* If we are doing scoring, are alive, and the move loses | |
2663 | * territory, no points. | |
2664 | */ | |
2665 | if (doing_scoring | |
2666 | && move[pos].territorial_value < 0.0 | |
2667 | && (DRAGON2(bb).safety == ALIVE | |
2668 | || DRAGON2(bb).safety == STRONGLY_ALIVE | |
2669 | || DRAGON2(bb).safety == INVINCIBLE)) | |
2670 | this_value = 0.0; | |
2671 | ||
2672 | if (this_value > dragon_value[bb]) { | |
2673 | DEBUG(DEBUG_MOVE_REASONS, | |
2674 | " %1m: %f - %1m attacked/defended\n", | |
2675 | pos, this_value, bb); | |
2676 | dragon_value[bb] = this_value; | |
2677 | } | |
2678 | } | |
2679 | ||
2680 | break; | |
2681 | ||
2682 | case ATTACK_THREAT: | |
2683 | case DEFEND_THREAT: | |
2684 | break; | |
2685 | ||
2686 | case EITHER_MOVE: | |
2687 | /* FIXME: Generalize this to more types of threats. */ | |
2688 | /* FIXME: We need a policy if a move has several EITHER_MOVE | |
2689 | * reasons. Most likely not all of them can be achieved. | |
2690 | */ | |
2691 | aa = either_data[move_reasons[r].what].what1; | |
2692 | bb = either_data[move_reasons[r].what].what2; | |
2693 | ||
2694 | /* If both worms are dead, this move reason has no value. */ | |
2695 | if (dragon[aa].status == DEAD | |
2696 | && dragon[bb].status == DEAD) | |
2697 | break; | |
2698 | ||
2699 | /* Also if there is a combination attack, we assume it covers | |
2700 | * the same thing. | |
2701 | * FIXME: This is only applicable as long as the only moves | |
2702 | * handled by EITHER_MOVE are attacks. | |
2703 | */ | |
2704 | if (move_reason_known(pos, MY_ATARI_ATARI_MOVE, -1)) | |
2705 | break; | |
2706 | ||
2707 | aa_value = adjusted_worm_attack_value(pos, aa); | |
2708 | bb_value = adjusted_worm_attack_value(pos, bb); | |
2709 | this_value = gg_min(aa_value, bb_value); | |
2710 | ||
2711 | TRACE(" %1m: %f - either attacks %1m (%f) or attacks %1m (%f)\n", | |
2712 | pos, this_value, aa, aa_value, bb, bb_value); | |
2713 | ||
2714 | tot_value += this_value; | |
2715 | break; | |
2716 | ||
2717 | case ALL_MOVE: | |
2718 | /* FIXME: Generalize this to more types of threats. */ | |
2719 | aa = all_data[move_reasons[r].what].what1; | |
2720 | bb = all_data[move_reasons[r].what].what2; | |
2721 | ||
2722 | /* If both worms are dead, this move reason has no value. */ | |
2723 | if (dragon[aa].status == DEAD | |
2724 | && dragon[bb].status == DEAD) | |
2725 | break; | |
2726 | ||
2727 | /* Also if there is a combination attack, we assume it covers | |
2728 | * the same thing. | |
2729 | */ | |
2730 | if (move_reason_known(pos, YOUR_ATARI_ATARI_MOVE, -1)) | |
2731 | break; | |
2732 | ||
2733 | aa_value = worm[aa].effective_size; | |
2734 | bb_value = worm[bb].effective_size; | |
2735 | this_value = 2 * gg_min(aa_value, bb_value); | |
2736 | ||
2737 | TRACE(" %1m: %f - both defends %1m (%f) and defends %1m (%f)\n", | |
2738 | pos, this_value, aa, aa_value, bb, bb_value); | |
2739 | ||
2740 | tot_value += this_value; | |
2741 | break; | |
2742 | ||
2743 | case CONNECT_MOVE: | |
2744 | ||
2745 | /* If the opponent just added a stone to a dead dragon, which is | |
2746 | * adjacent to both dragons being connected, then the connection | |
2747 | * is probably a good way to make sure the thrashing dragon | |
2748 | * stays dead. If we are ahead, add a safety move here, at most | |
2749 | * half the margin of victory. | |
2750 | * | |
2751 | * This does only apply if we decided earlier we want to use | |
2752 | * thrashing dragon heuristics. | |
2753 | */ | |
2754 | ||
2755 | if (use_thrashing_dragon_heuristics) { | |
2756 | int cc; | |
2757 | aa = dragon[conn_worm1[move_reasons[r].what]].origin; | |
2758 | bb = dragon[conn_worm2[move_reasons[r].what]].origin; | |
2759 | cc = get_last_opponent_move(color); | |
2760 | ||
2761 | if (cc != NO_MOVE | |
2762 | && thrashing_stone[cc] | |
2763 | && are_neighbor_dragons(aa, cc) | |
2764 | && are_neighbor_dragons(bb, cc)) { | |
2765 | if (aa == bb) | |
2766 | this_value = 1.6 * DRAGON2(cc).strategic_size; | |
2767 | else if (DRAGON2(aa).safety == INESSENTIAL | |
2768 | || DRAGON2(bb).safety == INESSENTIAL) { | |
2769 | if ((DRAGON2(aa).safety == INESSENTIAL | |
2770 | && max_lunch_eye_value(aa) == 0) | |
2771 | || (DRAGON2(bb).safety == INESSENTIAL | |
2772 | && max_lunch_eye_value(bb) == 0)) | |
2773 | this_value = 0.0; | |
2774 | else | |
2775 | this_value = 0.8 * DRAGON2(cc).strategic_size; | |
2776 | } | |
2777 | else | |
2778 | this_value = 1.7 * DRAGON2(cc).strategic_size; | |
2779 | ||
2780 | if (this_value > dragon_value[dragon[cc].origin]) { | |
2781 | dragon_value[dragon[cc].origin] = this_value; | |
2782 | DEBUG(DEBUG_MOVE_REASONS, | |
2783 | " %1m: %f - connect %1m and %1m to attack thrashing dragon %1m\n", | |
2784 | pos, this_value, aa, bb, cc); | |
2785 | } | |
2786 | } | |
2787 | } | |
2788 | ||
2789 | if (!move[pos].move_safety) | |
2790 | break; | |
2791 | /* Otherwise fall through. */ | |
2792 | case CUT_MOVE: | |
2793 | if (doing_scoring && !move[pos].move_safety) | |
2794 | break; | |
2795 | ||
2796 | aa = dragon[conn_worm1[move_reasons[r].what]].origin; | |
2797 | bb = dragon[conn_worm2[move_reasons[r].what]].origin; | |
2798 | ||
2799 | if (aa == bb) | |
2800 | continue; | |
2801 | ||
2802 | /* If we are ahead by more than 20, value connections more strongly */ | |
2803 | if (our_score > 20.0) | |
2804 | this_value = connection_value(aa, bb, pos, our_score); | |
2805 | else | |
2806 | this_value = connection_value(aa, bb, pos, 0); | |
2807 | if (this_value > dragon_value[aa]) { | |
2808 | dragon_value[aa] = this_value; | |
2809 | DEBUG(DEBUG_MOVE_REASONS, | |
2810 | " %1m: %f - %1m cut/connect strategic value\n", | |
2811 | pos, this_value, aa); | |
2812 | } | |
2813 | ||
2814 | ||
2815 | if (our_score > 20.0) | |
2816 | this_value = connection_value(bb, aa, pos, our_score); | |
2817 | else | |
2818 | this_value = connection_value(bb, aa, pos, 0); | |
2819 | if (this_value > dragon_value[bb]) { | |
2820 | dragon_value[bb] = this_value; | |
2821 | DEBUG(DEBUG_MOVE_REASONS, | |
2822 | " %1m: %f - %1m cut/connect strategic value\n", | |
2823 | pos, this_value, bb); | |
2824 | } | |
2825 | ||
2826 | break; | |
2827 | ||
2828 | case SEMEAI_MOVE: | |
2829 | /* | |
2830 | * The strategical value of winning a semeai is | |
2831 | * own dragons (usually) becomes fully secure, while adjoining | |
2832 | * enemy dragons do not. | |
2833 | * | |
2834 | * FIXME: Valuation not implemented at all yet. | |
2835 | */ | |
2836 | ||
2837 | break; | |
2838 | ||
2839 | case STRATEGIC_ATTACK_MOVE: | |
2840 | case STRATEGIC_DEFEND_MOVE: | |
2841 | /* The right way to do this is to estimate the safety of the | |
2842 | * dragon before and after the move. Unfortunately we are | |
2843 | * missing good ways to do this currently. | |
2844 | * | |
2845 | * Temporary solution is to only look at an ad hoc measure of | |
2846 | * the dragon safety and ignoring the effectiveness of the | |
2847 | * move. | |
2848 | * | |
2849 | * FIXME: Improve the implementation. | |
2850 | */ | |
2851 | aa = move_reasons[r].what; | |
2852 | ||
2853 | /* FIXME: This value cannot be computed without some | |
2854 | * measurement of how the actual move affects the dragon. The | |
2855 | * dragon safety alone is not enough. The question is whether | |
2856 | * the dragon is threatened by the move or not. | |
2857 | */ | |
2858 | if (use_thrashing_dragon_heuristics | |
2859 | && thrashing_stone[aa]) | |
2860 | this_value = 1.7 * DRAGON2(aa).strategic_size; | |
2861 | else | |
2862 | this_value = 1.8 * soft_cap(DRAGON2(aa).strategic_size, 15.0) | |
2863 | * dragon_weakness(aa, 1); | |
2864 | ||
2865 | /* No strategical attack value is awarded if the dragon at (aa) | |
2866 | * has an adjacent (friendly) critical dragon, which is not | |
2867 | * defended by this move. In that case it's probably a mistake | |
2868 | * to make the strategical attack since the dragon can defend | |
2869 | * itself with profit. | |
2870 | * | |
2871 | * FIXME: We probably need to verify that the critical dragon is | |
2872 | * substantial enough that capturing it saves the strategically | |
2873 | * attacked dragon. | |
2874 | */ | |
2875 | if (move_reasons[r].type == STRATEGIC_ATTACK_MOVE) { | |
2876 | int s; | |
2877 | ||
2878 | for (s = 0; s < DRAGON2(aa).neighbors; s++) { | |
2879 | int d = DRAGON2(aa).adjacent[s]; | |
2880 | int adj = dragon2[d].origin; | |
2881 | ||
2882 | if (dragon[adj].color == color | |
2883 | && dragon[adj].status == CRITICAL | |
2884 | && dragon2[d].safety != INESSENTIAL | |
2885 | && !owl_defense_move_reason_known(pos, adj)) | |
2886 | this_value = 0.0; | |
2887 | } | |
2888 | } | |
2889 | ||
2890 | /* Multiply by attack_dragon_weight to try to find a best fit */ | |
2891 | this_value = this_value * attack_dragon_weight; | |
2892 | ||
2893 | if (this_value > dragon_value[aa]) { | |
2894 | dragon_value[aa] = this_value; | |
2895 | DEBUG(DEBUG_MOVE_REASONS, | |
2896 | " %1m: %f - %1m strategic attack/defend\n", | |
2897 | pos, this_value, aa); | |
2898 | ||
2899 | } | |
2900 | break; | |
2901 | ||
2902 | case UNCERTAIN_OWL_DEFENSE: | |
2903 | aa = move_reasons[r].what; | |
2904 | ||
2905 | /* If there is an adjacent dragon which is critical we should | |
2906 | * skip this type of move reason, since attacking or defending | |
2907 | * the critical dragon is more urgent. | |
2908 | */ | |
2909 | { | |
2910 | int d; | |
2911 | int found_one = 0; | |
2912 | ||
2913 | for (d = 0; d < DRAGON2(aa).neighbors; d++) | |
2914 | if (DRAGON(DRAGON2(aa).adjacent[d]).status == CRITICAL) | |
2915 | found_one = 1; | |
2916 | if (found_one) | |
2917 | break; | |
2918 | } | |
2919 | ||
2920 | /* If we are behind, we should skip this type of move reason. | |
2921 | * If we are ahead, we should value it more. | |
2922 | */ | |
2923 | if (our_score < 0.0) | |
2924 | this_value = 0.0; | |
2925 | else | |
2926 | this_value = gg_min(2*DRAGON2(aa).strategic_size, 0.65*our_score); | |
2927 | ||
2928 | if (this_value > dragon_value[aa]) { | |
2929 | dragon_value[aa] = this_value; | |
2930 | DEBUG(DEBUG_MOVE_REASONS, | |
2931 | " %1m: %f - %1m uncertain owl defense bonus\n", | |
2932 | pos, this_value, aa); | |
2933 | } | |
2934 | ||
2935 | break; | |
2936 | } | |
2937 | } | |
2938 | ||
2939 | for (aa = BOARDMIN; aa < BOARDMAX; aa++) { | |
2940 | if (dragon_value[aa] == 0.0) | |
2941 | continue; | |
2942 | ||
2943 | ASSERT1(dragon[aa].origin == aa, aa); | |
2944 | ||
2945 | /* If this dragon is critical but not attacked/defended by this | |
2946 | * move, we ignore the strategic effect. | |
2947 | */ | |
2948 | if (dragon[aa].status == CRITICAL | |
2949 | && !owl_move_reason_known(pos, aa)) { | |
2950 | DEBUG(DEBUG_MOVE_REASONS, " %1m: 0.0 - disregarding strategic effect on %1m (critical dragon)\n", | |
2951 | pos, aa); | |
2952 | continue; | |
2953 | } | |
2954 | ||
2955 | /* If this dragon consists of only one worm and that worm can | |
2956 | * be tactically captured or defended by this move, we have | |
2957 | * already counted the points as territorial value, unless | |
2958 | * it's assumed to be dead. | |
2959 | * However, we still allow strategical excess value (see below) | |
2960 | * in case the effective_size is substantially bigger (by 2.0) | |
2961 | * than the actualy size. | |
2962 | */ | |
2963 | if (dragon[aa].status != DEAD | |
2964 | && dragon[aa].size == worm[aa].size | |
2965 | && worm[aa].effective_size < worm[aa].size + 2.0 | |
2966 | && (attack_move_reason_known(pos, aa) | |
2967 | || defense_move_reason_known(pos, aa))) { | |
2968 | TRACE(" %1m: %f - %1m strategic value already counted - A.\n", | |
2969 | pos, dragon_value[aa], aa); | |
2970 | continue; | |
2971 | } | |
2972 | /* If the dragon has been owl captured, owl defended, or involved | |
2973 | * in a semeai, we have likewise already counted the points as | |
2974 | * territorial value. | |
2975 | */ | |
2976 | if (attack_move_reason_known(pos, aa) | |
2977 | || defense_move_reason_known(pos, aa) | |
2978 | || (owl_move_reason_known(pos, aa) | |
2979 | && dragon[aa].status == CRITICAL) | |
2980 | || move_reason_known(pos, SEMEAI_MOVE, aa)) { | |
2981 | /* But if the strategical value was larger than the territorial | |
2982 | * value (e.g. because connecting to strong dragon) we award the | |
2983 | * excess value as a bonus. | |
2984 | */ | |
2985 | float excess_value = (dragon_value[aa] - | |
2986 | 2 * DRAGON2(aa).strategic_size); | |
2987 | if (excess_value > 0.0) { | |
2988 | TRACE(" %1m: %f - strategic bonus for %1m\n", pos, excess_value, aa); | |
2989 | tot_value += excess_value; | |
2990 | } | |
2991 | else { | |
2992 | TRACE(" %1m: %f - %1m strategic value already counted - B.\n", | |
2993 | pos, dragon_value[aa], aa); | |
2994 | } | |
2995 | ||
2996 | continue; | |
2997 | } | |
2998 | ||
2999 | TRACE(" %1m: %f - strategic effect on %1m\n", | |
3000 | pos, dragon_value[aa], aa); | |
3001 | tot_value += dragon_value[aa]; | |
3002 | } | |
3003 | ||
3004 | /* Finally, subtract penalty for invasion type moves. */ | |
3005 | this_value = strategic_penalty(pos, color); | |
3006 | /* Multiply by invasion_malus_weight to allow us to fit the weight */ | |
3007 | this_value = this_value * invasion_malus_weight; | |
3008 | if (this_value > 0.0) { | |
3009 | TRACE(" %1m: %f - strategic penalty, considered as invasion.\n", | |
3010 | pos, -this_value); | |
3011 | tot_value -= this_value; | |
3012 | } | |
3013 | ||
3014 | move[pos].strategical_value = tot_value; | |
3015 | } | |
3016 | ||
3017 | ||
3018 | /* Compare two move reasons, used for sorting before presentation. */ | |
3019 | static int | |
3020 | compare_move_reasons(const void *p1, const void *p2) | |
3021 | { | |
3022 | const int mr1 = *(const int *) p1; | |
3023 | const int mr2 = *(const int *) p2; | |
3024 | ||
3025 | if (move_reasons[mr1].type != move_reasons[mr2].type) | |
3026 | return move_reasons[mr2].type - move_reasons[mr1].type; | |
3027 | else | |
3028 | return move_reasons[mr2].what - move_reasons[mr1].what; | |
3029 | } | |
3030 | ||
3031 | ||
3032 | /* | |
3033 | * Combine the reasons for a move at (pos) into a simple numerical value. | |
3034 | * These heuristics are now somewhat less ad hoc than before but probably | |
3035 | * still need a lot of improvement. | |
3036 | */ | |
3037 | static float | |
3038 | value_move_reasons(int pos, int color, float pure_threat_value, | |
3039 | float our_score, int use_thrashing_dragon_heuristics) | |
3040 | { | |
3041 | float tot_value; | |
3042 | float shape_factor; | |
3043 | ||
3044 | gg_assert(stackp == 0); | |
3045 | ||
3046 | /* Is it an antisuji? */ | |
3047 | if (is_antisuji_move(pos)) | |
3048 | return 0.0; /* This move must not be played. End of story. */ | |
3049 | ||
3050 | /* Never play on a vertex which is unconditional territory for | |
3051 | * either player. There is absolutely nothing to gain. | |
3052 | */ | |
3053 | if (worm[pos].unconditional_status != UNKNOWN) | |
3054 | return 0.0; | |
3055 | ||
3056 | /* If this move has no reason at all, we can skip some steps. */ | |
3057 | if (move[pos].reason[0] >= 0 | |
3058 | || move[pos].min_territory > 0.0) { | |
3059 | int num_reasons; | |
3060 | ||
3061 | /* Sort the move reasons. This makes it easier to visually compare | |
3062 | * the reasons for different moves in the trace outputs. | |
3063 | */ | |
3064 | num_reasons = 0; | |
3065 | while (move[pos].reason[num_reasons] >= 0 && num_reasons < MAX_REASONS) | |
3066 | num_reasons++; | |
3067 | gg_sort(move[pos].reason, num_reasons, sizeof(move[pos].reason[0]), | |
3068 | compare_move_reasons); | |
3069 | ||
3070 | /* Discard move reasons that only duplicate another. */ | |
3071 | discard_redundant_move_reasons(pos); | |
3072 | ||
3073 | /* Estimate the value of various aspects of the move. The order | |
3074 | * is significant. Territorial value must be computed before | |
3075 | * strategical value. See connection_value(). | |
3076 | */ | |
3077 | estimate_territorial_value(pos, color, our_score, 0); | |
3078 | estimate_strategical_value(pos, color, our_score, | |
3079 | use_thrashing_dragon_heuristics); | |
3080 | } | |
3081 | ||
3082 | /* Introduction of strategical_weight and territorial_weight, | |
3083 | * for automatic fitting. (3.5.1) | |
3084 | */ | |
3085 | tot_value = territorial_weight * move[pos].territorial_value + | |
3086 | strategical_weight * move[pos].strategical_value; | |
3087 | ||
3088 | shape_factor = compute_shape_factor(pos); | |
3089 | ||
3090 | if (tot_value > 0.0) { | |
3091 | int c; | |
3092 | float followup_value; | |
3093 | ||
3094 | /* Negative territorial followup doesn't make make sense. */ | |
3095 | if (move[pos].influence_followup_value < 0.0) | |
3096 | move[pos].influence_followup_value = 0.0; | |
3097 | ||
3098 | followup_value = move[pos].followup_value | |
3099 | + move[pos].influence_followup_value; | |
3100 | TRACE(" %1m: %f - total followup value, added %f as territorial followup\n", | |
3101 | pos, followup_value, move[pos].influence_followup_value); | |
3102 | ||
3103 | /* In the endgame, there are a few situations where the value can | |
3104 | * be 0 points + followup. But we want to take the intersections first | |
3105 | * were we actually get some points. 0.5 points is a 1 point ko which | |
3106 | * is the smallest value that is actually worth something. | |
3107 | */ | |
3108 | if (tot_value >= 0.5) { | |
3109 | float old_tot_value = tot_value; | |
3110 | float contribution; | |
3111 | /* We adjust the value according to followup and reverse followup | |
3112 | * values. | |
3113 | */ | |
3114 | contribution = gg_min(gg_min(0.5 * followup_value | |
3115 | + 0.5 * move[pos].reverse_followup_value, | |
3116 | 1.0 * tot_value | |
3117 | + followup_value), | |
3118 | 1.1 * tot_value | |
3119 | + move[pos].reverse_followup_value); | |
3120 | tot_value += contribution * followup_weight; | |
3121 | /* The first case applies to gote vs gote situation, the | |
3122 | * second to reverse sente, and the third to sente situations. | |
3123 | * The usual rule is that a sente move should count at double | |
3124 | * value. But if we have a 1 point move with big followup (i.e. | |
3125 | * sente) we want to play that before a 2 point gote move. Hence | |
3126 | * the factor 1.1 above. | |
3127 | */ | |
3128 | ||
3129 | if (contribution != 0.0) { | |
3130 | TRACE(" %1m: %f - added due to followup (%f) and reverse followup values (%f)\n", | |
3131 | pos, contribution, followup_value, | |
3132 | move[pos].reverse_followup_value); | |
3133 | } | |
3134 | ||
3135 | /* If a ko fight is going on, we should use the full followup | |
3136 | * and reverse followup values in the total value. We save the | |
3137 | * additional contribution for later access. | |
3138 | */ | |
3139 | move[pos].additional_ko_value = | |
3140 | followup_value | |
3141 | + move[pos].reverse_followup_value | |
3142 | - (tot_value - old_tot_value); | |
3143 | ||
3144 | /* Not sure whether this could happen, but check for safety. */ | |
3145 | if (move[pos].additional_ko_value < 0.0) | |
3146 | move[pos].additional_ko_value = 0.0; | |
3147 | } | |
3148 | else { | |
3149 | move[pos].additional_ko_value = | |
3150 | shape_factor * (move[pos].followup_value | |
3151 | + move[pos].reverse_followup_value); | |
3152 | } | |
3153 | ||
3154 | tot_value += soft_cap(0.05 * move[pos].secondary_value, 0.4); | |
3155 | if (move[pos].secondary_value != 0.0) | |
3156 | TRACE(" %1m: %f - secondary\n", pos, | |
3157 | soft_cap(0.05 * move[pos].secondary_value, 0.4)); | |
3158 | ||
3159 | if (move[pos].numpos_shape + move[pos].numneg_shape > 0) { | |
3160 | /* shape_factor has already been computed. */ | |
3161 | float old_value = tot_value; | |
3162 | /* Maximum 15 points of the territorial value will be weighted by shape_factor */ | |
3163 | if (move[pos].territorial_value < 15) | |
3164 | tot_value *= shape_factor; | |
3165 | else { | |
3166 | float non_shape_val = move[pos].territorial_value - 15; | |
3167 | tot_value = (tot_value - non_shape_val) * shape_factor + non_shape_val; | |
3168 | } | |
3169 | ||
3170 | if (verbose) { | |
3171 | /* Should all have been TRACE, except we want field sizes. */ | |
3172 | gprintf(" %1m: %f - shape ", pos, tot_value - old_value); | |
3173 | fprintf(stderr, | |
3174 | "(shape values +%4.2f(%d) -%4.2f(%d), shape factor %5.3f)\n", | |
3175 | move[pos].maxpos_shape, move[pos].numpos_shape, | |
3176 | move[pos].maxneg_shape, move[pos].numneg_shape, | |
3177 | shape_factor); | |
3178 | } | |
3179 | } | |
3180 | ||
3181 | /* Add a special shape bonus for moves which connect own strings | |
3182 | * or cut opponent strings. | |
3183 | */ | |
3184 | c = (move_connects_strings(pos, color, 1) | |
3185 | + move_connects_strings(pos, OTHER_COLOR(color), 0)); | |
3186 | if (c > 0) { | |
3187 | float shape_factor2 = pow(1.02, (float) c) - 1; | |
3188 | float base_value = gg_max(gg_min(tot_value, 5.0), 1.0); | |
3189 | if (verbose) { | |
3190 | /* Should all have been TRACE, except we want field sizes. */ | |
3191 | gprintf(" %1m: %f - connects strings ", pos, | |
3192 | base_value * shape_factor2); | |
3193 | fprintf(stderr, "(connect value %d, shape factor %5.3f)\n", c, | |
3194 | shape_factor2); | |
3195 | } | |
3196 | tot_value += base_value * shape_factor2; | |
3197 | } | |
3198 | ||
3199 | /* Dame points which have a cut or connect move reason get a small | |
3200 | * extra bonus because these have a tendency to actually be worth | |
3201 | * a point. | |
3202 | */ | |
3203 | if (tot_value < 0.3 | |
3204 | && (move_reason_known(pos, CONNECT_MOVE, -1) | |
3205 | || move_reason_known(pos, CUT_MOVE, -1))) { | |
3206 | float old_tot_value = tot_value; | |
3207 | tot_value = gg_min(0.3, tot_value + 0.1); | |
3208 | TRACE(" %1m: %f - cut/connect dame bonus\n", pos, | |
3209 | tot_value - old_tot_value); | |
3210 | } | |
3211 | } | |
3212 | else { | |
3213 | move[pos].additional_ko_value = | |
3214 | shape_factor * (move[pos].followup_value + | |
3215 | gg_min(move[pos].followup_value, | |
3216 | move[pos].reverse_followup_value)); | |
3217 | } | |
3218 | ||
3219 | /* If the move is valued 0 or small, but has followup values and is | |
3220 | * flagged as a worthwhile threat, add up to pure_threat_value to | |
3221 | * the move. | |
3222 | * | |
3223 | * FIXME: We shouldn't have to call confirm_safety() here. It's | |
3224 | * potentially too expensive. | |
3225 | */ | |
3226 | if (pure_threat_value > 0.0 | |
3227 | && move[pos].worthwhile_threat | |
3228 | && tot_value <= pure_threat_value | |
3229 | && board[pos] == EMPTY | |
3230 | && move[pos].additional_ko_value > 0.0 | |
3231 | && is_legal(pos, color) | |
3232 | && value_moves_confirm_safety(pos, color)) { | |
3233 | float new_tot_value = gg_min(pure_threat_value, | |
3234 | tot_value | |
3235 | + 0.25 * move[pos].additional_ko_value); | |
3236 | ||
3237 | /* Make sure that moves with independent value are preferred over | |
3238 | * those without. | |
3239 | */ | |
3240 | new_tot_value *= (1.0 - 0.1 * (pure_threat_value - tot_value) | |
3241 | / pure_threat_value); | |
3242 | ||
3243 | if (new_tot_value > tot_value) { | |
3244 | TRACE(" %1m: %f - carry out threat or defend against threat\n", | |
3245 | pos, new_tot_value - tot_value); | |
3246 | tot_value = new_tot_value; | |
3247 | } | |
3248 | } | |
3249 | ||
3250 | /* min_value is now subject to reduction with a fitted weight (3.5.1) */ | |
3251 | move[pos].min_value = move[pos].min_value * minimum_value_weight; | |
3252 | move[pos].max_value = move[pos].max_value * maximum_value_weight; | |
3253 | ||
3254 | /* Test if min_value or max_value values constrain the total value. | |
3255 | * First avoid contradictions between min_value and max_value, | |
3256 | * assuming that min_value is right. | |
3257 | */ | |
3258 | if (move[pos].min_value > move[pos].max_value) | |
3259 | move[pos].max_value = move[pos].min_value; | |
3260 | ||
3261 | /* If several moves have an identical minimum value, then GNU Go uses the | |
3262 | * following secondary criterion (unless min_value and max_value agree, and | |
3263 | * unless min_value is bigger than 25, in which case it probably comes from | |
3264 | * a J or U pattern): | |
3265 | */ | |
3266 | if (move[pos].min_value < 25) | |
3267 | move[pos].min_value += tot_value / 200; | |
3268 | if (tot_value < move[pos].min_value | |
3269 | && move[pos].min_value > 0) { | |
3270 | tot_value = move[pos].min_value; | |
3271 | TRACE(" %1m: %f - minimum accepted value\n", pos, tot_value); | |
3272 | } | |
3273 | ||
3274 | if (tot_value > move[pos].max_value) { | |
3275 | tot_value = move[pos].max_value; | |
3276 | TRACE(" %1m: %f - maximum accepted value\n", | |
3277 | pos, tot_value); | |
3278 | } | |
3279 | ||
3280 | if (tot_value > 0 | |
3281 | || move[pos].territorial_value > 0 | |
3282 | || move[pos].strategical_value > 0) { | |
3283 | TRACE("Move generation values %1m to %f\n", pos, tot_value); | |
3284 | move_considered(pos, tot_value); | |
3285 | } | |
3286 | ||
3287 | return tot_value; | |
3288 | } | |
3289 | ||
3290 | ||
3291 | /* | |
3292 | * Loop over all possible moves and value the move reasons for each. | |
3293 | */ | |
3294 | static void | |
3295 | value_moves(int color, float pure_threat_value, float our_score, | |
3296 | int use_thrashing_dragon_heuristics) | |
3297 | { | |
3298 | int m, n; | |
3299 | int pos; | |
3300 | ||
3301 | TRACE("\nMove valuation:\n"); | |
3302 | ||
3303 | /* Visit the moves in the standard lexicographical order */ | |
3304 | for (n = 0; n < board_size; n++) | |
3305 | for (m = board_size-1; m >= 0; m--) { | |
3306 | pos = POS(m, n); | |
3307 | ||
3308 | move[pos].value = value_move_reasons(pos, color, | |
3309 | pure_threat_value, our_score, | |
3310 | use_thrashing_dragon_heuristics); | |
3311 | if (move[pos].value == 0.0) | |
3312 | continue; | |
3313 | ||
3314 | /* Maybe this test should be performed elsewhere. This is just | |
3315 | * to get some extra safety. We don't filter out illegal ko | |
3316 | * captures here though, because if that is the best move, we | |
3317 | * should reevaluate ko threats. | |
3318 | */ | |
3319 | if (is_legal(pos, color) || is_illegal_ko_capture(pos, color)) { | |
3320 | /* Add a random number between 0 and 0.01 to use in comparisons. */ | |
3321 | move[pos].value += | |
3322 | 0.01 * move[pos].random_number * move[pos].randomness_scaling; | |
3323 | } | |
3324 | else { | |
3325 | move[pos].value = 0.0; | |
3326 | TRACE("Move at %1m wasn't legal.\n", pos); | |
3327 | } | |
3328 | } | |
3329 | } | |
3330 | ||
3331 | ||
3332 | /* Print the values of all moves with values bigger than zero. */ | |
3333 | ||
3334 | void | |
3335 | print_all_move_values(FILE *output) | |
3336 | { | |
3337 | int pos; | |
3338 | ||
3339 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
3340 | if (!ON_BOARD(pos) || move[pos].final_value <= 0.0) | |
3341 | continue; | |
3342 | ||
3343 | gfprintf(output, "%1M %f\n", pos, move[pos].final_value); | |
3344 | } | |
3345 | } | |
3346 | ||
3347 | /* Search through all board positions for the 10 highest valued | |
3348 | * moves and print them. | |
3349 | */ | |
3350 | ||
3351 | static void | |
3352 | print_top_moves(void) | |
3353 | { | |
3354 | int k; | |
3355 | int pos; | |
3356 | float tval; | |
3357 | ||
3358 | for (k = 0; k < 10; k++) { | |
3359 | best_moves[k] = NO_MOVE; | |
3360 | best_move_values[k] = 0.0; | |
3361 | } | |
3362 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
3363 | if (!ON_BOARD(pos) || move[pos].final_value <= 0.0) | |
3364 | continue; | |
3365 | ||
3366 | tval = move[pos].final_value; | |
3367 | record_top_move(pos, tval); | |
3368 | } | |
3369 | ||
3370 | if (verbose > 0 || (debug & DEBUG_TOP_MOVES)) { | |
3371 | gprintf("\nTop moves:\n"); | |
3372 | for (k = 0; k < 10 && best_move_values[k] > 0.0; k++) | |
3373 | gprintf("%d. %1M %f\n", k+1, best_moves[k], best_move_values[k]); | |
3374 | } | |
3375 | } | |
3376 | ||
3377 | /* Add a move to the list of top moves (if it is among the top ten) */ | |
3378 | ||
3379 | void | |
3380 | record_top_move(int pos, float val) | |
3381 | { | |
3382 | int k; | |
3383 | for (k = 9; k >= 0; k--) | |
3384 | if (val > best_move_values[k]) { | |
3385 | if (k < 9) { | |
3386 | best_move_values[k+1] = best_move_values[k]; | |
3387 | best_moves[k+1] = best_moves[k]; | |
3388 | } | |
3389 | best_move_values[k] = val; | |
3390 | best_moves[k] = pos; | |
3391 | } | |
3392 | ||
3393 | move[pos].final_value = val; | |
3394 | } | |
3395 | ||
3396 | /* remove a rejected move from the list of top moves */ | |
3397 | ||
3398 | void | |
3399 | remove_top_move(int move) | |
3400 | { | |
3401 | int k; | |
3402 | for (k = 0; k < 10; k++) { | |
3403 | if (best_moves[k] == move) { | |
3404 | int l; | |
3405 | for (l = k; l < 9; l++) { | |
3406 | best_moves[l] = best_moves[l+1]; | |
3407 | best_move_values[l] = best_move_values[l+1]; | |
3408 | } | |
3409 | best_moves[9] = NO_MOVE; | |
3410 | best_move_values[9] = 0.0; | |
3411 | } | |
3412 | } | |
3413 | } | |
3414 | ||
3415 | /* This function is called if the biggest move on board was an illegal | |
3416 | * ko capture. | |
3417 | */ | |
3418 | static void | |
3419 | reevaluate_ko_threats(int ko_move, int color, float ko_value) | |
3420 | { | |
3421 | int ko_stone = NO_MOVE; | |
3422 | int opp_ko_move; | |
3423 | int pos; | |
3424 | int k; | |
3425 | int type, what; | |
3426 | int threat_does_work = 0; | |
3427 | int ko_move_target; | |
3428 | int num_good_threats = 0; | |
3429 | int good_threats[BOARDMAX]; | |
3430 | int best_threat_quality = -1; | |
3431 | float threat_size; | |
3432 | ||
3433 | ko_move_target = get_biggest_owl_target(ko_move); | |
3434 | ||
3435 | /* If the move is a simple ko recapture, find the ko stone. (If | |
3436 | * it's not a simple ko recapture, then the move must be a superko | |
3437 | * violation.) | |
3438 | */ | |
3439 | if (is_illegal_ko_capture(ko_move, color)) { | |
3440 | for (k = 0; k <= 3; k++) { | |
3441 | ko_stone = ko_move + delta[k]; | |
3442 | if (ON_BOARD(ko_stone) && countlib(ko_stone) == 1) | |
3443 | break; | |
3444 | } | |
3445 | ASSERT_ON_BOARD1(ko_stone); | |
3446 | } | |
3447 | ||
3448 | TRACE("Reevaluating ko threats.\n"); | |
3449 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
3450 | int threat_quality = 0; | |
3451 | ||
3452 | if (!ON_BOARD(pos) || pos == ko_move) | |
3453 | continue; | |
3454 | if (move[pos].additional_ko_value <= 0.0) | |
3455 | continue; | |
3456 | ||
3457 | /* Otherwise we look for the biggest threat, and then check whether | |
3458 | * it still works after ko has been resolved. | |
3459 | */ | |
3460 | ||
3461 | /* `additional_ko_value' includes reverse followup. While it is good to | |
3462 | * play ko threats which eliminate other threats in turn, we should | |
3463 | * always prefer threats that are larger than the value of the ko. | |
3464 | */ | |
3465 | if (move[pos].followup_value < ko_value) | |
3466 | threat_quality = -1; | |
3467 | ||
3468 | threat_size = 0.0; | |
3469 | type = -1; | |
3470 | what = -1; | |
3471 | for (k = 0; k < MAX_REASONS; k++) { | |
3472 | int r = move[pos].reason[k]; | |
3473 | if (r < 0) | |
3474 | break; | |
3475 | if (!(move_reasons[r].type & THREAT_BIT)) | |
3476 | continue; | |
3477 | ||
3478 | switch (move_reasons[r].type) { | |
3479 | case ATTACK_THREAT: | |
3480 | case DEFEND_THREAT: | |
3481 | if (worm[move_reasons[r].what].effective_size | |
3482 | > threat_size) { | |
3483 | threat_size = worm[move_reasons[r].what].effective_size; | |
3484 | type = move_reasons[r].type; | |
3485 | what = move_reasons[r].what; | |
3486 | } | |
3487 | break; | |
3488 | case OWL_ATTACK_THREAT: | |
3489 | case OWL_DEFEND_THREAT: | |
3490 | case SEMEAI_THREAT: | |
3491 | if (dragon[move_reasons[r].what].effective_size | |
3492 | > threat_size) { | |
3493 | threat_size = dragon[move_reasons[r].what]\ | |
3494 | .effective_size; | |
3495 | type = move_reasons[r].type; | |
3496 | what = move_reasons[r].what; | |
3497 | } | |
3498 | break; | |
3499 | default: | |
3500 | /* This means probably someone has introduced a new threat type | |
3501 | * without adding the corresponding case above. | |
3502 | */ | |
3503 | gg_assert(0); | |
3504 | break; | |
3505 | } | |
3506 | } | |
3507 | /* If there is no threat recorded, the followup value is probably | |
3508 | * contributed by a pattern. We can do nothing but accept this value. | |
3509 | * (although this does cause problems). | |
3510 | * | |
3511 | * FIXME: In the case of superko violation we have no ko_stone. | |
3512 | * Presumably some of the tests below should be applicable anyway. | |
3513 | * Currently we just say that any threat is ok. | |
3514 | */ | |
3515 | if (type == -1 || ko_stone == NO_MOVE) | |
3516 | threat_does_work = 1; | |
3517 | else { | |
3518 | if (trymove(pos, color, "reevaluate_ko_threats", ko_move)) { | |
3519 | ASSERT_ON_BOARD1(ko_stone); | |
3520 | if (!find_defense(ko_stone, &opp_ko_move)) | |
3521 | threat_does_work = 1; | |
3522 | else { | |
3523 | int threat_wastes_point = 0; | |
3524 | if (whose_area(OPPOSITE_INFLUENCE(color), pos) != EMPTY) | |
3525 | threat_wastes_point = 1; | |
3526 | ||
3527 | if (trymove(opp_ko_move, OTHER_COLOR(color), | |
3528 | "reevaluate_ko_threats", ko_move)) { | |
3529 | switch (type) { | |
3530 | case ATTACK_THREAT: | |
3531 | /* In case the attack threat was a snapback move, there | |
3532 | * is no stone on the board to attack now and we check | |
3533 | * for a defense of the threatening move instead. | |
3534 | */ | |
3535 | if (board[what] != EMPTY) | |
3536 | threat_does_work = attack(what, NULL); | |
3537 | else | |
3538 | threat_does_work = find_defense(pos, NULL); | |
3539 | break; | |
3540 | case DEFEND_THREAT: | |
3541 | threat_does_work = (board[what] != EMPTY | |
3542 | && find_defense(what, NULL)); | |
3543 | break; | |
3544 | case OWL_ATTACK_THREAT: | |
3545 | case OWL_DEFEND_THREAT: | |
3546 | /* Should we call do_owl_attack/defense here? | |
3547 | * Maybe too expensive? For the moment we just assume | |
3548 | * that the attack does not work if it concerns the | |
3549 | * same dragon as ko_move. (Can this really happen?) | |
3550 | */ | |
3551 | threat_does_work = (ko_move_target != what); | |
3552 | } | |
3553 | popgo(); | |
3554 | ||
3555 | /* Is this a losing ko threat? */ | |
3556 | if (threat_does_work && type == ATTACK_THREAT) { | |
3557 | int apos; | |
3558 | if (attack(pos, &apos) | |
3559 | && does_defend(apos, what) | |
3560 | && (forced_backfilling_moves[apos] | |
3561 | || (!is_proper_eye_space(apos) | |
3562 | && !false_eye_territory[apos]))) { | |
3563 | threat_does_work = 0; | |
3564 | } | |
3565 | } | |
3566 | ||
3567 | /* If we are fighting a tiny ko (1 - 2 points only), we pay | |
3568 | * extra attention to select threats that don't waste points. | |
3569 | * In particular, we don't play threats inside of opponent | |
3570 | * territory if they can be averted on a dame intersection. | |
3571 | */ | |
3572 | if (ko_value < 1.0 | |
3573 | && threat_does_work | |
3574 | && threat_quality >= 0 | |
3575 | && (type == ATTACK_THREAT || type == DEFEND_THREAT)) { | |
3576 | int averting_pos; | |
3577 | ||
3578 | if (type == ATTACK_THREAT) | |
3579 | find_defense(what, &averting_pos); | |
3580 | else | |
3581 | attack(what, &averting_pos); | |
3582 | ||
3583 | /* `averting_pos' can be NO_MOVE sometimes, at least when | |
3584 | * when the the threat is a threat to attack. It is not | |
3585 | * clear what to do in such cases. | |
3586 | */ | |
3587 | if (averting_pos != NO_MOVE) { | |
3588 | int averting_wastes_point = 0; | |
3589 | if (whose_territory(OPPOSITE_INFLUENCE(color), averting_pos) | |
3590 | != EMPTY) | |
3591 | averting_wastes_point = 1; | |
3592 | threat_quality = averting_wastes_point - threat_wastes_point; | |
3593 | if (threat_quality < 0) | |
3594 | threat_does_work = 0; | |
3595 | } | |
3596 | } | |
3597 | } | |
3598 | } | |
3599 | popgo(); | |
3600 | } | |
3601 | } | |
3602 | ||
3603 | if (threat_does_work) { | |
3604 | if (threat_quality == best_threat_quality) | |
3605 | good_threats[num_good_threats++] = pos; | |
3606 | else if (threat_quality > best_threat_quality) { | |
3607 | best_threat_quality = threat_quality; | |
3608 | num_good_threats = 0; | |
3609 | good_threats[num_good_threats++] = pos; | |
3610 | } | |
3611 | else | |
3612 | DEBUG(DEBUG_MOVE_REASONS, | |
3613 | "%1m: no additional ko value (threat does not work as ko threat)\n", pos); | |
3614 | } | |
3615 | } | |
3616 | ||
3617 | for (k = 0; k < num_good_threats; k++) { | |
3618 | pos = good_threats[k]; | |
3619 | ||
3620 | /* If the move previously had no value, we need to add in the | |
3621 | * randomness contribution now. | |
3622 | * | |
3623 | * FIXME: This is very ugly. Restructure the code so that the | |
3624 | * randomness need only be considered in one place. | |
3625 | */ | |
3626 | if (move[pos].value == 0.0) { | |
3627 | move[pos].value += | |
3628 | 0.01 * move[pos].random_number * move[pos].randomness_scaling; | |
3629 | } | |
3630 | ||
3631 | TRACE("%1m: %f + %f = %f\n", pos, move[pos].value, | |
3632 | move[pos].additional_ko_value, | |
3633 | move[pos].value + move[pos].additional_ko_value); | |
3634 | move[pos].value += move[pos].additional_ko_value; | |
3635 | } | |
3636 | } | |
3637 | ||
3638 | ||
3639 | /* Redistribute points. When one move is declared a replacement for | |
3640 | * another by a replacement move reason, the move values for the | |
3641 | * inferior move are transferred to the replacement. | |
3642 | */ | |
3643 | static void | |
3644 | redistribute_points(void) | |
3645 | { | |
3646 | int source; | |
3647 | int target; | |
3648 | ||
3649 | for (target = BOARDMIN; target < BOARDMAX; target++) | |
3650 | if (ON_BOARD(target)) | |
3651 | move[target].final_value = move[target].value; | |
3652 | ||
3653 | for (source = BOARDMIN; source < BOARDMAX; source++) { | |
3654 | if (!ON_BOARD(source)) | |
3655 | continue; | |
3656 | target = replacement_map[source]; | |
3657 | if (target == NO_MOVE) | |
3658 | continue; | |
3659 | ||
3660 | TRACE("Redistributing points from %1m to %1m.\n", source, target); | |
3661 | if (move[target].final_value < move[source].final_value) { | |
3662 | TRACE("%1m is now valued %f.\n", target, move[source].final_value); | |
3663 | move[target].final_value = move[source].final_value; | |
3664 | } | |
3665 | TRACE("%1m is now valued 0.\n", source); | |
3666 | move[source].final_value = 0.0; | |
3667 | } | |
3668 | } | |
3669 | ||
3670 | /* This selects the best move available according to their valuations. | |
3671 | * If the best move is an illegal ko capture, we add ko threat values. | |
3672 | * If the best move is a blunder, it gets devalued and continue to look | |
3673 | * for the best move. | |
3674 | */ | |
3675 | static int | |
3676 | find_best_move(int *the_move, float *value, int color, | |
3677 | int allowed_moves[BOARDMAX]) | |
3678 | { | |
3679 | int good_move_found = 0; | |
3680 | signed char blunder_tested[BOARDMAX]; | |
3681 | float best_value = 0.0; | |
3682 | int best_move = NO_MOVE; | |
3683 | int pos; | |
3684 | ||
3685 | memset(blunder_tested, 0, sizeof(blunder_tested)); | |
3686 | ||
3687 | while (!good_move_found) { | |
3688 | best_value = 0.0; | |
3689 | best_move = NO_MOVE; | |
3690 | ||
3691 | /* Search through all board positions for the highest valued move. */ | |
3692 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
3693 | float this_value = move[pos].final_value; | |
3694 | if (allowed_moves && !allowed_moves[pos]) | |
3695 | continue; | |
3696 | if (!ON_BOARD(pos) || move[pos].final_value == 0.0) | |
3697 | continue; | |
3698 | ||
3699 | if (this_value > best_value) { | |
3700 | if (is_legal(pos, color) || is_illegal_ko_capture(pos, color)) { | |
3701 | best_value = this_value; | |
3702 | best_move = pos; | |
3703 | } | |
3704 | else { | |
3705 | TRACE("Move at %1m would be suicide.\n", pos); | |
3706 | remove_top_move(pos); | |
3707 | move[pos].value = 0.0; | |
3708 | move[pos].final_value = 0.0; | |
3709 | } | |
3710 | } | |
3711 | } | |
3712 | ||
3713 | /* If the best move is an illegal ko capture, reevaluate ko | |
3714 | * threats and search again. | |
3715 | */ | |
3716 | if (best_value > 0.0 | |
3717 | && (is_illegal_ko_capture(best_move, color) | |
3718 | || !is_allowed_move(best_move, color))) { | |
3719 | TRACE("Move at %1m would be an illegal ko capture.\n", best_move); | |
3720 | reevaluate_ko_threats(best_move, color, best_value); | |
3721 | redistribute_points(); | |
3722 | time_report(2, " reevaluate_ko_threats", NO_MOVE, 1.0); | |
3723 | remove_top_move(best_move); | |
3724 | move[best_move].value = 0.0; | |
3725 | move[best_move].final_value = 0.0; | |
3726 | print_top_moves(); | |
3727 | good_move_found = 0; | |
3728 | } | |
3729 | /* Call blunder_size() to check that we're not about to make a | |
3730 | * blunder. Otherwise devalue this move and scan through all move | |
3731 | * values once more. | |
3732 | */ | |
3733 | else if (best_value > 0.0) { | |
3734 | if (!blunder_tested[best_move]) { | |
3735 | float blunder_size = value_moves_get_blunder_size(best_move, color); | |
3736 | if (blunder_size > 0.0) { | |
3737 | TRACE("Move at %1m is a blunder, subtracting %f.\n", best_move, | |
3738 | blunder_size); | |
3739 | remove_top_move(best_move); | |
3740 | move[best_move].value -= blunder_size; | |
3741 | move[best_move].final_value -= blunder_size; | |
3742 | TRACE("Move at %1m is now valued %f.\n", best_move, | |
3743 | move[best_move].final_value); | |
3744 | record_top_move(best_move, move[best_move].final_value); | |
3745 | good_move_found = 0; | |
3746 | blunder_tested[best_move] = 1; | |
3747 | } | |
3748 | else | |
3749 | good_move_found = 1; /* Best move was not a blunder. */ | |
3750 | } | |
3751 | else /* The move apparently was a blunder, but still the best move. */ | |
3752 | good_move_found = 1; | |
3753 | } | |
3754 | else | |
3755 | good_move_found = 1; /* It's best to pass. */ | |
3756 | } | |
3757 | ||
3758 | if (best_value > 0.0 | |
3759 | && best_move != NO_MOVE) { | |
3760 | *the_move = best_move; | |
3761 | *value = best_value; | |
3762 | return 1; | |
3763 | } | |
3764 | ||
3765 | return 0; | |
3766 | } | |
3767 | ||
3768 | ||
3769 | /* | |
3770 | * Review the move reasons to find which (if any) move we want to play. | |
3771 | * | |
3772 | * The parameter pure_threat_value is the value assigned to a move | |
3773 | * which only threatens to capture or kill something. The reason for | |
3774 | * playing these is that the move may be effective because we have | |
3775 | * misevaluated the dangers or because the opponent misplays. | |
3776 | * | |
3777 | * The array allowed_moves restricts which moves may be considered. If | |
3778 | * NULL any move is allowed. | |
3779 | */ | |
3780 | int | |
3781 | review_move_reasons(int *the_move, float *value, int color, | |
3782 | float pure_threat_value, float our_score, | |
3783 | int allowed_moves[BOARDMAX], | |
3784 | int use_thrashing_dragon_heuristics) | |
3785 | { | |
3786 | int save_verbose; | |
3787 | ||
3788 | current_color = color; | |
3789 | ||
3790 | start_timer(2); | |
3791 | find_more_attack_and_defense_moves(color); | |
3792 | time_report(2, " find_more_attack_and_defense_moves", NO_MOVE, 1.0); | |
3793 | ||
3794 | if (get_level() >= 6) { | |
3795 | find_more_owl_attack_and_defense_moves(color); | |
3796 | time_report(2, " find_more_owl_attack_and_defense_moves", NO_MOVE, 1.0); | |
3797 | } | |
3798 | ||
3799 | if (large_scale && get_level() >= 6) { | |
3800 | find_large_scale_owl_attack_moves(color); | |
3801 | time_report(2, " find_large_scale_owl_attack_moves", NO_MOVE, 1.0); | |
3802 | } | |
3803 | ||
3804 | find_more_semeai_moves(color); | |
3805 | time_report(2, " find_more_semeai_moves", NO_MOVE, 1.0); | |
3806 | ||
3807 | save_verbose = verbose; | |
3808 | if (verbose > 0) | |
3809 | verbose--; | |
3810 | examine_move_safety(color); | |
3811 | time_report(2, " examine_move_safety", NO_MOVE, 1.0); | |
3812 | verbose = save_verbose; | |
3813 | ||
3814 | /* We can't do this until move_safety is known. */ | |
3815 | induce_secondary_move_reasons(color); | |
3816 | time_report(2, " induce_secondary_move_reasons", NO_MOVE, 1.0); | |
3817 | ||
3818 | if (printworms || verbose) | |
3819 | list_move_reasons(stderr, NO_MOVE); | |
3820 | ||
3821 | /* Evaluate all moves with move reasons. */ | |
3822 | value_moves(color, pure_threat_value, our_score, | |
3823 | use_thrashing_dragon_heuristics); | |
3824 | time_report(2, " value_moves", NO_MOVE, 1.0); | |
3825 | ||
3826 | /* Perform point redistribution */ | |
3827 | redistribute_points(); | |
3828 | ||
3829 | /* Search through all board positions for the 10 highest valued | |
3830 | * moves and print them. | |
3831 | */ | |
3832 | print_top_moves(); | |
3833 | ||
3834 | /* Select the highest valued move and return it. */ | |
3835 | return find_best_move(the_move, value, color, allowed_moves); | |
3836 | } | |
3837 | ||
3838 | ||
3839 | /* | |
3840 | * Choosing a strategy based on the current score estimate | |
3841 | * and the game status (between 0.0 (start) and 1.0 (game over)). | |
3842 | */ | |
3843 | ||
3844 | void | |
3845 | choose_strategy(int color, float our_score, float game_status) | |
3846 | { | |
3847 | ||
3848 | minimum_value_weight = 1.0; | |
3849 | maximum_value_weight = 1.0; | |
3850 | territorial_weight = 1.0; | |
3851 | strategical_weight = 1.0; | |
3852 | attack_dragon_weight = 1.0; | |
3853 | invasion_malus_weight = 1.0; | |
3854 | followup_weight = 1.0; | |
3855 | ||
3856 | TRACE(" Game status = %f (0.0 = start, 1.0 = game over)\n", game_status); | |
3857 | ||
3858 | ||
3859 | if (cosmic_gnugo) { | |
3860 | ||
3861 | if (game_status > 0.65 && our_score > 15.0) { | |
3862 | ||
3863 | /* We seem to be winning, so we use conservative settings. */ | |
3864 | minimum_value_weight = 0.66; | |
3865 | maximum_value_weight = 2.0; | |
3866 | territorial_weight = 0.95; | |
3867 | strategical_weight = 1.0; | |
3868 | attack_dragon_weight = 1.1; | |
3869 | invasion_malus_weight = 1.3; | |
3870 | followup_weight = 1.1; | |
3871 | TRACE(" %s is leading, using conservative settings.\n", | |
3872 | color == WHITE ? "White" : "Black"); | |
3873 | } | |
3874 | else if (game_status > 0.16) { | |
3875 | ||
3876 | /* We're not winning enough yet, try aggressive settings. */ | |
3877 | minimum_value_weight = 0.66; | |
3878 | maximum_value_weight = 2.0; | |
3879 | territorial_weight = 1.4; | |
3880 | strategical_weight = 0.5; | |
3881 | attack_dragon_weight = 0.62; | |
3882 | invasion_malus_weight = 2.0; | |
3883 | followup_weight = 0.62; | |
3884 | ||
3885 | /* If we're getting desesperate, try invasions as a last resort */ | |
3886 | if (game_status > 0.75 && our_score < -25.0) | |
3887 | invasion_malus_weight = 0.2; | |
3888 | ||
3889 | TRACE(" %s is not winning enough, using aggressive settings.\n", | |
3890 | color == WHITE ? "White" : "Black"); | |
3891 | } | |
3892 | } | |
3893 | } | |
3894 | ||
3895 | /* In order to get valid influence data after a move, we need to rerun | |
3896 | * estimate_territorial_value() for that move. A prerequisite for | |
3897 | * using this function is that move reasons have already been collected. | |
3898 | * | |
3899 | * This function should only be used for debugging purposes. | |
3900 | */ | |
3901 | void | |
3902 | prepare_move_influence_debugging(int pos, int color) | |
3903 | { | |
3904 | float our_score; | |
3905 | ||
3906 | if (color == WHITE) | |
3907 | our_score = black_score; | |
3908 | else | |
3909 | our_score = -white_score; | |
3910 | ||
3911 | estimate_territorial_value(pos, color, our_score, 1); | |
3912 | } | |
3913 | ||
3914 | ||
3915 | /* Compute probabilities of each move being played. It is assumed | |
3916 | * that the `move[]' array is filled with proper values (i.e. that | |
3917 | * one of the genmove*() functions has been called). | |
3918 | * | |
3919 | * The value of each move `V_k' should be a uniformly distributed | |
3920 | * random variable (`k' is a unique move index). Let it have values | |
3921 | * from the interval [l_k; u_k] . Then move value has constant | |
3922 | * probability density on the interval: | |
3923 | * | |
3924 | * 1 | |
3925 | * d_k = -----------. | |
3926 | * u_k - l_k | |
3927 | * | |
3928 | * We need to determine the probability of `V_k' being the largest of | |
3929 | * {V_1, V_2, ..., V_n}. Probability density is like follows: | |
3930 | * | |
3931 | * D_k(t) = d_k * Product(P{V_i < t} for i != k), l_k <= t <= u_k, | |
3932 | * | |
3933 | * where P{A} is the probability of event `A'. By integrating D_k(t) | |
3934 | * from `l_k' to `u_k' we can find the probability in question: | |
3935 | * | |
3936 | * P{V_k > V_i for i != k} = Integrate(D_k(t) dt from l_k to u_k). | |
3937 | * | |
3938 | * Function D_k(t) is a polynomial on each of subintervals produced by | |
3939 | * points `l_k', `u_k', k = 1, ..., n. When t < min(l_k), D_k(t) is | |
3940 | * zero. On other subintervals it can be evaluated by taking into | |
3941 | * account that | |
3942 | * | |
3943 | * P{V_i < t} = d_i * (t - l_i) if t < u_i; | |
3944 | * P{V_i < t} = 1 if t >= u_i. | |
3945 | */ | |
3946 | void | |
3947 | compute_move_probabilities(float probabilities[BOARDMAX]) | |
3948 | { | |
3949 | int k; | |
3950 | int pos; | |
3951 | int num_moves = 0; | |
3952 | int moves[BOARDMAX]; | |
3953 | double lower_values[BOARDMAX]; | |
3954 | double upper_values[BOARDMAX]; | |
3955 | double densities[BOARDMAX]; | |
3956 | double common_lower_limit = 0.0; | |
3957 | ||
3958 | /* Find all moves with positive values. */ | |
3959 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
3960 | probabilities[pos] = 0.0; | |
3961 | ||
3962 | if (ON_BOARD(pos)) { | |
3963 | /* FIXME: what about point redistribution? */ | |
3964 | if (move[pos].final_value > 0.0) { | |
3965 | double scale = 0.01 * (double) move[pos].randomness_scaling; | |
3966 | ||
3967 | moves[num_moves] = pos; | |
3968 | lower_values[num_moves] = ((double) move[pos].final_value | |
3969 | - (scale * move[pos].random_number)); | |
3970 | upper_values[num_moves] = lower_values[num_moves] + scale; | |
3971 | densities[num_moves] = 1.0 / scale; | |
3972 | ||
3973 | if (lower_values[num_moves] > common_lower_limit) | |
3974 | common_lower_limit = lower_values[num_moves]; | |
3975 | ||
3976 | num_moves++; | |
3977 | } | |
3978 | } | |
3979 | } | |
3980 | ||
3981 | /* Compute probability of each move. */ | |
3982 | for (k = 0; k < num_moves; k++) { | |
3983 | int i; | |
3984 | double lower_limit = common_lower_limit; | |
3985 | ||
3986 | /* Iterate over subintervals for integration. */ | |
3987 | while (lower_limit < upper_values[k]) { | |
3988 | int j; | |
3989 | double upper_limit = upper_values[k]; | |
3990 | double span_power; | |
3991 | double polynomial[BOARDMAX]; | |
3992 | int degree; | |
3993 | ||
3994 | degree = 0; | |
3995 | polynomial[0] = 1.0; | |
3996 | ||
3997 | for (i = 0; i < num_moves; i++) { | |
3998 | /* See if we need to decrease current subinterval. */ | |
3999 | if (upper_values[i] > lower_limit && upper_values[i] < upper_limit) | |
4000 | upper_limit = upper_values[i]; | |
4001 | } | |
4002 | ||
4003 | /* Build the probability density polynomial for the current | |
4004 | * subinterval. | |
4005 | */ | |
4006 | for (i = 0; i < num_moves; i++) { | |
4007 | if (i != k && upper_values[i] >= upper_limit) { | |
4008 | polynomial[++degree] = 0.0; | |
4009 | for (j = degree; j > 0; j--) { | |
4010 | polynomial[j] = (densities[i] | |
4011 | * (polynomial[j - 1] | |
4012 | + ((lower_limit - lower_values[i]) | |
4013 | * polynomial[j]))); | |
4014 | } | |
4015 | ||
4016 | polynomial[0] *= densities[i] * (lower_limit - lower_values[i]); | |
4017 | } | |
4018 | } | |
4019 | ||
4020 | /* And compute the integral of the polynomial on the current | |
4021 | * subinterval. | |
4022 | */ | |
4023 | span_power = 1.0; | |
4024 | for (j = 0; j <= degree; j++) { | |
4025 | span_power *= upper_limit - lower_limit; | |
4026 | probabilities[moves[k]] += (polynomial[j] * span_power) / (j + 1); | |
4027 | } | |
4028 | ||
4029 | /* Go on to the next subinterval. */ | |
4030 | lower_limit = upper_limit; | |
4031 | } | |
4032 | ||
4033 | probabilities[moves[k]] *= densities[k]; | |
4034 | } | |
4035 | } | |
4036 | ||
4037 | ||
4038 | /* | |
4039 | * Local Variables: | |
4040 | * tab-width: 8 | |
4041 | * c-basic-offset: 2 | |
4042 | * End: | |
4043 | */ |