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 | /* | |
25 | * The code in this file implements persistent caching. | |
26 | * | |
27 | * The idea is that reading results are stored together with an | |
28 | * "active area", i.e. the part of the board having an effect on the | |
29 | * reading result. Thus if only moves outside of the active area has | |
30 | * been played since the result was stored, it can be reused. | |
31 | * | |
32 | * The active areas are not known exactly but are estimated | |
33 | * heuristically. The effects are that too large an active area | |
34 | * reduces the efficiency of the caching scheme while too small an | |
35 | * active area may cause an incorrect read result to be retrieved from | |
36 | * the cache. | |
37 | * | |
38 | * Persistent caching has so far been implemented for tactical reading, | |
39 | * owl reading, connection reading and break-in reading (with semeai | |
40 | * reading planned for the future). | |
41 | * | |
42 | * The hotspot functions are intended to locate where the most | |
43 | * expensive reading of either type is going on. This information can | |
44 | * be estimated from the contents of the persistent caches since the | |
45 | * most expensive readings are stored there with full information of | |
46 | * spent reading nodes, involved strings or dragons, and active areas. | |
47 | */ | |
48 | ||
49 | #include "gnugo.h" | |
50 | ||
51 | #include <stdio.h> | |
52 | #include <string.h> | |
53 | #include <stdlib.h> | |
54 | #include "liberty.h" | |
55 | #include "cache.h" | |
56 | ||
57 | ||
58 | /* ================================================================ */ | |
59 | /* Data structures */ | |
60 | /* ================================================================ */ | |
61 | ||
62 | /* Used in active area. */ | |
63 | #define HIGH_LIBERTY_BIT 4 | |
64 | #define HIGH_LIBERTY_BIT2 8 | |
65 | ||
66 | ||
67 | #define MAX_READING_CACHE_DEPTH 5 | |
68 | #define MAX_READING_CACHE_SIZE 100 | |
69 | ||
70 | #define MAX_OWL_CACHE_DEPTH 0 | |
71 | #define MAX_OWL_CACHE_SIZE 150 | |
72 | ||
73 | #define MAX_CONNECTION_CACHE_DEPTH 5 | |
74 | #define MAX_CONNECTION_CACHE_SIZE 100 | |
75 | ||
76 | #define MAX_BREAKIN_CACHE_DEPTH 1 | |
77 | #define MAX_BREAKIN_CACHE_SIZE 150 | |
78 | ||
79 | #define MAX_SEMEAI_CACHE_DEPTH 0 | |
80 | #define MAX_SEMEAI_CACHE_SIZE 150 | |
81 | ||
82 | #define MAX_CACHE_DEPTH 5 | |
83 | ||
84 | ||
85 | /* We use the same data structure for all of the caches. Some of the entries | |
86 | * below are unused for some of the caches. | |
87 | */ | |
88 | struct persistent_cache_entry { | |
89 | int boardsize; | |
90 | int movenum; | |
91 | Intersection board[BOARDMAX]; | |
92 | int stack[MAX_CACHE_DEPTH]; | |
93 | int move_color[MAX_CACHE_DEPTH]; | |
94 | enum routine_id routine; | |
95 | int apos; /* first input coordinate */ | |
96 | int bpos; /* second input coordinate */ | |
97 | int cpos; /* third input coordinate */ | |
98 | int color; /* Move at (cpos) by (color) in analyze_semeai_after_move() */ | |
99 | Hash_data goal_hash; /* hash of the goals in break-in and semeai reading */ | |
100 | int result; | |
101 | int result2; | |
102 | int result_certain; | |
103 | int remaining_depth; | |
104 | int node_limit; | |
105 | int move; /* first result coordinate */ | |
106 | int move2;/* second result coordinate */ | |
107 | int cost; /* Usually no. of tactical nodes spent on this reading result. */ | |
108 | int score; /* Heuristic guess of the worth of the cache entry. */ | |
109 | }; | |
110 | ||
111 | /* Callback function that implements the computation of the active area. | |
112 | * This function has to be provided by each cache. | |
113 | */ | |
114 | typedef void (*compute_active_area_fn)(struct persistent_cache_entry *entry, | |
115 | const signed char goal[BOARDMAX], | |
116 | int goal_color); | |
117 | ||
118 | struct persistent_cache { | |
119 | const int max_size; /* Size of above array. */ | |
120 | const int max_stackp; /* Don't store positions with stackp > max_stackp. */ | |
121 | const float age_factor; /* Reduce value of old entries with this factor. */ | |
122 | const char *name; /* For debugging purposes. */ | |
123 | const compute_active_area_fn compute_active_area; | |
124 | struct persistent_cache_entry *table; /* Array of actual results. */ | |
125 | int current_size; /* Current number of entries. */ | |
126 | int last_purge_position_number; | |
127 | }; | |
128 | ||
129 | static void compute_active_owl_area(struct persistent_cache_entry *entry, | |
130 | const signed char goal[BOARDMAX], | |
131 | int goal_color); | |
132 | static void compute_active_semeai_area(struct persistent_cache_entry *entry, | |
133 | const signed char goal[BOARDMAX], | |
134 | int dummy); | |
135 | static void compute_active_reading_area(struct persistent_cache_entry *entry, | |
136 | const signed char | |
137 | reading_shadow[BOARDMAX], | |
138 | int dummy); | |
139 | static void compute_active_connection_area(struct persistent_cache_entry *entry, | |
140 | const signed char | |
141 | connection_shadow[BOARDMAX], | |
142 | int goal_color); | |
143 | static void compute_active_breakin_area(struct persistent_cache_entry *entry, | |
144 | const signed char | |
145 | breakin_shadow[BOARDMAX], | |
146 | int dummy); | |
147 | ||
148 | static struct persistent_cache reading_cache = | |
149 | { MAX_READING_CACHE_SIZE, MAX_READING_CACHE_DEPTH, 1.0, | |
150 | "reading cache", compute_active_reading_area, | |
151 | NULL, 0, -1 }; | |
152 | ||
153 | static struct persistent_cache connection_cache = | |
154 | { MAX_CONNECTION_CACHE_SIZE, MAX_CONNECTION_CACHE_DEPTH, 1.0, | |
155 | "connection cache", compute_active_connection_area, | |
156 | NULL, 0, -1 }; | |
157 | ||
158 | static struct persistent_cache breakin_cache = | |
159 | { MAX_BREAKIN_CACHE_SIZE, MAX_BREAKIN_CACHE_DEPTH, 0.75, | |
160 | "breakin cache", compute_active_breakin_area, | |
161 | NULL, 0, -1 }; | |
162 | ||
163 | static struct persistent_cache owl_cache = | |
164 | { MAX_OWL_CACHE_SIZE, MAX_OWL_CACHE_DEPTH, 1.0, | |
165 | "owl cache", compute_active_owl_area, | |
166 | NULL, 0, -1 }; | |
167 | ||
168 | static struct persistent_cache semeai_cache = | |
169 | { MAX_SEMEAI_CACHE_SIZE, MAX_SEMEAI_CACHE_DEPTH, 0.75, | |
170 | "semeai cache", compute_active_semeai_area, | |
171 | NULL, 0, -1 }; | |
172 | ||
173 | /* ================================================================ */ | |
174 | /* Common helper functions. */ | |
175 | ||
176 | ||
177 | static void | |
178 | draw_active_area(Intersection board[BOARDMAX], int apos) | |
179 | { | |
180 | int i, j, ii; | |
181 | int c = ' '; | |
182 | int cw = (apos == NO_MOVE) ? 'O' : 'o'; | |
183 | int cb = (apos == NO_MOVE) ? 'X' : 'x'; | |
184 | ||
185 | start_draw_board(); | |
186 | ||
187 | for (i = 0; i < board_size; i++) { | |
188 | ii = board_size - i; | |
189 | fprintf(stderr, "\n%2d", ii); | |
190 | ||
191 | for (j = 0; j < board_size; j++) { | |
192 | int pos = POS(i, j); | |
193 | if (board[pos] == EMPTY) | |
194 | c = '.'; | |
195 | else if (board[pos] == WHITE) | |
196 | c = cw; | |
197 | else if ((board[pos] & 3) == WHITE) | |
198 | c = 'O'; | |
199 | else if (board[pos] == BLACK) | |
200 | c = cb; | |
201 | else if ((board[pos] & 3) == BLACK) | |
202 | c = 'X'; | |
203 | if (board[pos] == GRAY) | |
204 | c = '?'; | |
205 | ||
206 | if (pos == apos) | |
207 | fprintf(stderr, "[%c", c); | |
208 | else if (j > 0 && POS(i, j-1) == apos) | |
209 | fprintf(stderr, "]%c", c); | |
210 | else | |
211 | fprintf(stderr, " %c", c); | |
212 | } | |
213 | ||
214 | fprintf(stderr, " %d", ii); | |
215 | } | |
216 | ||
217 | end_draw_board(); | |
218 | } | |
219 | ||
220 | ||
221 | /* Returns 1 if the stored board is compatible with the current board, | |
222 | * 0 otherwise. | |
223 | */ | |
224 | static int | |
225 | verify_stored_board(Intersection p[BOARDMAX]) | |
226 | { | |
227 | int pos; | |
228 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
229 | if (!ON_BOARD(pos)) | |
230 | continue; | |
231 | else if (p[pos] == GRAY) | |
232 | continue; | |
233 | else if ((p[pos] & 3) != board[pos]) | |
234 | return 0; | |
235 | else if (!(p[pos] & (HIGH_LIBERTY_BIT | HIGH_LIBERTY_BIT2))) | |
236 | continue; | |
237 | else if (((p[pos] & HIGH_LIBERTY_BIT) && countlib(pos) <= 4) | |
238 | || (p[pos] & HIGH_LIBERTY_BIT2 && countlib(pos) <= 3)) | |
239 | return 0; | |
240 | } | |
241 | ||
242 | return 1; | |
243 | } | |
244 | ||
245 | ||
246 | /* Prints out all relevant information for a cache entry, and prints | |
247 | * a board showing the active area. | |
248 | */ | |
249 | static void | |
250 | print_persistent_cache_entry(struct persistent_cache_entry *entry) | |
251 | { | |
252 | int r; | |
253 | ||
254 | gprintf("%omovenum = %d\n", entry->movenum); | |
255 | gprintf("%oscore = %d\n", entry->score); | |
256 | gprintf("%ocost = %d\n", entry->cost); | |
257 | gprintf("%oroutine = %s\n", routine_id_to_string(entry->routine)); | |
258 | gprintf("%oapos = %1m\n", entry->apos); | |
259 | if (entry->bpos != NO_MOVE) | |
260 | gprintf("%obpos = %1m\n", entry->bpos); | |
261 | if (entry->cpos != NO_MOVE) | |
262 | gprintf("%ocpos = %1m\n", entry->cpos); | |
263 | gprintf("%oresult = %s\n", result_to_string(entry->result)); | |
264 | if (entry->result2 != 0) | |
265 | gprintf("%oresult2 = %s\n", result_to_string(entry->result2)); | |
266 | if (entry->result_certain != -1) | |
267 | gprintf("%oresult_certain = %d\n", entry->result_certain); | |
268 | if (entry->node_limit != -1) | |
269 | gprintf("%onode_limit = %d\n", entry->node_limit); | |
270 | if (entry->move != NO_MOVE) | |
271 | gprintf("%omove = %1m\n", entry->move); | |
272 | if (entry->move2 != NO_MOVE) | |
273 | gprintf("%omove2 = %1m\n", entry->move2); | |
274 | ||
275 | for (r = 0; r < MAX_CACHE_DEPTH; r++) { | |
276 | if (entry->stack[r] == 0) | |
277 | break; | |
278 | gprintf("%ostack[%d] = %C %1m\n", r, entry->move_color[r], | |
279 | entry->stack[r]); | |
280 | } | |
281 | ||
282 | draw_active_area(entry->board, entry->apos); | |
283 | } | |
284 | ||
285 | /* To keep GCC happy and have the function included in the | |
286 | * gnugo executable. Can be used from gdb. | |
287 | */ | |
288 | void print_persistent_cache(struct persistent_cache *cache); | |
289 | ||
290 | ||
291 | /* Can be used from gdb. */ | |
292 | void | |
293 | print_persistent_cache(struct persistent_cache *cache) | |
294 | { | |
295 | int k; | |
296 | gprintf("Entire content of %s:\n", cache->name); | |
297 | for (k = 0; k < cache->current_size; k++) | |
298 | print_persistent_cache_entry(cache->table + k); | |
299 | } | |
300 | ||
301 | ||
302 | /* ================================================================ */ | |
303 | /* Core functions. */ | |
304 | /* ================================================================ */ | |
305 | ||
306 | /* The static functions below implement the core infrastructure of the | |
307 | * persistent caches. Each cache only has to provide a function | |
308 | * computing the active area, and wrappers around the search_.. and store_.. | |
309 | * function below. | |
310 | */ | |
311 | ||
312 | /* Remove persistent cache entries which are no longer compatible with | |
313 | * the board. For efficient use of the cache, it's recommended to call | |
314 | * this function once per move, before starting the owl reading. It's | |
315 | * not required for correct operation though. | |
316 | */ | |
317 | static void | |
318 | purge_persistent_cache(struct persistent_cache *cache) | |
319 | { | |
320 | int k; | |
321 | int r; | |
322 | gg_assert(stackp == 0); | |
323 | ||
324 | /* Never do this more than once per move. */ | |
325 | if (cache->last_purge_position_number == position_number) | |
326 | return; | |
327 | else | |
328 | cache->last_purge_position_number = position_number; | |
329 | ||
330 | for (k = 0; k < cache->current_size; k++) { | |
331 | int played_moves = 0; | |
332 | int entry_ok = 1; | |
333 | struct persistent_cache_entry *entry = &(cache->table[k]); | |
334 | ||
335 | if (entry->boardsize != board_size) | |
336 | entry_ok = 0; | |
337 | else { | |
338 | for (r = 0; r < MAX_CACHE_DEPTH; r++) { | |
339 | int apos = entry->stack[r]; | |
340 | int color = entry->move_color[r]; | |
341 | if (apos == 0) | |
342 | break; | |
343 | if (board[apos] == EMPTY | |
344 | && trymove(apos, color, "purge_persistent_cache", 0)) | |
345 | played_moves++; | |
346 | else { | |
347 | entry_ok = 0; | |
348 | break; | |
349 | } | |
350 | } | |
351 | } | |
352 | ||
353 | if (!entry_ok | |
354 | || !verify_stored_board(entry->board)) { | |
355 | /* Move the last entry in the cache here and back up the loop | |
356 | * counter to redo the test at this position in the cache. | |
357 | */ | |
358 | if (0) | |
359 | gprintf("Purging entry %d from cache.\n", k); | |
360 | if (k < cache->current_size - 1) | |
361 | *entry = cache->table[cache->current_size - 1]; | |
362 | k--; | |
363 | cache->current_size--; | |
364 | } | |
365 | else { | |
366 | /* Reduce score here to penalize entries getting old. */ | |
367 | entry->score *= cache->age_factor; | |
368 | } | |
369 | ||
370 | while (played_moves > 0) { | |
371 | popgo(); | |
372 | played_moves--; | |
373 | } | |
374 | } | |
375 | } | |
376 | ||
377 | ||
378 | /* Find a cache entry matching the data given in the parameters. | |
379 | * Important: We assume that unused parameters are normalized to NO_MOVE | |
380 | * when storing or retrieving, so that we can ignore them here. | |
381 | */ | |
382 | static struct persistent_cache_entry * | |
383 | find_persistent_cache_entry(struct persistent_cache *cache, | |
384 | enum routine_id routine, int apos, int bpos, | |
385 | int cpos, int color, | |
386 | Hash_data *goal_hash, int node_limit) | |
387 | { | |
388 | int k; | |
389 | for (k = 0; k < cache->current_size; k++) { | |
390 | struct persistent_cache_entry *entry = cache->table + k; | |
391 | if (entry->routine == routine | |
392 | && entry->apos == apos | |
393 | && entry->bpos == bpos | |
394 | && entry->cpos == cpos | |
395 | && entry->color == color | |
396 | && depth - stackp <= entry->remaining_depth | |
397 | && (entry->node_limit >= node_limit || entry->result_certain) | |
398 | && (goal_hash == NULL | |
399 | || hashdata_is_equal(entry->goal_hash, *goal_hash)) | |
400 | && verify_stored_board(entry->board)) | |
401 | return entry; | |
402 | } | |
403 | return NULL; | |
404 | } | |
405 | ||
406 | /* Search through a persistent cache. Returns 0 if no matching entry was | |
407 | * found; returns 1 and sets the relevant return values otherwise. See | |
408 | * comment above find_persistent_cache_entry() about unused parameters. | |
409 | */ | |
410 | static int | |
411 | search_persistent_cache(struct persistent_cache *cache, | |
412 | enum routine_id routine, int apos, int bpos, | |
413 | int cpos, int color, | |
414 | Hash_data *goal_hash, int node_limit, | |
415 | int *result, int *result2, int *move, int *move2, | |
416 | int *certain) | |
417 | { | |
418 | /* Try to find entry. */ | |
419 | struct persistent_cache_entry *entry; | |
420 | entry = find_persistent_cache_entry(cache, routine, apos, bpos, cpos, color, | |
421 | goal_hash, node_limit); | |
422 | if (entry == NULL) | |
423 | return 0; | |
424 | ||
425 | /* Set return values. */ | |
426 | *result = entry->result; | |
427 | if (result2) | |
428 | *result2 = entry->result2; | |
429 | if (move) | |
430 | *move = entry->move; | |
431 | if (move2) | |
432 | *move2 = entry->move2; | |
433 | if (certain) | |
434 | *certain = entry->result_certain; | |
435 | ||
436 | /* Increase score for entry. */ | |
437 | entry->score += entry->cost; | |
438 | ||
439 | if (debug & DEBUG_PERSISTENT_CACHE) { | |
440 | gprintf("%oRetrieved position from %s:\n", cache->name); | |
441 | print_persistent_cache_entry(entry); | |
442 | } | |
443 | /* FIXME: This is an ugly hack. */ | |
444 | if (strcmp(cache->name, "reading cache") == 0 | |
445 | && (debug & DEBUG_READING_PERFORMANCE) | |
446 | && entry->cost >= MIN_READING_NODES_TO_REPORT) { | |
447 | if (entry->result != 0) | |
448 | gprintf("%o%s %1m = %d %1m, cached (%d nodes) ", | |
449 | routine == ATTACK ? "attack" : "defend", | |
450 | apos, entry->result, entry->move, entry->cost); | |
451 | else | |
452 | gprintf("%o%s %1m = %d, cached (%d nodes) ", | |
453 | routine == ATTACK ? "attack" : "defend", | |
454 | apos, entry->result, entry->cost); | |
455 | dump_stack(); | |
456 | } | |
457 | return 1; | |
458 | } | |
459 | ||
460 | /* Generic function that tries to store a cache entry. If the cache | |
461 | * is full, we delete the lowest scoring entry. | |
462 | * | |
463 | * Unused parameters have to be normalized to NO_MOVE by the calling | |
464 | * function. | |
465 | */ | |
466 | static void | |
467 | store_persistent_cache(struct persistent_cache *cache, | |
468 | enum routine_id routine, | |
469 | int apos, int bpos, int cpos, int color, | |
470 | Hash_data *goal_hash, | |
471 | int result, int result2, int move, int move2, | |
472 | int certain, int node_limit, | |
473 | int cost, const signed char goal[BOARDMAX], | |
474 | int goal_color) | |
475 | { | |
476 | int r; | |
477 | struct persistent_cache_entry *entry; | |
478 | if (stackp > cache->max_stackp) | |
479 | return; | |
480 | ||
481 | /* If cache is still full, consider kicking out an old entry. */ | |
482 | if (cache->current_size == cache->max_size) { | |
483 | int worst_entry = -1; | |
484 | int worst_score = cost; | |
485 | int k; | |
486 | ||
487 | for (k = 0; k < cache->current_size; k++) { | |
488 | if (cache->table[k].score < worst_score) { | |
489 | worst_score = cache->table[k].score; | |
490 | worst_entry = k; | |
491 | } | |
492 | } | |
493 | ||
494 | if (worst_entry != -1) { | |
495 | /* Move the last entry in the cache here to make space. | |
496 | */ | |
497 | if (worst_entry < cache->current_size - 1) | |
498 | cache->table[worst_entry] = cache->table[cache->current_size - 1]; | |
499 | cache->current_size--; | |
500 | } | |
501 | else | |
502 | return; | |
503 | } | |
504 | ||
505 | entry = &(cache->table[cache->current_size]); | |
506 | entry->boardsize = board_size; | |
507 | entry->routine = routine; | |
508 | entry->apos = apos; | |
509 | entry->bpos = bpos; | |
510 | entry->cpos = cpos; | |
511 | entry->color = color; | |
512 | if (goal_hash) | |
513 | entry->goal_hash = *goal_hash; | |
514 | entry->result = result; | |
515 | entry->result2 = result2; | |
516 | entry->result_certain = certain; | |
517 | entry->node_limit = node_limit; | |
518 | entry->remaining_depth = depth - stackp; | |
519 | entry->move = move; | |
520 | entry->move2 = move2; | |
521 | entry->score = cost; | |
522 | entry->cost = cost; | |
523 | entry->movenum = movenum; | |
524 | ||
525 | for (r = 0; r < MAX_CACHE_DEPTH; r++) { | |
526 | if (r < stackp) | |
527 | get_move_from_stack(r, &(entry->stack[r]), &(entry->move_color[r])); | |
528 | else { | |
529 | entry->stack[r] = 0; | |
530 | entry->move_color[r] = EMPTY; | |
531 | } | |
532 | } | |
533 | ||
534 | /* Remains to set the board. */ | |
535 | cache->compute_active_area(&(cache->table[cache->current_size]), | |
536 | goal, goal_color); | |
537 | cache->current_size++; | |
538 | ||
539 | if (debug & DEBUG_PERSISTENT_CACHE) { | |
540 | gprintf("%oEntered position in %s:\n", cache->name); | |
541 | print_persistent_cache_entry(entry); | |
542 | gprintf("%oCurrent size: %d\n", cache->current_size); | |
543 | } | |
544 | } | |
545 | ||
546 | ||
547 | /* ================================================================ */ | |
548 | /* Interface functions relevant to all caches. */ | |
549 | /* ================================================================ */ | |
550 | ||
551 | /* Allocate the actual cache table. */ | |
552 | static void | |
553 | init_cache(struct persistent_cache *cache) | |
554 | { | |
555 | cache->table = malloc(cache->max_size*sizeof(struct persistent_cache_entry)); | |
556 | gg_assert(cache->table); | |
557 | } | |
558 | ||
559 | /* Initializes all persistent caches. | |
560 | * Needs to be called only once at startup. | |
561 | */ | |
562 | void | |
563 | persistent_cache_init() | |
564 | { | |
565 | init_cache(&reading_cache); | |
566 | init_cache(&breakin_cache); | |
567 | init_cache(&connection_cache); | |
568 | init_cache(&owl_cache); | |
569 | init_cache(&semeai_cache); | |
570 | } | |
571 | ||
572 | ||
573 | /* Discards all persistent cache entries. */ | |
574 | void | |
575 | clear_persistent_caches() | |
576 | { | |
577 | reading_cache.current_size = 0; | |
578 | connection_cache.current_size = 0; | |
579 | breakin_cache.current_size = 0; | |
580 | owl_cache.current_size = 0; | |
581 | semeai_cache.current_size = 0; | |
582 | } | |
583 | ||
584 | /* Discards all persistent cache entries that are no longer useful. | |
585 | * Should be called once per move for optimal performance (but is not | |
586 | * necessary for proper operation). | |
587 | */ | |
588 | void | |
589 | purge_persistent_caches() | |
590 | { | |
591 | purge_persistent_cache(&reading_cache); | |
592 | purge_persistent_cache(&connection_cache); | |
593 | purge_persistent_cache(&breakin_cache); | |
594 | purge_persistent_cache(&owl_cache); | |
595 | purge_persistent_cache(&semeai_cache); | |
596 | } | |
597 | ||
598 | /* ================================================================ */ | |
599 | /* Tactical reading functions */ | |
600 | /* ================================================================ */ | |
601 | ||
602 | /* Look for a valid read result in the persistent cache. | |
603 | * Return 1 if found, 0 otherwise. | |
604 | */ | |
605 | int | |
606 | search_persistent_reading_cache(enum routine_id routine, int str, | |
607 | int *result, int *move) | |
608 | { | |
609 | return search_persistent_cache(&reading_cache, | |
610 | routine, str, NO_MOVE, NO_MOVE, EMPTY, NULL, | |
611 | -1, result, NULL, move, NULL, NULL); | |
612 | } | |
613 | ||
614 | ||
615 | /* Store a new read result in the persistent cache. */ | |
616 | void | |
617 | store_persistent_reading_cache(enum routine_id routine, int str, | |
618 | int result, int move, int nodes) | |
619 | { | |
620 | store_persistent_cache(&reading_cache, routine, | |
621 | str, NO_MOVE, NO_MOVE, EMPTY, NULL, | |
622 | result, NO_MOVE, move, NO_MOVE, -1, -1, | |
623 | nodes, shadow, EMPTY); | |
624 | } | |
625 | ||
626 | static void | |
627 | compute_active_reading_area(struct persistent_cache_entry *entry, | |
628 | const signed char goal[BOARDMAX], int dummy) | |
629 | { | |
630 | signed char active[BOARDMAX]; | |
631 | int pos, r; | |
632 | UNUSED(dummy); | |
633 | ||
634 | /* Remains to set the board. We let the active area be the contested | |
635 | * string and reading shadow + adjacent empty and strings + | |
636 | * neighbors of active area so far + one more expansion from empty | |
637 | * to empty. | |
638 | */ | |
639 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
640 | active[pos] = goal[pos]; | |
641 | ||
642 | mark_string(entry->apos, active, 1); | |
643 | ||
644 | /* To be safe, also add the successful move. */ | |
645 | if (entry->result != 0 && entry->move != 0) | |
646 | active[entry->move] = 1; | |
647 | ||
648 | /* Add adjacent strings and empty. */ | |
649 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
650 | if (!ON_BOARD(pos)) | |
651 | continue; | |
652 | if (active[pos] != 0) | |
653 | continue; | |
654 | if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] == 1) | |
655 | || (ON_BOARD(WEST(pos)) && active[WEST(pos)] == 1) | |
656 | || (ON_BOARD(NORTH(pos)) && active[NORTH(pos)] == 1) | |
657 | || (ON_BOARD(EAST(pos)) && active[EAST(pos)] == 1)) { | |
658 | if (IS_STONE(board[pos])) | |
659 | mark_string(pos, active, 2); | |
660 | else | |
661 | active[pos] = 2; | |
662 | } | |
663 | } | |
664 | ||
665 | /* Remove invincible strings. No point adding their liberties and | |
666 | * neighbors. | |
667 | */ | |
668 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
669 | if (!ON_BOARD(pos)) | |
670 | continue; | |
671 | if (IS_STONE(board[pos]) && worm[pos].invincible) | |
672 | active[pos] = 0; | |
673 | } | |
674 | ||
675 | /* Expand empty to empty. */ | |
676 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
677 | if (IS_STONE(board[pos]) || active[pos] != 0) | |
678 | continue; | |
679 | if ((board[SOUTH(pos)] == EMPTY && active[SOUTH(pos)] == 2) | |
680 | || (board[WEST(pos)] == EMPTY && active[WEST(pos)] == 2) | |
681 | || (board[NORTH(pos)] == EMPTY && active[NORTH(pos)] == 2) | |
682 | || (board[EAST(pos)] == EMPTY && active[EAST(pos)] == 2)) | |
683 | active[pos] = 3; | |
684 | } | |
685 | ||
686 | /* Add neighbors of active area so far. */ | |
687 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
688 | if (!ON_BOARD(pos)) | |
689 | continue; | |
690 | if (active[pos] != 0) | |
691 | continue; | |
692 | if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] > 0 | |
693 | && active[SOUTH(pos)] < 4) | |
694 | || (ON_BOARD(WEST(pos)) && active[WEST(pos)] > 0 | |
695 | && active[WEST(pos)] < 4) | |
696 | || (ON_BOARD(NORTH(pos)) && active[NORTH(pos)] > 0 | |
697 | && active[NORTH(pos)] < 4) | |
698 | || (ON_BOARD(EAST(pos)) && active[EAST(pos)] > 0 | |
699 | && active[EAST(pos)] < 4)) | |
700 | active[pos] = 4; | |
701 | } | |
702 | ||
703 | /* Also add the previously played stones to the active area. */ | |
704 | for (r = 0; r < stackp; r++) | |
705 | active[entry->stack[r]] = 5; | |
706 | ||
707 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
708 | if (!ON_BOARD(pos)) | |
709 | continue; | |
710 | entry->board[pos] = | |
711 | active[pos] != 0 ? board[pos] : GRAY; | |
712 | } | |
713 | } | |
714 | ||
715 | ||
716 | /* Helper for the reading_hotspots() function below. */ | |
717 | static void | |
718 | mark_string_hotspot_values(float values[BOARDMAX], | |
719 | int m, int n, float contribution) | |
720 | { | |
721 | int i, j, k; | |
722 | ||
723 | /* If p[m][n] is EMPTY, we just give the contribution to close empty | |
724 | * vertices. This is a rough simplification. | |
725 | */ | |
726 | if (BOARD(m, n) == EMPTY) { | |
727 | for (i = -1; i <= 1; i++) | |
728 | for (j = -1; j <= 1; j++) | |
729 | if (BOARD(m+i, n+j) == EMPTY) | |
730 | values[POS(m+i, n+j)] += contribution; | |
731 | return; | |
732 | } | |
733 | ||
734 | /* Otherwise we give contribution to liberties and diagonal | |
735 | * neighbors of the string at (m, n). | |
736 | */ | |
737 | for (i = 0; i < board_size; i++) | |
738 | for (j = 0; j < board_size; j++) { | |
739 | if (BOARD(i, j) != EMPTY) | |
740 | continue; | |
741 | for (k = 0; k < 8; k++) { | |
742 | int di = deltai[k]; | |
743 | int dj = deltaj[k]; | |
744 | if (IS_STONE(BOARD(i+di, j+dj)) | |
745 | && same_string(POS(i+di, j+dj), POS(m, n))) { | |
746 | if (k < 4) { | |
747 | values[POS(i, j)] += contribution; | |
748 | break; | |
749 | } | |
750 | else { | |
751 | if (BOARD(i+di, j) == EMPTY || countlib(POS(i+di, j)) <= 2 | |
752 | || BOARD(i, j+dj) == EMPTY || countlib(POS(i, j+dj)) <= 2) | |
753 | values[POS(i, j)] += contribution; | |
754 | break; | |
755 | } | |
756 | } | |
757 | } | |
758 | } | |
759 | } | |
760 | ||
761 | ||
762 | /* Based on the entries in the reading cache and their nodes field, | |
763 | * compute where the relatively most expensive tactical reading is | |
764 | * going on. | |
765 | */ | |
766 | void | |
767 | reading_hotspots(float values[BOARDMAX]) | |
768 | { | |
769 | int pos; | |
770 | int k; | |
771 | int sum_nodes = 0; | |
772 | ||
773 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
774 | values[pos] = 0.0; | |
775 | ||
776 | /* Compute the total number of nodes for the cached entries. */ | |
777 | for (k = 0; k < reading_cache.current_size; k++) | |
778 | sum_nodes += reading_cache.table[k].cost; | |
779 | ||
780 | if (sum_nodes <= 100) | |
781 | return; | |
782 | ||
783 | /* Loop over all entries and increase the value of vertices adjacent | |
784 | * to dragons involving expensive tactical reading. | |
785 | */ | |
786 | for (k = 0; k < reading_cache.current_size; k++) { | |
787 | struct persistent_cache_entry *entry = &(reading_cache.table[k]); | |
788 | float contribution = entry->cost / (float) sum_nodes; | |
789 | if (0) { | |
790 | gprintf("Reading hotspots: %d %1m %f\n", entry->routine, entry->apos, | |
791 | contribution); | |
792 | } | |
793 | switch (entry->routine) { | |
794 | case ATTACK: | |
795 | case FIND_DEFENSE: | |
796 | mark_string_hotspot_values(values, I(entry->apos), J(entry->apos), | |
797 | contribution); | |
798 | break; | |
799 | default: | |
800 | gg_assert(0); /* Shouldn't happen. */ | |
801 | break; | |
802 | } | |
803 | } | |
804 | } | |
805 | ||
806 | ||
807 | /* ================================================================ */ | |
808 | /* Connection reading functions */ | |
809 | /* ================================================================ */ | |
810 | ||
811 | /* Look for a valid read result in the persistent connection cache. | |
812 | * Return 1 if found, 0 otherwise. | |
813 | */ | |
814 | int | |
815 | search_persistent_connection_cache(enum routine_id routine, int str1, | |
816 | int str2, int *result, int *move) | |
817 | { | |
818 | return search_persistent_cache(&connection_cache, routine, | |
819 | str1, str2, NO_MOVE, EMPTY, NULL, | |
820 | connection_node_limit, | |
821 | result, NULL, move, NULL, NULL); | |
822 | } | |
823 | ||
824 | /* Store a new connection result in the persistent cache. */ | |
825 | void | |
826 | store_persistent_connection_cache(enum routine_id routine, | |
827 | int str1, int str2, | |
828 | int result, int move, int tactical_nodes, | |
829 | signed char connection_shadow[BOARDMAX]) | |
830 | { | |
831 | store_persistent_cache(&connection_cache, routine, | |
832 | str1, str2, NO_MOVE, EMPTY, NULL, | |
833 | result, NO_MOVE, move, NO_MOVE, -1, | |
834 | connection_node_limit, | |
835 | tactical_nodes, connection_shadow, EMPTY); | |
836 | } | |
837 | ||
838 | /* Computes the active area for the current board position and the | |
839 | * connection read result that has just been stored in *entry. | |
840 | */ | |
841 | static void | |
842 | compute_active_connection_area(struct persistent_cache_entry *entry, | |
843 | const signed char connection_shadow[BOARDMAX], | |
844 | int dummy) | |
845 | { | |
846 | int pos; | |
847 | int k, r; | |
848 | signed char active[BOARDMAX]; | |
849 | int other = OTHER_COLOR(board[entry->apos]); | |
850 | UNUSED(dummy); | |
851 | ||
852 | /* Remains to set the board. We let the active area be | |
853 | * the two strings to connect + | |
854 | * the connection shadow + | |
855 | * distance two expansion through empty intersections and own stones + | |
856 | * adjacent opponent strings + | |
857 | * liberties and neighbors of adjacent opponent strings with less than | |
858 | * five liberties + | |
859 | * liberties and neighbors of low liberty neighbors of adjacent opponent | |
860 | * strings with less than five liberties. | |
861 | */ | |
862 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
863 | active[pos] = connection_shadow[pos]; | |
864 | ||
865 | mark_string(entry->apos, active, 1); | |
866 | mark_string(entry->bpos, active, 1); | |
867 | ||
868 | /* To be safe, also add the successful move. */ | |
869 | if (entry->result != 0 && entry->move != 0) | |
870 | active[entry->move] = 1; | |
871 | ||
872 | /* Distance two expansion through empty intersections and own stones. */ | |
873 | for (k = 1; k < 3; k++) { | |
874 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
875 | if (!ON_BOARD(pos) || board[pos] == other || active[pos] != 0) | |
876 | continue; | |
877 | if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] == k) | |
878 | || (ON_BOARD(WEST(pos)) && active[WEST(pos)] == k) | |
879 | || (ON_BOARD(NORTH(pos)) && active[NORTH(pos)] == k) | |
880 | || (ON_BOARD(EAST(pos)) && active[EAST(pos)] == k)) { | |
881 | if (board[pos] == EMPTY) | |
882 | active[pos] = k + 1; | |
883 | else | |
884 | mark_string(pos, active, (signed char) (k + 1)); | |
885 | } | |
886 | } | |
887 | } | |
888 | ||
889 | /* Adjacent opponent strings. */ | |
890 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
891 | if (board[pos] != other || active[pos] != 0) | |
892 | continue; | |
893 | for (r = 0; r < 4; r++) { | |
894 | int pos2 = pos + delta[r]; | |
895 | if (ON_BOARD(pos2) && board[pos2] != other && active[pos2] != 0) { | |
896 | mark_string(pos, active, 1); | |
897 | break; | |
898 | } | |
899 | } | |
900 | } | |
901 | ||
902 | /* Liberties of adjacent opponent strings with less than five liberties + | |
903 | * liberties of low liberty neighbors of adjacent opponent strings | |
904 | * with less than five liberties. | |
905 | */ | |
906 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
907 | if (board[pos] == other && active[pos] > 0 && countlib(pos) < 5) { | |
908 | int libs[4]; | |
909 | int liberties = findlib(pos, 4, libs); | |
910 | int adjs[MAXCHAIN]; | |
911 | int adj; | |
912 | for (r = 0; r < liberties; r++) | |
913 | active[libs[r]] = 1; | |
914 | ||
915 | /* Also add liberties of neighbor strings if these are three | |
916 | * or less. | |
917 | */ | |
918 | adj = chainlinks(pos, adjs); | |
919 | for (r = 0; r < adj; r++) { | |
920 | mark_string(adjs[r], active, -1); | |
921 | if (countlib(adjs[r]) <= 3) { | |
922 | int s; | |
923 | int adjs2[MAXCHAIN]; | |
924 | int adj2; | |
925 | liberties = findlib(adjs[r], 3, libs); | |
926 | for (s = 0; s < liberties; s++) | |
927 | active[libs[s]] = 1; | |
928 | adj2 = chainlinks(pos, adjs2); | |
929 | for (s = 0; s < adj2; s++) | |
930 | mark_string(adjs2[s], active, -1); | |
931 | } | |
932 | } | |
933 | } | |
934 | } | |
935 | ||
936 | /* Also add the previously played stones to the active area. */ | |
937 | for (r = 0; r < stackp; r++) | |
938 | active[entry->stack[r]] = 1; | |
939 | ||
940 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
941 | int value = board[pos]; | |
942 | if (!ON_BOARD(pos)) | |
943 | continue; | |
944 | if (!active[pos]) | |
945 | value = GRAY; | |
946 | else if (IS_STONE(board[pos]) && countlib(pos) > 4 && active[pos] > 0) | |
947 | value |= HIGH_LIBERTY_BIT; | |
948 | ||
949 | entry->board[pos] = value; | |
950 | } | |
951 | ||
952 | } | |
953 | ||
954 | ||
955 | /* ================================================================ */ | |
956 | /* Break-in reading functions */ | |
957 | /* ================================================================ */ | |
958 | ||
959 | /* Look for a valid read result in the persistent breakin cache. | |
960 | * Return 1 if found, 0 otherwise. | |
961 | */ | |
962 | int | |
963 | search_persistent_breakin_cache(enum routine_id routine, | |
964 | int str, Hash_data *goal_hash, | |
965 | int node_limit, int *result, int *move) | |
966 | { | |
967 | return search_persistent_cache(&breakin_cache, routine, | |
968 | str, NO_MOVE, NO_MOVE, EMPTY, goal_hash, | |
969 | node_limit, result, NULL, move, NULL, NULL); | |
970 | } | |
971 | ||
972 | /* Store a new breakin result in the persistent cache. */ | |
973 | void | |
974 | store_persistent_breakin_cache(enum routine_id routine, | |
975 | int str, Hash_data *goal_hash, | |
976 | int result, int move, int tactical_nodes, | |
977 | int breakin_node_limit, | |
978 | signed char breakin_shadow[BOARDMAX]) | |
979 | { | |
980 | store_persistent_cache(&breakin_cache, routine, | |
981 | str, NO_MOVE, NO_MOVE, EMPTY, goal_hash, | |
982 | result, NO_MOVE, move, NO_MOVE, -1, breakin_node_limit, | |
983 | tactical_nodes, breakin_shadow, EMPTY); | |
984 | } | |
985 | ||
986 | ||
987 | /* Computes the active area for the current board position and the | |
988 | * read result that has just been stored in *entry. | |
989 | */ | |
990 | static void | |
991 | compute_active_breakin_area(struct persistent_cache_entry *entry, | |
992 | const signed char breakin_shadow[BOARDMAX], | |
993 | int dummy) | |
994 | { | |
995 | int pos; | |
996 | int k, r; | |
997 | signed char active[BOARDMAX]; | |
998 | int other = OTHER_COLOR(board[entry->apos]); | |
999 | UNUSED(dummy); | |
1000 | ||
1001 | /* We let the active area be | |
1002 | * the string to connect + | |
1003 | * the breakin shadow (which contains the goal) + | |
1004 | * distance two expansion through empty intersections and own stones + | |
1005 | * adjacent opponent strings + | |
1006 | * liberties and neighbors of adjacent opponent strings with less than | |
1007 | * five liberties + | |
1008 | * liberties and neighbors of low liberty neighbors of adjacent opponent | |
1009 | * strings with less than five liberties. | |
1010 | */ | |
1011 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1012 | active[pos] = breakin_shadow[pos]; | |
1013 | ||
1014 | mark_string(entry->apos, active, 1); | |
1015 | ||
1016 | /* To be safe, also add the successful move. */ | |
1017 | if (entry->result != 0 && entry->move != 0) | |
1018 | active[entry->move] = 1; | |
1019 | ||
1020 | /* Distance two expansion through empty intersections and own stones. */ | |
1021 | for (k = 1; k < 3; k++) { | |
1022 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1023 | if (!ON_BOARD(pos) || board[pos] == other || active[pos] != 0) | |
1024 | continue; | |
1025 | if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] == k) | |
1026 | || (ON_BOARD(WEST(pos)) && active[WEST(pos)] == k) | |
1027 | || (ON_BOARD(NORTH(pos)) && active[NORTH(pos)] == k) | |
1028 | || (ON_BOARD(EAST(pos)) && active[EAST(pos)] == k)) { | |
1029 | if (board[pos] == EMPTY) | |
1030 | active[pos] = k + 1; | |
1031 | else | |
1032 | mark_string(pos, active, (signed char) (k + 1)); | |
1033 | } | |
1034 | } | |
1035 | } | |
1036 | ||
1037 | /* Adjacent opponent strings. */ | |
1038 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1039 | if (board[pos] != other || active[pos] != 0) | |
1040 | continue; | |
1041 | for (r = 0; r < 4; r++) { | |
1042 | int pos2 = pos + delta[r]; | |
1043 | if (ON_BOARD(pos2) | |
1044 | && board[pos2] != other | |
1045 | && active[pos2] && active[pos2] <= 2) { | |
1046 | mark_string(pos, active, 1); | |
1047 | break; | |
1048 | } | |
1049 | } | |
1050 | } | |
1051 | ||
1052 | /* Liberties of adjacent opponent strings with less than four liberties + | |
1053 | * liberties of low liberty neighbors of adjacent opponent strings | |
1054 | * with less than five liberties. | |
1055 | */ | |
1056 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1057 | if (board[pos] == other && active[pos] > 0 && countlib(pos) < 4) { | |
1058 | int libs[4]; | |
1059 | int liberties = findlib(pos, 3, libs); | |
1060 | int adjs[MAXCHAIN]; | |
1061 | int adj; | |
1062 | for (r = 0; r < liberties; r++) | |
1063 | active[libs[r]] = 1; | |
1064 | ||
1065 | /* Also add liberties of neighbor strings if these are three | |
1066 | * or less. | |
1067 | */ | |
1068 | adj = chainlinks(pos, adjs); | |
1069 | for (r = 0; r < adj; r++) { | |
1070 | mark_string(adjs[r], active, -1); | |
1071 | if (countlib(adjs[r]) <= 3) { | |
1072 | int s; | |
1073 | int adjs2[MAXCHAIN]; | |
1074 | int adj2; | |
1075 | liberties = findlib(adjs[r], 3, libs); | |
1076 | for (s = 0; s < liberties; s++) | |
1077 | active[libs[s]] = 1; | |
1078 | adj2 = chainlinks(pos, adjs2); | |
1079 | for (s = 0; s < adj2; s++) | |
1080 | mark_string(adjs2[s], active, -1); | |
1081 | } | |
1082 | } | |
1083 | } | |
1084 | } | |
1085 | ||
1086 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1087 | Intersection value = board[pos]; | |
1088 | if (!ON_BOARD(pos)) | |
1089 | continue; | |
1090 | if (!active[pos]) | |
1091 | value = GRAY; | |
1092 | else if (IS_STONE(board[pos]) && countlib(pos) > 3 && active[pos] > 0) | |
1093 | value |= HIGH_LIBERTY_BIT2; | |
1094 | ||
1095 | entry->board[pos] = value; | |
1096 | } | |
1097 | } | |
1098 | ||
1099 | ||
1100 | /* ================================================================ */ | |
1101 | /* Owl reading functions */ | |
1102 | /* ================================================================ */ | |
1103 | int | |
1104 | search_persistent_owl_cache(enum routine_id routine, | |
1105 | int apos, int bpos, int cpos, | |
1106 | int *result, int *move, int *move2, int *certain) | |
1107 | { | |
1108 | return search_persistent_cache(&owl_cache, | |
1109 | routine, apos, bpos, cpos, EMPTY, NULL, | |
1110 | owl_node_limit, | |
1111 | result, NULL, move, move2, certain); | |
1112 | } | |
1113 | ||
1114 | ||
1115 | void | |
1116 | store_persistent_owl_cache(enum routine_id routine, | |
1117 | int apos, int bpos, int cpos, | |
1118 | int result, int move, int move2, int certain, | |
1119 | int tactical_nodes, | |
1120 | signed char goal[BOARDMAX], int goal_color) | |
1121 | { | |
1122 | store_persistent_cache(&owl_cache, routine, apos, bpos, cpos, EMPTY, NULL, | |
1123 | result, NO_MOVE, move, move2, certain, owl_node_limit, | |
1124 | tactical_nodes, goal, goal_color); | |
1125 | } | |
1126 | ||
1127 | ||
1128 | /* This function is used by owl and semai active area computation. We assume | |
1129 | * that (goal) marks a dragon of color (goal_color), i.e. all intersections | |
1130 | * in the goal that are not a stone of this color are ignored. The calling | |
1131 | * functions must have zeroed the active area, and is allowed to preset | |
1132 | * some intersection to be active. | |
1133 | */ | |
1134 | static void | |
1135 | compute_active_owl_type_area(const signed char goal[BOARDMAX], int goal_color, | |
1136 | signed char active[BOARDMAX]) | |
1137 | { | |
1138 | int k, r; | |
1139 | int pos; | |
1140 | int other = OTHER_COLOR(goal_color); | |
1141 | ||
1142 | /* We let the active area be the goal + | |
1143 | * distance four expansion through empty intersections and own stones + | |
1144 | * adjacent opponent strings + | |
1145 | * liberties and neighbors of adjacent opponent strings with less than | |
1146 | * five liberties + | |
1147 | * liberties and neighbors of low liberty neighbors of adjacent opponent | |
1148 | * strings with less than five liberties. | |
1149 | */ | |
1150 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1151 | if (ON_BOARD(pos) && goal[pos]) | |
1152 | active[pos] = 1; | |
1153 | ||
1154 | /* Distance four expansion through empty intersections and own stones. */ | |
1155 | for (k = 1; k < 5; k++) { | |
1156 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1157 | if (!ON_BOARD(pos) || board[pos] == other || active[pos] > 0) | |
1158 | continue; | |
1159 | if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] == k) | |
1160 | || (ON_BOARD(WEST(pos)) && active[WEST(pos)] == k) | |
1161 | || (ON_BOARD(NORTH(pos)) && active[NORTH(pos)] == k) | |
1162 | || (ON_BOARD(EAST(pos)) && active[EAST(pos)] == k)) { | |
1163 | if (board[pos] == EMPTY) | |
1164 | active[pos] = k + 1; | |
1165 | else | |
1166 | mark_string(pos, active, (signed char) (k + 1)); | |
1167 | } | |
1168 | } | |
1169 | } | |
1170 | ||
1171 | /* Adjacent opponent strings. */ | |
1172 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1173 | if (board[pos] != other || active[pos] != 0) | |
1174 | continue; | |
1175 | for (r = 0; r < 4; r++) { | |
1176 | int pos2 = pos + delta[r]; | |
1177 | if (ON_BOARD(pos2) && board[pos2] != other && active[pos2] != 0) { | |
1178 | mark_string(pos, active, 1); | |
1179 | break; | |
1180 | } | |
1181 | } | |
1182 | } | |
1183 | ||
1184 | /* Liberties of adjacent opponent strings with less than five liberties + | |
1185 | * liberties of low liberty neighbors of adjacent opponent strings | |
1186 | * with less than five liberties. | |
1187 | */ | |
1188 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1189 | if (board[pos] == other && active[pos] > 0 && countlib(pos) < 5) { | |
1190 | int libs[4]; | |
1191 | int liberties = findlib(pos, 4, libs); | |
1192 | int adjs[MAXCHAIN]; | |
1193 | int adj; | |
1194 | for (r = 0; r < liberties; r++) | |
1195 | active[libs[r]] = 1; | |
1196 | ||
1197 | /* Also add liberties of neighbor strings if these are three | |
1198 | * or less. | |
1199 | */ | |
1200 | adj = chainlinks(pos, adjs); | |
1201 | for (r = 0; r < adj; r++) { | |
1202 | mark_string(adjs[r], active, -1); | |
1203 | if (countlib(adjs[r]) <= 3) { | |
1204 | int s; | |
1205 | int adjs2[MAXCHAIN]; | |
1206 | int adj2; | |
1207 | liberties = findlib(adjs[r], 3, libs); | |
1208 | for (s = 0; s < liberties; s++) | |
1209 | active[libs[s]] = 1; | |
1210 | adj2 = chainlinks(pos, adjs2); | |
1211 | for (s = 0; s < adj2; s++) | |
1212 | mark_string(adjs2[s], active, -1); | |
1213 | } | |
1214 | } | |
1215 | } | |
1216 | } | |
1217 | } | |
1218 | ||
1219 | static void | |
1220 | compute_active_owl_area(struct persistent_cache_entry *entry, | |
1221 | const signed char goal[BOARDMAX], int goal_color) | |
1222 | { | |
1223 | int pos; | |
1224 | signed char active[BOARDMAX]; | |
1225 | memset(active, 0, BOARDMAX); | |
1226 | ||
1227 | /* Add critical moves to the active area. */ | |
1228 | if (ON_BOARD1(entry->move)) | |
1229 | active[entry->move] = 1; | |
1230 | ||
1231 | if (ON_BOARD1(entry->move2)) | |
1232 | active[entry->move2] = 1; | |
1233 | ||
1234 | compute_active_owl_type_area(goal, goal_color, active); | |
1235 | ||
1236 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1237 | int value = board[pos]; | |
1238 | if (!ON_BOARD(pos)) | |
1239 | continue; | |
1240 | if (!active[pos]) | |
1241 | value = GRAY; | |
1242 | else if (IS_STONE(board[pos]) && countlib(pos) > 4 && active[pos] > 0) | |
1243 | value |= HIGH_LIBERTY_BIT; | |
1244 | ||
1245 | entry->board[pos] = value; | |
1246 | } | |
1247 | } | |
1248 | ||
1249 | ||
1250 | /* ================================================================ */ | |
1251 | /* Semeai reading functions */ | |
1252 | /* ================================================================ */ | |
1253 | ||
1254 | /* Look for stored result in semeai cache. Returns 1 if result found, 0 | |
1255 | * otherwise. | |
1256 | */ | |
1257 | int | |
1258 | search_persistent_semeai_cache(enum routine_id routine, | |
1259 | int apos, int bpos, int cpos, int color, | |
1260 | Hash_data *goal_hash, | |
1261 | int *resulta, int *resultb, | |
1262 | int *move, int *certain) | |
1263 | { | |
1264 | return search_persistent_cache(&semeai_cache, routine, apos, bpos, cpos, | |
1265 | color, goal_hash, semeai_node_limit, | |
1266 | resulta, resultb, move, NULL, certain); | |
1267 | } | |
1268 | ||
1269 | ||
1270 | /* Store a new read result in the persistent semeai cache. */ | |
1271 | void | |
1272 | store_persistent_semeai_cache(enum routine_id routine, | |
1273 | int apos, int bpos, int cpos, int color, | |
1274 | Hash_data *goal_hash, | |
1275 | int resulta, int resultb, int move, int certain, | |
1276 | int tactical_nodes, | |
1277 | signed char goala[BOARDMAX], | |
1278 | signed char goalb[BOARDMAX]) | |
1279 | { | |
1280 | signed char goal[BOARDMAX]; | |
1281 | int pos; | |
1282 | ||
1283 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1284 | if (ON_BOARD(pos)) | |
1285 | goal[pos] = goala[pos] || goalb[pos]; | |
1286 | ||
1287 | store_persistent_cache(&semeai_cache, routine, | |
1288 | apos, bpos, cpos, color, goal_hash, | |
1289 | resulta, resultb, move, NO_MOVE, | |
1290 | certain, semeai_node_limit, | |
1291 | tactical_nodes, goal, EMPTY); | |
1292 | } | |
1293 | ||
1294 | ||
1295 | static void | |
1296 | compute_active_semeai_area(struct persistent_cache_entry *entry, | |
1297 | const signed char goal[BOARDMAX], int dummy) | |
1298 | { | |
1299 | int pos; | |
1300 | signed char active_b[BOARDMAX]; | |
1301 | signed char active_w[BOARDMAX]; | |
1302 | UNUSED(dummy); | |
1303 | memset(active_b, 0, BOARDMAX); | |
1304 | memset(active_w, 0, BOARDMAX); | |
1305 | ||
1306 | /* Add critical move to the active area. */ | |
1307 | if (ON_BOARD1(entry->move)) { | |
1308 | active_b[entry->move] = 1; | |
1309 | active_w[entry->move] = 1; | |
1310 | } | |
1311 | if (ON_BOARD1(entry->cpos)) { | |
1312 | active_b[entry->cpos] = 1; | |
1313 | active_w[entry->cpos] = 1; | |
1314 | } | |
1315 | ||
1316 | compute_active_owl_type_area(goal, BLACK, active_b); | |
1317 | compute_active_owl_type_area(goal, WHITE, active_w); | |
1318 | ||
1319 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1320 | int value = board[pos]; | |
1321 | if (!ON_BOARD(pos)) | |
1322 | continue; | |
1323 | if (!active_b[pos] && !active_w[pos]) | |
1324 | value = GRAY; | |
1325 | else if (IS_STONE(board[pos]) && countlib(pos) > 4 | |
1326 | && (active_b[pos] > 0 || active_w[pos] > 0)) | |
1327 | value |= HIGH_LIBERTY_BIT; | |
1328 | ||
1329 | entry->board[pos] = value; | |
1330 | } | |
1331 | } | |
1332 | ||
1333 | ||
1334 | ||
1335 | /* Helper for the owl_hotspots() function below. */ | |
1336 | static void | |
1337 | mark_dragon_hotspot_values(float values[BOARDMAX], int dr, | |
1338 | float contribution, | |
1339 | Intersection active_board[BOARDMAX]) | |
1340 | { | |
1341 | int pos; | |
1342 | int k; | |
1343 | if (!IS_STONE(board[dr])) | |
1344 | return; | |
1345 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1346 | if (board[pos] != EMPTY) | |
1347 | continue; | |
1348 | for (k = 0; k < 8; k++) { | |
1349 | int pos2 = pos + delta[k]; | |
1350 | if (IS_STONE(board[pos2]) | |
1351 | && (is_same_dragon(pos2, dr) | |
1352 | || (are_neighbor_dragons(pos2, dr) | |
1353 | && board[pos2] == board[dr])) | |
1354 | && (countlib(pos2) <= 4 | |
1355 | || is_edge_vertex(pos))) { | |
1356 | if (k < 4) { | |
1357 | if (is_same_dragon(pos2, dr)) | |
1358 | values[pos] += contribution; | |
1359 | else | |
1360 | values[pos] += 0.5 * contribution; | |
1361 | break; | |
1362 | } | |
1363 | else { | |
1364 | /* If pos2 = SOUTHWEST(pos), this construction makes | |
1365 | * pos3 = SOUTH(pos) and | |
1366 | * pos4 = WEST(pos) | |
1367 | * and corresponding for all other diagonal movements. | |
1368 | */ | |
1369 | int pos3 = pos + delta[k % 4]; | |
1370 | int pos4 = pos + delta[(k+1) % 4]; | |
1371 | if (board[pos3] == EMPTY || countlib(pos3) <= 2 | |
1372 | || board[pos4] == EMPTY || countlib(pos4) <= 2) | |
1373 | values[pos] += 0.5 * contribution; | |
1374 | break; | |
1375 | } | |
1376 | } | |
1377 | } | |
1378 | /* If not close to the dragon, but within the active area, give | |
1379 | * negative hotspot contribution. | |
1380 | */ | |
1381 | if (k == 8 && active_board[pos] == EMPTY) { | |
1382 | values[pos] -= 0.5 * contribution; | |
1383 | } | |
1384 | } | |
1385 | } | |
1386 | ||
1387 | ||
1388 | /* Based on the entries in the owl cache and their tactical_nodes | |
1389 | * field, compute where the relatively most expensive owl reading is | |
1390 | * going on. | |
1391 | */ | |
1392 | void | |
1393 | owl_hotspots(float values[BOARDMAX]) | |
1394 | { | |
1395 | int pos; | |
1396 | int k, r; | |
1397 | int libs[MAXLIBS]; | |
1398 | int liberties; | |
1399 | int sum_tactical_nodes = 0; | |
1400 | ||
1401 | /* Don't bother checking out of board. Set values[] to zero there too. */ | |
1402 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1403 | values[pos] = 0.0; | |
1404 | ||
1405 | /* Compute the total number of tactical nodes for the cached entries. */ | |
1406 | for (k = 0; k < owl_cache.current_size; k++) | |
1407 | sum_tactical_nodes += owl_cache.table[k].score; | |
1408 | ||
1409 | if (sum_tactical_nodes <= 100) | |
1410 | return; | |
1411 | ||
1412 | /* Loop over all entries and increase the value of vertices adjacent | |
1413 | * to dragons involving expensive owl reading. | |
1414 | */ | |
1415 | for (k = 0; k < owl_cache.current_size; k++) { | |
1416 | struct persistent_cache_entry *entry = &(owl_cache.table[k]); | |
1417 | float contribution = entry->score / (float) sum_tactical_nodes; | |
1418 | if (debug & DEBUG_PERSISTENT_CACHE) { | |
1419 | gprintf("Owl hotspots: %d %1m %f\n", entry->routine, entry->apos, | |
1420 | contribution); | |
1421 | } | |
1422 | switch (entry->routine) { | |
1423 | case OWL_ATTACK: | |
1424 | case OWL_THREATEN_ATTACK: | |
1425 | case OWL_DEFEND: | |
1426 | case OWL_THREATEN_DEFENSE: | |
1427 | mark_dragon_hotspot_values(values, entry->apos, | |
1428 | contribution, entry->board); | |
1429 | break; | |
1430 | case OWL_DOES_DEFEND: | |
1431 | case OWL_DOES_ATTACK: | |
1432 | case OWL_CONFIRM_SAFETY: | |
1433 | mark_dragon_hotspot_values(values, entry->bpos, | |
1434 | contribution, entry->board); | |
1435 | break; | |
1436 | case OWL_CONNECTION_DEFENDS: | |
1437 | mark_dragon_hotspot_values(values, entry->bpos, | |
1438 | contribution, entry->board); | |
1439 | mark_dragon_hotspot_values(values, entry->cpos, | |
1440 | contribution, entry->board); | |
1441 | break; | |
1442 | case OWL_SUBSTANTIAL: | |
1443 | /* Only consider the liberties of (apos). */ | |
1444 | if (!IS_STONE(board[entry->apos])) | |
1445 | continue; | |
1446 | liberties = findlib(entry->apos, MAXLIBS, libs); | |
1447 | for (r = 0; r < liberties; r++) | |
1448 | values[libs[r]] += contribution; | |
1449 | break; | |
1450 | default: | |
1451 | gg_assert(0); /* Shouldn't happen. */ | |
1452 | break; | |
1453 | } | |
1454 | } | |
1455 | } | |
1456 | ||
1457 | /* | |
1458 | * Local Variables: | |
1459 | * tab-width: 8 | |
1460 | * c-basic-offset: 2 | |
1461 | * End: | |
1462 | */ |