projects / sgk-go / blob
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Initial commit of GNU Go v3.8.
[sgk-go] / engine / persistent.c
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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
* the cache.
*
* 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.
*/
#include "gnugo.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "liberty.h"
#include "cache.h"
/* ================================================================ */
/* Data structures */
/* ================================================================ */
/* 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 {
int boardsize;
int movenum;
Intersection board[BOARDMAX];
int stack[MAX_CACHE_DEPTH];
int move_color[MAX_CACHE_DEPTH];
enum routine_id routine;
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 result;
int result2;
int result_certain;
int remaining_depth;
int node_limit;
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],
int goal_color);
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],
int goal_color);
static void compute_active_semeai_area(struct persistent_cache_entry *entry,
const signed char goal[BOARDMAX],
int dummy);
static void compute_active_reading_area(struct persistent_cache_entry *entry,
const signed char
reading_shadow[BOARDMAX],
int dummy);
static void compute_active_connection_area(struct persistent_cache_entry *entry,
const signed char
connection_shadow[BOARDMAX],
int goal_color);
static void compute_active_breakin_area(struct persistent_cache_entry *entry,
const signed char
breakin_shadow[BOARDMAX],
int dummy);
static struct persistent_cache reading_cache =
{ MAX_READING_CACHE_SIZE, MAX_READING_CACHE_DEPTH, 1.0,
"reading cache", compute_active_reading_area,
NULL, 0, -1 };
static struct persistent_cache connection_cache =
{ MAX_CONNECTION_CACHE_SIZE, MAX_CONNECTION_CACHE_DEPTH, 1.0,
"connection cache", compute_active_connection_area,
NULL, 0, -1 };
static struct persistent_cache breakin_cache =
{ MAX_BREAKIN_CACHE_SIZE, MAX_BREAKIN_CACHE_DEPTH, 0.75,
"breakin cache", compute_active_breakin_area,
NULL, 0, -1 };
static struct persistent_cache owl_cache =
{ MAX_OWL_CACHE_SIZE, MAX_OWL_CACHE_DEPTH, 1.0,
"owl cache", compute_active_owl_area,
NULL, 0, -1 };
static struct persistent_cache semeai_cache =
{ MAX_SEMEAI_CACHE_SIZE, MAX_SEMEAI_CACHE_DEPTH, 0.75,
"semeai cache", compute_active_semeai_area,
NULL, 0, -1 };
/* ================================================================ */
/* Common helper functions. */
static void
draw_active_area(Intersection board[BOARDMAX], int apos)
{
int i, j, ii;
int c = ' ';
int cw = (apos == NO_MOVE) ? 'O' : 'o';
int cb = (apos == NO_MOVE) ? 'X' : 'x';
start_draw_board();
for (i = 0; i < board_size; i++) {
ii = board_size - i;
fprintf(stderr, "\n%2d", ii);
for (j = 0; j < board_size; j++) {
int pos = POS(i, j);
if (board[pos] == EMPTY)
c = '.';
else if (board[pos] == WHITE)
c = cw;
else if ((board[pos] & 3) == WHITE)
c = 'O';
else if (board[pos] == BLACK)
c = cb;
else if ((board[pos] & 3) == BLACK)
c = 'X';
if (board[pos] == GRAY)
c = '?';
if (pos == apos)
fprintf(stderr, "[%c", c);
else if (j > 0 && POS(i, j-1) == apos)
fprintf(stderr, "]%c", c);
else
fprintf(stderr, " %c", c);
}
fprintf(stderr, " %d", ii);
}
end_draw_board();
}
/* Returns 1 if the stored board is compatible with the current board,
* 0 otherwise.
*/
static int
verify_stored_board(Intersection p[BOARDMAX])
{
int pos;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
else if (p[pos] == GRAY)
continue;
else if ((p[pos] & 3) != board[pos])
return 0;
else if (!(p[pos] & (HIGH_LIBERTY_BIT | HIGH_LIBERTY_BIT2)))
continue;
else if (((p[pos] & HIGH_LIBERTY_BIT) && countlib(pos) <= 4)
|| (p[pos] & HIGH_LIBERTY_BIT2 && countlib(pos) <= 3))
return 0;
}
return 1;
}
/* Prints out all relevant information for a cache entry, and prints
* a board showing the active area.
*/
static void
print_persistent_cache_entry(struct persistent_cache_entry *entry)
{
int r;
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));
if (entry->result2 != 0)
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)
break;
gprintf("%ostack[%d] = %C %1m\n", r, entry->move_color[r],
entry->stack[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. */
void
print_persistent_cache(struct persistent_cache *cache)
{
int k;
gprintf("Entire content of %s:\n", cache->name);
for (k = 0; k < cache->current_size; k++)
print_persistent_cache_entry(cache->table + k);
}
/* ================================================================ */
/* Core functions. */
/* ================================================================ */
/* 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_..
* function below.
*/
/* 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.
*/
static void
purge_persistent_cache(struct persistent_cache *cache)
{
int k;
int r;
gg_assert(stackp == 0);
/* Never do this more than once per move. */
if (cache->last_purge_position_number == position_number)
return;
else
cache->last_purge_position_number = position_number;
for (k = 0; k < cache->current_size; k++) {
int played_moves = 0;
int entry_ok = 1;
struct persistent_cache_entry *entry = &(cache->table[k]);
if (entry->boardsize != board_size)
entry_ok = 0;
else {
for (r = 0; r < MAX_CACHE_DEPTH; r++) {
int apos = entry->stack[r];
int color = entry->move_color[r];
if (apos == 0)
break;
if (board[apos] == EMPTY
&& trymove(apos, color, "purge_persistent_cache", 0))
played_moves++;
else {
entry_ok = 0;
break;
}
}
}
if (!entry_ok
|| !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.
*/
if (0)
gprintf("Purging entry %d from cache.\n", k);
if (k < cache->current_size - 1)
*entry = cache->table[cache->current_size - 1];
k--;
cache->current_size--;
}
else {
/* Reduce score here to penalize entries getting old. */
entry->score *= cache->age_factor;
}
while (played_moves > 0) {
popgo();
played_moves--;
}
}
}
/* 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,
int cpos, int color,
Hash_data *goal_hash, int node_limit)
{
int k;
for (k = 0; k < cache->current_size; k++) {
struct persistent_cache_entry *entry = cache->table + k;
if (entry->routine == routine
&& entry->apos == apos
&& entry->bpos == bpos
&& entry->cpos == cpos
&& entry->color == color
&& depth - stackp <= entry->remaining_depth
&& (entry->node_limit >= node_limit || entry->result_certain)
&& (goal_hash == NULL
|| hashdata_is_equal(entry->goal_hash, *goal_hash))
&& verify_stored_board(entry->board))
return entry;
}
return NULL;
}
/* 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.
*/
static int
search_persistent_cache(struct persistent_cache *cache,
enum routine_id routine, int apos, int bpos,
int cpos, int color,
Hash_data *goal_hash, int node_limit,
int *result, int *result2, int *move, int *move2,
int *certain)
{
/* Try to find entry. */
struct persistent_cache_entry *entry;
entry = find_persistent_cache_entry(cache, routine, apos, bpos, cpos, color,
goal_hash, node_limit);
if (entry == NULL)
return 0;
/* Set return values. */
*result = entry->result;
if (result2)
*result2 = entry->result2;
if (move)
*move = entry->move;
if (move2)
*move2 = entry->move2;
if (certain)
*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) {
if (entry->result != 0)
gprintf("%o%s %1m = %d %1m, cached (%d nodes) ",
routine == ATTACK ? "attack" : "defend",
apos, entry->result, entry->move, entry->cost);
else
gprintf("%o%s %1m = %d, cached (%d nodes) ",
routine == ATTACK ? "attack" : "defend",
apos, entry->result, entry->cost);
dump_stack();
}
return 1;
}
/* 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
* function.
*/
static void
store_persistent_cache(struct persistent_cache *cache,
enum routine_id routine,
int apos, int bpos, int cpos, int color,
Hash_data *goal_hash,
int result, int result2, int move, int move2,
int certain, int node_limit,
int cost, const signed char goal[BOARDMAX],
int goal_color)
{
int r;
struct persistent_cache_entry *entry;
if (stackp > cache->max_stackp)
return;
/* If cache is still full, consider kicking out an old entry. */
if (cache->current_size == cache->max_size) {
int worst_entry = -1;
int worst_score = cost;
int k;
for (k = 0; k < cache->current_size; k++) {
if (cache->table[k].score < worst_score) {
worst_score = cache->table[k].score;
worst_entry = k;
}
}
if (worst_entry != -1) {
/* 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];
cache->current_size--;
}
else
return;
}
entry = &(cache->table[cache->current_size]);
entry->boardsize = board_size;
entry->routine = routine;
entry->apos = apos;
entry->bpos = bpos;
entry->cpos = cpos;
entry->color = color;
if (goal_hash)
entry->goal_hash = *goal_hash;
entry->result = result;
entry->result2 = result2;
entry->result_certain = certain;
entry->node_limit = node_limit;
entry->remaining_depth = depth - stackp;
entry->move = move;
entry->move2 = move2;
entry->score = cost;
entry->cost = cost;
entry->movenum = movenum;
for (r = 0; r < MAX_CACHE_DEPTH; r++) {
if (r < stackp)
get_move_from_stack(r, &(entry->stack[r]), &(entry->move_color[r]));
else {
entry->stack[r] = 0;
entry->move_color[r] = EMPTY;
}
}
/* Remains to set the board. */
cache->compute_active_area(&(cache->table[cache->current_size]),
goal, goal_color);
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. */
static void
init_cache(struct persistent_cache *cache)
{
cache->table = malloc(cache->max_size*sizeof(struct persistent_cache_entry));
gg_assert(cache->table);
}
/* Initializes all persistent caches.
* Needs to be called only once at startup.
*/
void
persistent_cache_init()
{
init_cache(&reading_cache);
init_cache(&breakin_cache);
init_cache(&connection_cache);
init_cache(&owl_cache);
init_cache(&semeai_cache);
}
/* Discards all persistent cache entries. */
void
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).
*/
void
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.
*/
int
search_persistent_reading_cache(enum routine_id routine, int str,
int *result, int *move)
{
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. */
void
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,
nodes, shadow, EMPTY);
}
static void
compute_active_reading_area(struct persistent_cache_entry *entry,
const signed char goal[BOARDMAX], int dummy)
{
signed char active[BOARDMAX];
int pos, r;
UNUSED(dummy);
/* 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
* to empty.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
active[pos] = goal[pos];
mark_string(entry->apos, active, 1);
/* To be safe, also add the successful move. */
if (entry->result != 0 && entry->move != 0)
active[entry->move] = 1;
/* Add adjacent strings and empty. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
if (active[pos] != 0)
continue;
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);
else
active[pos] = 2;
}
}
/* Remove invincible strings. No point adding their liberties and
* neighbors.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
if (IS_STONE(board[pos]) && worm[pos].invincible)
active[pos] = 0;
}
/* Expand empty to empty. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (IS_STONE(board[pos]) || active[pos] != 0)
continue;
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))
active[pos] = 3;
}
/* Add neighbors of active area so far. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
if (active[pos] != 0)
continue;
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))
active[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++) {
if (!ON_BOARD(pos))
continue;
entry->board[pos] =
active[pos] != 0 ? board[pos] : GRAY;
}
}
/* Helper for the reading_hotspots() function below. */
static void
mark_string_hotspot_values(float values[BOARDMAX],
int m, int n, float contribution)
{
int i, j, k;
/* 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;
return;
}
/* 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)
continue;
for (k = 0; k < 8; k++) {
int di = deltai[k];
int dj = deltaj[k];
if (IS_STONE(BOARD(i+di, j+dj))
&& same_string(POS(i+di, j+dj), POS(m, n))) {
if (k < 4) {
values[POS(i, j)] += contribution;
break;
}
else {
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;
break;
}
}
}
}
}
/* Based on the entries in the reading cache and their nodes field,
* compute where the relatively most expensive tactical reading is
* going on.
*/
void
reading_hotspots(float values[BOARDMAX])
{
int pos;
int k;
int sum_nodes = 0;
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
values[pos] = 0.0;
/* 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;
if (sum_nodes <= 100)
return;
/* 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;
if (0) {
gprintf("Reading hotspots: %d %1m %f\n", entry->routine, entry->apos,
contribution);
}
switch (entry->routine) {
case ATTACK:
case FIND_DEFENSE:
mark_string_hotspot_values(values, I(entry->apos), J(entry->apos),
contribution);
break;
default:
gg_assert(0); /* Shouldn't happen. */
break;
}
}
}
/* ================================================================ */
/* Connection reading functions */
/* ================================================================ */
/* Look for a valid read result in the persistent connection cache.
* Return 1 if found, 0 otherwise.
*/
int
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,
connection_node_limit,
result, NULL, move, NULL, NULL);
}
/* Store a new connection result in the persistent cache. */
void
store_persistent_connection_cache(enum routine_id routine,
int str1, int str2,
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,
connection_node_limit,
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.
*/
static void
compute_active_connection_area(struct persistent_cache_entry *entry,
const signed char connection_shadow[BOARDMAX],
int dummy)
{
int pos;
int k, r;
signed char active[BOARDMAX];
int other = OTHER_COLOR(board[entry->apos]);
UNUSED(dummy);
/* 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
* five liberties +
* 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)
active[entry->move] = 1;
/* 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)
continue;
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)) {
if (board[pos] == EMPTY)
active[pos] = k + 1;
else
mark_string(pos, active, (signed char) (k + 1));
}
}
}
/* Adjacent opponent strings. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] != other || active[pos] != 0)
continue;
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);
break;
}
}
}
/* 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 libs[4];
int liberties = findlib(pos, 4, libs);
int adjs[MAXCHAIN];
int adj;
for (r = 0; r < liberties; r++)
active[libs[r]] = 1;
/* Also add liberties of neighbor strings if these are three
* or less.
*/
adj = chainlinks(pos, adjs);
for (r = 0; r < adj; r++) {
mark_string(adjs[r], active, -1);
if (countlib(adjs[r]) <= 3) {
int s;
int adjs2[MAXCHAIN];
int adj2;
liberties = findlib(adjs[r], 3, libs);
for (s = 0; s < liberties; s++)
active[libs[s]] = 1;
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++) {
int value = board[pos];
if (!ON_BOARD(pos))
continue;
if (!active[pos])
value = GRAY;
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.
*/
int
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. */
void
store_persistent_breakin_cache(enum routine_id routine,
int str, Hash_data *goal_hash,
int result, int move, int tactical_nodes,
int breakin_node_limit,
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.
*/
static void
compute_active_breakin_area(struct persistent_cache_entry *entry,
const signed char breakin_shadow[BOARDMAX],
int dummy)
{
int pos;
int k, r;
signed char active[BOARDMAX];
int other = OTHER_COLOR(board[entry->apos]);
UNUSED(dummy);
/* 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
* five liberties +
* 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)
active[entry->move] = 1;
/* 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)
continue;
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)) {
if (board[pos] == EMPTY)
active[pos] = k + 1;
else
mark_string(pos, active, (signed char) (k + 1));
}
}
}
/* Adjacent opponent strings. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] != other || active[pos] != 0)
continue;
for (r = 0; r < 4; r++) {
int pos2 = pos + delta[r];
if (ON_BOARD(pos2)
&& board[pos2] != other
&& active[pos2] && active[pos2] <= 2) {
mark_string(pos, active, 1);
break;
}
}
}
/* 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 libs[4];
int liberties = findlib(pos, 3, libs);
int adjs[MAXCHAIN];
int adj;
for (r = 0; r < liberties; r++)
active[libs[r]] = 1;
/* Also add liberties of neighbor strings if these are three
* or less.
*/
adj = chainlinks(pos, adjs);
for (r = 0; r < adj; r++) {
mark_string(adjs[r], active, -1);
if (countlib(adjs[r]) <= 3) {
int s;
int adjs2[MAXCHAIN];
int adj2;
liberties = findlib(adjs[r], 3, libs);
for (s = 0; s < liberties; s++)
active[libs[s]] = 1;
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];
if (!ON_BOARD(pos))
continue;
if (!active[pos])
value = GRAY;
else if (IS_STONE(board[pos]) && countlib(pos) > 3 && active[pos] > 0)
value |= HIGH_LIBERTY_BIT2;
entry->board[pos] = value;
}
}
/* ================================================================ */
/* Owl reading functions */
/* ================================================================ */
int
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,
owl_node_limit,
result, NULL, move, move2, certain);
}
void
store_persistent_owl_cache(enum routine_id routine,
int apos, int bpos, int cpos,
int result, int move, int move2, int certain,
int tactical_nodes,
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.
*/
static void
compute_active_owl_type_area(const signed char goal[BOARDMAX], int goal_color,
signed char active[BOARDMAX])
{
int k, r;
int pos;
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
* five liberties +
* 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])
active[pos] = 1;
/* 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)
continue;
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)) {
if (board[pos] == EMPTY)
active[pos] = k + 1;
else
mark_string(pos, active, (signed char) (k + 1));
}
}
}
/* Adjacent opponent strings. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] != other || active[pos] != 0)
continue;
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);
break;
}
}
}
/* 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 libs[4];
int liberties = findlib(pos, 4, libs);
int adjs[MAXCHAIN];
int adj;
for (r = 0; r < liberties; r++)
active[libs[r]] = 1;
/* Also add liberties of neighbor strings if these are three
* or less.
*/
adj = chainlinks(pos, adjs);
for (r = 0; r < adj; r++) {
mark_string(adjs[r], active, -1);
if (countlib(adjs[r]) <= 3) {
int s;
int adjs2[MAXCHAIN];
int adj2;
liberties = findlib(adjs[r], 3, libs);
for (s = 0; s < liberties; s++)
active[libs[s]] = 1;
adj2 = chainlinks(pos, adjs2);
for (s = 0; s < adj2; s++)
mark_string(adjs2[s], active, -1);
}
}
}
}
}
static void
compute_active_owl_area(struct persistent_cache_entry *entry,
const signed char goal[BOARDMAX], int goal_color)
{
int pos;
signed char active[BOARDMAX];
memset(active, 0, BOARDMAX);
/* Add critical moves to the active area. */
if (ON_BOARD1(entry->move))
active[entry->move] = 1;
if (ON_BOARD1(entry->move2))
active[entry->move2] = 1;
compute_active_owl_type_area(goal, goal_color, active);
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
int value = board[pos];
if (!ON_BOARD(pos))
continue;
if (!active[pos])
value = GRAY;
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
* otherwise.
*/
int
search_persistent_semeai_cache(enum routine_id routine,
int apos, int bpos, int cpos, int color,
Hash_data *goal_hash,
int *resulta, int *resultb,
int *move, int *certain)
{
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. */
void
store_persistent_semeai_cache(enum routine_id routine,
int apos, int bpos, int cpos, int color,
Hash_data *goal_hash,
int resulta, int resultb, int move, int certain,
int tactical_nodes,
signed char goala[BOARDMAX],
signed char goalb[BOARDMAX])
{
signed char goal[BOARDMAX];
int pos;
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(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);
}
static void
compute_active_semeai_area(struct persistent_cache_entry *entry,
const signed char goal[BOARDMAX], int dummy)
{
int pos;
signed char active_b[BOARDMAX];
signed char active_w[BOARDMAX];
UNUSED(dummy);
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++) {
int value = board[pos];
if (!ON_BOARD(pos))
continue;
if (!active_b[pos] && !active_w[pos])
value = GRAY;
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. */
static void
mark_dragon_hotspot_values(float values[BOARDMAX], int dr,
float contribution,
Intersection active_board[BOARDMAX])
{
int pos;
int k;
if (!IS_STONE(board[dr]))
return;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] != EMPTY)
continue;
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]))
&& (countlib(pos2) <= 4
|| is_edge_vertex(pos))) {
if (k < 4) {
if (is_same_dragon(pos2, dr))
values[pos] += contribution;
else
values[pos] += 0.5 * contribution;
break;
}
else {
/* If pos2 = SOUTHWEST(pos), this construction makes
* pos3 = SOUTH(pos) and
* pos4 = WEST(pos)
* 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;
break;
}
}
}
/* 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
* going on.
*/
void
owl_hotspots(float values[BOARDMAX])
{
int pos;
int k, r;
int libs[MAXLIBS];
int liberties;
int sum_tactical_nodes = 0;
/* Don't bother checking out of board. Set values[] to zero there too. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
values[pos] = 0.0;
/* 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)
return;
/* 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,
contribution);
}
switch (entry->routine) {
case OWL_ATTACK:
case OWL_THREATEN_ATTACK:
case OWL_DEFEND:
case OWL_THREATEN_DEFENSE:
mark_dragon_hotspot_values(values, entry->apos,
contribution, entry->board);
break;
case OWL_DOES_DEFEND:
case OWL_DOES_ATTACK:
case OWL_CONFIRM_SAFETY:
mark_dragon_hotspot_values(values, entry->bpos,
contribution, entry->board);
break;
case OWL_CONNECTION_DEFENDS:
mark_dragon_hotspot_values(values, entry->bpos,
contribution, entry->board);
mark_dragon_hotspot_values(values, entry->cpos,
contribution, entry->board);
break;
case OWL_SUBSTANTIAL:
/* Only consider the liberties of (apos). */
if (!IS_STONE(board[entry->apos]))
continue;
liberties = findlib(entry->apos, MAXLIBS, libs);
for (r = 0; r < liberties; r++)
values[libs[r]] += contribution;
break;
default:
gg_assert(0); /* Shouldn't happen. */
break;
}
}
}
/*
* Local Variables:
* tab-width: 8
* c-basic-offset: 2
* End:
*/
Fork of GNU Go supporting Xeon Phi coprocessors (and other modifications).