Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 or * | |
11 | * (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #include "gnugo.h" | |
25 | ||
26 | #include <stdio.h> | |
27 | #include <stdlib.h> | |
28 | #include <string.h> | |
29 | ||
30 | #include "liberty.h" | |
31 | #include "sgftree.h" | |
32 | #include "gg_utils.h" | |
33 | ||
34 | /* Return one if x doesn't equal position_number and 0 otherwise. | |
35 | * After using this macro x will always have the value | |
36 | * position_number. | |
37 | */ | |
38 | #define NEEDS_UPDATE(x) (x != position_number ? (x = position_number, 1) : 0) | |
39 | ||
40 | /* Mark a limited search area. If limit_search != 1, genmove | |
41 | * will only return moves within the area marked by the array | |
42 | * search_mask. | |
43 | */ | |
44 | static int limit_search = 0; | |
45 | static int search_mask[BOARDMAX]; | |
46 | ||
47 | static int do_genmove(int color, float pure_threat_value, | |
48 | int allowed_moves[BOARDMAX], float *value, int *resign); | |
49 | ||
50 | /* Position numbers for which various examinations were last made. */ | |
51 | static int worms_examined = -1; | |
52 | static int initial_influence_examined = -1; | |
53 | static int dragons_examined_without_owl = -1; | |
54 | static int dragons_examined = -1; | |
55 | static int initial_influence2_examined = -1; | |
56 | static int dragons_refinedly_examined = -1; | |
57 | ||
58 | static int revise_semeai(int color); | |
59 | static int revise_thrashing_dragon(int color, float our_score, | |
60 | float advantage); | |
61 | ||
62 | static void break_mirror_go(int color); | |
63 | static int find_mirror_move(int *move, int color); | |
64 | static int should_resign(int color, float optimistic_score, int move); | |
65 | static void compute_scores(int use_chinese_rules); | |
66 | ||
67 | ||
68 | /* Reset some things in the engine. | |
69 | * | |
70 | * This prepares the hash table for the reading code for use. It | |
71 | * should be called when we start examine a new position. | |
72 | */ | |
73 | ||
74 | void | |
75 | reset_engine() | |
76 | { | |
77 | /* To improve the reproducability of games, we restart the random | |
78 | * number generator with the same seed for each move. Thus we don't | |
79 | * have to know how many previous moves have been played, nor | |
80 | * actually play through them, in order to get the right random | |
81 | * numbers. | |
82 | */ | |
83 | reuse_random_seed(); | |
84 | ||
85 | /* Initialize things for hashing of positions. */ | |
86 | reading_cache_clear(); | |
87 | ||
88 | hashdata_recalc(&board_hash, board, board_ko_pos); | |
89 | ||
90 | worms_examined = -1; | |
91 | initial_influence_examined = -1; | |
92 | dragons_examined_without_owl = -1; | |
93 | dragons_examined = -1; | |
94 | initial_influence2_examined = -1; | |
95 | dragons_refinedly_examined = -1; | |
96 | ||
97 | /* Prepare our table of move reasons. */ | |
98 | clear_move_reasons(); | |
99 | clear_break_in_list(); | |
100 | ||
101 | /* Set up depth values (see comments there for details). */ | |
102 | set_depth_values(get_level(), 0); | |
103 | ||
104 | /* Initialize arrays of moves which are meaningless due to | |
105 | * static analysis of unconditional status. | |
106 | */ | |
107 | clear_unconditionally_meaningless_moves(); | |
108 | } | |
109 | ||
110 | /* | |
111 | * Examine the position and try to gather as much information as possible. | |
112 | * This is used mainly for move generation, but could also be called | |
113 | * for debugging purposes (decidestring, etc). | |
114 | * | |
115 | * The parameter how_much tells us how much of the work we have to do. | |
116 | * For move generation we have to do it all. For debugging we can | |
117 | * sometimes stop a little earlier. | |
118 | * | |
119 | * aftermath_play indicates we are in aftermath playout phase. It's only | |
120 | * effect is to always use chinese rules for the score estimates. | |
121 | */ | |
122 | ||
123 | void | |
124 | examine_position(int how_much, int aftermath_play) | |
125 | { | |
126 | int save_verbose = verbose; | |
127 | ||
128 | purge_persistent_caches(); | |
129 | ||
130 | /* Don't print reading traces during make_worms and make_dragons unless | |
131 | * the user really wants it (verbose == 3). | |
132 | */ | |
133 | if (verbose == 1 || verbose == 2) | |
134 | --verbose; | |
135 | ||
136 | if (NEEDS_UPDATE(worms_examined)) { | |
137 | start_timer(0); | |
138 | make_worms(); | |
139 | time_report(0, " make worms", NO_MOVE, 1.0); | |
140 | } | |
141 | ||
142 | if (how_much == EXAMINE_WORMS) { | |
143 | verbose = save_verbose; | |
144 | gg_assert(test_gray_border() < 0); | |
145 | return; | |
146 | } | |
147 | ||
148 | if (stones_on_board(BLACK | WHITE) != 0) { | |
149 | if (NEEDS_UPDATE(initial_influence_examined)) | |
150 | compute_worm_influence(); | |
151 | if (how_much == EXAMINE_INITIAL_INFLUENCE) { | |
152 | verbose = save_verbose; | |
153 | gg_assert(test_gray_border() < 0); | |
154 | return; | |
155 | } | |
156 | ||
157 | if (how_much == EXAMINE_DRAGONS_WITHOUT_OWL) { | |
158 | if (NEEDS_UPDATE(dragons_examined_without_owl)) | |
159 | make_dragons(1); | |
160 | verbose = save_verbose; | |
161 | gg_assert(test_gray_border() < 0); | |
162 | return; | |
163 | } | |
164 | ||
165 | if (NEEDS_UPDATE(dragons_examined)) { | |
166 | make_dragons(0); | |
167 | compute_scores(chinese_rules || aftermath_play); | |
168 | /* We have automatically done a partial dragon analysis as well. */ | |
169 | dragons_examined_without_owl = position_number; | |
170 | } | |
171 | if (how_much == EXAMINE_DRAGONS) { | |
172 | verbose = save_verbose; | |
173 | gg_assert(test_gray_border() < 0); | |
174 | return; | |
175 | } | |
176 | } | |
177 | else if (how_much == EXAMINE_INITIAL_INFLUENCE | |
178 | || how_much == EXAMINE_DRAGONS | |
179 | || how_much == EXAMINE_ALL) { | |
180 | initialize_dragon_data(); | |
181 | compute_scores(chinese_rules || aftermath_play); | |
182 | verbose = save_verbose; | |
183 | gg_assert(test_gray_border() < 0); | |
184 | return; | |
185 | } | |
186 | ||
187 | verbose = save_verbose; | |
188 | ||
189 | if (NEEDS_UPDATE(initial_influence2_examined)) { | |
190 | compute_dragon_influence(); | |
191 | } | |
192 | if (how_much == EXAMINE_INITIAL_INFLUENCE2) { | |
193 | gg_assert(test_gray_border() < 0); | |
194 | return; | |
195 | } | |
196 | ||
197 | if (NEEDS_UPDATE(dragons_refinedly_examined)) { | |
198 | compute_refined_dragon_weaknesses(); | |
199 | compute_strategic_sizes(); | |
200 | } | |
201 | if (how_much == FULL_EXAMINE_DRAGONS) { | |
202 | gg_assert(test_gray_border() < 0); | |
203 | return; | |
204 | } | |
205 | ||
206 | if (printworms) | |
207 | show_dragons(); | |
208 | } | |
209 | ||
210 | ||
211 | /* The same as examine_position(), except that all traces, debug | |
212 | * output, and sgf traces are turned off. | |
213 | */ | |
214 | void | |
215 | silent_examine_position(int how_much) | |
216 | { | |
217 | int save_verbose = verbose; | |
218 | SGFTree *save_sgf_dumptree = sgf_dumptree; | |
219 | int save_count_variations = count_variations; | |
220 | int save_debug = debug; | |
221 | int save_printmoyo = printmoyo; | |
222 | ||
223 | verbose = 0; | |
224 | sgf_dumptree = NULL; | |
225 | count_variations = 0; | |
226 | debug = 0; | |
227 | printmoyo = 0; | |
228 | ||
229 | examine_position(how_much, 0); | |
230 | ||
231 | verbose = save_verbose; | |
232 | sgf_dumptree = save_sgf_dumptree; | |
233 | count_variations = save_count_variations; | |
234 | debug = save_debug; | |
235 | printmoyo = save_printmoyo; | |
236 | } | |
237 | ||
238 | ||
239 | /* | |
240 | * Generate computer move for color. | |
241 | * | |
242 | * Return the generated move. | |
243 | */ | |
244 | ||
245 | int | |
246 | genmove(int color, float *value, int *resign) | |
247 | { | |
248 | int move = PASS_MOVE; | |
249 | if (resign) | |
250 | *resign = 0; | |
251 | ||
252 | #if ORACLE | |
253 | if (metamachine) { | |
254 | move = metamachine_genmove(color, value, limit_search); | |
255 | gg_assert(stackp == 0); | |
256 | if (move != PASS_MOVE) | |
257 | return move; | |
258 | } | |
259 | #endif | |
260 | ||
261 | if (limit_search) | |
262 | move = do_genmove(color, 0.4, search_mask, value, resign); | |
263 | else | |
264 | move = do_genmove(color, 0.4, NULL, value, resign); | |
265 | gg_assert(move == PASS_MOVE || ON_BOARD(move)); | |
266 | ||
267 | return move; | |
268 | } | |
269 | ||
270 | ||
271 | /* | |
272 | * Same as above but doesn't generate pure threat moves. Useful when | |
273 | * trying to score a game. | |
274 | */ | |
275 | ||
276 | int | |
277 | genmove_conservative(int color, float *value) | |
278 | { | |
279 | return do_genmove(color, 0.0, NULL, value, NULL); | |
280 | } | |
281 | ||
282 | ||
283 | int | |
284 | genmove_restricted(int color, int allowed_moves[BOARDMAX]) | |
285 | { | |
286 | return do_genmove(color, 0.0, allowed_moves, NULL, NULL); | |
287 | } | |
288 | ||
289 | /* This function collects move reasons can be generated immediately from | |
290 | * the data gathered in the examine_position() phase. | |
291 | */ | |
292 | void | |
293 | collect_move_reasons(int color) | |
294 | { | |
295 | worm_reasons(color); | |
296 | semeai_move_reasons(color); | |
297 | owl_reasons(color); | |
298 | cut_reasons(color); | |
299 | break_in_move_reasons(color); | |
300 | unconditional_move_reasons(color); | |
301 | } | |
302 | ||
303 | /* Call Monte Carlo module to generate a move. */ | |
304 | static int | |
305 | monte_carlo_genmove(int color, int allowed_moves[BOARDMAX], | |
306 | float *value, int *resign) | |
307 | { | |
308 | int pos; | |
309 | int best_move = PASS_MOVE; | |
310 | int best_uct_move = PASS_MOVE; | |
311 | int unconditional_territory_black[BOARDMAX]; | |
312 | int unconditional_territory_white[BOARDMAX]; | |
313 | int forbidden_move[BOARDMAX]; | |
314 | float move_values[BOARDMAX]; | |
315 | int move_frequencies[BOARDMAX]; | |
316 | float best_value; | |
317 | int frequency_cutoff; | |
318 | int frequency_cutoff2; | |
319 | int number_of_simulations; | |
320 | ||
321 | memset(move_values, 0, sizeof(move_values)); | |
322 | memset(move_frequencies, 0, sizeof(move_frequencies)); | |
323 | ||
324 | if (0) { | |
325 | simple_showboard(stderr); | |
326 | gprintf("\n"); | |
327 | } | |
328 | ||
329 | if (resign) | |
330 | *resign = 0; | |
331 | ||
332 | unconditional_life(unconditional_territory_black, BLACK); | |
333 | unconditional_life(unconditional_territory_white, WHITE); | |
334 | ||
335 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
336 | if (!ON_BOARD(pos)) | |
337 | continue; | |
338 | else if (unconditional_territory_black[pos]) | |
339 | forbidden_move[pos] = BLACK; | |
340 | else if (unconditional_territory_white[pos]) | |
341 | forbidden_move[pos] = WHITE; | |
342 | else | |
343 | forbidden_move[pos] = 0; | |
344 | ||
345 | number_of_simulations = mc_games_per_level * gg_max(get_level(), 1); | |
346 | ||
347 | uct_genmove(color, &best_uct_move, forbidden_move, allowed_moves, | |
348 | number_of_simulations, move_values, move_frequencies); | |
349 | ||
350 | best_move = best_uct_move; | |
351 | best_value = 0.0; | |
352 | frequency_cutoff = move_frequencies[best_uct_move] / 2; | |
353 | frequency_cutoff2 = move_frequencies[best_uct_move] / 10; | |
354 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
355 | if (ON_BOARD(pos) | |
356 | && (move_frequencies[pos] > frequency_cutoff | |
357 | || (move_values[pos] > 0.9 | |
358 | && move_frequencies[pos] > frequency_cutoff2) | |
359 | || move_values[best_uct_move] < 0.1) | |
360 | && (!allowed_moves || allowed_moves[pos]) | |
361 | && potential_moves[pos] > best_value) { | |
362 | best_move = pos; | |
363 | best_value = potential_moves[pos]; | |
364 | } | |
365 | } | |
366 | ||
367 | unconditionally_meaningless_move(best_move, color, &best_move); | |
368 | ||
369 | *value = 1.0; | |
370 | ||
371 | return best_move; | |
372 | } | |
373 | ||
374 | ||
375 | /* | |
376 | * Perform the actual move generation. | |
377 | * | |
378 | * The array allowed_moves restricts which moves may be considered. If | |
379 | * NULL any move is allowed. Pass is always allowed and will be chosen | |
380 | * if the move generation doesn't like any of the allowed moves (or | |
381 | * overlooks them). | |
382 | */ | |
383 | ||
384 | static int | |
385 | do_genmove(int color, float pure_threat_value, | |
386 | int allowed_moves[BOARDMAX], float *value, int *resign) | |
387 | { | |
388 | float average_score, pessimistic_score, optimistic_score; | |
389 | int save_verbose; | |
390 | int save_depth; | |
391 | int move; | |
392 | float dummy_value; | |
393 | int use_thrashing_dragon_heuristics = 0; | |
394 | ||
395 | if (!value) | |
396 | value = &dummy_value; | |
397 | ||
398 | start_timer(0); | |
399 | clearstats(); | |
400 | ||
401 | /* Usually we would not recommend resignation. */ | |
402 | if (resign) | |
403 | *resign = 0; | |
404 | ||
405 | /* Prepare our table of moves considered. */ | |
406 | memset(potential_moves, 0, sizeof(potential_moves)); | |
407 | ||
408 | /* no move is found yet. */ | |
409 | move = PASS_MOVE; | |
410 | *value = 0.0; | |
411 | ||
412 | /* Prepare pattern matcher and reading code. */ | |
413 | reset_engine(); | |
414 | ||
415 | /* Store the depth value so we can check that it hasn't changed when | |
416 | * we leave this function. | |
417 | */ | |
418 | save_depth = depth; | |
419 | ||
420 | /* If in mirror mode, try to find a mirror move. */ | |
421 | if (play_mirror_go | |
422 | && (mirror_stones_limit < 0 | |
423 | || stones_on_board(WHITE | BLACK) <= mirror_stones_limit) | |
424 | && find_mirror_move(&move, color)) { | |
425 | TRACE("genmove() recommends mirror move at %1m\n", move); | |
426 | *value = 1.0; | |
427 | return move; | |
428 | } | |
429 | ||
430 | /* Find out information about the worms and dragons. */ | |
431 | start_timer(1); | |
432 | examine_position(EXAMINE_ALL, 0); | |
433 | time_report(1, "examine position", NO_MOVE, 1.0); | |
434 | ||
435 | ||
436 | /* The score will be used to determine when we are safely | |
437 | * ahead. So we want the most conservative score. | |
438 | * | |
439 | * We always want to have the score from our point of view. So | |
440 | * negate it if we are black. | |
441 | */ | |
442 | if (color == WHITE) { | |
443 | pessimistic_score = black_score; | |
444 | optimistic_score = white_score; | |
445 | } | |
446 | else { | |
447 | pessimistic_score = -white_score; | |
448 | optimistic_score = -black_score; | |
449 | } | |
450 | ||
451 | if (color == WHITE) | |
452 | average_score = (white_score + black_score)/2.0; | |
453 | else | |
454 | average_score = -(white_score + black_score)/2.0; | |
455 | choose_strategy(color, average_score, game_status(color)); | |
456 | ||
457 | if (printboard) { | |
458 | if (printboard == 1) | |
459 | fprintf(stderr, "\n dragon_status display:\n\n"); | |
460 | if (printboard == 2) | |
461 | fprintf(stderr, "\n eye display:\n\n"); | |
462 | showboard(printboard); | |
463 | if (printboard == 1) { | |
464 | fprintf(stderr, "\n owl_status display:\n\n"); | |
465 | showboard(3); | |
466 | fprintf(stderr, "\n matcher_status display:\n\n"); | |
467 | showboard(4); | |
468 | } | |
469 | } | |
470 | ||
471 | gg_assert(stackp == 0); | |
472 | ||
473 | /* | |
474 | * Ok, information gathering is complete. Now start to find some moves! | |
475 | */ | |
476 | ||
477 | ||
478 | /* Pick up moves that we know of already. */ | |
479 | save_verbose = verbose; | |
480 | if (verbose > 0) | |
481 | verbose--; | |
482 | collect_move_reasons(color); | |
483 | verbose = save_verbose; | |
484 | time_report(1, "generate move reasons", NO_MOVE, 1.0); | |
485 | ||
486 | /* Try to find empty corner moves. */ | |
487 | fuseki(color); | |
488 | gg_assert(stackp == 0); | |
489 | ||
490 | /* Look for moves to break mirror play by the opponent. */ | |
491 | break_mirror_go(color); | |
492 | ||
493 | /* If we are ahead by 5 points or more, consider a thrashing | |
494 | * dragon dangerous and change its status from DEAD to | |
495 | * UNKNOWN. Otherwise, pretend there is no thrashing dragon. | |
496 | */ | |
497 | if (!doing_scoring) | |
498 | use_thrashing_dragon_heuristics | |
499 | = revise_thrashing_dragon(color, pessimistic_score, 5.0); | |
500 | ||
501 | /* The general pattern database. */ | |
502 | shapes(color); | |
503 | time_report(1, "shapes", NO_MOVE, 1.0); | |
504 | gg_assert(stackp == 0); | |
505 | ||
506 | /* Look for combination attacks and defenses against them. */ | |
507 | combinations(color); | |
508 | time_report(1, "combinations", NO_MOVE, 1.0); | |
509 | gg_assert(stackp == 0); | |
510 | ||
511 | /* Review the move reasons and estimate move values. */ | |
512 | if (review_move_reasons(&move, value, color, | |
513 | pure_threat_value, pessimistic_score, allowed_moves, | |
514 | use_thrashing_dragon_heuristics)) | |
515 | TRACE("Move generation likes %1m with value %f\n", move, *value); | |
516 | gg_assert(stackp == 0); | |
517 | time_report(1, "review move reasons", NO_MOVE, 1.0); | |
518 | ||
519 | ||
520 | /* If the move value is 6 or lower, we look for endgame patterns too. */ | |
521 | if (*value <= 6.0 && !disable_endgame_patterns) { | |
522 | endgame_shapes(color); | |
523 | endgame(color); | |
524 | gg_assert(stackp == 0); | |
525 | if (review_move_reasons(&move, value, color, pure_threat_value, | |
526 | pessimistic_score, allowed_moves, | |
527 | use_thrashing_dragon_heuristics)) | |
528 | TRACE("Move generation likes %1m with value %f\n", move, *value); | |
529 | gg_assert(stackp == 0); | |
530 | time_report(1, "endgame", NO_MOVE, 1.0); | |
531 | } | |
532 | ||
533 | /* If no move found yet, revisit any semeai and change the | |
534 | * status of the opponent group from DEAD to UNKNOWN, then | |
535 | * run shapes and endgame_shapes again. This may turn up a move. | |
536 | */ | |
537 | if (move == PASS_MOVE) { | |
538 | if (revise_semeai(color)) { | |
539 | shapes(color); | |
540 | endgame_shapes(color); | |
541 | if (review_move_reasons(&move, value, color, pure_threat_value, | |
542 | pessimistic_score, allowed_moves, | |
543 | use_thrashing_dragon_heuristics)) { | |
544 | TRACE("Upon reconsideration move generation likes %1m with value %f\n", | |
545 | move, *value); | |
546 | } | |
547 | } | |
548 | time_report(1, "move reasons with revised semeai status", | |
549 | NO_MOVE, 1.0); | |
550 | } | |
551 | ||
552 | /* If Monte Carlo move generation is enabled, call it now. Do not | |
553 | * override a fuseki move. | |
554 | * | |
555 | * FIXME: Identifying fuseki moves by checking the move value is | |
556 | * very ugly and fragile. | |
557 | */ | |
558 | if (use_monte_carlo_genmove && move != PASS_MOVE | |
559 | && (*value < 75.0 || *value > 75.01) && !doing_scoring) { | |
560 | int allowed_moves2[BOARDMAX]; | |
561 | int num_allowed_moves2 = 0; | |
562 | int pos; | |
563 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
564 | if (ON_BOARD(pos) | |
565 | && (!allowed_moves || allowed_moves[pos]) | |
566 | && is_allowed_move(pos, color)) { | |
567 | allowed_moves2[pos] = 1; | |
568 | num_allowed_moves2++; | |
569 | } | |
570 | else | |
571 | allowed_moves2[pos] = 0; | |
572 | ||
573 | if (num_allowed_moves2 > 1) | |
574 | move = monte_carlo_genmove(color, allowed_moves2, value, resign); | |
575 | } | |
576 | ||
577 | /* If still no move, fill a remaining liberty. This should pick up | |
578 | * all missing dame points. | |
579 | */ | |
580 | if (move == PASS_MOVE | |
581 | && fill_liberty(&move, color)) { | |
582 | if (!allowed_moves || allowed_moves[move]) { | |
583 | *value = 1.0; | |
584 | TRACE("Filling a liberty at %1m\n", move); | |
585 | record_top_move(move, *value); | |
586 | move_considered(move, *value); | |
587 | time_report(1, "fill liberty", NO_MOVE, 1.0); | |
588 | } | |
589 | else | |
590 | move = PASS_MOVE; | |
591 | } | |
592 | ||
593 | /* If we're instructed to play out the aftermath or capture all dead | |
594 | * opponent stones, or if the opponent is trying to live inside | |
595 | * our territory and we are clearly ahead, generate an aftermath move. | |
596 | */ | |
597 | if (move == PASS_MOVE) { | |
598 | if (play_out_aftermath | |
599 | || capture_all_dead | |
600 | || (!doing_scoring && thrashing_dragon && pessimistic_score > 15.0)) | |
601 | move = aftermath_genmove(color, capture_all_dead, allowed_moves); | |
602 | ||
603 | if (move != PASS_MOVE) { | |
604 | ASSERT1(is_legal(move, color), move); | |
605 | *value = 1.0; | |
606 | TRACE("Aftermath move at %1m\n", move); | |
607 | record_top_move(move, *value); | |
608 | move_considered(move, *value); | |
609 | time_report(1, "aftermath_genmove", NO_MOVE, 1.0); | |
610 | } | |
611 | } | |
612 | ||
613 | /* If we somehow have managed to generate an illegal move, pass instead. */ | |
614 | if (!is_allowed_move(move, color)) { | |
615 | TRACE("ILLEGAL MOVE GENERATED. Passing instead.\n"); | |
616 | move = PASS_MOVE; | |
617 | *value = -1.0; | |
618 | } | |
619 | ||
620 | /* If no move is found then pass. */ | |
621 | if (move == PASS_MOVE) { | |
622 | TRACE("I pass.\n"); | |
623 | } | |
624 | else { | |
625 | TRACE("genmove() recommends %1m with value %f\n", move, *value); | |
626 | } | |
627 | ||
628 | /* Maybe time to resign... | |
629 | */ | |
630 | if (resign && resign_allowed | |
631 | && *value < 10.0 && should_resign(color, optimistic_score, move)) { | |
632 | TRACE("... though, genmove() thinks the position is hopeless\n"); | |
633 | *resign = 1; | |
634 | } | |
635 | ||
636 | /* If statistics is turned on, this is the place to show it. */ | |
637 | if (showstatistics) | |
638 | showstats(); | |
639 | ||
640 | if (showtime) { | |
641 | double spent = time_report(0, "TIME to generate move at ", move, 1.0); | |
642 | total_time += spent; | |
643 | if (spent > slowest_time) { | |
644 | slowest_time = spent; | |
645 | slowest_move = move; | |
646 | slowest_movenum = movenum + 1; | |
647 | } | |
648 | } | |
649 | ||
650 | /* Some consistency checks to verify that things are properly | |
651 | * restored and/or have not been corrupted. | |
652 | */ | |
653 | gg_assert(stackp == 0); | |
654 | gg_assert(test_gray_border() < 0); | |
655 | gg_assert(depth == save_depth); | |
656 | ||
657 | return move; | |
658 | } | |
659 | ||
660 | ||
661 | ||
662 | /* This is called for each move which has been considered. For | |
663 | * debugging purposes, we keep a table of all the moves we | |
664 | * have considered. | |
665 | */ | |
666 | ||
667 | void | |
668 | move_considered(int move, float value) | |
669 | { | |
670 | if (value > potential_moves[move]) | |
671 | potential_moves[move] = value; | |
672 | } | |
673 | ||
674 | ||
675 | /* revise_semeai(color) changes the status of any DEAD dragon of | |
676 | * OPPOSITE_COLOR(color) which occurs in a semeai to UNKNOWN. | |
677 | * It returns true if such a dragon is found. | |
678 | */ | |
679 | ||
680 | static int | |
681 | revise_semeai(int color) | |
682 | { | |
683 | int pos; | |
684 | int found_one = 0; | |
685 | int other = OTHER_COLOR(color); | |
686 | ||
687 | if (stones_on_board(BLACK | WHITE) == 0) | |
688 | return 0; | |
689 | ||
690 | if (doing_scoring) | |
691 | return 0; | |
692 | ||
693 | gg_assert(dragon2 != NULL); | |
694 | ||
695 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
696 | if (ON_BOARD(pos) | |
697 | && dragon[pos].color == other | |
698 | && DRAGON2(pos).semeais | |
699 | && dragon[pos].status == DEAD) { | |
700 | found_one = 1; | |
701 | dragon[pos].status = UNKNOWN; | |
702 | if (dragon[pos].origin == pos) | |
703 | TRACE("revise_semeai: changed status of dragon %1m from DEAD to UNKNOWN\n", | |
704 | pos); | |
705 | } | |
706 | } | |
707 | ||
708 | return found_one; | |
709 | } | |
710 | ||
711 | ||
712 | /* If the opponent's last move added a stone to a dead dragon, | |
713 | * revise it's status to UNKNOWN. This will cause genmove to | |
714 | * generate moves restraining the dragon. We only do this if | |
715 | * we are ahead by 'advantage', and no owl threat has been found. | |
716 | */ | |
717 | ||
718 | static int | |
719 | revise_thrashing_dragon(int color, float our_score, float advantage) | |
720 | { | |
721 | int pos; | |
722 | signed char safe_stones[BOARDMAX]; | |
723 | float strength[BOARDMAX]; | |
724 | ||
725 | /* Trust the owl code's opinion if we are behind. */ | |
726 | if (our_score < advantage) | |
727 | return 0; | |
728 | ||
729 | if (disable_threat_computation | |
730 | || !thrashing_dragon | |
731 | || dragon[thrashing_dragon].status != DEAD) | |
732 | return 0; | |
733 | ||
734 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
735 | if (ON_BOARD(pos) && thrashing_stone[pos] | |
736 | && worm[pos].unconditional_status != DEAD) { | |
737 | dragon[pos].status = UNKNOWN; | |
738 | DRAGON2(pos).safety = ALIVE; | |
739 | } | |
740 | ||
741 | set_strength_data(OTHER_COLOR(color), safe_stones, strength); | |
742 | compute_influence(OTHER_COLOR(color), safe_stones, strength, | |
743 | OPPOSITE_INFLUENCE(color), | |
744 | NO_MOVE, "revised thrashing dragon"); | |
745 | compute_refined_dragon_weaknesses(); | |
746 | ||
747 | return 1; | |
748 | } | |
749 | ||
750 | ||
751 | /* Look for a mirror move. First try the mirror of the last move. If | |
752 | * none is available, test all moves to see if one makes the board | |
753 | * symmetric. | |
754 | * | |
755 | * To be able to deal with handicap stones we use a somewhat weak | |
756 | * definition of symmetry. | |
757 | */ | |
758 | ||
759 | static int | |
760 | find_mirror_move(int *move, int color) | |
761 | { | |
762 | int last_move = get_last_move(); | |
763 | int mirror_move; | |
764 | if (last_move != NO_MOVE) { | |
765 | mirror_move = MIRROR_MOVE(last_move); | |
766 | if (test_symmetry_after_move(mirror_move, color, 0)) { | |
767 | *move = mirror_move; | |
768 | return 1; | |
769 | } | |
770 | } | |
771 | else { | |
772 | for (mirror_move = BOARDMIN; mirror_move < BOARDMAX; mirror_move++) { | |
773 | if (ON_BOARD(mirror_move) | |
774 | && test_symmetry_after_move(mirror_move, color, 0)) { | |
775 | *move = mirror_move; | |
776 | return 1; | |
777 | } | |
778 | } | |
779 | } | |
780 | ||
781 | return 0; | |
782 | } | |
783 | ||
784 | /* Computer two territory estimates: for *upper, the status of all | |
785 | * cricital stones gets resolved in White's favor; vice verso for | |
786 | * black. | |
787 | */ | |
788 | static void | |
789 | compute_scores(int use_chinese_rules) | |
790 | { | |
791 | signed char safe_stones[BOARDMAX]; | |
792 | float strength[BOARDMAX]; | |
793 | ||
794 | set_strength_data(WHITE, safe_stones, strength); | |
795 | compute_influence(EMPTY, safe_stones, strength, &move_influence, | |
796 | NO_MOVE, "White territory estimate"); | |
797 | white_score = influence_score(&move_influence, use_chinese_rules); | |
798 | set_strength_data(BLACK, safe_stones, strength); | |
799 | compute_influence(EMPTY, safe_stones, strength, &move_influence, | |
800 | NO_MOVE, "White territory estimate"); | |
801 | black_score = influence_score(&move_influence, use_chinese_rules); | |
802 | ||
803 | if (verbose || showscore) { | |
804 | if (white_score == black_score) | |
805 | gprintf("Score estimate: %s %f\n", | |
806 | black_score > 0 ? "W " : "B ", gg_abs(black_score)); | |
807 | else | |
808 | gprintf("Score estimate: %s %f to %s %f\n", | |
809 | black_score > 0 ? "W " : "B ", gg_abs(black_score), | |
810 | white_score > 0 ? "W " : "B ", gg_abs(white_score)); | |
811 | fflush(stderr); | |
812 | } | |
813 | } | |
814 | ||
815 | ||
816 | /* Detect if a white opponent has played mirror go for at least 10 | |
817 | * moves and if so play on tengen. | |
818 | * | |
819 | * Mirror breaking moves in other situations are handled by patterns | |
820 | * in patterns.db. | |
821 | */ | |
822 | static void | |
823 | break_mirror_go(int color) | |
824 | { | |
825 | int tengen = POS((board_size - 1) / 2, (board_size - 1) / 2); | |
826 | if (board[tengen] == EMPTY | |
827 | && color == BLACK | |
828 | && stones_on_board(BLACK | WHITE) > 10 | |
829 | && test_symmetry_after_move(tengen, color, 1)) { | |
830 | set_minimum_move_value(tengen, 30.0); | |
831 | TRACE("Play %1m to break mirror go, value 30.\n", tengen); | |
832 | } | |
833 | } | |
834 | ||
835 | ||
836 | /* Helper to decide whether GG should resign a game | |
837 | */ | |
838 | static int | |
839 | should_resign(int color, float optimistic_score, int move) | |
840 | { | |
841 | float status; | |
842 | int d; | |
843 | /* We resign 19x19 games only, smaller board games are fast enough. | |
844 | * We resign only if the margin is bigger than 45 pts and if we are | |
845 | * behind (of course). | |
846 | * | |
847 | * As an exception to this rule, we resign on any board size if | |
848 | * it looks like all our dragons are dead and the generated move | |
849 | * is a pass. | |
850 | */ | |
851 | if (board_size > 2 && move == PASS_MOVE && !lively_dragon_exists(color)) | |
852 | return 1; | |
853 | ||
854 | if (move == PASS_MOVE | |
855 | || board_size < 19 | |
856 | || optimistic_score > -45.0) | |
857 | return 0; | |
858 | /* Check dragon statuses. If a friendly dragon is critical, we are | |
859 | * possibly not that much behind after we save it. If some hostile | |
860 | * dragon is at least weak, we possibly have a chance to come back | |
861 | * if we can kill it. | |
862 | */ | |
863 | for (d = 0; d < number_of_dragons; d++) { | |
864 | /* any friendly critical dragon ? */ | |
865 | if (board[dragon2[d].origin] == color | |
866 | && DRAGON(d).status == CRITICAL) | |
867 | return 0; | |
868 | /* any weak opponent dragon ? */ | |
869 | if (board[dragon2[d].origin] == OTHER_COLOR(color) | |
870 | && DRAGON(d).status != DEAD | |
871 | && DRAGON(d).effective_size >= 10 | |
872 | && dragon_weak(dragon2[d].origin)) | |
873 | return 0; | |
874 | } | |
875 | /* Is it already too late to try something ? */ | |
876 | status = game_status(color); | |
877 | if (status < 0.8) | |
878 | /* Still "too early". | |
879 | * Note: the 0.8 constant is very conservative, we actually could give | |
880 | * up a bit earlier. | |
881 | */ | |
882 | return 0; | |
883 | ||
884 | /* well, it is probably reasonable and polite to give up this game */ | |
885 | return 1; | |
886 | } | |
887 | ||
888 | ||
889 | /*********************************************************************\ | |
890 | * Mark a limited search area * | |
891 | \*********************************************************************/ | |
892 | ||
893 | /* Activate or deactivate search limit. */ | |
894 | void | |
895 | set_limit_search(int value) | |
896 | { | |
897 | limit_search = value; | |
898 | } | |
899 | ||
900 | /* The following function marks a diamond of radius 6 with center pos. */ | |
901 | ||
902 | void | |
903 | set_search_diamond(int pos) | |
904 | { | |
905 | int i = I(pos); | |
906 | int j = J(pos); | |
907 | int m, n; | |
908 | ||
909 | for (m = 0; m < board_size; m++) | |
910 | for (n = 0; n < board_size; n++) { | |
911 | if (gg_abs(m - i) + gg_abs(n - j) <= 6) | |
912 | search_mask[POS(m, n)] = 1; | |
913 | else | |
914 | search_mask[POS(m, n)] = 0; | |
915 | } | |
916 | limit_search = pos; | |
917 | if (0) | |
918 | draw_search_area(); | |
919 | } | |
920 | ||
921 | /* unmarks the entire board */ | |
922 | ||
923 | void | |
924 | reset_search_mask() | |
925 | { | |
926 | memset(search_mask, 0, sizeof(search_mask)); | |
927 | } | |
928 | ||
929 | /* marks a single vertex */ | |
930 | ||
931 | void | |
932 | set_search_mask(int pos, int value) | |
933 | { | |
934 | search_mask[pos] = value; | |
935 | } | |
936 | ||
937 | /* displays the search area */ | |
938 | ||
939 | void | |
940 | draw_search_area(void) | |
941 | { | |
942 | int m, n; | |
943 | ||
944 | start_draw_board(); | |
945 | for (m = 0; m < board_size; m++) | |
946 | for (n = 0; n < board_size; n++) { | |
947 | int col, c; | |
948 | ||
949 | if (search_mask[POS(m, n)]) | |
950 | col = GG_COLOR_RED; | |
951 | else | |
952 | col = GG_COLOR_BLACK; | |
953 | ||
954 | if (board[POS(m, n)] == BLACK) | |
955 | c = 'X'; | |
956 | else if (board[POS(m, n)] == WHITE) | |
957 | c = 'O'; | |
958 | else if (search_mask[POS(m, n)]) | |
959 | c = '*'; | |
960 | else | |
961 | c = '.'; | |
962 | draw_color_char(m, n, c, col); | |
963 | } | |
964 | end_draw_board(); | |
965 | } | |
966 | ||
967 | /* returns true if the position is within the search area */ | |
968 | int | |
969 | within_search_area(int pos) | |
970 | { | |
971 | if (!limit_search) | |
972 | return 1; | |
973 | return search_mask[pos]; | |
974 | } | |
975 | ||
976 | /* | |
977 | * Local Variables: | |
978 | * tab-width: 8 | |
979 | * c-basic-offset: 2 | |
980 | * End: | |
981 | */ |