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 / optics.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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include "gnugo.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "liberty.h"
#include "eyes.h"
#include "gg_utils.h"
#define MAXEYE 20
/* This structure is used in communication between read_eye() and
* recognize_eye().
*/
struct vital_points {
int attacks[4 * MAXEYE];
int defenses[4 * MAXEYE];
int num_attacks;
int num_defenses;
};
static void
compute_primary_domains(int color, int domain[BOARDMAX],
int lively[BOARDMAX],
int false_margins[BOARDMAX],
int first_time);
static void count_neighbours(struct eye_data eyedata[BOARDMAX]);
static int is_lively(int owl_call, int pos);
static int false_margin(int pos, int color, int lively[BOARDMAX]);
static void originate_eye(int origin, int pos,
int *esize, int *msize,
struct eye_data eye[BOARDMAX]);
static int read_eye(int pos, int *attack_point, int *defense_point,
struct eyevalue *value,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
int add_moves);
static int recognize_eye(int pos, int *attack_point, int *defense_point,
struct eyevalue *value,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
struct vital_points *vp);
static void guess_eye_space(int pos, int effective_eyesize, int margins,
int bulk_score, struct eye_data eye[BOARDMAX],
struct eyevalue *value, int *pessimistic_min);
static void reset_map(int size);
static void first_map(int *map_value);
static int next_map(int *q, int map[MAXEYE]);
static void print_eye(struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX], int pos);
static void add_false_eye(int pos, struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX]);
static float topological_eye(int pos, int color,
struct eye_data my_eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX]);
static float evaluate_diagonal_intersection(int m, int n, int color,
int *attack_point,
int *defense_point,
struct eye_data my_eye[BOARDMAX]);
/* These are used during the calculations of eye spaces. */
static int black_domain[BOARDMAX];
static int white_domain[BOARDMAX];
/* Used internally by mapping functions. */
static int map_size;
static signed char used_index[MAXEYE];
/*
* make_domains() is called from make_dragons() and from
* owl_determine_life(). It marks the black and white domains
* (eyeshape regions) and collects some statistics about each one.
*/
void
make_domains(struct eye_data b_eye[BOARDMAX],
struct eye_data w_eye[BOARDMAX],
int owl_call)
{
int k;
int pos;
int lively[BOARDMAX];
int false_margins[BOARDMAX];
memset(black_domain, 0, sizeof(black_domain));
memset(white_domain, 0, sizeof(white_domain));
memset(false_margins, 0, sizeof(false_margins));
if (b_eye)
memset(b_eye, 0, BOARDMAX * sizeof(b_eye[0]));
if (w_eye)
memset(w_eye, 0, BOARDMAX * sizeof(w_eye[0]));
/* Initialize eye data and compute the lively array. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos))
lively[pos] = is_lively(owl_call, pos);
/* Compute the domains of influence of each color. */
compute_primary_domains(BLACK, black_domain, lively, false_margins, 1);
compute_primary_domains(WHITE, white_domain, lively, false_margins, 0);
/* Now we fill out the arrays b_eye and w_eye with data describing
* each eye shape.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
if (board[pos] == EMPTY || !lively[pos]) {
if (black_domain[pos] == 0 && white_domain[pos] == 0) {
if (w_eye)
w_eye[pos].color = GRAY;
if (b_eye)
b_eye[pos].color = GRAY;
}
else if (black_domain[pos] == 1 && white_domain[pos] == 0 && b_eye) {
b_eye[pos].color = BLACK;
for (k = 0; k < 4; k++) {
int apos = pos + delta[k];
if (ON_BOARD(apos) && white_domain[apos] && !black_domain[apos]) {
b_eye[pos].marginal = 1;
break;
}
}
}
else if (black_domain[pos] == 0 && white_domain[pos] == 1 && w_eye) {
w_eye[pos].color = WHITE;
for (k = 0; k < 4; k++) {
int apos = pos + delta[k];
if (ON_BOARD(apos) && black_domain[apos] && !white_domain[apos]) {
w_eye[pos].marginal = 1;
break;
}
}
}
else if (black_domain[pos] == 1 && white_domain[pos] == 1) {
if (b_eye) {
for (k = 0; k < 4; k++) {
int apos = pos + delta[k];
if (ON_BOARD(apos) && black_domain[apos]
&& !white_domain[apos]) {
b_eye[pos].marginal = 1;
b_eye[pos].color = BLACK;
break;
}
}
if (k == 4)
b_eye[pos].color = GRAY;
}
if (w_eye) {
for (k = 0; k < 4; k++) {
int apos = pos + delta[k];
if (ON_BOARD(apos) && white_domain[apos]
&& !black_domain[apos]) {
w_eye[pos].marginal = 1;
w_eye[pos].color = WHITE;
break;
}
}
if (k == 4)
w_eye[pos].color = GRAY;
}
}
}
}
/* The eye spaces are all found. Now we need to find the origins. */
partition_eyespaces(b_eye, BLACK);
partition_eyespaces(w_eye, WHITE);
}
/* Find connected eyespace components and compute relevant statistics. */
void
partition_eyespaces(struct eye_data eye[BOARDMAX], int color)
{
int pos;
if (!eye)
return;
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos))
eye[pos].origin = NO_MOVE;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
if (eye[pos].origin == NO_MOVE && eye[pos].color == color) {
int esize = 0;
int msize = 0;
originate_eye(pos, pos, &esize, &msize, eye);
eye[pos].esize = esize;
eye[pos].msize = msize;
}
}
/* Now we count the number of neighbors and marginal neighbors
* of each vertex.
*/
count_neighbours(eye);
}
/* Compute the domains of influence of each color, used in determining
* eye shapes. NOTE: the term influence as used here is distinct from the
* influence in influence.c.
*
* For this algorithm the strings which are not lively are invisible. Ignoring
* these, the algorithm assigns friendly influence to:
*
* (1) every vertex which is occupied by a (lively) friendly stone,
* (2) every empty vertex adjoining a (lively) friendly stone,
* (3) every empty vertex for which two adjoining vertices (not
* on the first line) in the (usually 8) surrounding ones have friendly
* influence, with two CAVEATS explained below.
*
* Thus in the following diagram, e would be assigned friendly influence
* if a and b have friendly influence, or a and d. It is not sufficent
* for b and d to have friendly influence, because they are not adjoining.
*
* uabc
* def
* ghi
*
* The constraint that the two adjoining vertices not lie on the first
* line prevents influence from leaking under a stone on the third line.
*
* The first CAVEAT alluded to above is that even if a and b have friendly
* influence, this does not cause e to have friendly influence if there
* is a lively opponent stone at d. This constraint prevents
* influence from leaking past knight's move extensions.
*
* The second CAVEAT is that even if a and b have friendly influence
* this does not cause e to have influence if there are lively opponent
* stones at u and at c. This prevents influence from leaking past
* nikken tobis (two space jumps).
*
* The corner vertices are handled slightly different.
*
* +---
* |ab
* |cd
*
* We get friendly influence at a if we have friendly influence
* at b or c and no lively unfriendly stone at b, c or d.
*
*/
#define sufficient_influence(pos, apos, bpos) \
(ON_BOARD(bpos) && influence[bpos] > threshold[pos] - influence[apos])
static void
compute_primary_domains(int color, int domain[BOARDMAX],
int lively[BOARDMAX],
int false_margins[BOARDMAX],
int first_time)
{
int other = OTHER_COLOR(color);
int i, j, k;
int pos, pos2;
int own, enemy;
signed char threshold[BOARDMAX];
signed char influence[BOARDMAX];
int list[BOARDMAX];
int size = 0, lastchange = 0;
memset(threshold, 0, sizeof(threshold));
memset(influence, 0, sizeof(influence));
/* In the first pass we
* 1. Give influence to lively own stones and their neighbors.
* (Cases (1) and (2) above.)
* 2. Fill influence[] and threshold[] arrays with initial values.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos))
continue;
if (lively[pos]) {
if (board[pos] == color) {
domain[pos] = 1; /* Case (1) above. */
influence[pos] = 1;
}
else
influence[pos] = -1;
continue;
}
own = enemy = 0;
for (k = 0; k < 4; k++) {
pos2 = pos + delta[k];
if (ON_BOARD(pos2) && lively[pos2]) {
if (board[pos2] == color)
own = 1;
else
enemy = 1;
}
}
if (own) {
/* To explain the asymmetry between the first time around
* this loop and subsequent ones, a false margin is adjacent
* to both B and W lively stones, so it's found on the first
* pass through the loop.
*/
if (first_time) {
if (board[pos] == EMPTY && (false_margin(pos, color, lively)
|| false_margin(pos, other, lively)))
false_margins[pos] = 1;
else {
domain[pos] = 1;
influence[pos] = 1;
}
}
else if (board[pos] != EMPTY || !false_margins[pos]) {
domain[pos] = 1;
influence[pos] = 1;
}
}
else
list[size++] = pos;
if (enemy) {
threshold[pos] = 1;
influence[pos]--;
}
else if (is_edge_vertex(pos))
influence[pos]--;
}
/* Now we loop over the board until no more vertices can be added to
* the domain through case (3) above.
*/
if (size) {
k = size;
while (1) {
if (!k)
k = size;
pos = list[--k];
/* Case (3) above. */
if (sufficient_influence(pos, SOUTH(pos), SE(pos))
|| sufficient_influence(pos, SOUTH(pos), SW(pos))
|| sufficient_influence(pos, EAST(pos), SE(pos))
|| sufficient_influence(pos, EAST(pos), NE(pos))
|| sufficient_influence(pos, WEST(pos), SW(pos))
|| sufficient_influence(pos, WEST(pos), NW(pos))
|| sufficient_influence(pos, NORTH(pos), NW(pos))
|| sufficient_influence(pos, NORTH(pos), NE(pos))) {
domain[pos] = 1;
influence[pos]++;
if (!--size)
break;
if (k < size)
list[k] = list[size];
else
k--;
lastchange = k;
}
else if (k == lastchange)
break; /* Looped the whole list and found nothing new */
}
}
if (0 && (debug & DEBUG_EYES)) {
start_draw_board();
for (i = 0; i < board_size; i++)
for (j = 0; j < board_size; j++) {
draw_color_char(i, j, domain[POS(i, j)] ? '1' : '0', GG_COLOR_BLACK);
}
end_draw_board();
}
}
static void
count_neighbours(struct eye_data eyedata[BOARDMAX])
{
int pos;
int k;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos) || eyedata[pos].origin == NO_MOVE)
continue;
eyedata[pos].esize = eyedata[eyedata[pos].origin].esize;
eyedata[pos].msize = eyedata[eyedata[pos].origin].msize;
eyedata[pos].neighbors = 0;
eyedata[pos].marginal_neighbors = 0;
for (k = 0; k < 4; k++) {
int pos2 = pos + delta[k];
if (ON_BOARD(pos2) && eyedata[pos2].origin == eyedata[pos].origin) {
eyedata[pos].neighbors++;
if (eyedata[pos2].marginal)
eyedata[pos].marginal_neighbors++;
}
}
}
}
static int
is_lively(int owl_call, int pos)
{
if (board[pos] == EMPTY)
return 0;
if (owl_call)
return owl_lively(pos);
else
return (!worm[pos].inessential
&& (worm[pos].attack_codes[0] == 0
|| worm[pos].defense_codes[0] != 0));
}
/* In the following situation, we do not wish the vertex at 'a'
* included in the O eye space:
*
* OOOOXX
* OXaX..
* ------
*
* This eyespace should parse as (X), not (X!). Thus the vertex
* should not be included in the eyespace if it is adjacent to
* an X stone which is alive, yet X cannot play safely at a.
* The function returns 1 if this situation is found at
* (pos) for color O.
*
* The condition above is true, curiously enough, also for the
* following case:
* A group has two eyes, one of size 1 and one which is critical 1/2.
* It also has to have less than 4 external liberties, since the
* reading has to be able to capture the group tactically. In that
* case, the eye of size one will be treated as a false marginal.
* Thus we have to exclude this case, which is done by requiring (pos)
* to be adjacent to both white and black stones. Since this test is
* least expensive, we start with it.
*
* As a second optimization we require that one of the other colored
* neighbors is not lively. This should cut down on the number of
* calls to attack() and safe_move().
*/
static int
false_margin(int pos, int color, int lively[BOARDMAX])
{
int other = OTHER_COLOR(color);
int neighbors = 0;
int k;
int all_lively;
int potential_false_margin;
/* Require neighbors of both colors. */
for (k = 0; k < 4; k++)
if (ON_BOARD(pos + delta[k]))
neighbors |= board[pos + delta[k]];
if (neighbors != (WHITE | BLACK))
return 0;
/* At least one opponent neighbor should be not lively. */
all_lively = 1;
for (k = 0; k < 4; k++)
if (board[pos + delta[k]] == other && !lively[pos + delta[k]])
all_lively = 0;
if (all_lively)
return 0;
potential_false_margin = 0;
for (k = 0; k < 4; k++) {
int apos = pos + delta[k];
if (board[apos] != other || !lively[apos])
continue;
if (stackp == 0 && worm[apos].attack_codes[0] == 0)
potential_false_margin = 1;
if (stackp > 0 && !attack(apos, NULL))
potential_false_margin = 1;
}
if (potential_false_margin && safe_move(pos, other) == 0) {
DEBUG(DEBUG_EYES, "False margin for %C at %1m.\n", color, pos);
return 1;
}
return 0;
}
/*
* originate_eye(pos, pos, *esize, *msize, eye) creates an eyeshape
* with origin pos. esize and msize return the size and the number of
* marginal vertices. The repeated variables (pos) are due to the
* recursive definition of the function.
*/
static void
originate_eye(int origin, int pos,
int *esize, int *msize,
struct eye_data eye[BOARDMAX])
{
int k;
ASSERT_ON_BOARD1(origin);
ASSERT_ON_BOARD1(pos);
gg_assert(esize != NULL);
gg_assert(msize != NULL);
eye[pos].origin = origin;
(*esize)++;
if (eye[pos].marginal)
(*msize)++;
for (k = 0; k < 4; k++) {
int pos2 = pos + delta[k];
if (ON_BOARD(pos2)
&& eye[pos2].color == eye[pos].color
&& eye[pos2].origin == NO_MOVE
&& (!eye[pos2].marginal || !eye[pos].marginal))
originate_eye(origin, pos2, esize, msize, eye);
}
}
/*
* propagate_eye(origin) copies the data at the (origin) to the
* rest of the eye (invariant fields only).
*/
void
propagate_eye(int origin, struct eye_data eye[BOARDMAX])
{
int pos;
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos) && eye[pos].origin == origin) {
eye[pos].color = eye[origin].color;
eye[pos].esize = eye[origin].esize;
eye[pos].msize = eye[origin].msize;
eye[pos].origin = eye[origin].origin;
eye[pos].value = eye[origin].value;
}
}
/* Find the dragon or dragons surrounding an eye space. Up to
* max_dragons dragons adjacent to the eye space are added to
* the dragon array, and the number of dragons found is returned.
*/
int
find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color,
int dragons[], int max_dragons)
{
int mx[BOARDMAX];
int num_dragons = 0;
int pos;
memset(mx, 0, sizeof(mx));
DEBUG(DEBUG_MISCELLANEOUS, "find_eye_dragons: %1m %C\n", origin, eye_color);
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (board[pos] == eye_color
&& mx[dragon[pos].origin] == 0
&& ((ON_BOARD(SOUTH(pos))
&& eye[SOUTH(pos)].origin == origin
&& !eye[SOUTH(pos)].marginal)
|| (ON_BOARD(WEST(pos))
&& eye[WEST(pos)].origin == origin
&& !eye[WEST(pos)].marginal)
|| (ON_BOARD(NORTH(pos))
&& eye[NORTH(pos)].origin == origin
&& !eye[NORTH(pos)].marginal)
|| (ON_BOARD(EAST(pos))
&& eye[EAST(pos)].origin == origin
&& !eye[EAST(pos)].marginal))) {
DEBUG(DEBUG_MISCELLANEOUS,
" dragon: %1m %1m\n", pos, dragon[pos].origin);
mx[dragon[pos].origin] = 1;
if (dragons != NULL && num_dragons < max_dragons)
dragons[num_dragons] = dragon[pos].origin;
num_dragons++;
}
}
return num_dragons;
}
/* Print debugging data for the eyeshape at (i,j). Useful with GDB.
*/
static void
print_eye(struct eye_data eye[BOARDMAX], struct half_eye_data heye[BOARDMAX],
int pos)
{
int m, n;
int pos2;
int mini, maxi;
int minj, maxj;
int origin = eye[pos].origin;
gprintf("Eyespace at %1m: color=%C, esize=%d, msize=%d\n",
pos, eye[pos].color, eye[pos].esize, eye[pos].msize);
for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
if (!ON_BOARD(pos2))
continue;
if (eye[pos2].origin != pos)
continue;
if (eye[pos2].marginal && IS_STONE(board[pos2]))
gprintf("%1m (X!)\n", pos2);
else if (is_halfeye(heye, pos2) && IS_STONE(board[pos2])) {
if (heye[pos2].value == 3.0)
gprintf("%1m (XH)\n", pos2);
else
gprintf("%1m (XH) (topological eye value = %f)\n", pos2,
heye[pos2].value);
}
else if (!eye[pos2].marginal && IS_STONE(board[pos2]))
gprintf("%1m (X)\n", pos2);
else if (eye[pos2].marginal && board[pos2] == EMPTY)
gprintf("%1m (!)\n", pos2);
else if (is_halfeye(heye, pos2) && board[pos2] == EMPTY) {
if (heye[pos2].value == 3.0)
gprintf("%1m (H)\n", pos2);
else
gprintf("%1m (H) (topological eye value = %f)\n", pos2,
heye[pos2].value);
}
else
gprintf("%1m\n", pos2);
}
gprintf("\n");
/* Determine the size of the eye. */
mini = board_size;
maxi = -1;
minj = board_size;
maxj = -1;
for (m = 0; m < board_size; m++)
for (n = 0; n < board_size; n++) {
if (eye[POS(m, n)].origin != origin)
continue;
if (m < mini) mini = m;
if (m > maxi) maxi = m;
if (n < minj) minj = n;
if (n > maxj) maxj = n;
}
/* Prints the eye shape. A half eye is shown by h, if empty or H, if an
* enemy is present. Note that each half eye has a marginal point which is
* not printed, so the representation here may have less points than the
* matching eye pattern in eyes.db. Printing a marginal for the half eye
* would be nice, but difficult to implement.
*/
for (m = mini; m <= maxi; m++) {
gprintf(""); /* Get the indentation right. */
for (n = minj; n <= maxj; n++) {
int pos2 = POS(m, n);
if (eye[pos2].origin == origin) {
if (board[pos2] == EMPTY) {
if (eye[pos2].marginal)
gprintf("%o!");
else if (is_halfeye(heye, pos2))
gprintf("%oh");
else
gprintf("%o.");
}
else if (is_halfeye(heye, pos2))
gprintf("%oH");
else
gprintf("%oX");
}
else
gprintf("%o ");
}
gprintf("\n");
}
}
/*
* Given an eyespace with origin (pos), this function computes the
* minimum and maximum numbers of eyes the space can yield. If max and
* min are different, then vital points of attack and defense are also
* generated.
*
* If add_moves == 1, this function may add a move_reason for (color) at
* a vital point which is found by the function. If add_moves == 0,
* set color == EMPTY.
*/
void
compute_eyes(int pos, struct eyevalue *value,
int *attack_point, int *defense_point,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX], int add_moves)
{
if (attack_point)
*attack_point = NO_MOVE;
if (defense_point)
*defense_point = NO_MOVE;
if (debug & DEBUG_EYES) {
print_eye(eye, heye, pos);
DEBUG(DEBUG_EYES, "\n");
}
/* Look up the eye space in the graphs database. */
if (read_eye(pos, attack_point, defense_point, value, eye, heye, add_moves))
return;
/* Ideally any eye space that hasn't been matched yet should be two
* secure eyes. Until the database becomes more complete we have
* some additional heuristics to guess the values of unknown
* eyespaces.
*/
if (eye[pos].esize - 2*eye[pos].msize > 3)
set_eyevalue(value, 2, 2, 2, 2);
else if (eye[pos].esize - 2*eye[pos].msize > 0)
set_eyevalue(value, 1, 1, 1, 1);
else
set_eyevalue(value, 0, 0, 0, 0);
}
/*
* This function works like compute_eyes(), except that it also gives
* a pessimistic view of the chances to make eyes. Since it is intended
* to be used from the owl code, the option to add move reasons has
* been removed.
*/
void
compute_eyes_pessimistic(int pos, struct eyevalue *value,
int *pessimistic_min,
int *attack_point, int *defense_point,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX])
{
static int bulk_coefficients[5] = {-1, -1, 1, 4, 12};
int pos2;
int margins = 0;
int halfeyes = 0;
int margins_adjacent_to_margin = 0;
int effective_eyesize;
int bulk_score = 0;
signed char chainlinks[BOARDMAX];
/* Stones inside eyespace which do not coincide with a false eye or
* a halfeye.
*/
int interior_stones = 0;
memset(chainlinks, 0, BOARDMAX);
for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
int k;
if (!ON_BOARD(pos2) || eye[pos2].origin != pos)
continue;
if (eye[pos2].marginal || is_halfeye(heye, pos2)) {
margins++;
if (eye[pos2].marginal && eye[pos2].marginal_neighbors > 0)
margins_adjacent_to_margin++;
if (is_halfeye(heye, pos2))
halfeyes++;
}
else if (IS_STONE(board[pos2]))
interior_stones++;
bulk_score += bulk_coefficients[(int) eye[pos2].neighbors];
for (k = 0; k < 4; k++) {
int neighbor = pos2 + delta[k];
if (board[neighbor] == eye[pos].color) {
if (!chainlinks[neighbor]) {
bulk_score += 4;
mark_string(neighbor, chainlinks, 1);
}
}
else if (!ON_BOARD(neighbor))
bulk_score += 2;
}
}
/* This is a measure based on the simplified assumption that both
* players only cares about playing the marginal eye spaces. It is
* used later to guess the eye value for unidentified eye shapes.
*/
effective_eyesize = (eye[pos].esize + halfeyes - 2*margins
- margins_adjacent_to_margin);
if (attack_point)
*attack_point = NO_MOVE;
if (defense_point)
*defense_point = NO_MOVE;
if (debug & DEBUG_EYES) {
print_eye(eye, heye, pos);
DEBUG(DEBUG_EYES, "\n");
}
/* Look up the eye space in the graphs database. */
if (read_eye(pos, attack_point, defense_point, value,
eye, heye, 0)) {
*pessimistic_min = min_eyes(value) - margins;
/* A single point eye which is part of a ko can't be trusted. */
if (eye[pos].esize == 1
&& is_ko(pos, OTHER_COLOR(eye[pos].color), NULL))
*pessimistic_min = 0;
DEBUG(DEBUG_EYES, " graph matching - %s, pessimistic_min=%d\n",
eyevalue_to_string(value), *pessimistic_min);
}
/* Ideally any eye space that hasn't been matched yet should be two
* secure eyes. Until the database becomes more complete we have
* some additional heuristics to guess the values of unknown
* eyespaces.
*/
else {
guess_eye_space(pos, effective_eyesize, margins, bulk_score, eye,
value, pessimistic_min);
DEBUG(DEBUG_EYES, " guess_eye - %s, pessimistic_min=%d\n",
eyevalue_to_string(value), *pessimistic_min);
}
if (*pessimistic_min < 0) {
*pessimistic_min = 0;
DEBUG(DEBUG_EYES, " pessimistic min revised to 0\n");
}
/* An eyespace with at least two interior stones is assumed to be
* worth at least one eye, regardless of previous considerations.
*/
if (*pessimistic_min < 1 && interior_stones >= 2) {
*pessimistic_min = 1;
DEBUG(DEBUG_EYES, " pessimistic min revised to 1 (interior stones)\n");
}
if (attack_point
&& *attack_point == NO_MOVE
&& max_eyes(value) != *pessimistic_min) {
/* Find one marginal vertex and set as attack and defense point.
*
* We make some effort to find the best marginal vertex by giving
* priority to ones with more than one neighbor in the eyespace.
* We prefer non-halfeye margins and ones which are not self-atari
* for the opponent. Margins not on the edge are also favored.
*/
int best_attack_point = NO_MOVE;
int best_defense_point = NO_MOVE;
float score = 0.0;
for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
if (ON_BOARD(pos2) && eye[pos2].origin == pos) {
float this_score = 0.0;
int this_attack_point = NO_MOVE;
int this_defense_point = NO_MOVE;
if (eye[pos2].marginal && board[pos2] == EMPTY) {
this_score = eye[pos2].neighbors;
this_attack_point = pos2;
this_defense_point = pos2;
if (is_self_atari(pos2, OTHER_COLOR(eye[pos].color)))
this_score -= 0.5;
if (is_edge_vertex(pos2))
this_score -= 0.1;
}
else if (is_halfeye(heye, pos2)) {
this_score = 0.75;
this_defense_point = heye[pos2].defense_point[0];
this_attack_point = heye[pos2].attack_point[0];
}
else
continue;
if (gg_normalize_float2int(this_score, 0.01)
> gg_normalize_float2int(score, 0.01)) {
best_attack_point = this_attack_point;
best_defense_point = this_defense_point;
score = this_score;
}
}
}
if (score > 0.0) {
if (defense_point)
*defense_point = best_defense_point;
if (attack_point)
*attack_point = best_attack_point;
}
}
if (defense_point && *defense_point != NO_MOVE) {
ASSERT_ON_BOARD1(*defense_point);
}
if (attack_point && *attack_point != NO_MOVE) {
ASSERT_ON_BOARD1(*attack_point);
}
}
static void
guess_eye_space(int pos, int effective_eyesize, int margins,
int bulk_score, struct eye_data eye[BOARDMAX],
struct eyevalue *value, int *pessimistic_min)
{
if (effective_eyesize > 3) {
set_eyevalue(value, 2, 2, 2, 2);
*pessimistic_min = 1;
if ((margins == 0 && effective_eyesize > 7)
|| (margins > 0 && effective_eyesize > 9)) {
int eyes = 2 + (effective_eyesize - 2 * (margins > 0) - 8) / 2;
int threshold = (4 * (eye[pos].esize - 2)
+ (effective_eyesize - 8) * (effective_eyesize - 9));
DEBUG(DEBUG_EYES, "size: %d(%d), threshold: %d, bulk score: %d\n",
eye[pos].esize, effective_eyesize, threshold, bulk_score);
if (bulk_score > threshold && effective_eyesize < 15)
eyes = gg_max(2, eyes - ((bulk_score - threshold) / eye[pos].esize));
if (bulk_score < threshold + eye[pos].esize || effective_eyesize >= 15)
*pessimistic_min = eyes;
set_eyevalue(value, eyes, eyes, eyes, eyes);
}
}
else if (effective_eyesize > 0) {
set_eyevalue(value, 1, 1, 1, 1);
if (margins > 0)
*pessimistic_min = 0;
else
*pessimistic_min = 1;
}
else {
if (eye[pos].esize - margins > 2)
set_eyevalue(value, 0, 0, 1, 1);
else
set_eyevalue(value, 0, 0, 0, 0);
*pessimistic_min = 0;
}
}
/* This function does some minor reading to improve the results of
* recognize_eye(). Currently, it has two duties. One is to read
* positions like this:
*
* .XXXX| with half eye with proper eye
* XXOOO|
* XO.O.| . (1 eye) . (2 eyes)
* XXOa.| !.. .*
* -----+
*
* recognize_eye() sees the eyespace of the white dragon as shown
* (there's a half eye at a and it is considered the same as '!.' by
* the optics code). Normally, that eye shape gives only one secure
* eye, and owl thinks that the white dragon is dead unconditionally.
* This function tries to turn such ko-dependent half eyes into proper
* eyes and chooses the best alternative. Note that we don't have any
* attack/defense codes here, since owl will determine them itself.
*
* Another one is related to some cases when replacing half eyes with
* '!.' doesn't work. E.g. consider this eye (optics:328):
*
* XXXOO eye graph is 310:
* X..X.
* XOXX. !.! (second '!' is due to the halfeye)
* OXO..
* O.O..
*
* When this function detects such a half eye that can be attacked
* and/or defended inside its eyespace, it tries to turn it into a
* proper eye and see what happens. In case it gives an improvement
* for attacker and/or defender, the function keeps new result but
* only if new vital points are also vital points for the half eye.
* The heuristics used here might need improvements since they are
* based on a single game position.
*
* If add_moves != 0, this function may add move reasons for (color)
* at the vital points which are found by recognize_eye(). If add_moves
* == 0, set color to be EMPTY.
*/
static int
read_eye(int pos, int *attack_point, int *defense_point,
struct eyevalue *value, struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
int add_moves)
{
int eye_color;
int k;
int pos2;
int combination_halfeye = NO_MOVE;
int combination_attack = NO_MOVE;
int combination_defense = NO_MOVE;
int num_ko_halfeyes = 0;
int ko_halfeye = NO_MOVE;
struct vital_points vp;
struct vital_points ko_vp;
struct vital_points *best_vp = &vp;
eye_color = recognize_eye(pos, attack_point, defense_point, value,
eye, heye, &vp);
if (!eye_color)
return 0;
/* Find ko half eyes and "combination" half eyes if any. */
for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
if (ON_BOARD(pos2)
&& eye[pos2].origin == pos
&& heye[pos2].type == HALF_EYE) {
if (combination_halfeye == NO_MOVE) {
int apos = NO_MOVE;
int dpos = NO_MOVE;
for (k = 0; k < heye[pos2].num_attacks; k++) {
if (eye[heye[pos2].attack_point[k]].origin == pos) {
apos = heye[pos2].attack_point[k];
break;
}
}
for (k = 0; k < heye[pos2].num_defenses; k++) {
if (eye[heye[pos2].defense_point[k]].origin == pos) {
dpos = heye[pos2].defense_point[k];
break;
}
}
if (apos || dpos) {
combination_halfeye = pos2;
combination_attack = apos;
combination_defense = dpos;
}
}
if (heye[pos2].value < 3.0) {
num_ko_halfeyes++;
ko_halfeye = pos2;
}
}
}
/* In case we have a "combination" half eye, turn it into a proper eye
* vertex for a while and see what happens.
*/
if (combination_halfeye != NO_MOVE) {
int result;
int apos = NO_MOVE;
int dpos = NO_MOVE;
struct eyevalue combination_value;
struct vital_points combination_vp;
heye[combination_halfeye].type = 0;
result = recognize_eye(pos, &apos, &dpos, &combination_value, eye,
heye, &combination_vp);
heye[combination_halfeye].type = HALF_EYE;
if (result) {
if (combination_attack
&& min_eyes(value) > min_eyes(&combination_value)) {
/* FIXME: I'm not sure we can ever get here. */
for (k = 0; k < combination_vp.num_attacks; k++) {
if (combination_vp.attacks[k] == combination_attack) {
value->a = combination_value.a;
value->b = combination_value.b;
*attack_point = apos;
best_vp->num_attacks = 1;
best_vp->attacks[0] = combination_attack;
break;
}
}
}
if (combination_defense
&& max_eyes(value) < max_eyes(&combination_value)) {
/* Turning the half eye into a proper eye gives an improvement.
* However, we can only accept this result if there is a vital
* point that defends both the half eye and the whole eyespace.
*/
for (k = 0; k < combination_vp.num_defenses; k++) {
if (combination_vp.defenses[k] == combination_defense) {
value->c = combination_value.c;
value->d = combination_value.d;
*defense_point = dpos;
best_vp->num_defenses = 1;
best_vp->defenses[0] = combination_defense;
break;
}
}
}
if (min_eyes(value) != max_eyes(value)) {
ASSERT1(combination_attack || combination_defense, combination_halfeye);
if (*attack_point == NO_MOVE) {
*attack_point = combination_attack;
if (*attack_point == NO_MOVE)
*attack_point = combination_defense;
}
if (*defense_point == NO_MOVE) {
*defense_point = combination_defense;
if (*defense_point == NO_MOVE)
*defense_point = combination_defense;
}
}
}
}
/* The same with ko half eye (we cannot win two kos at once, therefore we
* give up if there is more than one ko half eye).
*/
if (num_ko_halfeyes == 1) {
int result;
int apos = NO_MOVE;
int dpos = NO_MOVE;
struct eyevalue ko_value;
heye[ko_halfeye].type = 0;
result = recognize_eye(pos, &apos, &dpos, &ko_value, eye,
heye, &ko_vp);
heye[ko_halfeye].type = HALF_EYE;
if (result && max_eyes(value) < max_eyes(&ko_value)) {
/* It is worthy to win the ko. */
*value = ko_value;
*attack_point = apos;
*defense_point = dpos;
best_vp = &ko_vp;
}
}
if (add_moves) {
struct vital_eye_points *vital;
if (eye_color == WHITE)
vital = white_vital_points;
else
vital = black_vital_points;
for (k = 0; k < best_vp->num_defenses && k < MAX_EYE_ATTACKS; k++)
vital[pos].defense_points[k] = best_vp->defenses[k];
for (k = 0; k < best_vp->num_attacks && k < MAX_EYE_ATTACKS; k++)
vital[pos].attack_points[k] = best_vp->attacks[k];
}
return 1;
}
/* recognize_eye(pos, *attack_point, *defense_point, *max, *min, eye_data,
* half_eye_data, color, vp), where pos is the origin of an eyespace, returns
* owner of eye (his color) if there is a pattern in eyes.db matching the
* eyespace, or 0 if no match is found. If there is a key point for attack,
* (*attack_point) is set to its location, or NO_MOVE if there is none.
* Similarly (*defense_point) is the location of a vital defense point.
* *value is set according to the pattern found. Vital attack/defense points
* exist if and only if min_eyes(value) != max_eyes(value).
*/
static int
recognize_eye(int pos, int *attack_point, int *defense_point,
struct eyevalue *value,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
struct vital_points *vp)
{
int pos2;
int eye_color;
int eye_size = 0;
int num_marginals = 0;
int vpos[MAXEYE];
signed char marginal[MAXEYE], edge[MAXEYE], neighbors[MAXEYE];
int graph;
int map[MAXEYE];
int best_score;
int r;
gg_assert(attack_point != NULL);
gg_assert(defense_point != NULL);
/* Set `eye_color' to the owner of the eye. */
eye_color = eye[pos].color;
if (eye[pos].esize-eye[pos].msize > 8)
return 0;
if (eye[pos].msize > MAXEYE)
return 0;
/* Create list of eye vertices */
for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
if (!ON_BOARD(pos2))
continue;
if (eye[pos2].origin == pos) {
vpos[eye_size] = pos2;
marginal[eye_size] = eye[pos2].marginal;
if (marginal[eye_size])
num_marginals++;
neighbors[eye_size] = eye[pos2].neighbors;
if (0) {
if (marginal[eye_size])
TRACE("(%1m)", vpos[eye_size]);
else
TRACE(" %1m ", vpos[eye_size]);
TRACE("\n");
}
if (is_corner_vertex(pos2))
edge[eye_size] = 2;
else if (is_edge_vertex(pos2))
edge[eye_size] = 1;
else
edge[eye_size] = 0;
if (is_halfeye(heye, pos2)) {
neighbors[eye_size]++; /* Increase neighbors of half eye. */
eye_size++;
/* Use a virtual marginal vertex for mapping purposes. We set it
* to be at NO_MOVE so it won't accidentally count as a
* neighbor for another vertex. Note that the half eye precedes
* the virtual marginal vertex in the list.
*/
vpos[eye_size] = NO_MOVE;
marginal[eye_size] = 1;
num_marginals++;
edge[eye_size] = 0;
neighbors[eye_size] = 1;
}
eye_size++;
}
}
/* We attempt to construct a map from the graph to the eyespace
* preserving the adjacency structure. If this can be done, we've
* identified the eyeshape.
*/
for (graph = 0; graphs[graph].vertex != NULL; graph++) {
int q;
if (graphs[graph].esize != eye_size
|| graphs[graph].msize != num_marginals)
continue;
reset_map(eye_size);
q = 0;
first_map(&map[0]);
while (1) {
struct eye_vertex *gv = &graphs[graph].vertex[q];
int mv = map[q];
int ok = 1;
if (0)
TRACE("q=%d: %d %d %d %d %d %d\n",
q, map[0], map[1], map[2], map[3], map[4], map[5]);
if (neighbors[mv] != gv->neighbors
|| marginal[mv] != gv->marginal
|| edge[mv] < gv->edge)
ok = 0;
if (ok) {
if (IS_STONE(board[vpos[mv]])) {
if (!(gv->flags & CAN_CONTAIN_STONE))
ok = 0;
}
/* Virtual half eye marginals also fall here since they are off
* board.
*/
else if (!(gv->flags & CAN_BE_EMPTY))
ok = 0;
}
if (ok) {
int k;
for (k = 0; k < gv->neighbors; k++) {
if (gv->n[k] < q) {
int mn = map[gv->n[k]];
/* Two eye vertices are neighbours if they are adjacent on the
* board or one of them is a half eye and the other is its
* virtual marginal vertex (and follows it in vpos[] array).
*/
if (vpos[mv] != SOUTH(vpos[mn])
&& vpos[mv] != WEST(vpos[mn])
&& vpos[mv] != NORTH(vpos[mn])
&& vpos[mv] != EAST(vpos[mn])
&& (mv != mn - 1
|| vpos[mv] == NO_MOVE
|| heye[vpos[mv]].type != HALF_EYE)
&& (mn != mv - 1
|| vpos[mn] == NO_MOVE
|| heye[vpos[mn]].type != HALF_EYE)) {
ok = 0;
break;
}
}
}
}
if (!ok) {
if (!next_map(&q, map))
break;
if (0)
gprintf(" q=%d, esize=%d: %d %d %d %d %d\n",
q, eye_size,
map[0], map[1], map[2], map[3], map[4]);
}
else {
q++;
if (q == eye_size)
break; /* A match! */
first_map(&map[q]);
}
}
if (q == eye_size) {
/* We have found a match! Now sort out the vital moves. */
*value = graphs[graph].value;
vp->num_attacks = 0;
vp->num_defenses = 0;
if (eye_move_urgency(value) > 0) {
/* Collect all attack and defense points in the pattern. */
int k;
for (k = 0; k < eye_size; k++) {
struct eye_vertex *ev = &graphs[graph].vertex[k];
if (ev->flags & EYE_ATTACK_POINT) {
/* Check for a marginal vertex matching a half eye virtual
* marginal. This is the case if a half eye preceeds the
* current vertex in the list.
*/
if (ev->marginal
&& map[k] > 0
&& vpos[map[k] - 1] != NO_MOVE
&& is_halfeye(heye, vpos[map[k] - 1])) {
/* Add all diagonals as vital. */
int ix;
struct half_eye_data *he = &heye[vpos[map[k] - 1]];
for (ix = 0; ix < he->num_attacks; ix++)
vp->attacks[vp->num_attacks++] = he->attack_point[ix];
}
else
vp->attacks[vp->num_attacks++] = vpos[map[k]];
}
if (ev->flags & EYE_DEFENSE_POINT) {
/* Check for a half eye virtual marginal vertex. */
if (ev->marginal
&& map[k] > 0
&& vpos[map[k] - 1] != NO_MOVE
&& is_halfeye(heye, vpos[map[k] - 1])) {
/* Add all diagonals as vital. */
int ix;
struct half_eye_data *he = &heye[vpos[map[k] - 1]];
for (ix = 0; ix < he->num_defenses; ix++)
vp->defenses[vp->num_defenses++] = he->defense_point[ix];
}
else
vp->defenses[vp->num_defenses++] = vpos[map[k]];
}
}
gg_assert(vp->num_attacks > 0 && vp->num_defenses > 0);
/* We now have all vital attack and defense points listed but
* we are also expected to single out of one of each to return
* in *attack_point and *defense_point. Since sometimes those
* are the only vital points considered, we want to choose the
* best ones, in the sense that they minimize the risk for
* error in the eye space analysis.
*
* One example is this position
*
* |..XXXX
* |XXX..X
* |..!O.X
* |OO.O.X
* |.O.!XX
* +------
*
* where O has an eyespace of the !..! type. The graph
* matching finds that both marginal vertices are vital points
* but here the one at 3-3 fails to defend. (For attack both
* points work but the 3-3 one is still worse since it leaves
* a ko threat.)
*
* In order to differentiate between the marginal points we
* count the number of straight and diagonal neighbors within
* the eye space. In the example above both have one straight
* neighbor each but the edge margin wins because it also has
* a diagonal margin.
*/
best_score = -10;
for (k = 0; k < vp->num_attacks; k++) {
int apos = vp->attacks[k];
int score = 0;
for (r = 0; r < 8; r++)
if (ON_BOARD(apos + delta[r])
&& eye[apos + delta[r]].color == eye[pos].color
&& !eye[apos + delta[r]].marginal) {
score++;
if (r < 4) {
score++;
if (board[apos + delta[r]] != EMPTY)
score++;
}
}
/* If a vital point is not adjacent to any point in the eye
* space, it must be a move to capture or defend a string
* related to a halfeye, e.g. the move * in this position,
*
* ......|
* .XXXX.|
* .X.O..|
* .XO.OO|
* .*XO..|
* ------+
*
* Playing this is probably a good idea.
*/
if (score == 0)
score += 2;
if (0)
gprintf("attack point %1m score %d\n", apos, score);
if (score > best_score) {
*attack_point = apos;
best_score = score;
}
}
best_score = -10;
for (k = 0; k < vp->num_defenses; k++) {
int dpos = vp->defenses[k];
int score = 0;
for (r = 0; r < 8; r++)
if (ON_BOARD(dpos + delta[r])
&& eye[dpos + delta[r]].color == eye[pos].color
&& !eye[dpos + delta[r]].marginal) {
score++;
if (r < 4) {
score++;
if (board[dpos + delta[r]] != EMPTY)
score++;
}
}
/* If possible, choose a non-sacrificial defense point.
* Compare white T8 and T6 in lazarus:21.
*/
if (safe_move(dpos, eye_color) != WIN)
score -= 5;
/* See comment to the same code for attack points. */
if (score == 0)
score += 2;
if (0)
gprintf("defense point %1m score %d\n", dpos, score);
if (score > best_score) {
*defense_point = dpos;
best_score = score;
}
}
DEBUG(DEBUG_EYES, " vital points: %1m (attack) %1m (defense)\n",
*attack_point, *defense_point);
DEBUG(DEBUG_EYES, " pattern matched: %d\n", graphs[graph].patnum);
}
TRACE("eye space at %1m of type %d\n", pos, graphs[graph].patnum);
return eye_color;
}
}
return 0;
}
/* a MAP is a map of the integers 0,1,2, ... ,q into
* 0,1, ... , esize-1 where q < esize. This determines a
* bijection of the first q+1 elements of the graph into the
* eyespace. The following three functions work with maps.
*/
/* Reset internal data structure used by first_map() and
* next_map() functions.
*/
static void
reset_map(int size)
{
map_size = size;
memset(used_index, 0, size * sizeof(used_index[0]));
}
/* The function first_map finds the smallest valid
* value of a map element.
*/
static void
first_map(int *map_value)
{
int k = 0;
while (used_index[k])
k++;
used_index[k] = 1;
*map_value = k;
}
/* The function next_map produces the next map in lexicographical
* order. If no next map can be found, q is decremented, then we
* try again. If the entire map is lexicographically last, the
* function returns false.
*/
static int
next_map(int *q, int map[MAXEYE])
{
int k;
do {
used_index[map[*q]] = 0;
for (k = map[*q]; ++k < map_size;) {
if (!used_index[k]) {
used_index[k] = 1;
map[*q] = k;
return 1;
}
}
(*q)--;
} while (*q >= 0);
return 0;
}
/* add_false_eye() turns a proper eyespace into a margin. */
static void
add_false_eye(int pos, struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX])
{
int k;
ASSERT1(heye[pos].type == FALSE_EYE, pos);
DEBUG(DEBUG_EYES, "false eye found at %1m\n", pos);
if (eye[pos].color == GRAY || eye[pos].marginal != 0)
return;
eye[pos].marginal = 1;
eye[eye[pos].origin].msize++;
for (k = 0; k < 4; k++)
if (ON_BOARD(pos + delta[k])
&& eye[pos + delta[k]].origin == eye[pos].origin)
eye[pos + delta[k]].marginal_neighbors++;
propagate_eye(eye[pos].origin, eye);
}
/* These functions are used from constraints to identify eye spaces,
* primarily for late endgame moves.
*/
int
is_eye_space(int pos)
{
return (white_eye[pos].color == WHITE
|| black_eye[pos].color == BLACK);
}
int
is_proper_eye_space(int pos)
{
return ((white_eye[pos].color == WHITE && !white_eye[pos].marginal)
|| (black_eye[pos].color == BLACK && !black_eye[pos].marginal));
}
/* Return the maximum number of eyes that can be obtained from the
* eyespace at (i, j). This is most useful in order to determine
* whether the eyespace can be assumed to produce any territory at
* all.
*/
int
max_eye_value(int pos)
{
int max_white = 0;
int max_black = 0;
if (white_eye[pos].color == WHITE)
max_white = max_eyes(&white_eye[pos].value);
if (black_eye[pos].color == BLACK)
max_black = max_eyes(&black_eye[pos].value);
return gg_max(max_white, max_black);
}
int
is_marginal_eye_space(int pos)
{
return (white_eye[pos].marginal || black_eye[pos].marginal);
}
int
is_halfeye(struct half_eye_data heye[BOARDMAX], int pos)
{
return heye[pos].type == HALF_EYE;
}
int
is_false_eye(struct half_eye_data heye[BOARDMAX], int pos)
{
return heye[pos].type == FALSE_EYE;
}
/* Find topological half eyes and false eyes by analyzing the
* diagonal intersections, as described in the Texinfo
* documentation (Eyes/Eye Topology).
*/
void
find_half_and_false_eyes(int color, struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
int find_mask[BOARDMAX])
{
int eye_color = color;
int pos;
float sum;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
/* skip eyespaces which owl doesn't want to be searched */
if (!ON_BOARD(pos) || (find_mask && find_mask[eye[pos].origin] <= 1))
continue;
/* skip every vertex which can't be a false or half eye */
if (eye[pos].color != eye_color
|| eye[pos].marginal
|| eye[pos].neighbors > 1)
continue;
sum = topological_eye(pos, color, eye, heye);
if (sum >= 4.0) {
/* false eye */
heye[pos].type = FALSE_EYE;
if (eye[pos].esize == 1
|| is_legal(pos, OTHER_COLOR(color))
|| board[pos] == OTHER_COLOR(color))
add_false_eye(pos, eye, heye);
}
else if (sum > 2.0) {
/* half eye */
heye[pos].type = HALF_EYE;
ASSERT1(heye[pos].num_attacks > 0, pos);
ASSERT_ON_BOARD1(heye[pos].attack_point[0]);
ASSERT1(heye[pos].num_defenses > 0, pos);
ASSERT_ON_BOARD1(heye[pos].defense_point[0]);
}
}
}
/* See Texinfo documentation (Eyes:Eye Topology). Returns:
* - 2 or less if (pos) is a proper eye for (color);
* - between 2 and 3 if the eye can be made false only by ko
* - 3 if (pos) is a half eye;
* - between 3 and 4 if the eye can be made real only by ko
* - 4 or more if (pos) is a false eye.
*
* Attack and defense points for control of the diagonals are stored
* in the heye[] array.
*
* my_eye is the eye space information with respect to (color).
*/
static float
topological_eye(int pos, int color,
struct eye_data my_eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX])
{
float sum = 0.0;
float val;
int num_attacks = 0;
int num_defenses = 0;
int attack_values[4];
int defense_values[4];
int k;
int r;
int attack_point;
int defense_point;
int attack_value;
int defense_value;
memset(attack_values, 0, sizeof(attack_values));
memset(defense_values, 0, sizeof(defense_values));
/* Loop over the diagonal directions. */
for (k = 4; k < 8; k++) {
int diag = pos + delta[k];
val = evaluate_diagonal_intersection(I(pos) + deltai[k],
J(pos) + deltaj[k], color,
&attack_point, &defense_point,
my_eye);
/*
* Eyespaces with cutting points are problematic. In this position
*
* .....XXXXX
* XXXXX.OO.X
* X.OOOO.O.X
* X.O.XXXO.X
* ----------
*
* the eyespace will be .XXX. which evaluates to two eyes (seki)
* unless countermeasures are taken.
*
* This can be worked around in the topological analysis by
* sometimes setting the diagonal value to 2.0 for vertices inside
* the eyespace which are occupied by opponent stones. More
* precisely all of the following conditions must hold:
*
* a) The value is not already 2.0.
* a) The (potential) eyepoint is empty.
* b) The diagonal is occupied by an opponent string,
* c) which is also adjacent to the (potential) eye and
* d) at least three stones long.
* e) The (potential) eye is not on the edge (to steer clear of all the
* hairy cases that are handled by eyes.db anyway).
* f) At least two own strings are adjacent to the (potential) eye.
* g) At least one of the own strings adjacent to the (potential) eye has
* only one liberty which is an eye space and not decided false, yet.
*
* With this revision the eyespace above becomes .XXXh or
* equivalently .XXX.! which is almost evaluated correctly, eye
* value 0122 instead of the correct 1122. Compared to the
* previous value 2222 it's a major improvement.
*
* FIXME: This approach has a number of shortcomings.
*
* 1. d) is kind of arbitrary and there may be exceptional
* cases.
*
* 2. This diagonal value modification should not apply to
* two diagonals of the same strings inside the eyespace.
* E.g. if we have a partial eyespace looking like
*
* .OOO.
* OO.OO
* OXXXO
*
* it doesn't make sense to mark the middle vertex as a
* false eye. Possibly this doesn't make any difference
* in practice but it's at the very least confusing.
*
* 3. Actually it doesn't make sense to mark vertices as
* false otherwise either due to these revisions (half
* eyes make good sense though) as can be seen if a
* stone is added to the initial diagram,
*
* .....XXXXX
* XXXXXXOO.X
* X.OOOO.O.X
* X.O.XXXO.X
* ----------
*
* Now the eyespace instead becomes .XXX! which has the
* eye value 0011 but if X tries to attack the eye O
* suddenly gets two solid eyes!
*
* The correct analysis would be to remove the vertex
* from the eyespace rather than turning it into a false
* eye. Then we would have the eyespace .XXX which is
* correctly evaluated to one eye (eye value 1112).
*
* The problem with this is that removing eye points is
* messy. It can surely be done but currently there is
* no support in the code for doing that. It has existed
* at an earlier time but was removed because the
* implementation was not robust enough and there was no
* longer any apparent need for it. To correct this
* problem is sufficient reason to reimplement that
* functionality.
*
* 4. The test of condition g) has a result which
* potentially depends on the ordering of the eyespaces
* and thus presumably on the orientation of the board.
* It might make more sense to examine whether the
* string neighbors more than one empty vertex in the
* same eyespace.
*/
if (val < 2.0 && board[pos] == EMPTY && board[diag] == OTHER_COLOR(color)
&& !is_edge_vertex(pos) && neighbor_of_string(pos, diag)
&& countstones(diag) >= 3) {
int strings[3];
int string_count;
int s;
string_count = 0;
for (r = 0; r < 4; r++) {
int str;
str = pos + delta[r];
if (board[str] != color)
continue;
ASSERT1(string_count < 3, pos);
for (s = 0; s < string_count; s++)
if (same_string(str, strings[s]))
break;
if (s != string_count)
continue;
strings[string_count++] = str;
}
if (string_count > 1) {
for (s = 0; s < string_count; s++) {
int libs[MAX_LIBERTIES];
int adj_eye_count;
int lib_count;
adj_eye_count = 0;
lib_count = findlib(strings[s], MAX_LIBERTIES, libs);
if (lib_count > MAX_LIBERTIES)
continue;
for (r = 0; r < lib_count && adj_eye_count < 2; r++)
if (my_eye[libs[r]].color == OTHER_COLOR(color)
&& !my_eye[libs[r]].marginal)
adj_eye_count++;
if (adj_eye_count < 2) {
val = 2.0;
break;
}
}
}
}
sum += val;
if (val > 0.0 && val < 2.0) {
/* Diagonals off the edge has value 1.0 but no attack or defense
* point.
*/
if (attack_point != NO_MOVE && defense_point != NO_MOVE) {
ASSERT_ON_BOARD1(attack_point);
ASSERT_ON_BOARD1(defense_point);
/* Store these in sorted (descending) order. We remap val
* differently for attack and defense points according to:
*
* val attack_value defense_value
* --- ------------ -------------
* 1.0 3 3
* <1.0 2 1
* >1.0 1 2
*
* This means that we primarily want to take control of
* diagonals without ko and secondarily of diagonals we can
* take unconditionally but not the opponent.
*/
if (val == 1.0) {
attack_value = 3;
defense_value = 3;
}
else if (val < 1.0) {
attack_value = 2;
defense_value = 1;
}
else {
attack_value = 1;
defense_value = 2;
}
for (r = 0; r < 4; r++) {
if (attack_values[r] < attack_value) {
int tmp_value = attack_values[r];
int tmp_point;
if (tmp_value)
tmp_point = heye[pos].attack_point[r];
else
tmp_point = 0;
attack_values[r] = attack_value;
heye[pos].attack_point[r] = attack_point;
attack_value = tmp_value;
attack_point = tmp_point;
}
if (defense_values[r] < defense_value) {
int tmp_value = defense_values[r];
int tmp_point;
if (tmp_value)
tmp_point = heye[pos].defense_point[r];
else
tmp_point = 0;
defense_values[r] = defense_value;
heye[pos].defense_point[r] = defense_point;
defense_value = tmp_value;
defense_point = tmp_point;
}
}
num_attacks++;
num_defenses++;
}
}
}
/* Remove attacks and defenses with smaller value than the best
* ones. (These might be useful to save as well, but not unless we
* also store the attack/defense values in the half_eye_data.)
*/
for (r = 0; r < num_attacks; r++) {
if (attack_values[r] < attack_values[0]) {
num_attacks = r;
break;
}
}
for (r = 0; r < num_defenses; r++) {
if (defense_values[r] < defense_values[0]) {
num_defenses = r;
break;
}
}
heye[pos].num_attacks = num_attacks;
heye[pos].num_defenses = num_defenses;
heye[pos].value = sum;
return sum;
}
/* Evaluate an intersection (m, n) which is diagonal to an eye space,
* as described in the Texinfo documentation (Eyes/Eye Topology).
*
* Returns:
*
* 0 if both coordinates are off the board
* 1 if one coordinate is off the board
*
* 0 if (color) has control over the vertex
* a if (color) can take control over the vertex unconditionally and
* the opponent can take control by winning a ko.
* 1 if both (color) and the opponent can take control of the vertex
* unconditionally
* b if (color) can take control over the vertex by winning a ko and
* the opponent can take control unconditionally.
* 2 if the opponent has control over the vertex
*
* The values a and b are discussed in the documentation. We are
* currently using a = 0.75 and b = 1.25.
*
* Notice that it's necessary to pass the coordinates separately
* instead of as a 1D coordinate. The reason is that the 1D mapping
* can't uniquely identify "off the corner" points.
*
* my_eye has to be the eye_data with respect to color.
*/
static float
evaluate_diagonal_intersection(int m, int n, int color,
int *attack_point, int *defense_point,
struct eye_data my_eye[BOARDMAX])
{
float value = 0;
int other = OTHER_COLOR(color);
int pos = POS(m, n);
int acode = 0;
int apos = NO_MOVE;
int dcode = 0;
int dpos = NO_MOVE;
int off_edge = 0;
const float a = 0.75;
const float b = 2 - a;
*attack_point = NO_MOVE;
*defense_point = NO_MOVE;
/* Check whether intersection is off the board. We must do this for
* each board coordinate separately because points "off the corner"
* are special cases.
*/
if (m < 0 || m >= board_size)
off_edge++;
if (n < 0 || n >= board_size)
off_edge++;
/* Must return 0 if both coordinates out of bounds. */
if (off_edge > 0)
return (float) (off_edge % 2);
/* Discard points within own eyespace, unless marginal or ko point.
*
* Comment: For some time discardment of points within own eyespace
* was contingent on this being the same eyespace as that of the
* examined vertex. This caused problems, e.g. in this position,
*
* |........
* |XXXXX...
* |OOOOX...
* |aO.OX...
* |OXXOX...
* |.XXOX...
* +--------
*
* where the empty vertex at a was evaluated as a false eye and the
* whole group as dead (instead of living in seki).
*
* The reason for the requirement of less than two marginal
* neighbors is this position:
*
* |.XXXX...
* |.OOOX...
* |O..OX...
* |aOO.X...
* |O..XX...
* |..O.X...
* |.X..X...
* |..XXX...
*
* where the empty vertex at a should not count as a solid eye.
* (The eyespace diagonally below a looks like this:
* .!
* !
* so we can clearly see why having two marginal vertices makes a
* difference.)
*/
if (my_eye[pos].color == color
&& !my_eye[pos].marginal
&& my_eye[pos].marginal_neighbors < 2
&& !(board[pos] == EMPTY && does_capture_something(pos, other)))
return 0.0;
if (board[pos] == EMPTY) {
int your_safety = safe_move(pos, other);
apos = pos;
dpos = pos;
/* We should normally have a safe move, but occasionally it may
* happen that it's not safe. There are complications, however,
* with a position like this:
*
* .XXXX|
* XXOO.|
* XO.O.|
* XXO.O|
* -----+
*
* Therefore we ignore our own safety if opponent's safety depends
* on ko.
*/
if (your_safety == 0)
value = 0.0;
else if (your_safety != WIN)
value = a;
else { /* So your_safety == WIN. */
int our_safety = safe_move(pos, color);
if (our_safety == 0) {
int k;
value = 2.0;
/* This check is intended to fix a certain special case, but might
* be helpful in other situations as well. Consider this position,
* happened in owl reading deep enough:
*
* |XXXXX
* |XOOXX
* |O.OOX
* |.OXX.
* +-----
*
* Without this check, the corner eye is considered false, not half-
* eye. Thus, owl thinks that the capture gains at most one eye and
* gives up.
*/
for (k = 4; k < 8; k++) {
int diagonal = pos + delta[k];
int lib;
if (board[diagonal] == other && findlib(diagonal, 1, &lib) == 1) {
if (lib != pos && does_secure(color, lib, pos)) {
value = 1.0;
apos = lib;
break;
}
}
}
}
else if (our_safety == WIN)
value = 1.0;
else /* our_safety depends on ko. */
value = b;
}
}
else if (board[pos] == color) {
/* This stone had better be safe, otherwise we wouldn't have an
* eyespace in the first place.
*/
value = 0.0;
}
else if (board[pos] == other) {
if (stackp == 0) {
acode = worm[pos].attack_codes[0];
apos = worm[pos].attack_points[0];
dcode = worm[pos].defense_codes[0];
dpos = worm[pos].defense_points[0];
}
else
attack_and_defend(pos, &acode, &apos, &dcode, &dpos);
/* Must test acode first since dcode only is reliable if acode is
* non-zero.
*/
if (acode == 0)
value = 2.0;
else if (dcode == 0)
value = 0.0;
else if (acode == WIN && dcode == WIN)
value = 1.0;
else if (acode == WIN && dcode != WIN)
value = a;
else if (acode != WIN && dcode == WIN)
value = b;
else if (acode != WIN && dcode != WIN)
value = 1.0; /* Both contingent on ko. Probably can't happen. */
}
if (value > 0.0 && value < 2.0) {
/* FIXME:
* Usually there are several attack and defense moves that would
* be equally valid. It's not good that we make an arbitrary
* choice at this point.
*/
ASSERT_ON_BOARD1(apos);
ASSERT_ON_BOARD1(dpos);
/* Notice:
* The point to ATTACK the half eye is the point which DEFENDS
* the stones on the diagonal intersection and vice versa. Thus
* we must switch attack and defense points here.
* If the vertex is empty, dpos == apos and it doesn't matter
* whether we switch.
*/
*attack_point = dpos;
*defense_point = apos;
}
return value;
}
/* Conservative relative of topological_eye(). Essentially the same
* algorithm is used, but only tactically safe opponent strings on
* diagonals are considered. This may underestimate the false/half eye
* status, but it should never be overestimated.
*/
int
obvious_false_eye(int pos, int color)
{
int i = I(pos);
int j = J(pos);
int k;
int diagonal_sum = 0;
for (k = 4; k < 8; k++) {
int di = deltai[k];
int dj = deltaj[k];
if (!ON_BOARD2(i+di, j) && !ON_BOARD2(i, j+dj))
diagonal_sum--;
if (!ON_BOARD2(i+di, j+dj))
diagonal_sum++;
else if (BOARD(i+di, j+dj) == OTHER_COLOR(color)
&& !attack(POS(i+di, j+dj), NULL))
diagonal_sum += 2;
}
return diagonal_sum >= 4;
}
/* Set the parameters into struct eyevalue as follows:
a = number of eyes if attacker plays first twice
b = number of eyes if attacker plays first
c = number of eyes if defender plays first
d =number of eyes if defender plays first twice
*/
void
set_eyevalue(struct eyevalue *e, int a, int b, int c, int d)
{
e->a = a;
e->b = b;
e->c = c;
e->d = d;
}
/* Number of eyes if attacker plays first twice (the threat of the first
* move by attacker).
*/
int
min_eye_threat(struct eyevalue *e)
{
return e->a;
}
/* Number of eyes if attacker plays first followed by alternating play. */
int
min_eyes(struct eyevalue *e)
{
return e->b;
}
/* Number of eyes if defender plays first followed by alternating play. */
int
max_eyes(struct eyevalue *e)
{
return e->c;
}
/* Number of eyes if defender plays first twice (the threat of the first
* move by defender).
*/
int
max_eye_threat(struct eyevalue *e)
{
return e->d;
}
/* Add the eyevalues *e1 and *e2, leaving the result in *sum. It is
* safe to let sum be the same as e1 or e2.
*/
void
add_eyevalues(struct eyevalue *e1, struct eyevalue *e2, struct eyevalue *sum)
{
struct eyevalue res;
res.a = gg_min(gg_min(e1->a + e2->c, e1->c + e2->a),
gg_max(e1->a + e2->b, e1->b + e2->a));
res.b = gg_min(gg_max(e1->b + e2->b, gg_min(e1->a + e2->d, e1->b + e2->c)),
gg_max(e1->b + e2->b, gg_min(e1->d + e2->a, e1->c + e2->b)));
res.c = gg_max(gg_min(e1->c + e2->c, gg_max(e1->d + e2->a, e1->c + e2->b)),
gg_min(e1->c + e2->c, gg_max(e1->a + e2->d, e1->b + e2->c)));
res.d = gg_max(gg_max(e1->d + e2->b, e1->b + e2->d),
gg_min(e1->d + e2->c, e1->c + e2->d));
/* The rules above give 0011 + 0002 = 0012, which is incorrect. Thus
* we need this annoying exception.
*/
if ((e1->d - e1->c == 2 && e2->c - e2->b == 1)
|| (e1->c - e1->b == 1 && e2->d - e2->c == 2)) {
res.d = gg_max(gg_min(e1->c + e2->d, e1->d + e2->b),
gg_min(e1->d + e2->c, e1->b + e2->d));
}
/* The temporary storage in res is necessary if sum is the same as
* e1 or e2.
*/
sum->a = res.a;
sum->b = res.b;
sum->c = res.c;
sum->d = res.d;
}
/* The impact on the number of eyes (counting up to two) if a vital
* move is made. The possible values are
* 0 - settled eye, no vital move
* 2 - 1/2 eye or 3/2 eyes
* 3 - 3/4 eyes or 5/4 eyes
* 4 - 1* eyes (a chimera)
*/
int
eye_move_urgency(struct eyevalue *e)
{
int a = gg_min(e->a, 2);
int b = gg_min(e->b, 2);
int c = gg_min(e->c, 2);
int d = gg_min(e->d, 2);
if (b == c)
return 0;
else
return d + c - b - a;
}
/* Produces a string representing the eyevalue.
*
* Note: the result string is stored in a statically allocated buffer
* which will be overwritten the next time this function is called.
*/
char *
eyevalue_to_string(struct eyevalue *e)
{
static char result[30];
if (e->a < 10 && e->b < 10 && e->c < 10 && e->d < 10)
gg_snprintf(result, 29, "%d%d%d%d", e->a, e->b, e->c, e->d);
else
gg_snprintf(result, 29, "[%d,%d,%d,%d]", e->a, e->b, e->c, e->d);
return result;
}
/* Test whether the optics code evaluates an eyeshape consistently. */
void
test_eyeshape(int eyesize, int *eye_vertices)
{
int k;
int n, N;
int mx[BOARDMAX];
int pos;
int str = NO_MOVE;
int attack_code;
int attack_point;
int defense_code;
int defense_point;
int save_verbose;
struct board_state starting_position;
/* Clear the board and initialize the engine properly. */
clear_board();
reset_engine();
/* Mark the eyespace in the mx array. */
memset(mx, 0, sizeof(mx));
for (k = 0; k < eyesize; k++) {
ASSERT_ON_BOARD1(eye_vertices[k]);
mx[eye_vertices[k]] = 1;
}
/* Play white stones surrounding the eyespace, including diagonals. */
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (!ON_BOARD(pos) || mx[pos] == 1)
continue;
for (k = 0; k < 8; k++) {
if (ON_BOARD(pos + delta[k]) && mx[pos + delta[k]] == 1) {
play_move(pos, WHITE);
str = pos;
break;
}
}
}
/* Play black stones surrounding the white group, but leaving all
* liberties empty.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
if (mx[pos] == 1 || board[pos] != EMPTY || liberty_of_string(pos, str))
continue;
for (k = 0; k < 8; k++) {
if (ON_BOARD(pos + delta[k])
&& liberty_of_string(pos + delta[k], str)) {
play_move(pos, BLACK);
break;
}
}
}
/* Show the board if verbose is on. Then turn off traces so we don't
* get any from make_worms(), make_dragons(), or the owl reading.
*/
if (verbose)
showboard(0);
save_verbose = verbose;
verbose = 0;
/* Store this position so we can come back to it. */
store_board(&starting_position);
/* Loop over all configurations of black stones inserted in the
* eyeshape. There are N = 2^(eyesize) configurations and we can
* straightforwardly use binary representation to enumerate them.
*/
N = 1 << eyesize;
for (n = 0; n < N; n++) {
int valid = 1;
int internal_stones = 0;
restore_board(&starting_position);
/* Play the stones for this configuration. */
for (k = 0; k < eyesize; k++) {
if (n & (1 << k)) {
if (!is_legal(eye_vertices[k], BLACK)) {
valid = 0;
break;
}
play_move(eye_vertices[k], BLACK);
internal_stones++;
}
}
if (!valid)
continue;
if (save_verbose > 1)
showboard(0);
/* Now we are ready to test the consistency. This is most easily
* done with help from the owl code. First we must prepare for
* this though.
*/
examine_position(EXAMINE_DRAGONS_WITHOUT_OWL, 0);
attack_code = owl_attack(str, &attack_point, NULL, NULL);
if (attack_code == 0) {
/* The owl code claims there is no attack. We test this by
* trying to attack on all empty spaces in the eyeshape.
*/
for (k = 0; k < eyesize; k++) {
if (board[eye_vertices[k]] == EMPTY
&& is_legal(eye_vertices[k], BLACK)
&& owl_does_attack(eye_vertices[k], str, NULL)) {
gprintf("%1m alive, but %1m attacks:\n", str, eye_vertices[k]);
showboard(0);
gprintf("\n");
}
}
/* Furthermore, if the eyespace is almost filled, white should
* be able to play on the remaining eyespace point and still be
* alive.
*/
if (internal_stones == eyesize - 1) {
for (k = 0; k < eyesize; k++) {
if (board[eye_vertices[k]] == EMPTY
&& !owl_does_defend(eye_vertices[k], str, NULL)) {
gprintf("%1m alive, but almost filled with nakade:\n", str);
showboard(0);
}
}
}
}
else {
defense_code = owl_defend(str, &defense_point, NULL, NULL);
if (defense_code == 0) {
/* The owl code claims there is no defense. We test this by
* trying to defend on all empty spaces in the eyeshape.
*/
for (k = 0; k < eyesize; k++) {
if (board[eye_vertices[k]] == EMPTY
&& is_legal(eye_vertices[k], WHITE)
&& owl_does_defend(eye_vertices[k], str, NULL)) {
gprintf("%1m dead, but %1m defends:\n", str, eye_vertices[k]);
showboard(0);
gprintf("\n");
}
}
}
else {
/* The owl code claims the dragon is critical. Verify the
* attack and defense points.
*/
if (board[attack_point] != EMPTY
|| !is_legal(attack_point, BLACK)) {
gprintf("Bad attack point %1m:\n", attack_point);
showboard(0);
}
else if (!owl_does_attack(attack_point, str, NULL)) {
gprintf("Attack point %1m failed:\n", attack_point);
showboard(0);
}
if (board[defense_point] != EMPTY
|| !is_legal(defense_point, WHITE)) {
gprintf("Bad defense point %1m:\n", defense_point);
showboard(0);
}
else if (!owl_does_defend(defense_point, str, NULL)) {
gprintf("Defense point %1m failed:\n", defense_point);
showboard(0);
}
}
}
}
verbose = save_verbose;
}
/********************************************************************
* The following static functions are helpers for analyze_eyegraph()
* further down. The purpose is to evaluate eye graphs according to
* the rules for local games, as described in doc/eyes.texi.
*
* The technique to do this is to convert the eye evaluation problem
* into a tactical style life and death reading problem. Tactical in
* the sense of needing to decide whether certain stones can be
* captured, but not in the sense of the tactical reading that five
* liberties are considered safe.
*
* We illustrate how this works with an example. Consider the eye shape
*
* !
* .X
* !...
*
* The basic idea is to embed the eyespace in a perfectly connected
* group without additional eyes or eye potential. This is most easily
* done by the somewhat brutal trick to fill the entire board with
* stones. We let the group consist of white stones (O) and get this
* result, disregarding the two marginal eye vertices:
*
* A B C D E F G H J K L M N O P Q R S T
* 19 O O O O O O O O O O O O O O O O O O O 19
* 18 O O O O O O O O O O O O O O O O O O O 18
* 17 O O O O O O O O O O O O O O O O O O O 17
* 16 O O O O O O O O O O O O O O O O O O O 16
* 15 O O O O O O O O O O O O O O O O O O O 15
* 14 O O O O O O O O O O O O O O O O O O O 14
* 13 O O O O O O O O O O O O O O O O O O O 13
* 12 O O O O O O O O . O O O O O O O O O O 12
* 11 O O O O O O O . X O O O O O O O O O O 11
* 10 O O O O O O . . . . O O O O O O O O O 10
* 9 O O O O O O O O O O O O O O O O O O O 9
* 8 O O O O O O O O O O O O O O O O O O O 8
* 7 O O O O O O O O O O O O O O O O O O O 7
* 6 O O O O O O O O O O O O O O O O O O O 6
* 5 O O O O O O O O O O O O O O O O O O O 5
* 4 O O O O O O O O O O O O O O O O O O O 4
* 3 O O O O O O O O O O O O O O O O O O O 3
* 2 O O O O O O O O O O O O O O O O O O O 2
* 1 O O O O O O O O O O O O O O O O O O O 1
* A B C D E F G H J K L M N O P Q R S T
*
* The question now is whether black can capture all the white stones
* under alternating play where only white may pass. However, first we
* need to make the top and leftmost eye vertices marginal. This is
* done by inserting small invincible black groups in the sea of white
* stones, in contact with the marginal vertices.
*
* A B C D E F G H J K L M N O P Q R S T
* 19 . O O O O O O O O O O O O O O O O O O 19
* 18 O O O O O O O O X X X O O O O O O O O 18
* 17 O O O O O O O O X . X O O O O O O O O 17
* 16 O O O O O O O O X X X O O O O O O O O 16
* 15 O O O O O O O O X . X O O O O O O O O 15
* 14 O O O O O O O O X X X O O O O O O O O 14
* 13 O O O O O O O O X O O O O O O O O O O 13
* 12 O O O O O O O O . O O O O O O O O O O 12
* 11 O O O O O O O . X O O O O O O O O O O 11
* 10 O O O O O O . . . . O O O O O O O O O 10
* 9 O O O O O O X O O O O O O O O O O O O 9
* 8 O O O O X X X O O O O O O O O O O O O 8
* 7 O O O O X . X O O O O O O O O O O O O 7
* 6 O O O O X X X O O O O O O O O O O O O 6
* 5 O O O O X . X O O O O O O O O O O O O 5
* 4 . O O O X X X O O O O O O O O O O O O 4
* 3 X X . O O O O O O O O O O O O O O O O 3
* 2 X . X O O O O O O O O O O O O O O O O 2
* 1 . X X O O O O O O O O O O O O O O O O 1
* A B C D E F G H J K L M N O P Q R S T
*
* In this diagram we have also added an invincible black group in the
* lower left corner in order to add two outer liberties (at A4 and
* C3) for the white group (this is sometimes needed for the tactical
* life and death reading to make sense). Furthermore there is an
* extra eye at A19. This is used when we want to distinguish between
* 0 and 1 (or 2) eyes since the tactical life and death reading by
* itself only cares about two eyes or not. When trying to distinguish
* between 1 (or 0) and 2 eyes we first fill in A19 again.
*
* Depending on the tactical life and death status with or without the
* extra eye we can determine the number of eyes. By evaluating
* tactical life and death status after having made a move we can also
* identify ko threats and critical moves.
*
* This code is organized as follows:
*
* analyze_eyegraph() converts the eyegraph into the tactical board
* position as demonstrated, then calls evaluate_eyespace() to its eye
* value.
*
* white_area() is a helper to add a small invincible black group on
* the board.
*
* evaluate_eyespace() calls tactical_life() and itself recursively to
* determine the eye value and the critical points.
*
* tactical_life() determines whether the white stones on the board
* (assumed to be a single string) can be captured under alternating
* play.
*
* tactical_life_attack() and tactical_life_defend() are two mutually
* recursive functions which perform the actual reading for
* tactical_life().
*
* Worth to mention in this overview is also the cache used for
* tactical_life_attack() and tactical_life_defend(). Since we have a
* limited number of vertices (eye space points + two outer liberties
* + possibly an extra eye) to play on we use a complete cache with a
* unique entry for every possible configuration of stones on the
* considered vertices.
*
* For each cache entry four bits are used, two for attack results and
* two four defense results. Each of these can take the values 0-3
* with the following interpretations:
* 0 - not yet considered
* 1 - result is being computed
* 2 - result has been computed and was a failure (0)
* 3 - result has been computed and was a success (1)
*/
/* Like trymove() except that it does a superko check. This does,
* however, only disallow repetition (besides simple ko) if the move
* does not capture any stones.
*/
static int
eyegraph_trymove(int pos, int color, const char *message, int str)
{
static Hash_data remembered_board_hashes[MAXSTACK];
int k;
int does_capture = does_capture_something(pos, color);
remembered_board_hashes[stackp] = board_hash;
if (!trymove(pos, color, message, str))
return 0;
if (does_capture)
return 1;
for (k = 0; k < stackp; k++)
if (hashdata_is_equal(board_hash, remembered_board_hashes[k])) {
popgo();
return 0;
}
return 1;
}
static int
eyegraph_is_margin_or_outer_liberty(int vertex)
{
int k;
int r;
int num_libs;
int libs[MAXLIBS];
int eyes;
for (k = 0; k < 4; k++) {
if (board[vertex + delta[k]] == BLACK) {
eyes = 0;
num_libs = findlib(vertex + delta[k], MAXLIBS, libs);
for (r = 0; r < num_libs; r++)
if (is_suicide(libs[r], WHITE))
eyes++;
if (eyes >= 2)
return 1;
}
}
return 0;
}
static int
eyegraph_order_moves(int num_vertices, int *vertices, int color_to_move, int *moves)
{
int num_moves = 0;
int scores[BOARDMAX];
int move;
int score;
int k;
int r;
for (k = 0; k < num_vertices; k++) {
if (k >= num_vertices - 3) {
/* Never useful for white to fill in outer liberties or a second eye. */
if (color_to_move == WHITE)
break;
/* No use playing the second outer liberty before the first one. */
if (k == num_vertices - 2 && board[vertices[num_vertices - 3]] == EMPTY)
continue;
}
move = vertices[k];
score = 0;
if (board[move] != EMPTY)
continue;
if (eyegraph_is_margin_or_outer_liberty(move)) {
if (k < num_vertices - 3)
score = 5; /* margin */
else
score = -10; /* outer liberty */
}
if (accuratelib(move, color_to_move, 2, NULL) == 1)
score -= 3;
for (r = 0; r < 4; r++) {
if (board[move + delta[r]] == EMPTY)
score += 2;
else if (board[move + delta[r]] == BLACK)
score += 3;
}
moves[num_moves] = move;
scores[num_moves] = score;
num_moves++;
}
for (k = 0; k < num_moves; k++) {
int maxscore = scores[k];
int max_at = 0;
/* Find the move with the biggest score. */
for (r = k + 1; r < num_moves; r++) {
if (scores[r] > maxscore) {
maxscore = scores[r];
max_at = r;
}
}
/* Now exchange the move at k with the move at max_at.
* Don't forget to exchange the scores as well.
*/
if (max_at != 0) {
int temp = moves[max_at];
moves[max_at] = moves[k];
moves[k] = temp;
temp = scores[max_at];
scores[max_at] = scores[k];
scores[k] = temp;
}
}
return num_moves;
}
/* Place a small invincible black group on the board.
* It is required that previously there were white stones at all
* involved vertices and on the surrounding vertices.
*
* Returns 1 if a group was placed, 0 otherwise.
*/
static int
white_area(int mx[BOARDMAX], int pos, int up, int right, int marginpos,
int distance)
{
int u, v;
int k;
int edge = is_edge_vertex(marginpos);
for (k = 1; k < distance; k++)
if (!ON_BOARD(marginpos + k * up)
|| mx[marginpos + k * up] != WHITE)
return 0;
for (u = -1; u <= 4; u++)
for (v = -1; v <= 4; v++) {
int pos2 = pos + u * up + v * right;
if (!ON_BOARD(pos2)) {
if (!edge)
return 0;
else if (u >= 0 && u <= 3 && v >= 0 && v <= 3)
return 0;
else if (I(pos2) != I(NORTH(marginpos))
&& I(pos2) != I(SOUTH(marginpos))
&& J(pos2) != J(WEST(marginpos))
&& J(pos2) != J(EAST(marginpos)))
return 0;
}
else if (mx[pos2] != WHITE)
return 0;
}
for (u = 0; u <= 3; u++)
for (v = 0; v <= 3; v++) {
int pos2 = pos + u * up + v * right;
mx[pos2] = BLACK;
}
mx[pos + up + right] = EMPTY;
mx[pos + 2 * up + 2 * right] = EMPTY;
return 1;
}
#define EYEGRAPH_RETURN(result, trace) \
do { \
if (sgf_dumptree) \
sgftreeAddComment(sgf_dumptree, (trace)); \
return (result); \
} while (0);
static int tactical_life_defend(int str, int num_vertices, int *vertices,
unsigned char *results);
/* Determine whether black can capture all white stones. */
static int
tactical_life_attack(int str, int num_vertices, int *vertices,
unsigned char *results)
{
int k;
int hash = 0;
int cached_result;
int result;
int num_moves;
int moves[BOARDMAX];
/* Compute hash value to index the result cache with. */
for (k = 0; k < num_vertices; k++) {
hash *= 3;
hash += board[vertices[k]];
}
hash *= 2;
hash += (board_ko_pos != NO_MOVE);
/* Is the result known from the cache? */
cached_result = results[hash] & 3;
if (0) {
showboard(0);
gprintf("%d %d (%d)\n", hash, cached_result, results[hash]);
}
if (cached_result == 2)
EYEGRAPH_RETURN(0, "tactical_life_attack: 0 (cached)");
if (cached_result == 3)
EYEGRAPH_RETURN(1, "tactical_life_attack: win (cached)");
if (cached_result == 1)
EYEGRAPH_RETURN(1, "tactical_life_attack: win (open node in cache)");
/* Mark this entry in the cache as currently being computed. */
results[hash] |= 1;
/* Try to play on all relevant vertices. */
num_moves = eyegraph_order_moves(num_vertices, vertices,
OTHER_COLOR(board[str]), moves);
for (k = 0; k < num_moves; k++) {
int move = moves[k];
if (eyegraph_trymove(move, OTHER_COLOR(board[str]),
"tactical_life_attack", str)) {
/* We were successful if the white stones were captured or if no
* defense can be found.
*/
if (board[str] == EMPTY)
result = 1;
else
result = !tactical_life_defend(str, num_vertices, vertices, results);
popgo();
if (result == 1) {
/* Store the result (success) in the cache. */
results[hash] = (results[hash] & (~3)) | 3;
EYEGRAPH_RETURN(1, "tactical_life_attack: win");
}
}
}
/* Store the result (failure) in the cache. */
results[hash] = (results[hash] & (~3)) | 2;
EYEGRAPH_RETURN(0, "tactical_life_attack: 0");
}
/* Determine whether white can live with all stones. */
static int
tactical_life_defend(int str, int num_vertices, int *vertices,
unsigned char *results)
{
int k;
int hash = 0;
int cached_result;
int result;
int num_moves;
int moves[BOARDMAX];
/* Compute hash value to index the result cache with. */
for (k = 0; k < num_vertices; k++) {
hash *= 3;
ASSERT1(board[vertices[k]] <= 2, vertices[k]);
hash += board[vertices[k]];
}
hash *= 2;
hash += (board_ko_pos != NO_MOVE);
/* Is the result known from the cache? */
cached_result = (results[hash] >> 2) & 3;
if (0) {
showboard(0);
gprintf("%d %d (%d)\n", hash, cached_result, results[hash]);
}
if (cached_result == 2)
EYEGRAPH_RETURN(0, "tactical_life_defend: 0 (cached)");
if (cached_result == 3)
EYEGRAPH_RETURN(1, "tactical_life_defend: win (cached)");
if (cached_result == 1)
EYEGRAPH_RETURN(1, "tactical_life_defend: win (node open in cache)");
/* Mark this entry in the cache as currently being computed. */
results[hash] |= (1 << 2);
/* Try to play on all relevant vertices. */
num_moves = eyegraph_order_moves(num_vertices, vertices, board[str], moves);
for (k = 0; k < num_moves; k++) {
int move = moves[k];
if ((!is_suicide(move, OTHER_COLOR(board[str]))
|| does_capture_something(move, board[str]))
&& eyegraph_trymove(move, board[str], "tactical_life_defend", str)) {
/* We were successful if no attack can be found. */
result = !tactical_life_attack(str, num_vertices, vertices, results);
popgo();
if (result == 1) {
/* Store the result (success) in the cache. */
results[hash] = (results[hash] & (~12)) | (3 << 2);
EYEGRAPH_RETURN(1, "tactical_life_defend: win");
}
}
}
/* If no move worked, also try passing. */
if (!tactical_life_attack(str, num_vertices, vertices, results)) {
/* Store the result (success) in the cache. */
results[hash] = (results[hash] & (~12)) | (3 << 2);
EYEGRAPH_RETURN(1, "tactical_life_defend: win");
}
/* Store the result (failure) in the cache. */
results[hash] = (results[hash] & (~12)) | (2 << 2);
EYEGRAPH_RETURN(0, "tactical_life_defend: 0");
}
/* Determine the tactical life and death status of all white stones.
* Also find all attack and defense moves. The parameter have_eye
* determines whether the extra eye in the upper left corner should be
* used or filled in before starting reading.
*/
static void
tactical_life(int have_eye, int num_vertices, int *vertices,
int *attack_code, int *num_attacks, int *attack_points,
int *defense_code, int *num_defenses, int *defense_points,
unsigned char *results)
{
int k;
int str;
int num_moves;
int moves[BOARDMAX];
gg_assert(attack_code != NULL && defense_code != NULL);
/* We know that the large white group includes A18. This is the
* vertex we test to determine whether the white stones have been
* captured.
*/
str = POS(1, 0);
if (board[str] == EMPTY) {
/* The stones have already been captured, too late to defend. */
*attack_code = WIN;
*defense_code = 0;
return;
}
/* Fill in the extra eye if have_eye is 0. If filling in would be
* suicide the white stones can be considered dead.
*/
if (!have_eye) {
if (!eyegraph_trymove(POS(0, 0), WHITE, "tactical_life-A", NO_MOVE)) {
*attack_code = WIN;
*defense_code = 0;
return;
}
}
*attack_code = 0;
*defense_code = 0;
/* Call tactical_life_attack() and tactical_life_defend() to
* determine status.
*/
if (tactical_life_attack(str, num_vertices, vertices, results)) {
*attack_code = WIN;
if (tactical_life_defend(str, num_vertices, vertices, results))
*defense_code = WIN;
}
else
*defense_code = WIN;
/* If the status is critical, try to play at each relevant vertex
* and call tactical_life_defend() or tactical_life_attack() to
* determine whether the move works as attack or defense.
*/
if (*attack_code != 0 && *defense_code != 0) {
if (num_attacks != NULL && attack_points != NULL) {
*num_attacks = 0;
num_moves = eyegraph_order_moves(num_vertices, vertices,
OTHER_COLOR(board[str]), moves);
for (k = 0; k < num_moves; k++) {
int move = moves[k];
if (eyegraph_trymove(move, OTHER_COLOR(board[str]), "tactical_life-B",
str)) {
if (board[str] == EMPTY
|| !tactical_life_defend(str, num_vertices, vertices, results))
attack_points[(*num_attacks)++] = move;
popgo();
}
}
}
if (num_defenses != NULL && defense_points != NULL) {
*num_defenses = 0;
num_moves = eyegraph_order_moves(num_vertices, vertices, board[str],
moves);
for (k = 0; k < num_moves; k++) {
int move = moves[k];
if (eyegraph_trymove(move, board[str], "tactical_life-C", str)) {
if (!tactical_life_attack(str, num_vertices, vertices, results))
defense_points[(*num_defenses)++] = move;
popgo();
}
}
}
}
/* Unfill the extra eye if we didn't use it. */
if (!have_eye)
popgo();
}
/* Determine the eye value of the eyespace for the big white group on
* the board and vital moves. The possible eye values are documented
* in the preamble to eyes.db. By calling tactical_life() multiple
* times, with and without using an extra eye, we can compute the eye
* values. To determine ko threats and vital moves, tactical_life() is
* called again after trying to play on one of the relevant vertices.
* In order to find out whether ko threats really are effective and to
* distinguish between 0122/1122 and 0012/0011 eye values (see
* discussion on pattern 6141 in the preamble of eyes.db), we may also
* need to recursively call ourselves after a move has been made.
*/
static void
evaluate_eyespace(struct eyevalue *result, int num_vertices, int *vertices,
int *num_vital_attacks, int *vital_attacks,
int *num_vital_defenses, int *vital_defenses,
unsigned char *tactical_life_results)
{
int k;
int attack_code;
int num_attacks;
int attack_points[BOARDMAX];
int defense_code;
int num_defenses;
int defense_points[BOARDMAX];
int attack_code2;
int num_attacks2;
int attack_points2[BOARDMAX];
int defense_code2;
struct eyevalue result2;
int num_vital_attacks2;
int vital_attacks2[BOARDMAX];
int num_vital_defenses2;
int vital_defenses2[BOARDMAX];
int num_moves;
int moves[BOARDMAX];
*num_vital_attacks = 0;
*num_vital_defenses = 0;
/* Determine tactical life without an extra eye. */
tactical_life(0, num_vertices, vertices,
&attack_code, &num_attacks, attack_points,
&defense_code, &num_defenses, defense_points,
tactical_life_results);
if (attack_code == 0) {
/* Alive without extra eye.
* Possible results: 0222, 1222, 2222
*
* Determine whether there are ko threats and how serious.
*/
int a = 2;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Alive without extra eye.\n");
num_moves = eyegraph_order_moves(num_vertices, vertices, BLACK, moves);
for (k = 0; k < num_moves; k++) {
int acode, dcode;
int move = moves[k];
if (eyegraph_trymove(move, BLACK, "evaluate_eyespace-A", NO_MOVE)) {
tactical_life(0, num_vertices, vertices, &acode, NULL, NULL,
&dcode, NULL, NULL, tactical_life_results);
if (acode != 0) {
tactical_life(1, num_vertices, vertices, &acode, NULL, NULL,
&dcode, NULL, NULL, tactical_life_results);
if (acode != 0) {
if (a == 1)
*num_vital_attacks = 0;
a = 0;
vital_attacks[(*num_vital_attacks)++] = move;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree,
"Ko threat to remove both eyes.\n");
}
else {
if (a != 0) {
vital_attacks[(*num_vital_attacks)++] = move;
a = 1;
}
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Ko threat to remove one eye.\n");
}
}
popgo();
}
}
set_eyevalue(result, a, 2, 2, 2);
if (sgf_dumptree) {
if (a == 0)
sgftreeAddComment(sgf_dumptree, "Eyevalue 0222.\n");
else if (a == 1)
sgftreeAddComment(sgf_dumptree, "Eyevalue 1222.\n");
else
sgftreeAddComment(sgf_dumptree, "Eyevalue 2222.\n");
}
}
else if (defense_code != 0) {
/* Critical without extra eye.
* Possible results: 0022, 0122, 1122
*/
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Critical without extra eye.\n");
tactical_life(1, num_vertices, vertices,
&attack_code2, &num_attacks2, attack_points2,
&defense_code2, NULL, NULL, tactical_life_results);
for (k = 0; k < num_defenses; k++)
vital_defenses[(*num_vital_defenses)++] = defense_points[k];
if (attack_code2 == WIN) {
/* A chimera. 0022. */
set_eyevalue(result, 0, 0, 2, 2);
for (k = 0; k < num_attacks2; k++)
vital_attacks[(*num_vital_attacks)++] = attack_points2[k];
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Eyevalue: 0022.\n");
}
else {
int a = 1;
for (k = 0; k < num_attacks; k++) {
int move = attack_points[k];
if (eyegraph_trymove(move, BLACK, "evaluate_eyespace-B", NO_MOVE)) {
evaluate_eyespace(&result2, num_vertices, vertices,
&num_vital_attacks2, vital_attacks2,
&num_vital_defenses2, vital_defenses2,
tactical_life_results);
/* If result2 is 0011 for some move we have 0122 as final
* result, otherwise 1122.
*/
if (min_eyes(&result2) == 0
&& max_eyes(&result2) == 1
&& max_eye_threat(&result2) == 1) {
if (a == 1)
*num_vital_attacks = 0;
a = 0;
vital_attacks[(*num_vital_attacks)++] = move;
}
else if (a == 1)
vital_attacks[(*num_vital_attacks)++] = move;
popgo();
}
}
set_eyevalue(result, a, 1, 2, 2);
if (sgf_dumptree) {
if (a == 0)
sgftreeAddComment(sgf_dumptree, "Eyevalue: 0122.\n");
else
sgftreeAddComment(sgf_dumptree, "Eyevalue: 1122.\n");
}
}
}
else {
/* Dead without extra eye.
* Possible results: 0000, 0001, 0002, 0011, 0012, 0111, 0112, 1111, 1112
*
* Now determine tactical life with an extra eye.
*/
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Dead without extra eye.\n");
tactical_life(1, num_vertices, vertices,
&attack_code, &num_attacks, attack_points,
&defense_code, &num_defenses, defense_points,
tactical_life_results);
if (attack_code == 0) {
/* Alive with extra eye.
* Possible results: 0111, 0112, 1111, 1112
*/
int a = 1;
int d = 1;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Alive with extra eye.\n");
num_moves = eyegraph_order_moves(num_vertices, vertices, BLACK, moves);
for (k = 0; k < num_moves; k++) {
int acode, dcode;
int move = moves[k];
if (eyegraph_trymove(move, BLACK, "evaluate_eyespace-C", NO_MOVE)) {
tactical_life(1, num_vertices, vertices, &acode, NULL, NULL,
&dcode, NULL, NULL, tactical_life_results);
if (acode != 0) {
evaluate_eyespace(&result2, num_vertices, vertices,
&num_vital_attacks2, vital_attacks2,
&num_vital_defenses2, vital_defenses2,
tactical_life_results);
/* This is either 0011 or 0012. Only the first is acceptable. */
if (max_eye_threat(&result2) == 1) {
vital_attacks[(*num_vital_attacks)++] = move;
a = 0;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Attacking ko threat.\n");
}
}
popgo();
}
}
num_moves = eyegraph_order_moves(num_vertices, vertices, WHITE, moves);
for (k = 0; k < num_moves; k++) {
int acode, dcode;
int move = moves[k];
if (eyegraph_trymove(move, WHITE, "evaluate_eyespace-D", NO_MOVE)) {
tactical_life(0, num_vertices, vertices, &acode, NULL, NULL,
&dcode, NULL, NULL, tactical_life_results);
if (dcode != 0) {
evaluate_eyespace(&result2, num_vertices, vertices,
&num_vital_attacks2, vital_attacks2,
&num_vital_defenses2, vital_defenses2,
tactical_life_results);
/* This is either 1122 or 0122. Only the first is acceptable. */
if (min_eye_threat(&result2) == 1) {
vital_defenses[(*num_vital_defenses)++] = move;
d = 2;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Defending ko threat.\n");
}
}
popgo();
}
}
set_eyevalue(result, a, 1, 1, d);
if (sgf_dumptree) {
if (a == 0 && d == 1)
sgftreeAddComment(sgf_dumptree, "Eyevalue 0111.\n");
else if (a == 0 && d == 2)
sgftreeAddComment(sgf_dumptree, "Eyevalue 0112.\n");
else if (a == 1 && d == 1)
sgftreeAddComment(sgf_dumptree, "Eyevalue 1111.\n");
else
sgftreeAddComment(sgf_dumptree, "Eyevalue 1112.\n");
}
}
else if (defense_code != 0) {
/* Critical with extra eye.
* Possible results: 0011, 0012
*/
int d = 1;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Critical with extra eye.\n");
for (k = 0; k < num_attacks; k++)
vital_attacks[(*num_vital_attacks)++] = attack_points[k];
for (k = 0; k < num_defenses; k++) {
int move = defense_points[k];
if (eyegraph_trymove(move, WHITE, "evaluate_eyespace-E", NO_MOVE)) {
evaluate_eyespace(&result2, num_vertices, vertices,
&num_vital_attacks2, vital_attacks2,
&num_vital_defenses2, vital_defenses2,
tactical_life_results);
/* If result2 is 1122 for some move we have 0012 as final
* result, otherwise 0011.
*/
if (min_eye_threat(&result2) == 1
&& min_eyes(&result2) == 1
&& max_eyes(&result2) == 2) {
if (d == 1)
*num_vital_defenses = 0;
d = 2;
vital_defenses[(*num_vital_defenses)++] = move;
}
else if (d == 1)
vital_defenses[(*num_vital_defenses)++] = move;
popgo();
}
}
set_eyevalue(result, 0, 0, 1, d);
if (sgf_dumptree) {
if (d == 1)
sgftreeAddComment(sgf_dumptree, "Eyevalue: 0011.\n");
else
sgftreeAddComment(sgf_dumptree, "Eyevalue: 0012.\n");
}
}
else {
/* Dead with extra eye.
* Possible results: 0000, 0001, 0002
*
* Determine whether there are ko threats and how serious.
*/
int d = 0;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree, "Dead with extra eye.\n");
num_moves = eyegraph_order_moves(num_vertices, vertices, WHITE, moves);
for (k = 0; k < num_moves; k++) {
int acode, dcode;
int move = moves[k];
if (eyegraph_trymove(move, WHITE, "evaluate_eyespace-F", NO_MOVE)) {
tactical_life(1, num_vertices, vertices, &acode, NULL, NULL,
&dcode, NULL, NULL, tactical_life_results);
if (dcode != 0) {
tactical_life(0, num_vertices, vertices, &acode, NULL, NULL,
&dcode, NULL, NULL, tactical_life_results);
if (dcode != 0) {
if (d == 1)
*num_vital_defenses = 0;
d = 2;
vital_defenses[(*num_vital_defenses)++] = move;
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree,
"Ko threat to make two eyes.\n");
}
else {
if (d != 2) {
vital_defenses[(*num_vital_defenses)++] = move;
d = 1;
}
if (sgf_dumptree)
sgftreeAddComment(sgf_dumptree,
"Ko threat to make one eye.\n");
}
}
popgo();
}
}
set_eyevalue(result, 0, 0, 0, d);
if (sgf_dumptree) {
if (d == 0)
sgftreeAddComment(sgf_dumptree, "Eyevalue 0000.\n");
else if (d == 1)
sgftreeAddComment(sgf_dumptree, "Eyevalue 0001.\n");
else
sgftreeAddComment(sgf_dumptree, "Eyevalue 0002.\n");
}
}
}
}
/* Add small invincible black groups in contact with the marginal
* vertices, without destroying the connectivity of the white stones.
*
*/
static int
add_margins(int num_margins, int *margins, int mx[BOARDMAX])
{
int k;
int i, j;
int old_mx[BOARDMAX];
int pos;
if (num_margins == 0)
return 1;
memcpy(old_mx, mx, sizeof(old_mx));
pos = margins[num_margins - 1];
for (k = 0; k < 4; k++) {
int up = delta[k];
int right = delta[(k + 1) % 4];
if (!ON_BOARD(pos + up))
continue;
if (mx[pos + up] == WHITE
&& (!ON_BOARD(pos + up + right) || mx[pos + up + right] == WHITE)
&& (!ON_BOARD(pos + up - right) || mx[pos + up - right] == WHITE)) {
for (i = -3; i <= 0; i++) {
for (j = 2; j < 6; j++) {
if (white_area(mx, pos + j * up + i * right, up, right, pos, j)) {
int s = 1;
while (mx[pos + s * up] == WHITE) {
mx[pos + s * up] = BLACK;
s++;
}
if (add_margins(num_margins - 1, margins, mx))
return 1;
else
memcpy(mx, old_mx, sizeof(old_mx));
}
}
}
}
}
return 0;
}
/* Analyze an eye graph to determine the eye value and vital moves.
*
* The eye graph is given by a string which is encoded with "%" for
* newlines and "O" for spaces. E.g., the eye graph
*
* !
* .X
* !...
*
* is encoded as "OO!%O.X%!...". (The encoding is needed for the GTP
* interface to this function.)
*
* The result is an eye value and a (nonencoded) pattern showing the
* vital moves, using the same notation as eyes.db. In the example above
* we would get the eye value 0112 and the graph (showing ko threat moves)
*
* @
* .X
* !.*.
*
* If the eye graph cannot be realized, 0 is returned, 1 otherwise.
*/
int
analyze_eyegraph(const char *coded_eyegraph, struct eyevalue *value,
char *analyzed_eyegraph)
{
int k;
int i, j;
int mini, minj;
int mx[BOARDMAX];
char mg[BOARDMAX];
int pos;
int num_vital_attacks;
int vital_attacks[BOARDMAX]; /* Way larger than necessary. */
int num_vital_defenses;
int vital_defenses[BOARDMAX]; /* Way larger than necessary. */
int maxwidth;
int current_width;
int num_rows;
int horizontal_edge;
int vertical_edge;
int num_margins;
int margins[BOARDMAX]; /* Way larger than necessary. */
int num_vertices;
int vertices[BOARDMAX]; /* Way larger than necessary. */
int table_size;
unsigned char *tactical_life_results;
if (0)
gprintf("Analyze eyegraph %s\n", coded_eyegraph);
/* Mark the eyespace in the mx array. We construct the position in
* the mx array and copy it to the actual board later.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos))
mx[pos] = WHITE;
/* Find out the size of the eye graph pattern so that we can center
* it properly.
*/
maxwidth = 0;
current_width = 0;
num_rows = 1;
horizontal_edge = -1;
vertical_edge = -1;
for (k = 0; k < (int) strlen(coded_eyegraph); k++) {
if (coded_eyegraph[k] == '\n')
continue;
if (coded_eyegraph[k] == '%') {
num_rows++;
if (current_width > maxwidth)
maxwidth = current_width;
current_width = 0;
}
else {
if (coded_eyegraph[k] == '-')
horizontal_edge = num_rows - 1;
else if (coded_eyegraph[k] == '|')
vertical_edge = current_width;
current_width++;
}
}
if (current_width > maxwidth)
maxwidth = current_width;
/* Cut out the eyespace from the solid white string. */
num_margins = 0;
num_vertices = 0;
if (horizontal_edge == 0)
mini = -1;
else if (horizontal_edge > 0)
mini = board_size - num_rows + 1;
else
mini = (board_size - num_rows) / 2;
if (vertical_edge == 0)
minj = -1;
else if (vertical_edge > 0)
minj = board_size - maxwidth + 1;
else
minj = (board_size - maxwidth) / 2;
i = mini;
j = minj;
for (k = 0; k < (int) strlen(coded_eyegraph); k++) {
char c = coded_eyegraph[k];
if (c == '\n')
continue;
if (c == '%') {
i++;
j = minj - 1;
}
else if (c == 'X' || c == '$')
mx[POS(i, j)] = BLACK;
else if (c == '.' || c == '*' || c == '<' || c == '>'
|| c == '!' || c == '@' || c == '(' || c == ')')
mx[POS(i, j)] = EMPTY;
if (c == '!' || c == '@' || c == '(' || c == ')' || c == '$')
margins[num_margins++] = POS(i, j);
if (c != '|' && c != '-' && c != '+' && c != '%'
&& ON_BOARD(POS(i, j)) && mx[POS(i, j)] != WHITE)
vertices[num_vertices++] = POS(i, j);
j++;
}
/* Add an invincible black group in the lower left plus two outer
* liberties for the white string. However, if the eyespace is
* placed in or near the lower left corner, we put this group in the
* upper right instead.
*/
pos = POS(board_size - 2, 1);
if ((vertical_edge == 0 && horizontal_edge != 0)
|| (horizontal_edge > 0 && vertical_edge <= 0))
pos = POS(1, board_size - 2);
mx[pos] = EMPTY;
mx[NORTH(pos)] = BLACK;
mx[NW(pos)] = BLACK;
mx[NE(pos)] = EMPTY;
mx[WEST(pos)] = BLACK;
mx[EAST(pos)] = BLACK;
mx[SW(pos)] = EMPTY;
mx[SOUTH(pos)] = BLACK;
mx[SE(pos)] = BLACK;
if (ON_BOARD(NN(pos)))
mx[NN(pos)] = EMPTY;
else
mx[SS(pos)] = EMPTY;
/* Add the two outer liberties in the lower left or upper right to
* the list of vertices.
*/
if (ON_BOARD(NN(pos))) {
vertices[num_vertices++] = NE(pos);
vertices[num_vertices++] = NN(pos);
}
else {
vertices[num_vertices++] = SW(pos);
vertices[num_vertices++] = SS(pos);
}
/* Add an extra eye in the upper left corner. */
mx[POS(0, 0)] = EMPTY;
vertices[num_vertices++] = POS(0, 0);
if (!add_margins(num_margins, margins, mx))
return 0;
/* Copy the mx array over to the board. */
clear_board();
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos)) {
if (mx[pos] == WHITE)
add_stone(pos, WHITE);
else if (mx[pos] == BLACK)
add_stone(pos, BLACK);
}
if (verbose)
showboard(0);
/* If there are any isolated O stones, those should also be added to
* the playable vertices.
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (board[pos] == WHITE && !same_string(pos, POS(1, 0))) {
vertices[num_vertices] = vertices[num_vertices - 1];
vertices[num_vertices - 1] = vertices[num_vertices - 2];
vertices[num_vertices - 2] = vertices[num_vertices - 3];
vertices[num_vertices - 3] = pos;
num_vertices++;
}
if (verbose) {
int k;
gprintf("\nPlayable vertices:\n");
for (k = 0; k < num_vertices; k++)
gprintf("%1m ", vertices[k]);
gprintf("\n\n");
}
/* Disable this test if you need to evaluate larger eyespaces, have
* no shortage of memory, and know what you're doing.
*/
if (num_vertices > 17) {
gprintf("analyze_eyegraph: too large eyespace, %d vertices\n",
num_vertices);
gg_assert(num_vertices <= 17);
}
/* The cache must have 2*3^num_vertices entries. */
table_size = 2;
for (k = 0; k < num_vertices; k++)
table_size *= 3;
/* Allocate memory for the cache. */
tactical_life_results = malloc(table_size);
if (!tactical_life_results) {
gprintf("analyze_eyegraph: failed to allocate %d bytes\n", table_size);
gg_assert(tactical_life_results != NULL);
}
memset(tactical_life_results, 0, table_size);
if (sgf_dumptree)
sgffile_printboard(sgf_dumptree);
/* Evaluate the eyespace on the board. */
evaluate_eyespace(value, num_vertices, vertices,
&num_vital_attacks, vital_attacks,
&num_vital_defenses, vital_defenses,
tactical_life_results);
/* Return the cache memory. */
free(tactical_life_results);
if (verbose) {
gprintf("Eyevalue: %s\n", eyevalue_to_string(value));
for (k = 0; k < num_vital_attacks; k++)
gprintf(" vital attack point %1m\n", vital_attacks[k]);
for (k = 0; k < num_vital_defenses; k++)
gprintf(" vital defense point %1m\n", vital_defenses[k]);
}
/* Encode the attack and defense points with symbols in the mg[] array. */
memset(mg, ' ', sizeof(mg));
for (k = 0; k < num_vertices - 2; k++)
mg[vertices[k]] = (board[vertices[k]] == BLACK ? 'X' : '.');
for (k = 0; k < num_margins; k++)
mg[margins[k]] = (mg[margins[k]] == 'X' ? '$' : '!');
for (k = 0; k < num_vital_attacks; k++)
mg[vital_attacks[k]] = (mg[vital_attacks[k]] == '!' ? '(' : '<');
for (k = 0; k < num_vital_defenses; k++) {
int pos = vital_defenses[k];
if (mg[pos] == '.')
mg[pos] = '>';
else if (mg[pos] == '!')
mg[pos] = ')';
else if (mg[pos] == '<')
mg[pos] = '*';
else if (mg[pos] == '(')
mg[pos] = '@';
}
/* Return the central part of the mg[] array (corresponding to the
* input eye graph).
*/
k = 0;
for (i = mini; i < mini + num_rows; i++) {
for (j = minj; j < minj + maxwidth; j++) {
if ((i < 0 || i >= board_size) && (j < 0 || j >= board_size))
analyzed_eyegraph[k++] = '+';
else if (i < 0 || i >= board_size)
analyzed_eyegraph[k++] = '-';
else if (j < 0 || j >= board_size)
analyzed_eyegraph[k++] = '|';
else
analyzed_eyegraph[k++] = mg[POS(i, j)];
}
analyzed_eyegraph[k++] = '\n';
}
analyzed_eyegraph[k - 1] = 0;
return 1;
}
/*
* Local Variables:
* tab-width: 8
* c-basic-offset: 2
* End:
*/
Fork of GNU Go supporting Xeon Phi coprocessors (and other modifications).