/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 by the Free Software Foundation. *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation - version 3 or *
* (at your option) any later version. *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License in file COPYING for more details. *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
* The code in this file implements persistent caching.
* The idea is that reading results are stored together with an
* "active area", i.e. the part of the board having an effect on the
* reading result. Thus if only moves outside of the active area has
* been played since the result was stored, it can be reused.
* The active areas are not known exactly but are estimated
* heuristically. The effects are that too large an active area
* reduces the efficiency of the caching scheme while too small an
* active area may cause an incorrect read result to be retrieved from
* Persistent caching has so far been implemented for tactical reading,
* owl reading, connection reading and break-in reading (with semeai
* reading planned for the future).
* The hotspot functions are intended to locate where the most
* expensive reading of either type is going on. This information can
* be estimated from the contents of the persistent caches since the
* most expensive readings are stored there with full information of
* spent reading nodes, involved strings or dragons, and active areas.
/* ================================================================ */
/* ================================================================ */
/* Used in active area. */
#define HIGH_LIBERTY_BIT 4
#define HIGH_LIBERTY_BIT2 8
#define MAX_READING_CACHE_DEPTH 5
#define MAX_READING_CACHE_SIZE 100
#define MAX_OWL_CACHE_DEPTH 0
#define MAX_OWL_CACHE_SIZE 150
#define MAX_CONNECTION_CACHE_DEPTH 5
#define MAX_CONNECTION_CACHE_SIZE 100
#define MAX_BREAKIN_CACHE_DEPTH 1
#define MAX_BREAKIN_CACHE_SIZE 150
#define MAX_SEMEAI_CACHE_DEPTH 0
#define MAX_SEMEAI_CACHE_SIZE 150
#define MAX_CACHE_DEPTH 5
/* We use the same data structure for all of the caches. Some of the entries
* below are unused for some of the caches.
struct persistent_cache_entry
{
Intersection board
[BOARDMAX
];
int stack
[MAX_CACHE_DEPTH
];
int move_color
[MAX_CACHE_DEPTH
];
int apos
; /* first input coordinate */
int bpos
; /* second input coordinate */
int cpos
; /* third input coordinate */
int color
; /* Move at (cpos) by (color) in analyze_semeai_after_move() */
Hash_data goal_hash
; /* hash of the goals in break-in and semeai reading */
int move
; /* first result coordinate */
int move2
;/* second result coordinate */
int cost
; /* Usually no. of tactical nodes spent on this reading result. */
int score
; /* Heuristic guess of the worth of the cache entry. */
/* Callback function that implements the computation of the active area.
* This function has to be provided by each cache.
typedef void (*compute_active_area_fn
)(struct persistent_cache_entry
*entry
,
const signed char goal
[BOARDMAX
],
struct persistent_cache
{
const int max_size
; /* Size of above array. */
const int max_stackp
; /* Don't store positions with stackp > max_stackp. */
const float age_factor
; /* Reduce value of old entries with this factor. */
const char *name
; /* For debugging purposes. */
const compute_active_area_fn compute_active_area
;
struct persistent_cache_entry
*table
; /* Array of actual results. */
int current_size
; /* Current number of entries. */
int last_purge_position_number
;
static void compute_active_owl_area(struct persistent_cache_entry
*entry
,
const signed char goal
[BOARDMAX
],
static void compute_active_semeai_area(struct persistent_cache_entry
*entry
,
const signed char goal
[BOARDMAX
],
static void compute_active_reading_area(struct persistent_cache_entry
*entry
,
reading_shadow
[BOARDMAX
],
static void compute_active_connection_area(struct persistent_cache_entry
*entry
,
connection_shadow
[BOARDMAX
],
static void compute_active_breakin_area(struct persistent_cache_entry
*entry
,
breakin_shadow
[BOARDMAX
],
static struct persistent_cache reading_cache
=
{ MAX_READING_CACHE_SIZE
, MAX_READING_CACHE_DEPTH
, 1.0,
"reading cache", compute_active_reading_area
,
static struct persistent_cache connection_cache
=
{ MAX_CONNECTION_CACHE_SIZE
, MAX_CONNECTION_CACHE_DEPTH
, 1.0,
"connection cache", compute_active_connection_area
,
static struct persistent_cache breakin_cache
=
{ MAX_BREAKIN_CACHE_SIZE
, MAX_BREAKIN_CACHE_DEPTH
, 0.75,
"breakin cache", compute_active_breakin_area
,
static struct persistent_cache owl_cache
=
{ MAX_OWL_CACHE_SIZE
, MAX_OWL_CACHE_DEPTH
, 1.0,
"owl cache", compute_active_owl_area
,
static struct persistent_cache semeai_cache
=
{ MAX_SEMEAI_CACHE_SIZE
, MAX_SEMEAI_CACHE_DEPTH
, 0.75,
"semeai cache", compute_active_semeai_area
,
/* ================================================================ */
/* Common helper functions. */
draw_active_area(Intersection board
[BOARDMAX
], int apos
)
int cw
= (apos
== NO_MOVE
) ? 'O' : 'o';
int cb
= (apos
== NO_MOVE
) ? 'X' : 'x';
for (i
= 0; i
< board_size
; i
++) {
fprintf(stderr
, "\n%2d", ii
);
for (j
= 0; j
< board_size
; j
++) {
else if (board
[pos
] == WHITE
)
else if ((board
[pos
] & 3) == WHITE
)
else if (board
[pos
] == BLACK
)
else if ((board
[pos
] & 3) == BLACK
)
fprintf(stderr
, "[%c", c
);
else if (j
> 0 && POS(i
, j
-1) == apos
)
fprintf(stderr
, "]%c", c
);
fprintf(stderr
, " %c", c
);
fprintf(stderr
, " %d", ii
);
/* Returns 1 if the stored board is compatible with the current board,
verify_stored_board(Intersection p
[BOARDMAX
])
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
else if ((p
[pos
] & 3) != board
[pos
])
else if (!(p
[pos
] & (HIGH_LIBERTY_BIT
| HIGH_LIBERTY_BIT2
)))
else if (((p
[pos
] & HIGH_LIBERTY_BIT
) && countlib(pos
) <= 4)
|| (p
[pos
] & HIGH_LIBERTY_BIT2
&& countlib(pos
) <= 3))
/* Prints out all relevant information for a cache entry, and prints
* a board showing the active area.
print_persistent_cache_entry(struct persistent_cache_entry
*entry
)
gprintf("%omovenum = %d\n", entry
->movenum
);
gprintf("%oscore = %d\n", entry
->score
);
gprintf("%ocost = %d\n", entry
->cost
);
gprintf("%oroutine = %s\n", routine_id_to_string(entry
->routine
));
gprintf("%oapos = %1m\n", entry
->apos
);
if (entry
->bpos
!= NO_MOVE
)
gprintf("%obpos = %1m\n", entry
->bpos
);
if (entry
->cpos
!= NO_MOVE
)
gprintf("%ocpos = %1m\n", entry
->cpos
);
gprintf("%oresult = %s\n", result_to_string(entry
->result
));
gprintf("%oresult2 = %s\n", result_to_string(entry
->result2
));
if (entry
->result_certain
!= -1)
gprintf("%oresult_certain = %d\n", entry
->result_certain
);
if (entry
->node_limit
!= -1)
gprintf("%onode_limit = %d\n", entry
->node_limit
);
if (entry
->move
!= NO_MOVE
)
gprintf("%omove = %1m\n", entry
->move
);
if (entry
->move2
!= NO_MOVE
)
gprintf("%omove2 = %1m\n", entry
->move2
);
for (r
= 0; r
< MAX_CACHE_DEPTH
; r
++) {
if (entry
->stack
[r
] == 0)
gprintf("%ostack[%d] = %C %1m\n", r
, entry
->move_color
[r
],
draw_active_area(entry
->board
, entry
->apos
);
/* To keep GCC happy and have the function included in the
* gnugo executable. Can be used from gdb.
void print_persistent_cache(struct persistent_cache
*cache
);
/* Can be used from gdb. */
print_persistent_cache(struct persistent_cache
*cache
)
gprintf("Entire content of %s:\n", cache
->name
);
for (k
= 0; k
< cache
->current_size
; k
++)
print_persistent_cache_entry(cache
->table
+ k
);
/* ================================================================ */
/* ================================================================ */
/* The static functions below implement the core infrastructure of the
* persistent caches. Each cache only has to provide a function
* computing the active area, and wrappers around the search_.. and store_..
/* Remove persistent cache entries which are no longer compatible with
* the board. For efficient use of the cache, it's recommended to call
* this function once per move, before starting the owl reading. It's
* not required for correct operation though.
purge_persistent_cache(struct persistent_cache
*cache
)
/* Never do this more than once per move. */
if (cache
->last_purge_position_number
== position_number
)
cache
->last_purge_position_number
= position_number
;
for (k
= 0; k
< cache
->current_size
; k
++) {
struct persistent_cache_entry
*entry
= &(cache
->table
[k
]);
if (entry
->boardsize
!= board_size
)
for (r
= 0; r
< MAX_CACHE_DEPTH
; r
++) {
int apos
= entry
->stack
[r
];
int color
= entry
->move_color
[r
];
&& trymove(apos
, color
, "purge_persistent_cache", 0))
|| !verify_stored_board(entry
->board
)) {
/* Move the last entry in the cache here and back up the loop
* counter to redo the test at this position in the cache.
gprintf("Purging entry %d from cache.\n", k
);
if (k
< cache
->current_size
- 1)
*entry
= cache
->table
[cache
->current_size
- 1];
/* Reduce score here to penalize entries getting old. */
entry
->score
*= cache
->age_factor
;
while (played_moves
> 0) {
/* Find a cache entry matching the data given in the parameters.
* Important: We assume that unused parameters are normalized to NO_MOVE
* when storing or retrieving, so that we can ignore them here.
static struct persistent_cache_entry
*
find_persistent_cache_entry(struct persistent_cache
*cache
,
enum routine_id routine
, int apos
, int bpos
,
Hash_data
*goal_hash
, int node_limit
)
for (k
= 0; k
< cache
->current_size
; k
++) {
struct persistent_cache_entry
*entry
= cache
->table
+ k
;
if (entry
->routine
== routine
&& depth
- stackp
<= entry
->remaining_depth
&& (entry
->node_limit
>= node_limit
|| entry
->result_certain
)
|| hashdata_is_equal(entry
->goal_hash
, *goal_hash
))
&& verify_stored_board(entry
->board
))
/* Search through a persistent cache. Returns 0 if no matching entry was
* found; returns 1 and sets the relevant return values otherwise. See
* comment above find_persistent_cache_entry() about unused parameters.
search_persistent_cache(struct persistent_cache
*cache
,
enum routine_id routine
, int apos
, int bpos
,
Hash_data
*goal_hash
, int node_limit
,
int *result
, int *result2
, int *move
, int *move2
,
struct persistent_cache_entry
*entry
;
entry
= find_persistent_cache_entry(cache
, routine
, apos
, bpos
, cpos
, color
,
*result2
= entry
->result2
;
*certain
= entry
->result_certain
;
/* Increase score for entry. */
entry
->score
+= entry
->cost
;
if (debug
& DEBUG_PERSISTENT_CACHE
) {
gprintf("%oRetrieved position from %s:\n", cache
->name
);
print_persistent_cache_entry(entry
);
/* FIXME: This is an ugly hack. */
if (strcmp(cache
->name
, "reading cache") == 0
&& (debug
& DEBUG_READING_PERFORMANCE
)
&& entry
->cost
>= MIN_READING_NODES_TO_REPORT
) {
gprintf("%o%s %1m = %d %1m, cached (%d nodes) ",
routine
== ATTACK
? "attack" : "defend",
apos
, entry
->result
, entry
->move
, entry
->cost
);
gprintf("%o%s %1m = %d, cached (%d nodes) ",
routine
== ATTACK
? "attack" : "defend",
apos
, entry
->result
, entry
->cost
);
/* Generic function that tries to store a cache entry. If the cache
* is full, we delete the lowest scoring entry.
* Unused parameters have to be normalized to NO_MOVE by the calling
store_persistent_cache(struct persistent_cache
*cache
,
int apos
, int bpos
, int cpos
, int color
,
int result
, int result2
, int move
, int move2
,
int certain
, int node_limit
,
int cost
, const signed char goal
[BOARDMAX
],
struct persistent_cache_entry
*entry
;
if (stackp
> cache
->max_stackp
)
/* If cache is still full, consider kicking out an old entry. */
if (cache
->current_size
== cache
->max_size
) {
for (k
= 0; k
< cache
->current_size
; k
++) {
if (cache
->table
[k
].score
< worst_score
) {
worst_score
= cache
->table
[k
].score
;
/* Move the last entry in the cache here to make space.
if (worst_entry
< cache
->current_size
- 1)
cache
->table
[worst_entry
] = cache
->table
[cache
->current_size
- 1];
entry
= &(cache
->table
[cache
->current_size
]);
entry
->boardsize
= board_size
;
entry
->routine
= routine
;
entry
->goal_hash
= *goal_hash
;
entry
->result2
= result2
;
entry
->result_certain
= certain
;
entry
->node_limit
= node_limit
;
entry
->remaining_depth
= depth
- stackp
;
entry
->movenum
= movenum
;
for (r
= 0; r
< MAX_CACHE_DEPTH
; r
++) {
get_move_from_stack(r
, &(entry
->stack
[r
]), &(entry
->move_color
[r
]));
entry
->move_color
[r
] = EMPTY
;
/* Remains to set the board. */
cache
->compute_active_area(&(cache
->table
[cache
->current_size
]),
if (debug
& DEBUG_PERSISTENT_CACHE
) {
gprintf("%oEntered position in %s:\n", cache
->name
);
print_persistent_cache_entry(entry
);
gprintf("%oCurrent size: %d\n", cache
->current_size
);
/* ================================================================ */
/* Interface functions relevant to all caches. */
/* ================================================================ */
/* Allocate the actual cache table. */
init_cache(struct persistent_cache
*cache
)
cache
->table
= malloc(cache
->max_size
*sizeof(struct persistent_cache_entry
));
/* Initializes all persistent caches.
* Needs to be called only once at startup.
init_cache(&reading_cache
);
init_cache(&breakin_cache
);
init_cache(&connection_cache
);
init_cache(&semeai_cache
);
/* Discards all persistent cache entries. */
clear_persistent_caches()
reading_cache
.current_size
= 0;
connection_cache
.current_size
= 0;
breakin_cache
.current_size
= 0;
owl_cache
.current_size
= 0;
semeai_cache
.current_size
= 0;
/* Discards all persistent cache entries that are no longer useful.
* Should be called once per move for optimal performance (but is not
* necessary for proper operation).
purge_persistent_caches()
purge_persistent_cache(&reading_cache
);
purge_persistent_cache(&connection_cache
);
purge_persistent_cache(&breakin_cache
);
purge_persistent_cache(&owl_cache
);
purge_persistent_cache(&semeai_cache
);
/* ================================================================ */
/* Tactical reading functions */
/* ================================================================ */
/* Look for a valid read result in the persistent cache.
* Return 1 if found, 0 otherwise.
search_persistent_reading_cache(enum routine_id routine
, int str
,
return search_persistent_cache(&reading_cache
,
routine
, str
, NO_MOVE
, NO_MOVE
, EMPTY
, NULL
,
-1, result
, NULL
, move
, NULL
, NULL
);
/* Store a new read result in the persistent cache. */
store_persistent_reading_cache(enum routine_id routine
, int str
,
int result
, int move
, int nodes
)
store_persistent_cache(&reading_cache
, routine
,
str
, NO_MOVE
, NO_MOVE
, EMPTY
, NULL
,
result
, NO_MOVE
, move
, NO_MOVE
, -1, -1,
compute_active_reading_area(struct persistent_cache_entry
*entry
,
const signed char goal
[BOARDMAX
], int dummy
)
signed char active
[BOARDMAX
];
/* Remains to set the board. We let the active area be the contested
* string and reading shadow + adjacent empty and strings +
* neighbors of active area so far + one more expansion from empty
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
mark_string(entry
->apos
, active
, 1);
/* To be safe, also add the successful move. */
if (entry
->result
!= 0 && entry
->move
!= 0)
/* Add adjacent strings and empty. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if ((ON_BOARD(SOUTH(pos
)) && active
[SOUTH(pos
)] == 1)
|| (ON_BOARD(WEST(pos
)) && active
[WEST(pos
)] == 1)
|| (ON_BOARD(NORTH(pos
)) && active
[NORTH(pos
)] == 1)
|| (ON_BOARD(EAST(pos
)) && active
[EAST(pos
)] == 1)) {
if (IS_STONE(board
[pos
]))
mark_string(pos
, active
, 2);
/* Remove invincible strings. No point adding their liberties and
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
]) && worm
[pos
].invincible
)
/* Expand empty to empty. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
]) || active
[pos
] != 0)
if ((board
[SOUTH(pos
)] == EMPTY
&& active
[SOUTH(pos
)] == 2)
|| (board
[WEST(pos
)] == EMPTY
&& active
[WEST(pos
)] == 2)
|| (board
[NORTH(pos
)] == EMPTY
&& active
[NORTH(pos
)] == 2)
|| (board
[EAST(pos
)] == EMPTY
&& active
[EAST(pos
)] == 2))
/* Add neighbors of active area so far. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if ((ON_BOARD(SOUTH(pos
)) && active
[SOUTH(pos
)] > 0
&& active
[SOUTH(pos
)] < 4)
|| (ON_BOARD(WEST(pos
)) && active
[WEST(pos
)] > 0
&& active
[WEST(pos
)] < 4)
|| (ON_BOARD(NORTH(pos
)) && active
[NORTH(pos
)] > 0
&& active
[NORTH(pos
)] < 4)
|| (ON_BOARD(EAST(pos
)) && active
[EAST(pos
)] > 0
&& active
[EAST(pos
)] < 4))
/* Also add the previously played stones to the active area. */
for (r
= 0; r
< stackp
; r
++)
active
[entry
->stack
[r
]] = 5;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
active
[pos
] != 0 ? board
[pos
] : GRAY
;
/* Helper for the reading_hotspots() function below. */
mark_string_hotspot_values(float values
[BOARDMAX
],
int m
, int n
, float contribution
)
/* If p[m][n] is EMPTY, we just give the contribution to close empty
* vertices. This is a rough simplification.
if (BOARD(m
, n
) == EMPTY
) {
for (i
= -1; i
<= 1; i
++)
for (j
= -1; j
<= 1; j
++)
if (BOARD(m
+i
, n
+j
) == EMPTY
)
values
[POS(m
+i
, n
+j
)] += contribution
;
/* Otherwise we give contribution to liberties and diagonal
* neighbors of the string at (m, n).
for (i
= 0; i
< board_size
; i
++)
for (j
= 0; j
< board_size
; j
++) {
if (BOARD(i
, j
) != EMPTY
)
for (k
= 0; k
< 8; k
++) {
if (IS_STONE(BOARD(i
+di
, j
+dj
))
&& same_string(POS(i
+di
, j
+dj
), POS(m
, n
))) {
values
[POS(i
, j
)] += contribution
;
if (BOARD(i
+di
, j
) == EMPTY
|| countlib(POS(i
+di
, j
)) <= 2
|| BOARD(i
, j
+dj
) == EMPTY
|| countlib(POS(i
, j
+dj
)) <= 2)
values
[POS(i
, j
)] += contribution
;
/* Based on the entries in the reading cache and their nodes field,
* compute where the relatively most expensive tactical reading is
reading_hotspots(float values
[BOARDMAX
])
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
/* Compute the total number of nodes for the cached entries. */
for (k
= 0; k
< reading_cache
.current_size
; k
++)
sum_nodes
+= reading_cache
.table
[k
].cost
;
/* Loop over all entries and increase the value of vertices adjacent
* to dragons involving expensive tactical reading.
for (k
= 0; k
< reading_cache
.current_size
; k
++) {
struct persistent_cache_entry
*entry
= &(reading_cache
.table
[k
]);
float contribution
= entry
->cost
/ (float) sum_nodes
;
gprintf("Reading hotspots: %d %1m %f\n", entry
->routine
, entry
->apos
,
switch (entry
->routine
) {
mark_string_hotspot_values(values
, I(entry
->apos
), J(entry
->apos
),
gg_assert(0); /* Shouldn't happen. */
/* ================================================================ */
/* Connection reading functions */
/* ================================================================ */
/* Look for a valid read result in the persistent connection cache.
* Return 1 if found, 0 otherwise.
search_persistent_connection_cache(enum routine_id routine
, int str1
,
int str2
, int *result
, int *move
)
return search_persistent_cache(&connection_cache
, routine
,
str1
, str2
, NO_MOVE
, EMPTY
, NULL
,
result
, NULL
, move
, NULL
, NULL
);
/* Store a new connection result in the persistent cache. */
store_persistent_connection_cache(enum routine_id routine
,
int result
, int move
, int tactical_nodes
,
signed char connection_shadow
[BOARDMAX
])
store_persistent_cache(&connection_cache
, routine
,
str1
, str2
, NO_MOVE
, EMPTY
, NULL
,
result
, NO_MOVE
, move
, NO_MOVE
, -1,
tactical_nodes
, connection_shadow
, EMPTY
);
/* Computes the active area for the current board position and the
* connection read result that has just been stored in *entry.
compute_active_connection_area(struct persistent_cache_entry
*entry
,
const signed char connection_shadow
[BOARDMAX
],
signed char active
[BOARDMAX
];
int other
= OTHER_COLOR(board
[entry
->apos
]);
/* Remains to set the board. We let the active area be
* the two strings to connect +
* the connection shadow +
* distance two expansion through empty intersections and own stones +
* adjacent opponent strings +
* liberties and neighbors of adjacent opponent strings with less than
* liberties and neighbors of low liberty neighbors of adjacent opponent
* strings with less than five liberties.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
active
[pos
] = connection_shadow
[pos
];
mark_string(entry
->apos
, active
, 1);
mark_string(entry
->bpos
, active
, 1);
/* To be safe, also add the successful move. */
if (entry
->result
!= 0 && entry
->move
!= 0)
/* Distance two expansion through empty intersections and own stones. */
for (k
= 1; k
< 3; k
++) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || board
[pos
] == other
|| active
[pos
] != 0)
if ((ON_BOARD(SOUTH(pos
)) && active
[SOUTH(pos
)] == k
)
|| (ON_BOARD(WEST(pos
)) && active
[WEST(pos
)] == k
)
|| (ON_BOARD(NORTH(pos
)) && active
[NORTH(pos
)] == k
)
|| (ON_BOARD(EAST(pos
)) && active
[EAST(pos
)] == k
)) {
mark_string(pos
, active
, (signed char) (k
+ 1));
/* Adjacent opponent strings. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] != other
|| active
[pos
] != 0)
for (r
= 0; r
< 4; r
++) {
int pos2
= pos
+ delta
[r
];
if (ON_BOARD(pos2
) && board
[pos2
] != other
&& active
[pos2
] != 0) {
mark_string(pos
, active
, 1);
/* Liberties of adjacent opponent strings with less than five liberties +
* liberties of low liberty neighbors of adjacent opponent strings
* with less than five liberties.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == other
&& active
[pos
] > 0 && countlib(pos
) < 5) {
int liberties
= findlib(pos
, 4, libs
);
for (r
= 0; r
< liberties
; r
++)
/* Also add liberties of neighbor strings if these are three
adj
= chainlinks(pos
, adjs
);
for (r
= 0; r
< adj
; r
++) {
mark_string(adjs
[r
], active
, -1);
if (countlib(adjs
[r
]) <= 3) {
liberties
= findlib(adjs
[r
], 3, libs
);
for (s
= 0; s
< liberties
; s
++)
adj2
= chainlinks(pos
, adjs2
);
for (s
= 0; s
< adj2
; s
++)
mark_string(adjs2
[s
], active
, -1);
/* Also add the previously played stones to the active area. */
for (r
= 0; r
< stackp
; r
++)
active
[entry
->stack
[r
]] = 1;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
else if (IS_STONE(board
[pos
]) && countlib(pos
) > 4 && active
[pos
] > 0)
value
|= HIGH_LIBERTY_BIT
;
entry
->board
[pos
] = value
;
/* ================================================================ */
/* Break-in reading functions */
/* ================================================================ */
/* Look for a valid read result in the persistent breakin cache.
* Return 1 if found, 0 otherwise.
search_persistent_breakin_cache(enum routine_id routine
,
int str
, Hash_data
*goal_hash
,
int node_limit
, int *result
, int *move
)
return search_persistent_cache(&breakin_cache
, routine
,
str
, NO_MOVE
, NO_MOVE
, EMPTY
, goal_hash
,
node_limit
, result
, NULL
, move
, NULL
, NULL
);
/* Store a new breakin result in the persistent cache. */
store_persistent_breakin_cache(enum routine_id routine
,
int str
, Hash_data
*goal_hash
,
int result
, int move
, int tactical_nodes
,
signed char breakin_shadow
[BOARDMAX
])
store_persistent_cache(&breakin_cache
, routine
,
str
, NO_MOVE
, NO_MOVE
, EMPTY
, goal_hash
,
result
, NO_MOVE
, move
, NO_MOVE
, -1, breakin_node_limit
,
tactical_nodes
, breakin_shadow
, EMPTY
);
/* Computes the active area for the current board position and the
* read result that has just been stored in *entry.
compute_active_breakin_area(struct persistent_cache_entry
*entry
,
const signed char breakin_shadow
[BOARDMAX
],
signed char active
[BOARDMAX
];
int other
= OTHER_COLOR(board
[entry
->apos
]);
/* We let the active area be
* the string to connect +
* the breakin shadow (which contains the goal) +
* distance two expansion through empty intersections and own stones +
* adjacent opponent strings +
* liberties and neighbors of adjacent opponent strings with less than
* liberties and neighbors of low liberty neighbors of adjacent opponent
* strings with less than five liberties.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
active
[pos
] = breakin_shadow
[pos
];
mark_string(entry
->apos
, active
, 1);
/* To be safe, also add the successful move. */
if (entry
->result
!= 0 && entry
->move
!= 0)
/* Distance two expansion through empty intersections and own stones. */
for (k
= 1; k
< 3; k
++) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || board
[pos
] == other
|| active
[pos
] != 0)
if ((ON_BOARD(SOUTH(pos
)) && active
[SOUTH(pos
)] == k
)
|| (ON_BOARD(WEST(pos
)) && active
[WEST(pos
)] == k
)
|| (ON_BOARD(NORTH(pos
)) && active
[NORTH(pos
)] == k
)
|| (ON_BOARD(EAST(pos
)) && active
[EAST(pos
)] == k
)) {
mark_string(pos
, active
, (signed char) (k
+ 1));
/* Adjacent opponent strings. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] != other
|| active
[pos
] != 0)
for (r
= 0; r
< 4; r
++) {
int pos2
= pos
+ delta
[r
];
&& active
[pos2
] && active
[pos2
] <= 2) {
mark_string(pos
, active
, 1);
/* Liberties of adjacent opponent strings with less than four liberties +
* liberties of low liberty neighbors of adjacent opponent strings
* with less than five liberties.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == other
&& active
[pos
] > 0 && countlib(pos
) < 4) {
int liberties
= findlib(pos
, 3, libs
);
for (r
= 0; r
< liberties
; r
++)
/* Also add liberties of neighbor strings if these are three
adj
= chainlinks(pos
, adjs
);
for (r
= 0; r
< adj
; r
++) {
mark_string(adjs
[r
], active
, -1);
if (countlib(adjs
[r
]) <= 3) {
liberties
= findlib(adjs
[r
], 3, libs
);
for (s
= 0; s
< liberties
; s
++)
adj2
= chainlinks(pos
, adjs2
);
for (s
= 0; s
< adj2
; s
++)
mark_string(adjs2
[s
], active
, -1);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
Intersection value
= board
[pos
];
else if (IS_STONE(board
[pos
]) && countlib(pos
) > 3 && active
[pos
] > 0)
value
|= HIGH_LIBERTY_BIT2
;
entry
->board
[pos
] = value
;
/* ================================================================ */
/* Owl reading functions */
/* ================================================================ */
search_persistent_owl_cache(enum routine_id routine
,
int apos
, int bpos
, int cpos
,
int *result
, int *move
, int *move2
, int *certain
)
return search_persistent_cache(&owl_cache
,
routine
, apos
, bpos
, cpos
, EMPTY
, NULL
,
result
, NULL
, move
, move2
, certain
);
store_persistent_owl_cache(enum routine_id routine
,
int apos
, int bpos
, int cpos
,
int result
, int move
, int move2
, int certain
,
signed char goal
[BOARDMAX
], int goal_color
)
store_persistent_cache(&owl_cache
, routine
, apos
, bpos
, cpos
, EMPTY
, NULL
,
result
, NO_MOVE
, move
, move2
, certain
, owl_node_limit
,
tactical_nodes
, goal
, goal_color
);
/* This function is used by owl and semai active area computation. We assume
* that (goal) marks a dragon of color (goal_color), i.e. all intersections
* in the goal that are not a stone of this color are ignored. The calling
* functions must have zeroed the active area, and is allowed to preset
* some intersection to be active.
compute_active_owl_type_area(const signed char goal
[BOARDMAX
], int goal_color
,
signed char active
[BOARDMAX
])
int other
= OTHER_COLOR(goal_color
);
/* We let the active area be the goal +
* distance four expansion through empty intersections and own stones +
* adjacent opponent strings +
* liberties and neighbors of adjacent opponent strings with less than
* liberties and neighbors of low liberty neighbors of adjacent opponent
* strings with less than five liberties.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && goal
[pos
])
/* Distance four expansion through empty intersections and own stones. */
for (k
= 1; k
< 5; k
++) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || board
[pos
] == other
|| active
[pos
] > 0)
if ((ON_BOARD(SOUTH(pos
)) && active
[SOUTH(pos
)] == k
)
|| (ON_BOARD(WEST(pos
)) && active
[WEST(pos
)] == k
)
|| (ON_BOARD(NORTH(pos
)) && active
[NORTH(pos
)] == k
)
|| (ON_BOARD(EAST(pos
)) && active
[EAST(pos
)] == k
)) {
mark_string(pos
, active
, (signed char) (k
+ 1));
/* Adjacent opponent strings. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] != other
|| active
[pos
] != 0)
for (r
= 0; r
< 4; r
++) {
int pos2
= pos
+ delta
[r
];
if (ON_BOARD(pos2
) && board
[pos2
] != other
&& active
[pos2
] != 0) {
mark_string(pos
, active
, 1);
/* Liberties of adjacent opponent strings with less than five liberties +
* liberties of low liberty neighbors of adjacent opponent strings
* with less than five liberties.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == other
&& active
[pos
] > 0 && countlib(pos
) < 5) {
int liberties
= findlib(pos
, 4, libs
);
for (r
= 0; r
< liberties
; r
++)
/* Also add liberties of neighbor strings if these are three
adj
= chainlinks(pos
, adjs
);
for (r
= 0; r
< adj
; r
++) {
mark_string(adjs
[r
], active
, -1);
if (countlib(adjs
[r
]) <= 3) {
liberties
= findlib(adjs
[r
], 3, libs
);
for (s
= 0; s
< liberties
; s
++)
adj2
= chainlinks(pos
, adjs2
);
for (s
= 0; s
< adj2
; s
++)
mark_string(adjs2
[s
], active
, -1);
compute_active_owl_area(struct persistent_cache_entry
*entry
,
const signed char goal
[BOARDMAX
], int goal_color
)
signed char active
[BOARDMAX
];
memset(active
, 0, BOARDMAX
);
/* Add critical moves to the active area. */
if (ON_BOARD1(entry
->move
))
if (ON_BOARD1(entry
->move2
))
active
[entry
->move2
] = 1;
compute_active_owl_type_area(goal
, goal_color
, active
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
else if (IS_STONE(board
[pos
]) && countlib(pos
) > 4 && active
[pos
] > 0)
value
|= HIGH_LIBERTY_BIT
;
entry
->board
[pos
] = value
;
/* ================================================================ */
/* Semeai reading functions */
/* ================================================================ */
/* Look for stored result in semeai cache. Returns 1 if result found, 0
search_persistent_semeai_cache(enum routine_id routine
,
int apos
, int bpos
, int cpos
, int color
,
int *resulta
, int *resultb
,
return search_persistent_cache(&semeai_cache
, routine
, apos
, bpos
, cpos
,
color
, goal_hash
, semeai_node_limit
,
resulta
, resultb
, move
, NULL
, certain
);
/* Store a new read result in the persistent semeai cache. */
store_persistent_semeai_cache(enum routine_id routine
,
int apos
, int bpos
, int cpos
, int color
,
int resulta
, int resultb
, int move
, int certain
,
signed char goala
[BOARDMAX
],
signed char goalb
[BOARDMAX
])
signed char goal
[BOARDMAX
];
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
goal
[pos
] = goala
[pos
] || goalb
[pos
];
store_persistent_cache(&semeai_cache
, routine
,
apos
, bpos
, cpos
, color
, goal_hash
,
resulta
, resultb
, move
, NO_MOVE
,
certain
, semeai_node_limit
,
tactical_nodes
, goal
, EMPTY
);
compute_active_semeai_area(struct persistent_cache_entry
*entry
,
const signed char goal
[BOARDMAX
], int dummy
)
signed char active_b
[BOARDMAX
];
signed char active_w
[BOARDMAX
];
memset(active_b
, 0, BOARDMAX
);
memset(active_w
, 0, BOARDMAX
);
/* Add critical move to the active area. */
if (ON_BOARD1(entry
->move
)) {
active_b
[entry
->move
] = 1;
active_w
[entry
->move
] = 1;
if (ON_BOARD1(entry
->cpos
)) {
active_b
[entry
->cpos
] = 1;
active_w
[entry
->cpos
] = 1;
compute_active_owl_type_area(goal
, BLACK
, active_b
);
compute_active_owl_type_area(goal
, WHITE
, active_w
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!active_b
[pos
] && !active_w
[pos
])
else if (IS_STONE(board
[pos
]) && countlib(pos
) > 4
&& (active_b
[pos
] > 0 || active_w
[pos
] > 0))
value
|= HIGH_LIBERTY_BIT
;
entry
->board
[pos
] = value
;
/* Helper for the owl_hotspots() function below. */
mark_dragon_hotspot_values(float values
[BOARDMAX
], int dr
,
Intersection active_board
[BOARDMAX
])
if (!IS_STONE(board
[dr
]))
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
for (k
= 0; k
< 8; k
++) {
int pos2
= pos
+ delta
[k
];
if (IS_STONE(board
[pos2
])
&& (is_same_dragon(pos2
, dr
)
|| (are_neighbor_dragons(pos2
, dr
)
&& board
[pos2
] == board
[dr
]))
|| is_edge_vertex(pos
))) {
if (is_same_dragon(pos2
, dr
))
values
[pos
] += contribution
;
values
[pos
] += 0.5 * contribution
;
/* If pos2 = SOUTHWEST(pos), this construction makes
* and corresponding for all other diagonal movements.
int pos3
= pos
+ delta
[k
% 4];
int pos4
= pos
+ delta
[(k
+1) % 4];
if (board
[pos3
] == EMPTY
|| countlib(pos3
) <= 2
|| board
[pos4
] == EMPTY
|| countlib(pos4
) <= 2)
values
[pos
] += 0.5 * contribution
;
/* If not close to the dragon, but within the active area, give
* negative hotspot contribution.
if (k
== 8 && active_board
[pos
] == EMPTY
) {
values
[pos
] -= 0.5 * contribution
;
/* Based on the entries in the owl cache and their tactical_nodes
* field, compute where the relatively most expensive owl reading is
owl_hotspots(float values
[BOARDMAX
])
int sum_tactical_nodes
= 0;
/* Don't bother checking out of board. Set values[] to zero there too. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
/* Compute the total number of tactical nodes for the cached entries. */
for (k
= 0; k
< owl_cache
.current_size
; k
++)
sum_tactical_nodes
+= owl_cache
.table
[k
].score
;
if (sum_tactical_nodes
<= 100)
/* Loop over all entries and increase the value of vertices adjacent
* to dragons involving expensive owl reading.
for (k
= 0; k
< owl_cache
.current_size
; k
++) {
struct persistent_cache_entry
*entry
= &(owl_cache
.table
[k
]);
float contribution
= entry
->score
/ (float) sum_tactical_nodes
;
if (debug
& DEBUG_PERSISTENT_CACHE
) {
gprintf("Owl hotspots: %d %1m %f\n", entry
->routine
, entry
->apos
,
switch (entry
->routine
) {
case OWL_THREATEN_ATTACK
:
case OWL_THREATEN_DEFENSE
:
mark_dragon_hotspot_values(values
, entry
->apos
,
contribution
, entry
->board
);
mark_dragon_hotspot_values(values
, entry
->bpos
,
contribution
, entry
->board
);
case OWL_CONNECTION_DEFENDS
:
mark_dragon_hotspot_values(values
, entry
->bpos
,
contribution
, entry
->board
);
mark_dragon_hotspot_values(values
, entry
->cpos
,
contribution
, entry
->board
);
/* Only consider the liberties of (apos). */
if (!IS_STONE(board
[entry
->apos
]))
liberties
= findlib(entry
->apos
, MAXLIBS
, libs
);
for (r
= 0; r
< liberties
; r
++)
values
[libs
[r
]] += contribution
;
gg_assert(0); /* Shouldn't happen. */