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 | /* A "dragon" is a union of strings of the same color which will be | |
25 | * treated as a unit. The dragons are generated anew at each | |
26 | * move. If two strings are in the dragon, it is GNU Go's working | |
27 | * hypothesis that they will live or die together and are | |
28 | * effectively connected. | |
29 | * | |
30 | * _____/| (! !) | |
31 | * / ____/| /@ @) | |
32 | * / / __ // +--oo | |
33 | * | / | >> /< _-v--} | |
34 | * | | UUU\\\ / / \\ | |
35 | * | | __ _\\\ \ \ U | |
36 | * | | / V \\--> \ \ | |
37 | * | <_/ \_/ } | |
38 | * | __ ____ / | |
39 | * \ / \___/ / /\ | |
40 | * < \< < <\ \ | |
41 | * ( ))) ( ))))) | |
42 | */ | |
43 | ||
44 | #include "gnugo.h" | |
45 | ||
46 | #include <stdio.h> | |
47 | #include <stdlib.h> | |
48 | #include <string.h> | |
49 | #include <ctype.h> | |
50 | ||
51 | #include "liberty.h" | |
52 | #include "gg_utils.h" | |
53 | ||
54 | static void initialize_supplementary_dragon_data(void); | |
55 | static void find_lunches(void); | |
56 | static void eye_computations(void); | |
57 | static void revise_inessentiality(void); | |
58 | static void find_neighbor_dragons(void); | |
59 | static void add_adjacent_dragons(int a, int b); | |
60 | static void add_adjacent_dragon(int a, int b); | |
61 | static int dragon_invincible(int pos); | |
62 | static int dragon_looks_inessential(int origin); | |
63 | static void identify_thrashing_dragons(void); | |
64 | static void analyze_false_eye_territory(void); | |
65 | static int connected_to_eye(int pos, int str, int color, int eye_color, | |
66 | struct eye_data *eye); | |
67 | static void connected_to_eye_recurse(int pos, int str, int color, | |
68 | int eye_color, struct eye_data *eye, | |
69 | signed char *mx, signed char *me, | |
70 | int *halfeyes); | |
71 | static enum dragon_status compute_crude_status(int pos); | |
72 | static int compute_escape(int pos, int dragon_status_known); | |
73 | static void compute_surrounding_moyo_sizes(const struct influence_data *q); | |
74 | static void clear_cut_list(void); | |
75 | ||
76 | static int dragon2_initialized; | |
77 | static int lively_white_dragons; | |
78 | static int lively_black_dragons; | |
79 | ||
80 | /* This is a private array to obtain a list of worms belonging to each | |
81 | * dragon. Public access is via first_worm_in_dragon() and | |
82 | * next_worm_in_dragon(). | |
83 | */ | |
84 | static int next_worm_list[BOARDMAX]; | |
85 | ||
86 | /* Alternative for DRAGON2 macro with asserts. */ | |
87 | struct dragon_data2 * | |
88 | dragon2_func(int pos) | |
89 | { | |
90 | ASSERT1(ON_BOARD1(pos) | |
91 | && dragon[pos].id >= 0 | |
92 | && dragon[pos].id < number_of_dragons, pos); | |
93 | return &dragon2[dragon[pos].id]; | |
94 | } | |
95 | ||
96 | /* This basic function finds all dragons and collects some basic information | |
97 | * about them in the dragon array. | |
98 | * | |
99 | * color is the player in turn to move. This does in no way affect the | |
100 | * information collected about the dragons, but it does affect what | |
101 | * information is passed on to the move generation code. If | |
102 | * color == EMPTY no information at all is passed on to the move generation. | |
103 | */ | |
104 | ||
105 | void | |
106 | make_dragons(int stop_before_owl) | |
107 | { | |
108 | int str; | |
109 | int d; | |
110 | ||
111 | dragon2_initialized = 0; | |
112 | initialize_dragon_data(); | |
113 | ||
114 | /* Find explicit connections patterns in database and amalgamate | |
115 | * involved dragons. | |
116 | */ | |
117 | memset(cutting_points, 0, sizeof(cutting_points)); | |
118 | find_cuts(); | |
119 | find_connections(); | |
120 | ||
121 | /* At this time, all dragons have been finalized and we can | |
122 | * initialize the dragon2[] array. After that we can no longer allow | |
123 | * amalgamation of dragons. | |
124 | */ | |
125 | initialize_supplementary_dragon_data(); | |
126 | ||
127 | make_domains(black_eye, white_eye, 0); | |
128 | ||
129 | /* Find adjacent worms which can be easily captured: */ | |
130 | find_lunches(); | |
131 | ||
132 | /* Find topological half eyes and false eyes. */ | |
133 | find_half_and_false_eyes(BLACK, black_eye, half_eye, NULL); | |
134 | find_half_and_false_eyes(WHITE, white_eye, half_eye, NULL); | |
135 | ||
136 | /* Compute the number of eyes, half eyes, determine attack/defense points | |
137 | * etc. for all eye spaces. */ | |
138 | eye_computations(); | |
139 | /* Try to determine whether topologically false and half eye points | |
140 | * contribute to territory even if the eye doesn't solidify. | |
141 | */ | |
142 | analyze_false_eye_territory(); | |
143 | ||
144 | /* Now we compute the genus. */ | |
145 | for (d = 0; d < number_of_dragons; d++) | |
146 | compute_dragon_genus(dragon2[d].origin, &dragon2[d].genus, NO_MOVE); | |
147 | ||
148 | /* Compute the escape route measure. */ | |
149 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
150 | if (IS_STONE(board[str]) && dragon[str].origin == str) | |
151 | DRAGON2(str).escape_route = compute_escape(str, 0); | |
152 | ||
153 | /* Set dragon weaknesses according to initial_influence. */ | |
154 | compute_refined_dragon_weaknesses(); | |
155 | for (d = 0; d < number_of_dragons; d++) | |
156 | dragon2[d].weakness_pre_owl = dragon2[d].weakness; | |
157 | ||
158 | /* Determine status: ALIVE, DEAD, CRITICAL or UNKNOWN */ | |
159 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
160 | if (ON_BOARD(str)) | |
161 | if (dragon[str].origin == str && board[str]) | |
162 | dragon[str].crude_status = compute_crude_status(str); | |
163 | ||
164 | /* We must update the dragon status at every intersection before we | |
165 | * call the owl code. This updates all fields. | |
166 | */ | |
167 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
168 | if (ON_BOARD(str) && board[str] != EMPTY) | |
169 | dragon[str] = dragon[dragon[str].origin]; | |
170 | ||
171 | find_neighbor_dragons(); | |
172 | ||
173 | for (d = 0; d < number_of_dragons; d++) { | |
174 | dragon2[d].surround_status | |
175 | = compute_surroundings(dragon2[d].origin, NO_MOVE, 0, | |
176 | &(dragon2[d].surround_size)); | |
177 | if (dragon2[d].surround_status == SURROUNDED) { | |
178 | dragon2[d].escape_route = 0; | |
179 | if (debug & DEBUG_DRAGONS) | |
180 | gprintf("surrounded dragon found at %1m\n", dragon2[d].origin); | |
181 | } | |
182 | else if (dragon2[d].surround_status == WEAKLY_SURROUNDED) { | |
183 | dragon2[d].escape_route /= 2; | |
184 | if (debug & DEBUG_DRAGONS) | |
185 | gprintf("weakly surrounded dragon found at %1m\n", dragon2[d].origin); | |
186 | } | |
187 | } | |
188 | ||
189 | if (stop_before_owl) | |
190 | return; | |
191 | ||
192 | /* Determine life and death status of each dragon using the owl code | |
193 | * if necessary. | |
194 | */ | |
195 | start_timer(2); | |
196 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
197 | if (ON_BOARD(str)) { | |
198 | int attack_point = NO_MOVE; | |
199 | int defense_point = NO_MOVE; | |
200 | struct eyevalue no_eyes; | |
201 | set_eyevalue(&no_eyes, 0, 0, 0, 0); | |
202 | ||
203 | if (board[str] == EMPTY | |
204 | || dragon[str].origin != str) | |
205 | continue; | |
206 | ||
207 | /* Some dragons can be ignored but be extra careful with big dragons. */ | |
208 | if (crude_dragon_weakness(ALIVE, &no_eyes, 0, | |
209 | DRAGON2(str).moyo_territorial_value, | |
210 | DRAGON2(str).escape_route - 10) | |
211 | < 0.00001 + gg_max(0.12, 0.32 - 0.01*dragon[str].effective_size)) { | |
212 | DRAGON2(str).owl_status = UNCHECKED; | |
213 | DRAGON2(str).owl_attack_point = NO_MOVE; | |
214 | DRAGON2(str).owl_defense_point = NO_MOVE; | |
215 | } | |
216 | else { | |
217 | int acode = 0; | |
218 | int dcode = 0; | |
219 | int kworm = NO_MOVE; | |
220 | int owl_nodes_before = get_owl_node_counter(); | |
221 | start_timer(3); | |
222 | acode = owl_attack(str, &attack_point, | |
223 | &DRAGON2(str).owl_attack_certain, &kworm); | |
224 | DRAGON2(str).owl_attack_node_count | |
225 | = get_owl_node_counter() - owl_nodes_before; | |
226 | if (acode != 0) { | |
227 | DRAGON2(str).owl_attack_point = attack_point; | |
228 | DRAGON2(str).owl_attack_code = acode; | |
229 | DRAGON2(str).owl_attack_kworm = kworm; | |
230 | if (attack_point != NO_MOVE) { | |
231 | kworm = NO_MOVE; | |
232 | dcode = owl_defend(str, &defense_point, | |
233 | &DRAGON2(str).owl_defense_certain, &kworm); | |
234 | if (dcode != 0) { | |
235 | if (defense_point != NO_MOVE) { | |
236 | DRAGON2(str).owl_status = (acode == GAIN ? ALIVE : CRITICAL); | |
237 | DRAGON2(str).owl_defense_point = defense_point; | |
238 | DRAGON2(str).owl_defense_code = dcode; | |
239 | DRAGON2(str).owl_defense_kworm = kworm; | |
240 | } | |
241 | else { | |
242 | /* Due to irregularities in the owl code, it may | |
243 | * occasionally happen that a dragon is found to be | |
244 | * attackable but also alive as it stands. In this case | |
245 | * we still choose to say that the owl_status is | |
246 | * CRITICAL, although we don't have any defense move to | |
247 | * propose. Having the status right is important e.g. | |
248 | * for connection moves to be properly valued. | |
249 | */ | |
250 | DRAGON2(str).owl_status = (acode == GAIN ? ALIVE : CRITICAL); | |
251 | DEBUG(DEBUG_OWL_PERFORMANCE, | |
252 | "Inconsistent owl attack and defense results for %1m.\n", | |
253 | str); | |
254 | /* Let's see whether the attacking move might be the right | |
255 | * defense: | |
256 | */ | |
257 | dcode = owl_does_defend(DRAGON2(str).owl_attack_point, | |
258 | str, NULL); | |
259 | if (dcode != 0) { | |
260 | DRAGON2(str).owl_defense_point | |
261 | = DRAGON2(str).owl_attack_point; | |
262 | DRAGON2(str).owl_defense_code = dcode; | |
263 | } | |
264 | } | |
265 | } | |
266 | } | |
267 | if (dcode == 0) { | |
268 | DRAGON2(str).owl_status = DEAD; | |
269 | DRAGON2(str).owl_defense_point = NO_MOVE; | |
270 | DRAGON2(str).owl_defense_code = 0; | |
271 | } | |
272 | } | |
273 | else { | |
274 | if (!DRAGON2(str).owl_attack_certain) { | |
275 | kworm = NO_MOVE; | |
276 | dcode = owl_defend(str, &defense_point, | |
277 | &DRAGON2(str).owl_defense_certain, &kworm); | |
278 | if (dcode != 0) { | |
279 | /* If the result of owl_attack was not certain, we may | |
280 | * still want the result of owl_defend */ | |
281 | DRAGON2(str).owl_defense_point = defense_point; | |
282 | DRAGON2(str).owl_defense_code = dcode; | |
283 | DRAGON2(str).owl_defense_kworm = kworm; | |
284 | } | |
285 | } | |
286 | DRAGON2(str).owl_status = ALIVE; | |
287 | DRAGON2(str).owl_attack_point = NO_MOVE; | |
288 | DRAGON2(str).owl_attack_code = 0; | |
289 | ||
290 | } | |
291 | } | |
292 | } | |
293 | time_report(2, " owl reading", NO_MOVE, 1.0); | |
294 | ||
295 | /* Compute the status to be used by the matcher. We most trust the | |
296 | * owl status, if it is available. If it's not we assume that we are | |
297 | * already confident that the dragon is alive, regardless of | |
298 | * crude_status. | |
299 | */ | |
300 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
301 | if (IS_STONE(board[str])) { | |
302 | if (DRAGON2(str).owl_status != UNCHECKED) | |
303 | dragon[str].status = DRAGON2(str).owl_status; | |
304 | else | |
305 | dragon[str].status = ALIVE; | |
306 | } | |
307 | ||
308 | /* The dragon data is now correct at the origin of each dragon but | |
309 | * we need to copy it to every vertex. | |
310 | */ | |
311 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
312 | if (ON_BOARD(str) && board[str] != EMPTY) | |
313 | dragon[str] = dragon[dragon[str].origin]; | |
314 | ||
315 | identify_thrashing_dragons(); | |
316 | ||
317 | /* Owl threats. */ | |
318 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
319 | if (ON_BOARD(str) | |
320 | && board[str] != EMPTY | |
321 | && dragon[str].origin == str) { | |
322 | struct eyevalue no_eyes; | |
323 | set_eyevalue(&no_eyes, 0, 0, 0, 0); | |
324 | if (crude_dragon_weakness(ALIVE, &no_eyes, 0, | |
325 | DRAGON2(str).moyo_territorial_value, | |
326 | DRAGON2(str).escape_route - 10) | |
327 | < 0.00001 + gg_max(0.12, 0.32 - 0.01*dragon[str].effective_size)) { | |
328 | DRAGON2(str).owl_threat_status = UNCHECKED; | |
329 | DRAGON2(str).owl_second_attack_point = NO_MOVE; | |
330 | DRAGON2(str).owl_second_defense_point = NO_MOVE; | |
331 | } | |
332 | else { | |
333 | int acode = DRAGON2(str).owl_attack_code; | |
334 | int dcode = DRAGON2(str).owl_defense_code; | |
335 | int defense_point, second_defense_point; | |
336 | ||
337 | if (get_level() >= 8 | |
338 | && !disable_threat_computation | |
339 | && (owl_threats | |
340 | || thrashing_stone[str])) { | |
341 | if (acode && !dcode && DRAGON2(str).owl_attack_point != NO_MOVE) { | |
342 | if (owl_threaten_defense(str, &defense_point, | |
343 | &second_defense_point)) { | |
344 | DRAGON2(str).owl_threat_status = CAN_THREATEN_DEFENSE; | |
345 | DRAGON2(str).owl_defense_point = defense_point; | |
346 | DRAGON2(str).owl_second_defense_point = second_defense_point; | |
347 | } | |
348 | else | |
349 | DRAGON2(str).owl_threat_status = DEAD; | |
350 | } | |
351 | else if (!acode) { | |
352 | int attack_point, second_attack_point; | |
353 | if (owl_threaten_attack(str, | |
354 | &attack_point, &second_attack_point)) { | |
355 | DRAGON2(str).owl_threat_status = CAN_THREATEN_ATTACK; | |
356 | DRAGON2(str).owl_attack_point = attack_point; | |
357 | DRAGON2(str).owl_second_attack_point = second_attack_point; | |
358 | } | |
359 | else | |
360 | DRAGON2(str).owl_threat_status = ALIVE; | |
361 | } | |
362 | } | |
363 | } | |
364 | } | |
365 | ||
366 | /* Once again, the dragon data is now correct at the origin of each dragon | |
367 | * but we need to copy it to every vertex. | |
368 | */ | |
369 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
370 | if (ON_BOARD(str) && board[str] != EMPTY) | |
371 | dragon[str] = dragon[dragon[str].origin]; | |
372 | ||
373 | time_report(2, " owl threats ", NO_MOVE, 1.0); | |
374 | ||
375 | ||
376 | /* Compute the safety value. */ | |
377 | for (d = 0; d < number_of_dragons; d++) { | |
378 | int true_genus; | |
379 | int origin = dragon2[d].origin; | |
380 | struct eyevalue *genus = &dragon2[d].genus; | |
381 | ||
382 | /* FIXME: We lose information when constructing true_genus. This | |
383 | * code can be improved. | |
384 | */ | |
385 | true_genus = max_eyes(genus) + min_eyes(genus); | |
386 | if (dragon_looks_inessential(origin)) | |
387 | dragon2[d].safety = INESSENTIAL; | |
388 | else if (dragon[origin].size == worm[origin].size | |
389 | && worm[origin].attack_codes[0] != 0 | |
390 | && worm[origin].defense_codes[0] == 0) | |
391 | dragon2[d].safety = TACTICALLY_DEAD; | |
392 | else if (0) /* Seki is detected by the call to semeai() below. */ | |
393 | dragon2[d].safety = ALIVE_IN_SEKI; | |
394 | else if (dragon_invincible(origin)) { | |
395 | dragon2[d].safety = INVINCIBLE; | |
396 | /* Sometimes the owl analysis may have misevaluated invincible | |
397 | * dragons, typically if they live by topologically false eyes. | |
398 | * Therefore we also set the status here. | |
399 | */ | |
400 | DRAGON(d).status = ALIVE; | |
401 | } | |
402 | else if (dragon2[d].owl_status == DEAD) | |
403 | dragon2[d].safety = DEAD; | |
404 | else if (dragon2[d].owl_status == CRITICAL) | |
405 | dragon2[d].safety = CRITICAL; | |
406 | else if (true_genus >= 6 || dragon2[d].moyo_size > 20) | |
407 | dragon2[d].safety = STRONGLY_ALIVE; | |
408 | else | |
409 | dragon2[d].safety = ALIVE; | |
410 | } | |
411 | ||
412 | /* The status is now correct at the origin of each dragon | |
413 | * but we need to copy it to every vertex. | |
414 | */ | |
415 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
416 | if (ON_BOARD(str)) | |
417 | dragon[str].status = dragon[dragon[str].origin].status; | |
418 | ||
419 | /* Revise inessentiality of critical worms and dragons. */ | |
420 | revise_inessentiality(); | |
421 | ||
422 | semeai(); | |
423 | time_report(2, " semeai module", NO_MOVE, 1.0); | |
424 | ||
425 | /* Count the non-dead dragons. */ | |
426 | lively_white_dragons = 0; | |
427 | lively_black_dragons = 0; | |
428 | for (d = 0; d < number_of_dragons; d++) | |
429 | if (DRAGON(d).status != DEAD) { | |
430 | if (DRAGON(d).color == WHITE) | |
431 | lively_white_dragons++; | |
432 | else | |
433 | lively_black_dragons++; | |
434 | } | |
435 | } | |
436 | ||
437 | ||
438 | /* Find capturable worms adjacent to each dragon. */ | |
439 | static void | |
440 | find_lunches() | |
441 | { | |
442 | int str; | |
443 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
444 | if (ON_BOARD(str)) { | |
445 | int food; | |
446 | ||
447 | if (worm[str].origin != str | |
448 | || board[str] == EMPTY | |
449 | || worm[str].lunch == NO_MOVE) | |
450 | continue; | |
451 | ||
452 | food = worm[str].lunch; | |
453 | ||
454 | /* In contrast to worm lunches, a dragon lunch must also be | |
455 | * able to defend itself. | |
456 | */ | |
457 | if (worm[food].defense_codes[0] == 0) | |
458 | continue; | |
459 | ||
460 | /* Tell the move generation code about the lunch. */ | |
461 | add_lunch(str, food); | |
462 | ||
463 | /* If several lunches are found, we pick the juiciest. | |
464 | * First maximize cutstone, then minimize liberties. | |
465 | */ | |
466 | { | |
467 | int origin = dragon[str].origin; | |
468 | int lunch = DRAGON2(origin).lunch; | |
469 | ||
470 | if (lunch == NO_MOVE | |
471 | || worm[food].cutstone > worm[lunch].cutstone | |
472 | || (worm[food].cutstone == worm[lunch].cutstone | |
473 | && (worm[food].liberties < worm[lunch].liberties))) { | |
474 | DRAGON2(origin).lunch = worm[food].origin; | |
475 | TRACE("at %1m setting %1m.lunch to %1m (cutstone=%d)\n", | |
476 | str, origin, | |
477 | worm[food].origin, worm[food].cutstone); | |
478 | } | |
479 | } | |
480 | } | |
481 | } | |
482 | ||
483 | ||
484 | /* Compute the value of each eye space. Store its attack and defense point. | |
485 | * A more comlete list of attack and defense points is stored in the lists | |
486 | * black_vital_points and white_vital_points. | |
487 | */ | |
488 | static void | |
489 | eye_computations() | |
490 | { | |
491 | int str; | |
492 | ||
493 | for (str = BOARDMIN; str < BOARDMAX; str++) { | |
494 | if (!ON_BOARD(str)) | |
495 | continue; | |
496 | ||
497 | if (black_eye[str].color == BLACK | |
498 | && black_eye[str].origin == str) { | |
499 | struct eyevalue value; | |
500 | int attack_point, defense_point; | |
501 | ||
502 | compute_eyes(str, &value, &attack_point, &defense_point, | |
503 | black_eye, half_eye, 1); | |
504 | DEBUG(DEBUG_EYES, "Black eyespace at %1m: %s\n", str, | |
505 | eyevalue_to_string(&value)); | |
506 | black_eye[str].value = value; | |
507 | propagate_eye(str, black_eye); | |
508 | } | |
509 | ||
510 | if (white_eye[str].color == WHITE | |
511 | && white_eye[str].origin == str) { | |
512 | struct eyevalue value; | |
513 | int attack_point, defense_point; | |
514 | ||
515 | compute_eyes(str, &value, &attack_point, &defense_point, | |
516 | white_eye, half_eye, 1); | |
517 | DEBUG(DEBUG_EYES, "White eyespace at %1m: %s\n", str, | |
518 | eyevalue_to_string(&value)); | |
519 | white_eye[str].value = value; | |
520 | propagate_eye(str, white_eye); | |
521 | } | |
522 | } | |
523 | } | |
524 | ||
525 | ||
526 | /* This function revises the inessentiality of critical worms and dragons | |
527 | * according to the criteria explained in the comments below. | |
528 | */ | |
529 | static void | |
530 | revise_inessentiality() | |
531 | { | |
532 | int str; | |
533 | /* Revise essentiality of critical worms. Specifically, a critical | |
534 | * worm which is adjacent to no enemy dragon with status | |
535 | * better than DEAD, is considered INESSENTIAL. | |
536 | * | |
537 | * A typical case of this is | |
538 | * | |
539 | * |.XXXX | |
540 | * |.OO.X | |
541 | * |X.O.X | |
542 | * |.OO.X | |
543 | * +----- | |
544 | * | |
545 | * However, to be able to deal with the position | |
546 | * | |
547 | * |.XXXX | |
548 | * |.OOOO | |
549 | * |..O.O | |
550 | * |X.OOO | |
551 | * |..O.O | |
552 | * +----- | |
553 | * | |
554 | * we need to extend "adjacent" to "adjacent or shares a liberty", | |
555 | * which is why we use extended_chainlinks() rather than | |
556 | * chainlinks(). | |
557 | * | |
558 | * Finally, if the position above is slightly modified to | |
559 | * | |
560 | * |.XXXXX | |
561 | * |.OOOOO | |
562 | * |...O.O | |
563 | * |X..OOO | |
564 | * |...O.O | |
565 | * +------ | |
566 | * | |
567 | * we have a position where the critical X stone doesn't share a | |
568 | * liberty with any string at all. Thus the revised rule is: | |
569 | * | |
570 | * A critical worm which is adjacent to or share a liberty with at | |
571 | * least one dead opponent dragon and no opponent dragon which is | |
572 | * not dead, is considered inessential. | |
573 | */ | |
574 | ||
575 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
576 | if (ON_BOARD(str)) { | |
577 | if (is_worm_origin(str, str) | |
578 | && worm[str].attack_codes[0] != 0 | |
579 | && worm[str].defense_codes[0] != 0 | |
580 | && !worm[str].inessential) { | |
581 | int adjs[MAXCHAIN]; | |
582 | int neighbors; | |
583 | int r; | |
584 | int essential = 0; | |
585 | ||
586 | neighbors = extended_chainlinks(str, adjs, 0); | |
587 | for (r = 0; r < neighbors; r++) | |
588 | if (dragon[adjs[r]].status != DEAD) { | |
589 | essential = 1; | |
590 | break; | |
591 | } | |
592 | ||
593 | if (!essential && neighbors > 0) { | |
594 | DEBUG(DEBUG_WORMS, "Worm %1m revised to be inessential.\n", str); | |
595 | worm[str].inessential = 1; | |
596 | propagate_worm(str); | |
597 | } | |
598 | } | |
599 | } | |
600 | ||
601 | /* Revise essentiality of critical dragons. Specifically, a critical | |
602 | * dragon consisting entirely of inessential worms is considered | |
603 | * INESSENTIAL. | |
604 | */ | |
605 | for (str = BOARDMIN; str < BOARDMAX; str++) { | |
606 | if (ON_BOARD(str) | |
607 | && board[str] != EMPTY | |
608 | && dragon[str].origin == str | |
609 | && DRAGON2(str).safety == CRITICAL) { | |
610 | int w; | |
611 | for (w = first_worm_in_dragon(str); w != NO_MOVE; | |
612 | w = next_worm_in_dragon(w)) { | |
613 | if (!worm[w].inessential) | |
614 | break; | |
615 | } | |
616 | ||
617 | if (w == NO_MOVE) { | |
618 | DEBUG(DEBUG_DRAGONS, "Dragon %1m revised to be inessential.\n", str); | |
619 | DRAGON2(str).safety = INESSENTIAL; | |
620 | } | |
621 | } | |
622 | } | |
623 | } | |
624 | ||
625 | /* Initialize the dragon[] array. */ | |
626 | ||
627 | void | |
628 | initialize_dragon_data(void) | |
629 | { | |
630 | int str; | |
631 | /* VALGRIND_MAKE_WRITABLE(dragon, BOARDMAX * sizeof(struct dragon_data)); */ | |
632 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
633 | if (ON_BOARD(str)) { | |
634 | ||
635 | dragon[str].id = -1; | |
636 | dragon[str].size = worm[str].size; | |
637 | dragon[str].effective_size = worm[str].effective_size; | |
638 | dragon[str].color = worm[str].color; | |
639 | dragon[str].origin = worm[str].origin; | |
640 | dragon[str].crude_status = UNKNOWN; | |
641 | dragon[str].status = UNKNOWN; | |
642 | half_eye[str].type = 0; | |
643 | half_eye[str].value = 10.0; /* Something big. */ | |
644 | ||
645 | if (IS_STONE(board[str]) && worm[str].origin == str) | |
646 | DEBUG(DEBUG_DRAGONS, | |
647 | "Initializing dragon from worm at %1m, size %d\n", | |
648 | str, worm[str].size); | |
649 | } | |
650 | memset(next_worm_list, 0, sizeof(next_worm_list)); | |
651 | ||
652 | /* We need to reset this to avoid trouble on an empty board when | |
653 | * moves have previously been generated for a non-empty board. | |
654 | * | |
655 | * Comment: The cause of this is that make_dragons() is not called | |
656 | * for an empty board, only initialize_dragon_data(), so we never | |
657 | * reach initialize_supplementary_dragon_data(). | |
658 | */ | |
659 | number_of_dragons = 0; | |
660 | ||
661 | clear_cut_list(); | |
662 | ||
663 | memset(black_vital_points, 0, BOARDMAX * sizeof(struct vital_eye_points)); | |
664 | memset(white_vital_points, 0, BOARDMAX * sizeof(struct vital_eye_points)); | |
665 | } | |
666 | ||
667 | ||
668 | /* Initialize the dragon2[] array. */ | |
669 | static void | |
670 | initialize_supplementary_dragon_data(void) | |
671 | { | |
672 | int str; | |
673 | int d; | |
674 | int origin; | |
675 | ||
676 | /* Give each dragon (caves excluded) an id number for indexing into | |
677 | * the dragon2 array. After this the DRAGON2 macro can be used. | |
678 | */ | |
679 | number_of_dragons = 0; | |
680 | for (str = BOARDMIN; str < BOARDMAX; str++) { | |
681 | if (!ON_BOARD(str)) | |
682 | continue; | |
683 | origin = dragon[str].origin; | |
684 | ||
685 | if (board[str] == EMPTY) | |
686 | continue; | |
687 | ||
688 | if (dragon[origin].id == -1) | |
689 | dragon[origin].id = number_of_dragons++; | |
690 | dragon[str].id = dragon[origin].id; | |
691 | } | |
692 | ||
693 | /* Now number_of_dragons contains the number of dragons and we can | |
694 | * allocate a dragon2 array of the appropriate size. First throw | |
695 | * away the old array. | |
696 | * | |
697 | * FIXME: As a future optimization we should only allocate a new | |
698 | * array if the old one is too small. | |
699 | */ | |
700 | if (dragon2 != NULL) | |
701 | free(dragon2); | |
702 | ||
703 | dragon2 = malloc(number_of_dragons * sizeof(*dragon2)); | |
704 | gg_assert(dragon2 != NULL); | |
705 | ||
706 | /* Find the origins of the dragons to establish the mapping back to | |
707 | * the board. After this the DRAGON macro can be used. | |
708 | */ | |
709 | for (str = BOARDMIN; str < BOARDMAX; str++) { | |
710 | if (!ON_BOARD(str)) | |
711 | continue; | |
712 | if (IS_STONE(board[str]) | |
713 | && dragon[str].origin == str) { | |
714 | DRAGON2(str).origin = str; | |
715 | } | |
716 | } | |
717 | ||
718 | /* Initialize the rest of the dragon2 data. */ | |
719 | for (d = 0; d < number_of_dragons; d++) { | |
720 | dragon2[d].neighbors = 0; | |
721 | dragon2[d].hostile_neighbors = 0; | |
722 | ||
723 | dragon2[d].moyo_size = -1; | |
724 | dragon2[d].moyo_territorial_value = 0.0; | |
725 | dragon2[d].safety = -1; | |
726 | dragon2[d].escape_route = 0; | |
727 | dragon2[d].heye = NO_MOVE; | |
728 | dragon2[d].lunch = NO_MOVE; | |
729 | dragon2[d].surround_status = 0; | |
730 | set_eyevalue(&dragon2[d].genus, 0, 0, 0, 0); | |
731 | ||
732 | dragon2[d].semeais = 0; | |
733 | dragon2[d].semeai_defense_code = 0; | |
734 | dragon2[d].semeai_defense_point = NO_MOVE; | |
735 | dragon2[d].semeai_attack_code = 0; | |
736 | dragon2[d].semeai_attack_point = NO_MOVE; | |
737 | dragon2[d].owl_attack_point = NO_MOVE; | |
738 | dragon2[d].owl_attack_code = 0; | |
739 | dragon2[d].owl_attack_certain = 1; | |
740 | dragon2[d].owl_defense_point = NO_MOVE; | |
741 | dragon2[d].owl_defense_code = 0; | |
742 | dragon2[d].owl_defense_certain = 1; | |
743 | dragon2[d].owl_status = UNCHECKED; | |
744 | dragon2[d].owl_threat_status = UNCHECKED; | |
745 | dragon2[d].owl_second_attack_point = NO_MOVE; | |
746 | dragon2[d].owl_second_defense_point = NO_MOVE; | |
747 | } | |
748 | ||
749 | dragon2_initialized = 1; | |
750 | } | |
751 | ||
752 | ||
753 | /* Examine which dragons are adjacent to each other. This is | |
754 | * complicated by the fact that adjacency may involve a certain | |
755 | * amount of empty space. | |
756 | * | |
757 | * The approach we use is to extend the dragons into their | |
758 | * surrounding influence areas until they collide. We also accept | |
759 | * one step extensions into neutral regions. After having done this | |
760 | * we can look for immediate adjacencies. | |
761 | */ | |
762 | static void | |
763 | find_neighbor_dragons() | |
764 | { | |
765 | int m, n; | |
766 | int pos; | |
767 | int pos2; | |
768 | int i, j; | |
769 | int d; | |
770 | int dragons[BOARDMAX]; | |
771 | int distances[BOARDMAX]; | |
772 | int dist; | |
773 | int k; | |
774 | int color; | |
775 | ||
776 | gg_assert(dragon2_initialized); | |
777 | ||
778 | /* Initialize the arrays. */ | |
779 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
780 | if (IS_STONE(board[pos])) { | |
781 | dragons[pos] = dragon[pos].id; | |
782 | distances[pos] = 0; | |
783 | } | |
784 | else if (ON_BOARD(pos)) { | |
785 | dragons[pos] = -1; | |
786 | distances[pos] = -1; | |
787 | } | |
788 | } | |
789 | ||
790 | /* Expand from dist-1 to dist. Break out of the loop at the end if | |
791 | * we couldn't expand anything. Never expand more than five steps. | |
792 | */ | |
793 | for (dist = 1; dist <= 5; dist++) { | |
794 | int found_one = 0; | |
795 | ||
796 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
797 | if (!ON_BOARD(pos)) | |
798 | continue; | |
799 | ||
800 | if (distances[pos] != dist-1 || dragons[pos] < 0) | |
801 | continue; | |
802 | ||
803 | color = DRAGON(dragons[pos]).color; | |
804 | for (k = 0; k < 4; k++) { | |
805 | pos2 = pos + delta[k]; | |
806 | ||
807 | if (!ON_BOARD1(pos2)) | |
808 | continue; | |
809 | ||
810 | /* Consider expansion from (pos) to adjacent intersection | |
811 | * (pos2). | |
812 | */ | |
813 | if (distances[pos2] >= 0 && distances[pos2] < dist) | |
814 | continue; /* (pos2) already occupied. */ | |
815 | ||
816 | /* We can always expand the first step, regardless of influence. */ | |
817 | if (dist == 1 | |
818 | || (whose_area(INITIAL_INFLUENCE(color), pos) == color | |
819 | && whose_area(INITIAL_INFLUENCE(color), pos2) | |
820 | != OTHER_COLOR(color))) { | |
821 | /* Expansion ok. Now see if someone else has tried to | |
822 | * expand here. In that case we indicate a collision by | |
823 | * setting the dragon number to -2. | |
824 | */ | |
825 | if (distances[pos2] == dist) { | |
826 | if (dragons[pos2] != dragons[pos]) | |
827 | dragons[pos2] = -2; | |
828 | } | |
829 | else { | |
830 | dragons[pos2] = dragons[pos]; | |
831 | distances[pos2] = dist; | |
832 | found_one = 1; | |
833 | } | |
834 | } | |
835 | } | |
836 | } | |
837 | if (!found_one) | |
838 | break; | |
839 | } | |
840 | ||
841 | if (0) { | |
842 | for (m = 0; m < board_size; m++) { | |
843 | for (n = 0; n < board_size; n++) | |
844 | fprintf(stderr, "%3d", dragons[POS(m, n)]); | |
845 | fprintf(stderr, "\n"); | |
846 | } | |
847 | fprintf(stderr, "\n"); | |
848 | ||
849 | for (m = 0; m < board_size; m++) { | |
850 | for (n = 0; n < board_size; n++) | |
851 | fprintf(stderr, "%3d", distances[POS(m, n)]); | |
852 | fprintf(stderr, "\n"); | |
853 | } | |
854 | fprintf(stderr, "\n"); | |
855 | } | |
856 | ||
857 | /* Now go through dragons to find neighbors. It suffices to look | |
858 | * south and east for neighbors. In the case of a collision zone | |
859 | * where dragons==-2 we set all the neighbors of this intersection | |
860 | * as adjacent to each other. | |
861 | */ | |
862 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
863 | if (!ON_BOARD(pos)) | |
864 | continue; | |
865 | if (dragons[pos] == -2) { | |
866 | int neighbors = 0; | |
867 | int adjacent[4]; | |
868 | ||
869 | for (k = 0; k < 4; k++) { | |
870 | pos2 = pos + delta[k]; | |
871 | ||
872 | if (ON_BOARD1(pos2) && dragons[pos2] >= 0) | |
873 | adjacent[neighbors++] = dragons[pos2]; | |
874 | } | |
875 | for (i = 0; i < neighbors; i++) | |
876 | for (j = i+1; j < neighbors; j++) | |
877 | add_adjacent_dragons(adjacent[i], adjacent[j]); | |
878 | } | |
879 | else if (dragons[pos] >= 0) { | |
880 | if (ON_BOARD(NORTH(pos))) { | |
881 | if (dragons[NORTH(pos)] >= 0 | |
882 | && dragons[NORTH(pos)] != dragons[pos]) | |
883 | add_adjacent_dragons(dragons[pos], dragons[NORTH(pos)]); | |
884 | } | |
885 | if (ON_BOARD(EAST(pos))) { | |
886 | if (dragons[EAST(pos)] >= 0 | |
887 | && dragons[EAST(pos)] != dragons[pos]) | |
888 | add_adjacent_dragons(dragons[pos], dragons[EAST(pos)]); | |
889 | } | |
890 | } | |
891 | } | |
892 | ||
893 | if (0) { | |
894 | for (d = 0; d < number_of_dragons; d++) { | |
895 | gprintf("dragon %d at %1m:", d, dragon2[d].origin); | |
896 | for (i = 0; i < dragon2[d].neighbors; i++) | |
897 | gprintf(" %1m(%d)", dragon2[dragon2[d].adjacent[i]].origin, | |
898 | dragon2[d].adjacent[i]); | |
899 | gprintf("\n"); | |
900 | } | |
901 | } | |
902 | } | |
903 | ||
904 | /* Add the dragons with id a and b as adjacent to each other. */ | |
905 | static void | |
906 | add_adjacent_dragons(int a, int b) | |
907 | { | |
908 | gg_assert(a >= 0 && a < number_of_dragons | |
909 | && b >= 0 && b < number_of_dragons); | |
910 | if (a == b) | |
911 | return; | |
912 | add_adjacent_dragon(a, b); | |
913 | add_adjacent_dragon(b, a); | |
914 | } | |
915 | ||
916 | /* Add the dragon with id b as adjacent to a. */ | |
917 | static void | |
918 | add_adjacent_dragon(int a, int b) | |
919 | { | |
920 | int i; | |
921 | gg_assert(a >= 0 && a < number_of_dragons | |
922 | && b >= 0 && b < number_of_dragons); | |
923 | /* If the array of adjacent dragons already is full, ignore | |
924 | * additional neighbors. | |
925 | */ | |
926 | if (dragon2[a].neighbors == MAX_NEIGHBOR_DRAGONS) | |
927 | return; | |
928 | ||
929 | for (i = 0; i < dragon2[a].neighbors; i++) | |
930 | if (dragon2[a].adjacent[i] == b) | |
931 | return; | |
932 | ||
933 | dragon2[a].adjacent[dragon2[a].neighbors++] = b; | |
934 | ||
935 | if (DRAGON(a).color == OTHER_COLOR(DRAGON(b).color)) | |
936 | dragon2[a].hostile_neighbors++; | |
937 | } | |
938 | ||
939 | /* A dragon is considered invincible if it satisfies either of the two | |
940 | * following conditions: | |
941 | * a) At least two distinct eyespaces without topological halfeyes, | |
942 | * marginal vertices, or tactically critical or alive opponent strings. | |
943 | * Furthermore there may not be an owl attack of the dragon. | |
944 | * b) At least one string which is unconditionally alive according to the | |
945 | * unconditional_life() function in utils.c. | |
946 | * | |
947 | * For the requirement on opponent strings in a), see e.g. | |
948 | * seki:404,408,409,413,504,604,908. | |
949 | */ | |
950 | ||
951 | static int | |
952 | dragon_invincible(int dr) | |
953 | { | |
954 | struct eye_data *eye; | |
955 | int eye_color; | |
956 | int k; | |
957 | int pos; | |
958 | int strong_eyes = 0; | |
959 | int mx[BOARDMAX]; | |
960 | ||
961 | ASSERT1(IS_STONE(board[dr]), dr); | |
962 | ||
963 | /* First look for invincible strings in the dragon. */ | |
964 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
965 | if (ON_BOARD(pos) && is_same_dragon(pos, dr) && worm[pos].invincible) | |
966 | return 1; | |
967 | } | |
968 | ||
969 | /* Can the dragon be owl attacked? */ | |
970 | if (DRAGON2(dr).owl_status != UNCHECKED && DRAGON2(dr).owl_status != ALIVE) | |
971 | return 0; | |
972 | ||
973 | /* Examine the eye spaces. */ | |
974 | if (board[dr] == BLACK) { | |
975 | eye = black_eye; | |
976 | eye_color = BLACK; | |
977 | } | |
978 | else { | |
979 | eye = white_eye; | |
980 | eye_color = WHITE; | |
981 | } | |
982 | ||
983 | memset(mx, 0, sizeof(mx)); | |
984 | ||
985 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
986 | if (board[pos] == board[dr] && is_same_dragon(pos, dr)) { | |
987 | for (k = 0; k < 4; k++) { | |
988 | int pos2 = pos + delta[k]; | |
989 | if (ON_BOARD(pos2) | |
990 | && eye[pos2].color == eye_color | |
991 | && eye[pos2].origin != NO_MOVE) { | |
992 | if (eye[pos2].marginal | |
993 | || is_halfeye(half_eye, pos2)) | |
994 | mx[eye[pos2].origin] = 2; /* bad eye */ | |
995 | else if (mx[eye[pos2].origin] == 0) | |
996 | mx[eye[pos2].origin] = 1; /* good eye */ | |
997 | ||
998 | if (board[pos2] == OTHER_COLOR(board[dr]) | |
999 | && (!attack(pos2, NULL) || find_defense(pos2, NULL))) | |
1000 | mx[eye[pos2].origin] = 2; /* bad eye */ | |
1001 | } | |
1002 | } | |
1003 | } | |
1004 | } | |
1005 | ||
1006 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1007 | /* Necessary to check eye margins here since the loop above only | |
1008 | * considers margins which are directly adjacent to some stone of | |
1009 | * the dragon. | |
1010 | */ | |
1011 | if (mx[pos] == 1 | |
1012 | && eye[pos].msize == 0) | |
1013 | strong_eyes++; | |
1014 | } | |
1015 | ||
1016 | if (strong_eyes >= 2) | |
1017 | return 1; | |
1018 | ||
1019 | return 0; | |
1020 | } | |
1021 | ||
1022 | ||
1023 | /* A dragon looks inessential if it satisfies all of | |
1024 | * 1. Is a single string. | |
1025 | * 2. Is not owl substantial. | |
1026 | * | |
1027 | * FIXME: Probably need a better definition of INESSENTIAL dragons. | |
1028 | * There are cases where a string is owl insubstantial | |
1029 | * yet allowing it to be captured greatly weakens our | |
1030 | * position. | |
1031 | */ | |
1032 | static int | |
1033 | dragon_looks_inessential(int origin) | |
1034 | { | |
1035 | #if 0 | |
1036 | int d; | |
1037 | int k; | |
1038 | #endif | |
1039 | ||
1040 | if (dragon[origin].size != worm[origin].size) | |
1041 | return 0; | |
1042 | ||
1043 | if (owl_substantial(origin)) | |
1044 | return 0; | |
1045 | ||
1046 | #if 0 | |
1047 | /* This is a proposed modification which solves 13x13:72 but | |
1048 | * breaks buzco:5. It adds the two requirements: | |
1049 | * | |
1050 | * 3. Has no opponent neighbor with status better than DEAD. | |
1051 | * 4. Has no opponent neighbor with escape value bigger than 0. | |
1052 | * | |
1053 | * This probably needs to be revised before it's enabled. | |
1054 | */ | |
1055 | for (k = 0; k < DRAGON2(origin).neighbors; k++) { | |
1056 | d = DRAGON2(origin).adjacent[k]; | |
1057 | if (DRAGON(d).color != board[origin] | |
1058 | && (DRAGON(d).status != DEAD | |
1059 | || dragon2[d].escape_route > 0)) | |
1060 | return 0; | |
1061 | } | |
1062 | #endif | |
1063 | ||
1064 | return 1; | |
1065 | } | |
1066 | ||
1067 | ||
1068 | /* Report which stones are alive if it's (color)'s turn to move. I.e. | |
1069 | * critical stones belonging to (color) are considered alive. | |
1070 | * A stone is dead resp. critical if the tactical reading code _or_ the | |
1071 | * owl code thinks so. | |
1072 | */ | |
1073 | static void | |
1074 | get_alive_stones(int color, signed char safe_stones[BOARDMAX]) | |
1075 | { | |
1076 | int d; | |
1077 | get_lively_stones(color, safe_stones); | |
1078 | for (d = 0; d < number_of_dragons; d++) { | |
1079 | if (dragon2[d].safety == DEAD | |
1080 | || (dragon2[d].safety == CRITICAL | |
1081 | && board[dragon2[d].origin] == OTHER_COLOR(color))) { | |
1082 | mark_dragon(dragon2[d].origin, safe_stones, 0); | |
1083 | } | |
1084 | } | |
1085 | } | |
1086 | ||
1087 | ||
1088 | /* If the opponent's last move is a dead dragon, this is called a | |
1089 | * *thrashing dragon*. We must be careful because the opponent may be | |
1090 | * trying to trick us, so even though GNU Go thinks the stone is dead, | |
1091 | * we should consider attacking it, particularly if we are ahead. | |
1092 | * | |
1093 | * This function determines whether the last played move is part of a | |
1094 | * dead dragon. It also looks for dead friendly neighbors of the | |
1095 | * thrashing dragon, which are also considered as thrashing. The | |
1096 | * stones of the primary thrashing dragon are marked by 1 in the | |
1097 | * thrashing_stone[] array and its neighbors are marked by 2. | |
1098 | * Neighbors of neighbors are marked 3, and so on, up to at most | |
1099 | * distance 5. | |
1100 | */ | |
1101 | static void | |
1102 | identify_thrashing_dragons() | |
1103 | { | |
1104 | int k; | |
1105 | int dist; | |
1106 | int last_move; | |
1107 | int color; | |
1108 | ||
1109 | thrashing_dragon = 0; | |
1110 | memset(thrashing_stone, 0, sizeof(thrashing_stone)); | |
1111 | ||
1112 | last_move = get_last_move(); | |
1113 | if (last_move == NO_MOVE | |
1114 | || dragon[last_move].status != DEAD) | |
1115 | return; | |
1116 | ||
1117 | thrashing_dragon = dragon[last_move].origin; | |
1118 | DEBUG(DEBUG_DRAGONS, "thrashing dragon found at %1m\n", thrashing_dragon); | |
1119 | mark_dragon(thrashing_dragon, thrashing_stone, 1); | |
1120 | color = board[thrashing_dragon]; | |
1121 | ||
1122 | for (dist = 1; dist < 5; dist++) { | |
1123 | int pos; | |
1124 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1125 | if (board[pos] != color | |
1126 | || dragon[pos].origin != pos | |
1127 | || thrashing_stone[pos] != dist) | |
1128 | continue; | |
1129 | ||
1130 | for (k = 0; k < DRAGON2(pos).neighbors; k++) { | |
1131 | int d = DRAGON2(pos).adjacent[k]; | |
1132 | if (DRAGON(d).color == color | |
1133 | && DRAGON(d).status == DEAD | |
1134 | && thrashing_stone[dragon2[d].origin] == 0) { | |
1135 | DEBUG(DEBUG_DRAGONS, | |
1136 | "neighbor at distance %d of thrashing dragon found at %1m\n", | |
1137 | dist + 1, DRAGON(d).origin); | |
1138 | mark_dragon(DRAGON(d).origin, thrashing_stone, | |
1139 | (signed char)(dist + 1)); | |
1140 | } | |
1141 | } | |
1142 | } | |
1143 | } | |
1144 | } | |
1145 | ||
1146 | ||
1147 | static void | |
1148 | set_dragon_strengths(const signed char safe_stones[BOARDMAX], | |
1149 | float strength[BOARDMAX]) | |
1150 | { | |
1151 | int ii; | |
1152 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1153 | if (ON_BOARD(ii)) { | |
1154 | if (safe_stones[ii]) { | |
1155 | ASSERT1(IS_STONE(board[ii]), ii); | |
1156 | strength[ii] = DEFAULT_STRENGTH | |
1157 | * (1.0 - 0.3 * DRAGON2(ii).weakness_pre_owl); | |
1158 | } | |
1159 | else | |
1160 | strength[ii] = 0.0; | |
1161 | } | |
1162 | } | |
1163 | ||
1164 | /* Marks all inessential stones with INFLUENCE_SAFE_STONE, leaves | |
1165 | * everything else unchanged. | |
1166 | */ | |
1167 | void | |
1168 | mark_inessential_stones(int color, signed char safe_stones[BOARDMAX]) | |
1169 | { | |
1170 | int ii; | |
1171 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1172 | if (IS_STONE(board[ii]) | |
1173 | && (DRAGON2(ii).safety == INESSENTIAL | |
1174 | || (worm[ii].inessential | |
1175 | /* FIXME: Why is the check below needed? | |
1176 | * Why does it use .safety, not .status? /ab | |
1177 | */ | |
1178 | && ((DRAGON2(ii).safety != DEAD | |
1179 | && DRAGON2(ii).safety != TACTICALLY_DEAD | |
1180 | && DRAGON2(ii).safety != CRITICAL) | |
1181 | || (DRAGON2(ii).safety == CRITICAL | |
1182 | && board[ii] == color))))) | |
1183 | safe_stones[ii] = INFLUENCE_SAFE_STONE; | |
1184 | } | |
1185 | ||
1186 | void | |
1187 | set_strength_data(int color, signed char safe_stones[BOARDMAX], | |
1188 | float strength[BOARDMAX]) | |
1189 | { | |
1190 | gg_assert(IS_STONE(color) || color == EMPTY); | |
1191 | ||
1192 | get_alive_stones(color, safe_stones); | |
1193 | set_dragon_strengths(safe_stones, strength); | |
1194 | mark_inessential_stones(color, safe_stones); | |
1195 | } | |
1196 | ||
1197 | ||
1198 | void | |
1199 | compute_dragon_influence() | |
1200 | { | |
1201 | signed char safe_stones[BOARDMAX]; | |
1202 | float strength[BOARDMAX]; | |
1203 | ||
1204 | set_strength_data(BLACK, safe_stones, strength); | |
1205 | compute_influence(BLACK, safe_stones, strength, &initial_black_influence, | |
1206 | NO_MOVE, "initial black influence, dragons known"); | |
1207 | break_territories(BLACK, &initial_black_influence, 1, NO_MOVE); | |
1208 | ||
1209 | set_strength_data(WHITE, safe_stones, strength); | |
1210 | compute_influence(WHITE, safe_stones, strength, &initial_white_influence, | |
1211 | NO_MOVE, "initial white influence, dragons known"); | |
1212 | break_territories(WHITE, &initial_white_influence, 1, NO_MOVE); | |
1213 | } | |
1214 | ||
1215 | ||
1216 | /* Compute dragon's genus, possibly excluding one given eye. To | |
1217 | * compute full genus, just set `eye_to_exclude' to NO_MOVE. | |
1218 | */ | |
1219 | void | |
1220 | compute_dragon_genus(int d, struct eyevalue *genus, int eye_to_exclude) | |
1221 | { | |
1222 | int pos; | |
1223 | int dr; | |
1224 | ||
1225 | ASSERT1(IS_STONE(board[d]), d); | |
1226 | gg_assert(eye_to_exclude == NO_MOVE || ON_BOARD1(eye_to_exclude)); | |
1227 | ||
1228 | set_eyevalue(genus, 0, 0, 0, 0); | |
1229 | ||
1230 | if (board[d] == BLACK) { | |
1231 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1232 | if (!ON_BOARD(pos)) | |
1233 | continue; | |
1234 | ||
1235 | if (black_eye[pos].color == BLACK | |
1236 | && black_eye[pos].origin == pos | |
1237 | && (eye_to_exclude == NO_MOVE | |
1238 | || black_eye[eye_to_exclude].origin != pos) | |
1239 | && find_eye_dragons(pos, black_eye, BLACK, &dr, 1) == 1 | |
1240 | && is_same_dragon(dr, d)) { | |
1241 | TRACE("eye at %1m (%s) found for dragon at %1m--augmenting genus\n", | |
1242 | pos, eyevalue_to_string(&black_eye[pos].value), dr); | |
1243 | ||
1244 | if (eye_to_exclude == NO_MOVE | |
1245 | && (eye_move_urgency(&black_eye[pos].value) | |
1246 | > eye_move_urgency(genus))) | |
1247 | DRAGON2(d).heye = black_vital_points[pos].defense_points[0]; | |
1248 | ||
1249 | add_eyevalues(genus, &black_eye[pos].value, genus); | |
1250 | } | |
1251 | } | |
1252 | } | |
1253 | else { | |
1254 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1255 | if (!ON_BOARD(pos)) | |
1256 | continue; | |
1257 | ||
1258 | if (white_eye[pos].color == WHITE | |
1259 | && white_eye[pos].origin == pos | |
1260 | && (eye_to_exclude == NO_MOVE | |
1261 | || white_eye[eye_to_exclude].origin != pos) | |
1262 | && find_eye_dragons(pos, white_eye, WHITE, &dr, 1) == 1 | |
1263 | && is_same_dragon(dr, d)) { | |
1264 | TRACE("eye at %1m (%s) found for dragon at %1m--augmenting genus\n", | |
1265 | pos, eyevalue_to_string(&white_eye[pos].value), dr); | |
1266 | ||
1267 | if (eye_to_exclude == NO_MOVE | |
1268 | && (eye_move_urgency(&white_eye[pos].value) | |
1269 | > eye_move_urgency(genus))) | |
1270 | DRAGON2(d).heye = white_vital_points[pos].defense_points[0]; | |
1271 | ||
1272 | add_eyevalues(genus, &white_eye[pos].value, genus); | |
1273 | } | |
1274 | } | |
1275 | } | |
1276 | } | |
1277 | ||
1278 | ||
1279 | /* Try to determine whether topologically false and half eye points | |
1280 | * contribute to territory even if the eye doesn't solidify. The purpose | |
1281 | * is to be able to distinguish between, e.g., these positions: | |
1282 | * | |
1283 | * |.OOOOO |.OOOOO | |
1284 | * |.O.XXO |.O.OXO | |
1285 | * |OOX.XO |OOX.XO | |
1286 | * |O*XXXO and |O*XXXO | |
1287 | * |OX.XOO |OX.XOO | |
1288 | * |X.XOO. |X.XOO. | |
1289 | * |.XXO.. |.XXO.. | |
1290 | * +------ +------ | |
1291 | * | |
1292 | * In the left one the move at * is a pure dame point while in the | |
1293 | * right one it is worth one point of territory for either player. | |
1294 | * | |
1295 | * In general the question is whether a topologically false eye vertex | |
1296 | * counts as territory or not and the answer depends on whether each | |
1297 | * string adjoining the eye is externally connected to at least one | |
1298 | * proper eye. | |
1299 | * | |
1300 | * This function loops over the topologically false and half eye | |
1301 | * vertices and calls connected_to_eye() for each adjoining string to | |
1302 | * determine whether they all have external connection to an eye. The | |
1303 | * result is stored in the false_eye_territory[] array. | |
1304 | */ | |
1305 | static void | |
1306 | analyze_false_eye_territory(void) | |
1307 | { | |
1308 | int pos; | |
1309 | int color; | |
1310 | int eye_color; | |
1311 | struct eye_data *eye; | |
1312 | int k; | |
1313 | ||
1314 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1315 | if (!ON_BOARD(pos)) | |
1316 | continue; | |
1317 | ||
1318 | false_eye_territory[pos] = 0; | |
1319 | ||
1320 | /* The analysis only applies to false and half eyes. */ | |
1321 | if (half_eye[pos].type == 0) | |
1322 | continue; | |
1323 | ||
1324 | /* Determine the color of the eye. */ | |
1325 | if (white_eye[pos].color == WHITE) { | |
1326 | color = WHITE; | |
1327 | eye_color = WHITE; | |
1328 | eye = white_eye; | |
1329 | } | |
1330 | else if (black_eye[pos].color == BLACK) { | |
1331 | color = BLACK; | |
1332 | eye_color = BLACK; | |
1333 | eye = black_eye; | |
1334 | } | |
1335 | else | |
1336 | continue; | |
1337 | ||
1338 | /* Make sure we have a "closed" position. Positions like | |
1339 | * | |
1340 | * |XXXXXX. | |
1341 | * |OOOOOXX | |
1342 | * |.O.O*.. | |
1343 | * +------- | |
1344 | * | |
1345 | * disqualify without further analysis. (* is a false eye vertex) | |
1346 | */ | |
1347 | for (k = 0; k < 4; k++) | |
1348 | if (ON_BOARD(pos + delta[k]) | |
1349 | && board[pos + delta[k]] != color | |
1350 | && eye[pos + delta[k]].color != eye_color) | |
1351 | break; | |
1352 | ||
1353 | if (k < 4) | |
1354 | continue; | |
1355 | ||
1356 | /* Check that all adjoining strings have external connection to an | |
1357 | * eye. | |
1358 | */ | |
1359 | for (k = 0; k < 4; k++) | |
1360 | if (ON_BOARD(pos + delta[k]) | |
1361 | && board[pos + delta[k]] == color | |
1362 | && !connected_to_eye(pos, pos + delta[k], color, eye_color, eye)) | |
1363 | break; | |
1364 | ||
1365 | if (k == 4) { | |
1366 | false_eye_territory[pos] = 1; | |
1367 | if (0) | |
1368 | gprintf("False eye territory at %1m\n", pos); | |
1369 | } | |
1370 | } | |
1371 | ||
1372 | /* FIXME: This initialization doesn't really belong here but must be | |
1373 | * done somewhere within examine_position(). | |
1374 | * The array is eventually filled by the endgame() function. | |
1375 | */ | |
1376 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1377 | if (ON_BOARD(pos)) | |
1378 | forced_backfilling_moves[pos] = 0; | |
1379 | } | |
1380 | ||
1381 | /* | |
1382 | * This function (implicitly) finds the connected set of strings of a | |
1383 | * dragon, starting from (str) which is next to the analyzed halfeye | |
1384 | * at (pos). Strings are for this purpose considered connected if and | |
1385 | * only if they have a common liberty, which is not allowed to be the | |
1386 | * half eye itself or one of its diagonal neighbors. For these strings | |
1387 | * it is examined whether their liberties are parts of eyespaces worth | |
1388 | * at least two halfeyes (again not counting the eyespace at (pos)). | |
1389 | * | |
1390 | * The real work is done by the recursive function | |
1391 | * connected_to_eye_recurse() below. | |
1392 | */ | |
1393 | static int | |
1394 | connected_to_eye(int pos, int str, int color, int eye_color, | |
1395 | struct eye_data *eye) | |
1396 | { | |
1397 | signed char mx[BOARDMAX]; | |
1398 | signed char me[BOARDMAX]; | |
1399 | int k; | |
1400 | int halfeyes; | |
1401 | ||
1402 | /* mx marks strings and liberties which have already been investigated. | |
1403 | * me marks the origins of eyespaces which have already been counted. | |
1404 | * Start by marking (pos) and the surrounding vertices in mx. | |
1405 | */ | |
1406 | memset(mx, 0, sizeof(mx)); | |
1407 | memset(me, 0, sizeof(me)); | |
1408 | mx[pos] = 1; | |
1409 | for (k = 0; k < 8; k++) | |
1410 | if (ON_BOARD(pos + delta[k])) | |
1411 | mx[pos + delta[k]] = 1; | |
1412 | ||
1413 | halfeyes = 0; | |
1414 | connected_to_eye_recurse(pos, str, color, eye_color, eye, mx, me, &halfeyes); | |
1415 | ||
1416 | if (halfeyes >= 2) | |
1417 | return 1; | |
1418 | ||
1419 | return 0; | |
1420 | } | |
1421 | ||
1422 | /* Recursive helper for connected_to_eye(). Stop searching when we | |
1423 | * have found at least two halfeyes. | |
1424 | */ | |
1425 | static void | |
1426 | connected_to_eye_recurse(int pos, int str, int color, int eye_color, | |
1427 | struct eye_data *eye, signed char *mx, | |
1428 | signed char *me, int *halfeyes) | |
1429 | { | |
1430 | int liberties; | |
1431 | int libs[MAXLIBS]; | |
1432 | int r; | |
1433 | int k; | |
1434 | ||
1435 | mark_string(str, mx, 1); | |
1436 | liberties = findlib(str, MAXLIBS, libs); | |
1437 | ||
1438 | /* Search the liberties of (str) for eyespaces. */ | |
1439 | for (r = 0; r < liberties; r++) { | |
1440 | if (eye[libs[r]].color == eye_color | |
1441 | && libs[r] != pos | |
1442 | && !me[eye[libs[r]].origin]) { | |
1443 | me[eye[libs[r]].origin] = 1; | |
1444 | *halfeyes += (min_eyes(&eye[libs[r]].value) | |
1445 | + max_eyes(&eye[libs[r]].value)); | |
1446 | } | |
1447 | } | |
1448 | ||
1449 | if (*halfeyes >= 2) | |
1450 | return; | |
1451 | ||
1452 | /* Search for new strings in the same dragon with a liberty in | |
1453 | * common with (str), and recurse. | |
1454 | */ | |
1455 | for (r = 0; r < liberties; r++) { | |
1456 | if (mx[libs[r]]) | |
1457 | continue; | |
1458 | mx[libs[r]] = 1; | |
1459 | for (k = 0; k < 4; k++) { | |
1460 | if (ON_BOARD(libs[r] + delta[k]) | |
1461 | && board[libs[r] + delta[k]] == color | |
1462 | && is_same_dragon(str, libs[r] + delta[k]) | |
1463 | && !mx[libs[r] + delta[k]]) | |
1464 | connected_to_eye_recurse(pos, libs[r] + delta[k], color, eye_color, | |
1465 | eye, mx, me, halfeyes); | |
1466 | if (*halfeyes >= 2) | |
1467 | return; | |
1468 | } | |
1469 | } | |
1470 | } | |
1471 | ||
1472 | /* print status info on all dragons. (Can be invoked from gdb) | |
1473 | */ | |
1474 | void | |
1475 | show_dragons(void) | |
1476 | { | |
1477 | int pos; | |
1478 | int k; | |
1479 | ||
1480 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1481 | struct worm_data *w = &(worm[pos]); | |
1482 | if (!IS_STONE(board[pos])) | |
1483 | continue; | |
1484 | ||
1485 | if (w->origin == pos) { | |
1486 | gprintf("%1m : (dragon %1m) %s string of size %d (%f), genus %d: (%d,%d,%d,%d)", | |
1487 | pos, dragon[pos].origin, | |
1488 | color_to_string(board[pos]), | |
1489 | w->size, | |
1490 | w->effective_size, | |
1491 | w->genus, | |
1492 | w->liberties, | |
1493 | w->liberties2, | |
1494 | w->liberties3, | |
1495 | w->liberties4); | |
1496 | if (w->cutstone == 1) | |
1497 | gprintf("%o - is a potential cutting stone\n"); | |
1498 | else if (w->cutstone == 2) | |
1499 | gprintf("%o - is a cutting stone\n"); | |
1500 | else | |
1501 | gprintf("%o\n"); | |
1502 | ||
1503 | if (w->cutstone2 > 0) | |
1504 | gprintf("- cutstone2 = %d\n", w->cutstone2); | |
1505 | ||
1506 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { | |
1507 | if (w->attack_codes[k] == 0) | |
1508 | break; | |
1509 | gprintf("- attackable at %1m, attack code = %d\n", | |
1510 | w->attack_points[k], w->attack_codes[k]); | |
1511 | } | |
1512 | ||
1513 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { | |
1514 | if (w->defense_codes[k] == 0) | |
1515 | break; | |
1516 | gprintf("- defendable at %1m, defend code = %d\n", | |
1517 | w->defense_points[k], w->defense_codes[k]); | |
1518 | } | |
1519 | ||
1520 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { | |
1521 | if (w->attack_threat_codes[k] == 0) | |
1522 | break; | |
1523 | gprintf("- attack threat at %1m, attack threat code = %d\n", | |
1524 | w->attack_threat_points[k], w->attack_threat_codes[k]); | |
1525 | } | |
1526 | ||
1527 | for (k = 0; k < MAX_TACTICAL_POINTS; k++) { | |
1528 | if (w->defense_threat_codes[k] == 0) | |
1529 | break; | |
1530 | gprintf("- defense threat at %1m, defense threat code = %d\n", | |
1531 | w->defense_threat_points[k], w->defense_threat_codes[k]); | |
1532 | } | |
1533 | ||
1534 | if (w->lunch != NO_MOVE) | |
1535 | gprintf("... adjacent worm %1m is lunch\n", w->lunch); | |
1536 | ||
1537 | if (w->inessential) | |
1538 | gprintf("- is inessential\n"); | |
1539 | ||
1540 | if (w->invincible) | |
1541 | gprintf("- is invincible\n"); | |
1542 | ||
1543 | if (is_ko_point(pos)) | |
1544 | gprintf("- is a ko stone\n"); | |
1545 | } | |
1546 | } | |
1547 | ||
1548 | gprintf("%o\n"); | |
1549 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1550 | struct dragon_data *dd = &(dragon[pos]); | |
1551 | struct dragon_data2 *d2; | |
1552 | ||
1553 | if (!IS_STONE(board[pos])) | |
1554 | continue; | |
1555 | ||
1556 | d2 = &(dragon2[dd->id]); | |
1557 | ||
1558 | if (dd->origin == pos) { | |
1559 | gprintf("%1m : %s dragon size %d (%f), genus %s, escape factor %d, crude status %s, status %s, moyo size %d, moyo territory value %f, safety %s, weakness pre owl %f, weakness %f", | |
1560 | pos, | |
1561 | board[pos] == BLACK ? "B" : "W", | |
1562 | dd->size, | |
1563 | dd->effective_size, | |
1564 | eyevalue_to_string(&d2->genus), | |
1565 | d2->escape_route, | |
1566 | status_to_string(dd->crude_status), | |
1567 | status_to_string(dd->status), | |
1568 | d2->moyo_size, | |
1569 | d2->moyo_territorial_value, | |
1570 | status_to_string(d2->safety), | |
1571 | d2->weakness_pre_owl, | |
1572 | d2->weakness); | |
1573 | gprintf(", owl status %s\n", status_to_string(d2->owl_status)); | |
1574 | if (d2->owl_status == CRITICAL) { | |
1575 | gprintf("... owl attackable at %1m, code %d\n", | |
1576 | d2->owl_attack_point, d2->owl_attack_code); | |
1577 | gprintf("... owl defendable at %1m, code %d\n", | |
1578 | d2->owl_defense_point, d2->owl_defense_code); | |
1579 | } | |
1580 | if (dd->status == CRITICAL && d2->semeais) { | |
1581 | if (d2->semeai_defense_point) | |
1582 | gprintf("... semeai defense move at %1m, result code %s\n", | |
1583 | d2->semeai_defense_point, | |
1584 | result_to_string(d2->semeai_defense_code)); | |
1585 | if (d2->semeai_attack_point) | |
1586 | gprintf("... semeai attack move at %1m, result code %s\n", | |
1587 | d2->semeai_attack_point, | |
1588 | result_to_string(d2->semeai_attack_code)); | |
1589 | } | |
1590 | gprintf("... neighbors"); | |
1591 | for (k = 0; k < d2->neighbors; k++) { | |
1592 | int d = d2->adjacent[k]; | |
1593 | gprintf(" %1m", dragon2[d].origin); | |
1594 | } | |
1595 | gprintf("\n"); | |
1596 | if (d2->lunch != NO_MOVE) | |
1597 | gprintf("... adjacent worm %1m is lunch\n", d2->lunch); | |
1598 | } | |
1599 | } | |
1600 | } | |
1601 | ||
1602 | ||
1603 | static int new_dragon_origins[BOARDMAX]; | |
1604 | ||
1605 | /* Compute new dragons, e.g. after having made a move. This will not | |
1606 | * affect any global state. | |
1607 | */ | |
1608 | void | |
1609 | compute_new_dragons(int dragon_origins[BOARDMAX]) | |
1610 | { | |
1611 | int pos; | |
1612 | int saved_cutting_points[BOARDMAX]; | |
1613 | ||
1614 | /* This is currently necessary in order not to mess up the | |
1615 | * worm[].cutstone2 field. See cutstone2_helper in | |
1616 | * patterns/helpers.c. On the other hand it shouldn't be very | |
1617 | * interesting to recompute dragons in the original position. | |
1618 | */ | |
1619 | gg_assert(stackp > 0); | |
1620 | ||
1621 | memcpy(saved_cutting_points, cutting_points, sizeof(cutting_points)); | |
1622 | memset(cutting_points, 0, sizeof(cutting_points)); | |
1623 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1624 | if (ON_BOARD(pos)) { | |
1625 | if (board[pos] == EMPTY) | |
1626 | new_dragon_origins[pos] = NO_MOVE; | |
1627 | else | |
1628 | new_dragon_origins[pos] = find_origin(pos); | |
1629 | } | |
1630 | ||
1631 | find_cuts(); | |
1632 | find_connections(); | |
1633 | ||
1634 | memcpy(cutting_points, saved_cutting_points, sizeof(cutting_points)); | |
1635 | memcpy(dragon_origins, new_dragon_origins, sizeof(new_dragon_origins)); | |
1636 | } | |
1637 | ||
1638 | ||
1639 | /* This gets called if we are trying to compute dragons outside of | |
1640 | * make_dragons(), typically after a move has been made. | |
1641 | */ | |
1642 | static void | |
1643 | join_new_dragons(int d1, int d2) | |
1644 | { | |
1645 | int pos; | |
1646 | /* Normalize dragon coordinates. */ | |
1647 | d1 = new_dragon_origins[d1]; | |
1648 | d2 = new_dragon_origins[d2]; | |
1649 | ||
1650 | /* If d1 and d2 are the same dragon, we do nothing. */ | |
1651 | if (d1 == d2) | |
1652 | return; | |
1653 | ||
1654 | ASSERT1(board[d1] == board[d2], d1); | |
1655 | ASSERT1(IS_STONE(board[d1]), d1); | |
1656 | ||
1657 | /* Don't bother to do anything fancy with dragon origins. */ | |
1658 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1659 | if (ON_BOARD(pos) && new_dragon_origins[pos] == d2) | |
1660 | new_dragon_origins[pos] = d1; | |
1661 | } | |
1662 | ||
1663 | /* | |
1664 | * join_dragons amalgamates the dragon at (d1) to the | |
1665 | * dragon at (d2). | |
1666 | */ | |
1667 | ||
1668 | void | |
1669 | join_dragons(int d1, int d2) | |
1670 | { | |
1671 | int ii; | |
1672 | int origin; /* new origin */ | |
1673 | ||
1674 | /* If not called from make_dragons(), we don't work on the main | |
1675 | * dragon[] array. | |
1676 | */ | |
1677 | if (stackp > 0) { | |
1678 | join_new_dragons(d1, d2); | |
1679 | return; | |
1680 | } | |
1681 | ||
1682 | /* Normalize dragon coordinates. */ | |
1683 | d1 = dragon[d1].origin; | |
1684 | d2 = dragon[d2].origin; | |
1685 | ||
1686 | /* If d1 and d2 are the same dragon, we do nothing. */ | |
1687 | if (d1 == d2) | |
1688 | return; | |
1689 | ||
1690 | ASSERT1(board[d1] == board[d2], d1); | |
1691 | gg_assert(dragon2_initialized == 0); | |
1692 | ASSERT1(IS_STONE(board[d1]), d1); | |
1693 | ||
1694 | /* We want to have the origin pointing to the largest string of | |
1695 | * the dragon. If this is not unique, we take the "upper | |
1696 | * leftmost" one. | |
1697 | */ | |
1698 | if (worm[d1].size > worm[d2].size | |
1699 | || (worm[d1].size == worm[d2].size | |
1700 | && d1 < d2)) { | |
1701 | origin = d1; | |
1702 | DEBUG(DEBUG_DRAGONS, "joining dragon at %1m to dragon at %1m\n", d2, d1); | |
1703 | } | |
1704 | else { | |
1705 | origin = d2; | |
1706 | DEBUG(DEBUG_DRAGONS, "joining dragon at %1m to dragon at %1m\n", d1, d2); | |
1707 | } | |
1708 | ||
1709 | dragon[origin].size = dragon[d2].size + dragon[d1].size; | |
1710 | dragon[origin].effective_size = (dragon[d2].effective_size | |
1711 | + dragon[d1].effective_size); | |
1712 | ||
1713 | /* Join the second next_worm_in_dragon chain at the end of the first one. */ | |
1714 | { | |
1715 | int last_worm_origin_dragon = origin; | |
1716 | while (next_worm_list[last_worm_origin_dragon] != NO_MOVE) | |
1717 | last_worm_origin_dragon = next_worm_list[last_worm_origin_dragon]; | |
1718 | if (origin == d1) | |
1719 | next_worm_list[last_worm_origin_dragon] = d2; | |
1720 | else | |
1721 | next_worm_list[last_worm_origin_dragon] = d1; | |
1722 | } | |
1723 | ||
1724 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
1725 | if (ON_BOARD(ii) | |
1726 | && (dragon[ii].origin == d1 || dragon[ii].origin == d2)) | |
1727 | dragon[ii].origin = origin; | |
1728 | } | |
1729 | } | |
1730 | ||
1731 | ||
1732 | ||
1733 | /* | |
1734 | * compute_crude_status(pos) tries to determine whether the dragon | |
1735 | * at (pos) is ALIVE, DEAD, or UNKNOWN. The algorithm is not perfect | |
1736 | * and can give incorrect answers. | |
1737 | * | |
1738 | * The dragon is judged alive if its genus is >1. It is judged dead if | |
1739 | * the genus is <2, it has no escape route, and no adjoining string can | |
1740 | * be easily captured. Otherwise it is judged UNKNOWN. */ | |
1741 | ||
1742 | static enum dragon_status | |
1743 | compute_crude_status(int pos) | |
1744 | { | |
1745 | /* FIXME: We lose information when constructing true_genus. This | |
1746 | * code can be improved. | |
1747 | */ | |
1748 | struct eyevalue *genus = &DRAGON2(pos).genus; | |
1749 | int true_genus = max_eyes(genus) + min_eyes(genus); | |
1750 | int lunch = DRAGON2(pos).lunch; | |
1751 | ||
1752 | gg_assert(dragon2_initialized); | |
1753 | ||
1754 | /* If it has two sure eyes, everything is just dandy. */ | |
1755 | if (true_genus > 3) | |
1756 | return ALIVE; | |
1757 | ||
1758 | /* If the dragon consists of one worm, there is an attack, but | |
1759 | * no defense and there is less than one eye and one half eye, | |
1760 | * the situation is hopeless. | |
1761 | */ | |
1762 | if (dragon[pos].size == worm[pos].size | |
1763 | && worm[pos].attack_codes[0] != 0 | |
1764 | && worm[pos].defense_codes[0] == 0 | |
1765 | && true_genus < 3) | |
1766 | return DEAD; | |
1767 | ||
1768 | if (lunch != NO_MOVE | |
1769 | && true_genus < 3 | |
1770 | && worm[lunch].defense_codes[0] != 0 | |
1771 | && DRAGON2(pos).escape_route < 5) | |
1772 | if (true_genus == 2 || worm[lunch].size > 2) | |
1773 | return CRITICAL; | |
1774 | ||
1775 | if (lunch != NO_MOVE | |
1776 | && true_genus >= 3) | |
1777 | return ALIVE; | |
1778 | ||
1779 | if (lunch == NO_MOVE || worm[lunch].cutstone < 2) { | |
1780 | if (true_genus < 3 | |
1781 | && DRAGON2(pos).escape_route == 0 | |
1782 | && DRAGON2(pos).moyo_size < 5) | |
1783 | return DEAD; | |
1784 | ||
1785 | if (true_genus == 3 | |
1786 | && DRAGON2(pos).escape_route < 5) | |
1787 | return CRITICAL; | |
1788 | } | |
1789 | ||
1790 | if (DRAGON2(pos).moyo_territorial_value > 9.99) | |
1791 | return ALIVE; | |
1792 | ||
1793 | return UNKNOWN; | |
1794 | } | |
1795 | ||
1796 | ||
1797 | /* The dragon escape measure. This is defined as follows. | |
1798 | * | |
1799 | * Let a PATH be a sequence of adjacent intersections that do nowhere | |
1800 | * touch or include an opponent stone or touch the border. It may | |
1801 | * include friendly stones and those are allowed to touch opponent | |
1802 | * stones or the border). Let a DISTANCE N INTERSECTION be an | |
1803 | * intersection connected to a dragon by a path of length N, but by no | |
1804 | * shorter path. The connection of the path to the dragon may either | |
1805 | * be by direct adjacency or, in the first step, diagonally if both | |
1806 | * adjoining intersections are empty. | |
1807 | * | |
1808 | * It is assumed that each intersection has an escape value, which | |
1809 | * would typically depend on influence and (preliminary) dragon | |
1810 | * status. We define the escape potential as the sum of the escape | |
1811 | * values over the distance four intersections of the dragon. | |
1812 | * | |
1813 | * Example of distance N intersections, 1 <= N <= 4: | |
1814 | * | |
1815 | * . . . . . . . . . . . . . . . . . . | |
1816 | * . . . . . X . . O . . . . . X . . O | |
1817 | * . . X . . . . . O . . X . 2 . 4 . O | |
1818 | * X . . . . . . . . X . . 1 1 2 3 4 . | |
1819 | * X O . O . . . . O X O 1 O 1 2 3 4 O | |
1820 | * X O . O . . . . . X O 1 O 1 . 4 . . | |
1821 | * X O . . . X . O O X O 1 . . X . . O | |
1822 | * . . . X . . . . . . 1 . X . . . . . | |
1823 | * X . . . . X . . . X . . . . X . . . | |
1824 | * . . . . . . . . . . . . . . . . . . | |
1825 | * | |
1826 | * Additionally, a path may not pass a connection inhibited | |
1827 | * intersection. | |
1828 | */ | |
1829 | ||
1830 | #define ENQUEUE(pos) (queue[queue_end++] = (pos),\ | |
1831 | mx[pos] = 1) | |
1832 | ||
1833 | /* Compute the escape potential described above. The dragon is marked | |
1834 | * in the goal array. | |
1835 | */ | |
1836 | int | |
1837 | dragon_escape(signed char goal[BOARDMAX], int color, | |
1838 | signed char escape_value[BOARDMAX]) | |
1839 | { | |
1840 | int ii; | |
1841 | int k; | |
1842 | static int mx[BOARDMAX]; | |
1843 | static int mx_initialized = 0; | |
1844 | int queue[MAX_BOARD * MAX_BOARD]; | |
1845 | int queue_start = 0; | |
1846 | int queue_end = 0; | |
1847 | int other = OTHER_COLOR(color); | |
1848 | int distance; | |
1849 | int escape_potential = 0; | |
1850 | ||
1851 | gg_assert(IS_STONE(color)); | |
1852 | ||
1853 | if (!mx_initialized) { | |
1854 | memset(mx, 0, sizeof(mx)); | |
1855 | mx_initialized = 1; | |
1856 | } | |
1857 | ||
1858 | /* Enter the stones of the dragon in the queue. */ | |
1859 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1860 | if (ON_BOARD(ii) && goal[ii]) | |
1861 | ENQUEUE(ii); | |
1862 | ||
1863 | /* Find points at increasing distances from the dragon. At distance | |
1864 | * four, sum the escape values at those points to get the escape | |
1865 | * potential. | |
1866 | */ | |
1867 | for (distance = 0; distance <= 4; distance++) { | |
1868 | int save_queue_end = queue_end; | |
1869 | while (queue_start < save_queue_end) { | |
1870 | ii = queue[queue_start]; | |
1871 | queue_start++; | |
1872 | ||
1873 | /* Do not pass connection inhibited intersections. */ | |
1874 | if (cut_possible(ii, OTHER_COLOR(color))) | |
1875 | continue; | |
1876 | if (distance == 4) | |
1877 | escape_potential += escape_value[ii]; | |
1878 | else { | |
1879 | if (ON_BOARD(SOUTH(ii)) | |
1880 | && !mx[SOUTH(ii)] | |
1881 | && (board[SOUTH(ii)] == color | |
1882 | || (board[SOUTH(ii)] == EMPTY | |
1883 | && ON_BOARD(SE(ii)) && board[SE(ii)] != other | |
1884 | && ON_BOARD(SS(ii)) && board[SS(ii)] != other | |
1885 | && ON_BOARD(SW(ii)) && board[SW(ii)] != other))) | |
1886 | ENQUEUE(SOUTH(ii)); | |
1887 | ||
1888 | if (ON_BOARD(WEST(ii)) | |
1889 | && !mx[WEST(ii)] | |
1890 | && (board[WEST(ii)] == color | |
1891 | || (board[WEST(ii)] == EMPTY | |
1892 | && ON_BOARD(SW(ii)) && board[SW(ii)] != other | |
1893 | && ON_BOARD(WW(ii)) && board[WW(ii)] != other | |
1894 | && ON_BOARD(NW(ii)) && board[NW(ii)] != other))) | |
1895 | ENQUEUE(WEST(ii)); | |
1896 | ||
1897 | if (ON_BOARD(NORTH(ii)) | |
1898 | && !mx[NORTH(ii)] | |
1899 | && (board[NORTH(ii)] == color | |
1900 | || (board[NORTH(ii)] == EMPTY | |
1901 | && ON_BOARD(NW(ii)) && board[NW(ii)] != other | |
1902 | && ON_BOARD(NN(ii)) && board[NN(ii)] != other | |
1903 | && ON_BOARD(NE(ii)) && board[NE(ii)] != other))) | |
1904 | ENQUEUE(NORTH(ii)); | |
1905 | ||
1906 | if (ON_BOARD(EAST(ii)) | |
1907 | && !mx[EAST(ii)] | |
1908 | && (board[EAST(ii)] == color | |
1909 | || (board[EAST(ii)] == EMPTY | |
1910 | && ON_BOARD(NE(ii)) && board[NE(ii)] != other | |
1911 | && ON_BOARD(EE(ii)) && board[EE(ii)] != other | |
1912 | && ON_BOARD(SE(ii)) && board[SE(ii)] != other))) | |
1913 | ENQUEUE(EAST(ii)); | |
1914 | ||
1915 | /* For distance one intersections, allow kosumi to move out. I.e. | |
1916 | * | |
1917 | * ??.. | |
1918 | * X.*. | |
1919 | * ?O.? | |
1920 | * ??X? | |
1921 | * | |
1922 | */ | |
1923 | if (distance == 0) { | |
1924 | if (board[SOUTH(ii)] == EMPTY | |
1925 | && board[WEST(ii)] == EMPTY | |
1926 | && !mx[SW(ii)] | |
1927 | && (board[SW(ii)] == color | |
1928 | || (board[SW(ii)] == EMPTY | |
1929 | && ON_BOARD(SOUTH(SW(ii))) | |
1930 | && board[SOUTH(SW(ii))] != other | |
1931 | && ON_BOARD(WEST(SW(ii))) | |
1932 | && board[WEST(SW(ii))] != other))) | |
1933 | ENQUEUE(SW(ii)); | |
1934 | ||
1935 | if (board[WEST(ii)] == EMPTY | |
1936 | && board[NORTH(ii)] == EMPTY | |
1937 | && !mx[NW(ii)] | |
1938 | && (board[NW(ii)] == color | |
1939 | || (board[NW(ii)] == EMPTY | |
1940 | && ON_BOARD(WEST(NW(ii))) | |
1941 | && board[WEST(NW(ii))] != other | |
1942 | && ON_BOARD(NORTH(NW(ii))) | |
1943 | && board[NORTH(NW(ii))] != other))) | |
1944 | ENQUEUE(NW(ii)); | |
1945 | ||
1946 | if (board[NORTH(ii)] == EMPTY | |
1947 | && board[EAST(ii)] == EMPTY | |
1948 | && !mx[NE(ii)] | |
1949 | && (board[NE(ii)] == color | |
1950 | || (board[NE(ii)] == EMPTY | |
1951 | && ON_BOARD(NORTH(NE(ii))) | |
1952 | && board[NORTH(NE(ii))] != other | |
1953 | && ON_BOARD(EAST(NE(ii))) | |
1954 | && board[EAST(NE(ii))] != other))) | |
1955 | ENQUEUE(NE(ii)); | |
1956 | ||
1957 | if (board[EAST(ii)] == EMPTY | |
1958 | && board[SOUTH(ii)] == EMPTY | |
1959 | && !mx[SE(ii)] | |
1960 | && (board[SE(ii)] == color | |
1961 | || (board[SE(ii)] == EMPTY | |
1962 | && ON_BOARD(EAST(SE(ii))) | |
1963 | && board[EAST(SE(ii))] != other | |
1964 | && ON_BOARD(SOUTH(SE(ii))) | |
1965 | && board[SOUTH(SE(ii))] != other))) | |
1966 | ENQUEUE(SE(ii)); | |
1967 | } | |
1968 | } | |
1969 | } | |
1970 | } | |
1971 | ||
1972 | /* Reset used mx cells. */ | |
1973 | for (k = 0; k < queue_end; k++) { | |
1974 | /* The assertion fails if the same element should have been queued | |
1975 | * twice, which might happen if ENQUEUE() is called without | |
1976 | * checking mx[]. | |
1977 | */ | |
1978 | ASSERT1(mx[queue[k]] == 1, queue[k]); | |
1979 | mx[queue[k]] = 0; | |
1980 | } | |
1981 | ||
1982 | return escape_potential; | |
1983 | } | |
1984 | ||
1985 | /* Wrapper to call the function above and compute the escape potential | |
1986 | * for the dragon at (pos). | |
1987 | */ | |
1988 | static int | |
1989 | compute_escape(int pos, int dragon_status_known) | |
1990 | { | |
1991 | int ii; | |
1992 | signed char goal[BOARDMAX]; | |
1993 | signed char escape_value[BOARDMAX]; | |
1994 | signed char safe_stones[BOARDMAX]; | |
1995 | ||
1996 | ASSERT1(IS_STONE(board[pos]), pos); | |
1997 | ||
1998 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) | |
1999 | if (ON_BOARD(ii)) | |
2000 | goal[ii] = is_same_dragon(ii, pos); | |
2001 | ||
2002 | /* Compute escape_value array. Points are awarded for moyo (4), | |
2003 | * area (2) or EMPTY (1). Values may change without notice. | |
2004 | */ | |
2005 | get_lively_stones(OTHER_COLOR(board[pos]), safe_stones); | |
2006 | compute_escape_influence(board[pos], safe_stones, NULL, 0, escape_value); | |
2007 | ||
2008 | /* If we can reach a live group, award 6 points. */ | |
2009 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) { | |
2010 | if (!ON_BOARD(ii)) | |
2011 | continue; | |
2012 | ||
2013 | if (dragon_status_known) { | |
2014 | if (dragon[ii].crude_status == ALIVE) | |
2015 | escape_value[ii] = 6; | |
2016 | else if (dragon[ii].crude_status == UNKNOWN | |
2017 | && (DRAGON2(ii).escape_route > 5 | |
2018 | || DRAGON2(ii).moyo_size > 5)) | |
2019 | escape_value[ii] = 4; | |
2020 | } | |
2021 | else { | |
2022 | if (board[ii] == board[pos] | |
2023 | && !goal[ii] | |
2024 | && worm[ii].attack_codes[0] == 0) | |
2025 | escape_value[ii] = 2; | |
2026 | } | |
2027 | } | |
2028 | ||
2029 | return dragon_escape(goal, board[pos], escape_value); | |
2030 | } | |
2031 | ||
2032 | /* | |
2033 | * Sum up the surrounding moyo sizes for each dragon. For this | |
2034 | * we retrieve the moyo data stored in influence_data (*q) (which must | |
2035 | * have been computed previously) from the influence module. | |
2036 | * We set dragon2[].moyo_size and .moyo_value if it is smaller than the | |
2037 | * current entry. | |
2038 | * | |
2039 | * Currently this is implemented differently depending on whether | |
2040 | * experimental connections are used or not. The reason why this is | |
2041 | * needed is that most of the B patterns in conn.db are disabled for | |
2042 | * experimental connections, which may cause the moyo segmentation to | |
2043 | * pass through cutting points between dragons, making the surrounding | |
2044 | * moyo size mostly useless. Instead we only use the part of the | |
2045 | * surrounding moyo which is closest to some worm of the dragon. | |
2046 | */ | |
2047 | static void | |
2048 | compute_surrounding_moyo_sizes(const struct influence_data *q) | |
2049 | { | |
2050 | int pos; | |
2051 | int d; | |
2052 | int k; | |
2053 | int moyo_color; | |
2054 | float moyo_sizes[BOARDMAX]; | |
2055 | float moyo_values[BOARDMAX]; | |
2056 | ||
2057 | ||
2058 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
2059 | moyo_sizes[pos] = 0.0; | |
2060 | moyo_values[pos] = 0.0; | |
2061 | } | |
2062 | ||
2063 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
2064 | if (!ON_BOARD(pos)) | |
2065 | continue; | |
2066 | moyo_color = whose_moyo_restricted(q, pos); | |
2067 | ||
2068 | if (moyo_color == board[pos]) | |
2069 | continue; | |
2070 | ||
2071 | if (moyo_color == WHITE) { | |
2072 | for (k = 0; k < number_close_white_worms[pos]; k++) { | |
2073 | int w = close_white_worms[pos][k]; | |
2074 | int dr = dragon[w].origin; | |
2075 | ||
2076 | moyo_sizes[dr] += 1.0 / number_close_white_worms[pos]; | |
2077 | moyo_values[dr] += (gg_min(influence_territory(q, pos, WHITE), 1.0) | |
2078 | / number_close_white_worms[pos]); | |
2079 | } | |
2080 | } | |
2081 | ||
2082 | if (moyo_color == BLACK) { | |
2083 | for (k = 0; k < number_close_black_worms[pos]; k++) { | |
2084 | int w = close_black_worms[pos][k]; | |
2085 | int dr = dragon[w].origin; | |
2086 | ||
2087 | moyo_sizes[dr] += 1.0 / number_close_black_worms[pos]; | |
2088 | moyo_values[dr] += (gg_min(influence_territory(q, pos, BLACK), 1.0) | |
2089 | / number_close_black_worms[pos]); | |
2090 | } | |
2091 | } | |
2092 | } | |
2093 | ||
2094 | for (d = 0; d < number_of_dragons; d++) { | |
2095 | int this_moyo_size = (int) moyo_sizes[dragon2[d].origin]; | |
2096 | float this_moyo_value = moyo_values[dragon2[d].origin]; | |
2097 | ||
2098 | if (this_moyo_size < dragon2[d].moyo_size) { | |
2099 | dragon2[d].moyo_size = this_moyo_size; | |
2100 | dragon2[d].moyo_territorial_value = this_moyo_value; | |
2101 | } | |
2102 | } | |
2103 | } | |
2104 | ||
2105 | ||
2106 | static struct interpolation_data moyo_value2weakness = | |
2107 | { 5, 0.0, 15.0, {1.0, 0.65, 0.3, 0.15, 0.05, 0.0}}; | |
2108 | static struct interpolation_data escape_route2weakness = | |
2109 | { 5, 0.0, 25.0, {1.0, 0.6, 0.3, 0.1, 0.05, 0.0}}; | |
2110 | static struct interpolation_data genus2weakness = | |
2111 | { 6, 0.0, 3.0, {1.0, 0.95, 0.8, 0.5, 0.2, 0.1, 0.0}}; | |
2112 | ||
2113 | float | |
2114 | crude_dragon_weakness(int safety, struct eyevalue *genus, int has_lunch, | |
2115 | float moyo_value, float escape_route) | |
2116 | { | |
2117 | /* FIXME: We lose information when constructing true_genus. This | |
2118 | * code can be improved. | |
2119 | */ | |
2120 | float true_genus = 0.5 * (max_eyes(genus) + min_eyes(genus) | |
2121 | + (has_lunch != 0)); | |
2122 | float weakness_value[3]; | |
2123 | float weakness; | |
2124 | int i, j; | |
2125 | ||
2126 | if (safety == INVINCIBLE || safety == INESSENTIAL) | |
2127 | return 0.0; | |
2128 | if (safety == TACTICALLY_DEAD || safety == DEAD || safety == CRITICAL) | |
2129 | return 1.0; | |
2130 | ||
2131 | weakness_value[0] = gg_interpolate(&moyo_value2weakness, moyo_value); | |
2132 | weakness_value[1] = gg_interpolate(&escape_route2weakness, escape_route); | |
2133 | weakness_value[2] = gg_interpolate(&genus2weakness, true_genus); | |
2134 | ||
2135 | DEBUG(DEBUG_DRAGONS, | |
2136 | " moyo value %f -> %f, escape %f -> %f, eyes %f -> %f\n", | |
2137 | moyo_value, weakness_value[0], | |
2138 | escape_route, weakness_value[1], | |
2139 | true_genus, weakness_value[2]); | |
2140 | ||
2141 | for (i = 0; i < 3; i++) | |
2142 | for (j = i + 1; j < 3; j++) | |
2143 | if (weakness_value[j] < weakness_value[i]) { | |
2144 | float tmp = weakness_value[i]; | |
2145 | weakness_value[i] = weakness_value[j]; | |
2146 | weakness_value[j] = tmp; | |
2147 | } | |
2148 | ||
2149 | /* The overall weakness is mostly, but not completely determined by the | |
2150 | * best value found so far: | |
2151 | */ | |
2152 | weakness = gg_min(0.7 * weakness_value[0] + 0.3 * weakness_value[1], | |
2153 | 1.3 * weakness_value[0]); | |
2154 | ||
2155 | gg_assert(weakness >= 0.0 && weakness <= 1.0); | |
2156 | ||
2157 | return weakness; | |
2158 | } | |
2159 | ||
2160 | /* This function tries to guess a coefficient measuring the weakness of | |
2161 | * a dragon. This coefficient * the effective size of the dragon can be | |
2162 | * used to award a strategic penalty for weak dragons. | |
2163 | */ | |
2164 | static float | |
2165 | compute_dragon_weakness_value(int d) | |
2166 | { | |
2167 | int origin = dragon2[d].origin; | |
2168 | float weakness; | |
2169 | ||
2170 | /* Possible ingredients for the computation: | |
2171 | * '+' means currently used, '-' means not (yet?) used | |
2172 | * - pre-owl moyo_size | |
2173 | * + post-owl moyo_size and its territory value | |
2174 | * + escape factor | |
2175 | * + number of eyes | |
2176 | * - minus number of vital attack moves? | |
2177 | * + from owl: | |
2178 | * + attack certain? | |
2179 | * - number of owl nodes | |
2180 | * - maybe reading shadow? | |
2181 | * + threat to attack? | |
2182 | * - possible connections to neighbour dragons | |
2183 | */ | |
2184 | ||
2185 | DEBUG(DEBUG_DRAGONS, "Computing weakness of dragon at %1m:\n", origin); | |
2186 | ||
2187 | weakness = crude_dragon_weakness(dragon2[d].safety, &dragon2[d].genus, | |
2188 | dragon2[d].lunch != NO_MOVE, | |
2189 | dragon2[d].moyo_territorial_value, | |
2190 | (float) dragon2[d].escape_route); | |
2191 | ||
2192 | /* Now corrections due to (uncertain) owl results resp. owl threats. */ | |
2193 | if (!dragon2[d].owl_attack_certain) | |
2194 | weakness += gg_min(0.25 * (1.0 - weakness), 0.25 * weakness); | |
2195 | if (!dragon2[d].owl_defense_certain) | |
2196 | weakness += gg_min(0.25 * (1.0 - weakness), 0.25 * weakness); | |
2197 | if (dragon2[d].owl_threat_status == CAN_THREATEN_ATTACK) | |
2198 | weakness += 0.15 * (1.0 - weakness); | |
2199 | ||
2200 | if (weakness < 0.0) | |
2201 | weakness = 0.0; | |
2202 | if (weakness > 1.0) | |
2203 | weakness = 1.0; | |
2204 | ||
2205 | DEBUG(DEBUG_DRAGONS, " result: %f.\n", weakness); | |
2206 | return weakness; | |
2207 | } | |
2208 | ||
2209 | ||
2210 | /* This function has to be called _after_ the owl analysis and the | |
2211 | * subsequent re-run of the influence code. | |
2212 | */ | |
2213 | void | |
2214 | compute_refined_dragon_weaknesses() | |
2215 | { | |
2216 | int d; | |
2217 | ||
2218 | /* Compute the surrounding moyo sizes. */ | |
2219 | for (d = 0; d < number_of_dragons; d++) | |
2220 | dragon2[d].moyo_size = 2 * BOARDMAX; | |
2221 | ||
2222 | /* Set moyo sizes according to initial_influence. */ | |
2223 | compute_surrounding_moyo_sizes(&initial_black_influence); | |
2224 | compute_surrounding_moyo_sizes(&initial_white_influence); | |
2225 | ||
2226 | for (d = 0; d < number_of_dragons; d++) | |
2227 | dragon2[d].weakness = compute_dragon_weakness_value(d); | |
2228 | } | |
2229 | ||
2230 | /* The strategic size is the effective size, plus a bonus for all weak | |
2231 | * neighbouring dragons of the opponent. | |
2232 | */ | |
2233 | void | |
2234 | compute_strategic_sizes() | |
2235 | { | |
2236 | float *bonus = calloc(number_of_dragons, sizeof(float)); | |
2237 | int d; | |
2238 | int k; | |
2239 | ||
2240 | for (d = 0; d < number_of_dragons; d++) { | |
2241 | /* Compute bonus for all neighbors of dragon (d). The total bonus for | |
2242 | * all neighbors is effective_size(d) * weakness(d), and it is given | |
2243 | * to a neighbor d2 proportionally to the value of | |
2244 | * effective_size(d2) * weakness(d2). | |
2245 | */ | |
2246 | float sum = 0.0; | |
2247 | if (dragon2[d].safety == INESSENTIAL) | |
2248 | continue; | |
2249 | for (k = 0; k < dragon2[d].neighbors; k++) { | |
2250 | int d2 = dragon2[d].adjacent[k]; | |
2251 | if (board[dragon2[d2].origin] == OTHER_COLOR(board[dragon2[d].origin]) | |
2252 | && dragon2[d2].safety != INESSENTIAL) | |
2253 | sum += DRAGON(d2).effective_size * dragon2[d2].weakness; | |
2254 | } | |
2255 | if (sum == 0.0) | |
2256 | continue; | |
2257 | for (k = 0; k < dragon2[d].neighbors; k++) { | |
2258 | int d2 = dragon2[d].adjacent[k]; | |
2259 | if (board[dragon2[d2].origin] == OTHER_COLOR(board[dragon2[d].origin]) | |
2260 | && dragon2[d2].safety != INESSENTIAL) { | |
2261 | bonus[d2] += ((DRAGON(d2).effective_size * dragon2[d2].weakness) / sum) | |
2262 | * DRAGON(d).effective_size * dragon2[d].weakness; | |
2263 | if (0) | |
2264 | gprintf("Dragon %1m receives %f effective size bonus from %1m.\n", | |
2265 | dragon2[d2].origin, | |
2266 | ((DRAGON(d2).effective_size * dragon2[d2].weakness) / sum) | |
2267 | * DRAGON(d).effective_size * dragon2[d].weakness, | |
2268 | dragon2[d].origin); | |
2269 | } | |
2270 | } | |
2271 | } | |
2272 | ||
2273 | for (d = 0; d < number_of_dragons; d++) { | |
2274 | if (0) | |
2275 | gprintf("Dragon %1m gets effective size bonus of %f.\n", | |
2276 | dragon2[d].origin, bonus[d]); | |
2277 | /* We cap strategic size at 3 * effective_size. (This is ad hoc.) */ | |
2278 | dragon2[d].strategic_size = gg_min(bonus[d] + DRAGON(d).effective_size, | |
2279 | 3 * DRAGON(d).effective_size); | |
2280 | } | |
2281 | ||
2282 | free(bonus); | |
2283 | } | |
2284 | ||
2285 | ||
2286 | /* | |
2287 | * Test whether two dragons are the same. Used by autohelpers and elsewhere. | |
2288 | */ | |
2289 | ||
2290 | int | |
2291 | is_same_dragon(int d1, int d2) | |
2292 | { | |
2293 | if (d1 == NO_MOVE || d2 == NO_MOVE) | |
2294 | return (d1 == d2); | |
2295 | ||
2296 | ASSERT_ON_BOARD1(d1); | |
2297 | ASSERT_ON_BOARD1(d2); | |
2298 | ||
2299 | return (dragon[d1].origin == dragon[d2].origin); | |
2300 | } | |
2301 | ||
2302 | /* Test whether two dragons are neighbors. */ | |
2303 | int | |
2304 | are_neighbor_dragons(int d1, int d2) | |
2305 | { | |
2306 | int k; | |
2307 | d1 = dragon[d1].origin; | |
2308 | d2 = dragon[d2].origin; | |
2309 | ||
2310 | for (k = 0; k < DRAGON2(d1).neighbors; k++) | |
2311 | if (dragon2[DRAGON2(d1).adjacent[k]].origin == d2) | |
2312 | return 1; | |
2313 | ||
2314 | /* Just to be make sure that this function is always symmetric, we | |
2315 | * do it the other way round too. | |
2316 | */ | |
2317 | for (k = 0; k < DRAGON2(d2).neighbors; k++) | |
2318 | if (dragon2[DRAGON2(d2).adjacent[k]].origin == d1) | |
2319 | return 1; | |
2320 | ||
2321 | return 0; | |
2322 | } | |
2323 | ||
2324 | ||
2325 | /* Mark the stones of a dragon. */ | |
2326 | void | |
2327 | mark_dragon(int pos, signed char mx[BOARDMAX], signed char mark) | |
2328 | { | |
2329 | int w; | |
2330 | for (w = first_worm_in_dragon(dragon[pos].origin); w != NO_MOVE; | |
2331 | w = next_worm_in_dragon(w)) | |
2332 | mark_string(w, mx, mark); | |
2333 | } | |
2334 | ||
2335 | ||
2336 | /* The following two functions allow to traverse all worms in a dragon: | |
2337 | * for (ii = first_worm_in_dragon(pos); ii != NO_MOVE; | |
2338 | * ii = next_worm_in_dragon(ii);) | |
2339 | * ... | |
2340 | * At the moment first_worm_in_dragon(pos) will always be the origin | |
2341 | * of the dragon, but you should not rely on that. | |
2342 | */ | |
2343 | int | |
2344 | first_worm_in_dragon(int d) | |
2345 | { | |
2346 | return dragon[d].origin; | |
2347 | } | |
2348 | ||
2349 | int | |
2350 | next_worm_in_dragon(int w) | |
2351 | { | |
2352 | ASSERT1(worm[w].origin == w, w); | |
2353 | return next_worm_list[w]; | |
2354 | } | |
2355 | ||
2356 | ||
2357 | /* ================================================================ */ | |
2358 | /* A few status functions */ | |
2359 | /* ================================================================ */ | |
2360 | ||
2361 | /* | |
2362 | * These functions are only here because then we don't need to expose | |
2363 | * the dragon structure to the external program. | |
2364 | */ | |
2365 | ||
2366 | enum dragon_status | |
2367 | crude_status(int pos) | |
2368 | { | |
2369 | return dragon[pos].crude_status; | |
2370 | } | |
2371 | ||
2372 | ||
2373 | enum dragon_status | |
2374 | dragon_status(int pos) | |
2375 | { | |
2376 | return dragon[pos].status; | |
2377 | } | |
2378 | ||
2379 | ||
2380 | int | |
2381 | lively_dragon_exists(int color) | |
2382 | { | |
2383 | if (color == WHITE) | |
2384 | return lively_white_dragons > 0; | |
2385 | else | |
2386 | return lively_black_dragons > 0; | |
2387 | } | |
2388 | ||
2389 | ||
2390 | /* Is this dragon weak? */ | |
2391 | ||
2392 | int | |
2393 | dragon_weak(int pos) | |
2394 | { | |
2395 | ASSERT_ON_BOARD1(pos); | |
2396 | /* FIXME: This should not happen, but avoids a crash. What is | |
2397 | * the proper fix for calling this at stackp != 0 ? | |
2398 | */ | |
2399 | if (dragon[pos].id < 0 || dragon[pos].id >= number_of_dragons) | |
2400 | return 1; | |
2401 | return (DRAGON2(pos).weakness > 0.40001); | |
2402 | } | |
2403 | ||
2404 | ||
2405 | /* Returns the size of the biggest critical dragon on the board. */ | |
2406 | ||
2407 | int | |
2408 | size_of_biggest_critical_dragon(void) | |
2409 | { | |
2410 | int str; | |
2411 | int max_size = 0; | |
2412 | ||
2413 | for (str = BOARDMIN; str < BOARDMAX; str++) | |
2414 | if (ON_BOARD(str)) { | |
2415 | ||
2416 | if (board[str] == EMPTY | |
2417 | || dragon[str].origin != str) | |
2418 | continue; | |
2419 | ||
2420 | /* Get the best available status for the dragon */ | |
2421 | if (dragon[str].status == CRITICAL) { | |
2422 | if (dragon[str].size >= max_size) | |
2423 | max_size = dragon[str].size; | |
2424 | } | |
2425 | } | |
2426 | return max_size; | |
2427 | } | |
2428 | ||
2429 | ||
2430 | /************************************************************************ | |
2431 | * A list of all cuts found during connection matching * | |
2432 | ************************************************************************/ | |
2433 | ||
2434 | #define MAX_CUTS 3 * MAX_BOARD * MAX_BOARD | |
2435 | ||
2436 | struct cut_data { | |
2437 | int apos; | |
2438 | int bpos; | |
2439 | int move; | |
2440 | }; | |
2441 | ||
2442 | static int num_cuts = 0; | |
2443 | static struct cut_data cut_list[MAX_CUTS]; | |
2444 | ||
2445 | static void | |
2446 | clear_cut_list() | |
2447 | { | |
2448 | num_cuts = 0; | |
2449 | } | |
2450 | ||
2451 | /* Store in the list that (move) disconnects the two strings at | |
2452 | * apos and bpos. | |
2453 | */ | |
2454 | void | |
2455 | add_cut(int apos, int bpos, int move) | |
2456 | { | |
2457 | gg_assert(board[apos] == board[bpos]); | |
2458 | if (num_cuts == MAX_CUTS) | |
2459 | return; | |
2460 | if (apos > bpos) { | |
2461 | int tmp = apos; | |
2462 | apos = bpos; | |
2463 | bpos = tmp; | |
2464 | } | |
2465 | if (move == NO_MOVE) | |
2466 | return; | |
2467 | cut_list[num_cuts].apos = apos; | |
2468 | cut_list[num_cuts].bpos = bpos; | |
2469 | cut_list[num_cuts].move = move; | |
2470 | num_cuts++; | |
2471 | if (0) | |
2472 | gprintf("Added %d-th cut at %1m between %1m and %1m.\n", num_cuts, | |
2473 | move, apos, bpos); | |
2474 | } | |
2475 | ||
2476 | /* For every move in the cut list disconnecting two of opponent's strings, | |
2477 | * test whether the two strings can be connected at all. If so, add a | |
2478 | * CUT_MOVE reason. | |
2479 | */ | |
2480 | void | |
2481 | cut_reasons(int color) | |
2482 | { | |
2483 | int k; | |
2484 | for (k = 0; k < num_cuts; k++) | |
2485 | if (board[cut_list[k].apos] == OTHER_COLOR(color) | |
2486 | && !is_same_dragon(cut_list[k].apos, cut_list[k].bpos) | |
2487 | && string_connect(cut_list[k].apos, cut_list[k].bpos, NULL) == WIN) | |
2488 | add_cut_move(cut_list[k].move, cut_list[k].apos, cut_list[k].bpos); | |
2489 | } | |
2490 | ||
2491 | ||
2492 | /* ================================================================ */ | |
2493 | /* Debugger functions */ | |
2494 | /* ================================================================ */ | |
2495 | ||
2496 | /* For use in gdb, print details of the dragon at (m, n). | |
2497 | * Add this to your .gdbinit file: | |
2498 | * | |
2499 | * define dragon | |
2500 | * set ascii_report_dragon("$arg0") | |
2501 | * end | |
2502 | * | |
2503 | * Now 'dragon S8' will report the details of the S8 dragon. | |
2504 | * | |
2505 | */ | |
2506 | ||
2507 | void | |
2508 | ascii_report_dragon(char *string) | |
2509 | { | |
2510 | int pos = string_to_location(board_size, string); | |
2511 | ||
2512 | if (!ON_BOARD(pos)) | |
2513 | fprintf(stderr, "unknown position %s\n", string); | |
2514 | else | |
2515 | report_dragon(stderr, pos); | |
2516 | } | |
2517 | ||
2518 | ||
2519 | void | |
2520 | report_dragon(FILE *outfile, int pos) | |
2521 | { | |
2522 | int w; | |
2523 | int k; | |
2524 | struct dragon_data *d = &(dragon[pos]); | |
2525 | struct dragon_data2 *d2 = &(dragon2[d->id]); | |
2526 | ||
2527 | if (board[pos] == EMPTY) { | |
2528 | gprintf("There is no dragon at %1m\n", pos); | |
2529 | return; | |
2530 | } | |
2531 | ||
2532 | if (d->id < 0) { | |
2533 | gprintf("Dragon data not available at %1m\n", pos); | |
2534 | return; | |
2535 | } | |
2536 | ||
2537 | gfprintf(outfile, "color %s\n", color_to_string(d->color)); | |
2538 | gfprintf(outfile, "origin %1m\n", d->origin); | |
2539 | gfprintf(outfile, "size %d\n", d->size); | |
2540 | gfprintf(outfile, "effective_size %f\n", d->effective_size); | |
2541 | gfprintf(outfile, "strategic_size %f\n", d2->strategic_size); | |
2542 | gfprintf(outfile, "genus %s\n", | |
2543 | eyevalue_to_string(&d2->genus)); | |
2544 | gfprintf(outfile, "heye %1m\n", d2->heye); | |
2545 | gfprintf(outfile, "escape_route %d\n", d2->escape_route); | |
2546 | gfprintf(outfile, "lunch %1m\n", d2->lunch); | |
2547 | gfprintf(outfile, "crude_status %s\n", | |
2548 | status_to_string(d->crude_status)); | |
2549 | gfprintf(outfile, "owl_status %s\n", | |
2550 | status_to_string(d2->owl_status)); | |
2551 | gfprintf(outfile, "status %s\n", | |
2552 | status_to_string(d->status)); | |
2553 | gfprintf(outfile, "safety %s\n", | |
2554 | status_to_string(d2->safety)); | |
2555 | gfprintf(outfile, "weakness %f\n", d2->weakness); | |
2556 | gfprintf(outfile, "weakness_pre_owl %f\n", d2->weakness_pre_owl); | |
2557 | gfprintf(outfile, "surround_status %d\n", d2->surround_status); | |
2558 | gfprintf(outfile, "surround_size %d\n", d2->surround_size); | |
2559 | gfprintf(outfile, "moyo_size %d\n", d2->moyo_size); | |
2560 | gfprintf(outfile, "moyo_territorial_value %f\n", | |
2561 | d2->moyo_territorial_value); | |
2562 | gfprintf(outfile, "neighbors "); | |
2563 | for (k = 0; k < d2->neighbors; k++) | |
2564 | gfprintf(outfile, "%1m ", DRAGON(d2->adjacent[k]).origin); | |
2565 | gfprintf(outfile, "\nhostile_neighbors %d\n", d2->hostile_neighbors); | |
2566 | gfprintf(outfile, "owl_attack_code %d\n", d2->owl_attack_code); | |
2567 | gfprintf(outfile, "owl_attack_point %1m\n", d2->owl_attack_point); | |
2568 | gfprintf(outfile, "owl_attack_certain %s\n", | |
2569 | (d2->owl_attack_certain) ? "YES" : "NO"); | |
2570 | gfprintf(outfile, "owl_2nd_attack_point %1m\n", | |
2571 | d2->owl_second_attack_point); | |
2572 | gfprintf(outfile, "owl_threat_status %s\n", | |
2573 | status_to_string(d2->owl_threat_status)); | |
2574 | gfprintf(outfile, "owl_defense_code %d\n", d2->owl_defense_code); | |
2575 | gfprintf(outfile, "owl_defense_point %1m\n", d2->owl_defense_point); | |
2576 | gfprintf(outfile, "owl_defense_certain %s\n", | |
2577 | (d2->owl_defense_certain) ? "YES" : "NO"); | |
2578 | gfprintf(outfile, "owl_2nd_defense_point %1m\n", | |
2579 | d2->owl_second_defense_point); | |
2580 | gfprintf(outfile, "owl_attack_kworm %1m\n", d2->owl_attack_kworm); | |
2581 | gfprintf(outfile, "owl_defense_kworm %1m\n", d2->owl_defense_kworm); | |
2582 | gfprintf(outfile, "semeais %d\n", d2->semeais); | |
2583 | gfprintf(outfile, "semeai_defense_code %d\n", d2->semeai_defense_code); | |
2584 | gfprintf(outfile, "semeai_defense_point %1m\n", d2->semeai_defense_point); | |
2585 | gfprintf(outfile, "semeai_defense_certain %d\n", | |
2586 | d2->semeai_defense_certain); | |
2587 | gfprintf(outfile, "semeai_defense_target %1m\n", | |
2588 | d2->semeai_defense_target); | |
2589 | gfprintf(outfile, "semeai_attack_code %d\n", d2->semeai_attack_code); | |
2590 | gfprintf(outfile, "semeai_attack_point %1m\n", d2->semeai_attack_point); | |
2591 | gfprintf(outfile, "semeai_attack_certain %d\n", d2->semeai_attack_certain); | |
2592 | gfprintf(outfile, "semeai_attack_target %1m\n", d2->semeai_attack_target); | |
2593 | gfprintf(outfile, "strings "); | |
2594 | for (w = first_worm_in_dragon(pos); w != NO_MOVE; w = next_worm_in_dragon(w)) | |
2595 | gfprintf(outfile, "%1m ", w); | |
2596 | gfprintf(outfile, "\n"); | |
2597 | } | |
2598 | ||
2599 | ||
2600 | /* | |
2601 | * Local Variables: | |
2602 | * tab-width: 8 | |
2603 | * c-basic-offset: 2 | |
2604 | * End: | |
2605 | */ |