/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* This structure is used in communication between read_eye() and
int defenses
[4 * MAXEYE
];
compute_primary_domains(int color
, int domain
[BOARDMAX
],
int false_margins
[BOARDMAX
],
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
,
struct eye_data eye
[BOARDMAX
]);
static int read_eye(int pos
, int *attack_point
, int *defense_point
,
struct eye_data eye
[BOARDMAX
],
struct half_eye_data heye
[BOARDMAX
],
static int recognize_eye(int pos
, int *attack_point
, int *defense_point
,
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
,
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 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.
make_domains(struct eye_data b_eye
[BOARDMAX
],
struct eye_data w_eye
[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
));
memset(b_eye
, 0, BOARDMAX
* sizeof(b_eye
[0]));
memset(w_eye
, 0, BOARDMAX
* sizeof(w_eye
[0]));
/* Initialize eye data and compute the lively array. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; 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
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == EMPTY
|| !lively
[pos
]) {
if (black_domain
[pos
] == 0 && white_domain
[pos
] == 0) {
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
]) {
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
]) {
else if (black_domain
[pos
] == 1 && white_domain
[pos
] == 1) {
for (k
= 0; k
< 4; k
++) {
int apos
= pos
+ delta
[k
];
if (ON_BOARD(apos
) && black_domain
[apos
]
&& !white_domain
[apos
]) {
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
]) {
w_eye
[pos
].color
= WHITE
;
/* 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. */
partition_eyespaces(struct eye_data eye
[BOARDMAX
], int color
)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
eye
[pos
].origin
= NO_MOVE
;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (eye
[pos
].origin
== NO_MOVE
&& eye
[pos
].color
== color
) {
originate_eye(pos
, pos
, &esize
, &msize
, eye
);
/* Now we count the number of neighbors and marginal neighbors
/* 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.
* 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.
* 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])
compute_primary_domains(int color
, int domain
[BOARDMAX
],
int false_margins
[BOARDMAX
],
int other
= OTHER_COLOR(color
);
signed char threshold
[BOARDMAX
];
signed char influence
[BOARDMAX
];
int size
= 0, lastchange
= 0;
memset(threshold
, 0, sizeof(threshold
));
memset(influence
, 0, sizeof(influence
));
* 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 (board
[pos
] == color
) {
domain
[pos
] = 1; /* Case (1) above. */
for (k
= 0; k
< 4; k
++) {
if (ON_BOARD(pos2
) && lively
[pos2
]) {
if (board
[pos2
] == color
)
/* 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
if (board
[pos
] == EMPTY
&& (false_margin(pos
, color
, lively
)
|| false_margin(pos
, other
, lively
)))
else if (board
[pos
] != EMPTY
|| !false_margins
[pos
]) {
else if (is_edge_vertex(pos
))
/* Now we loop over the board until no more vertices can be added to
* the domain through 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
))) {
else if (k
== lastchange
)
break; /* Looped the whole list and found nothing new */
if (0 && (debug
& DEBUG_EYES
)) {
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
);
count_neighbours(struct eye_data eyedata
[BOARDMAX
])
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || eyedata
[pos
].origin
== NO_MOVE
)
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
++;
is_lively(int owl_call
, int pos
)
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:
* 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
* The condition above is true, curiously enough, also for the
* 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().
false_margin(int pos
, int color
, int lively
[BOARDMAX
])
int other
= OTHER_COLOR(color
);
int potential_false_margin
;
/* Require neighbors of both colors. */
if (ON_BOARD(pos
+ delta
[k
]))
neighbors
|= board
[pos
+ delta
[k
]];
if (neighbors
!= (WHITE
| BLACK
))
/* At least one opponent neighbor should be not lively. */
if (board
[pos
+ delta
[k
]] == other
&& !lively
[pos
+ delta
[k
]])
potential_false_margin
= 0;
for (k
= 0; k
< 4; k
++) {
int apos
= pos
+ delta
[k
];
if (board
[apos
] != other
|| !lively
[apos
])
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
);
* 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.
originate_eye(int origin
, int pos
,
struct eye_data eye
[BOARDMAX
])
ASSERT_ON_BOARD1(origin
);
gg_assert(esize
!= NULL
);
gg_assert(msize
!= NULL
);
eye
[pos
].origin
= origin
;
for (k
= 0; k
< 4; k
++) {
int pos2
= pos
+ delta
[k
];
&& 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).
propagate_eye(int origin
, struct eye_data eye
[BOARDMAX
])
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.
find_eye_dragons(int origin
, struct eye_data eye
[BOARDMAX
], int eye_color
,
int dragons
[], int max_dragons
)
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
)
&& eye
[WEST(pos
)].origin
== origin
&& !eye
[WEST(pos
)].marginal
)
&& eye
[NORTH(pos
)].origin
== origin
&& !eye
[NORTH(pos
)].marginal
)
&& 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
;
/* Print debugging data for the eyeshape at (i,j). Useful with GDB.
print_eye(struct eye_data eye
[BOARDMAX
], struct half_eye_data heye
[BOARDMAX
],
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 (eye
[pos2
].origin
!= pos
)
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
);
gprintf("%1m (XH) (topological eye value = %f)\n", pos2
,
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
);
gprintf("%1m (H) (topological eye value = %f)\n", pos2
,
/* Determine the size of the eye. */
for (m
= 0; m
< board_size
; m
++)
for (n
= 0; n
< board_size
; n
++) {
if (eye
[POS(m
, n
)].origin
!= origin
)
/* 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
++) {
if (eye
[pos2
].origin
== origin
) {
if (board
[pos2
] == EMPTY
) {
else if (is_halfeye(heye
, pos2
))
else if (is_halfeye(heye
, pos2
))
* 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
* 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,
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
)
*defense_point
= NO_MOVE
;
if (debug
& DEBUG_EYES
) {
print_eye(eye
, heye
, pos
);
/* Look up the eye space in the graphs database. */
if (read_eye(pos
, attack_point
, defense_point
, value
, eye
, heye
, add_moves
))
/* 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
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);
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
compute_eyes_pessimistic(int pos
, struct eyevalue
*value
,
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 margins_adjacent_to_margin
= 0;
signed char chainlinks
[BOARDMAX
];
/* Stones inside eyespace which do not coincide with a false eye or
memset(chainlinks
, 0, BOARDMAX
);
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
if (!ON_BOARD(pos2
) || eye
[pos2
].origin
!= pos
)
if (eye
[pos2
].marginal
|| is_halfeye(heye
, pos2
)) {
if (eye
[pos2
].marginal
&& eye
[pos2
].marginal_neighbors
> 0)
margins_adjacent_to_margin
++;
if (is_halfeye(heye
, pos2
))
else if (IS_STONE(board
[pos2
]))
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
]) {
mark_string(neighbor
, chainlinks
, 1);
else if (!ON_BOARD(neighbor
))
/* 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
);
*defense_point
= NO_MOVE
;
if (debug
& DEBUG_EYES
) {
print_eye(eye
, heye
, pos
);
/* Look up the eye space in the graphs database. */
if (read_eye(pos
, attack_point
, defense_point
, value
,
*pessimistic_min
= min_eyes(value
) - margins
;
/* A single point eye which is part of a ko can't be trusted. */
&& is_ko(pos
, OTHER_COLOR(eye
[pos
].color
), NULL
))
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
guess_eye_space(pos
, effective_eyesize
, margins
, bulk_score
, eye
,
DEBUG(DEBUG_EYES
, " guess_eye - %s, pessimistic_min=%d\n",
eyevalue_to_string(value
), *pessimistic_min
);
if (*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) {
DEBUG(DEBUG_EYES
, " pessimistic min revised to 1 (interior stones)\n");
&& *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
;
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
if (ON_BOARD(pos2
) && eye
[pos2
].origin
== pos
) {
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
)))
if (is_edge_vertex(pos2
))
else if (is_halfeye(heye
, pos2
)) {
this_defense_point
= heye
[pos2
].defense_point
[0];
this_attack_point
= heye
[pos2
].attack_point
[0];
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
;
*defense_point
= best_defense_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
);
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);
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)
set_eyevalue(value
, eyes
, eyes
, eyes
, eyes
);
else if (effective_eyesize
> 0) {
set_eyevalue(value
, 1, 1, 1, 1);
if (eye
[pos
].esize
- margins
> 2)
set_eyevalue(value
, 0, 0, 1, 1);
set_eyevalue(value
, 0, 0, 0, 0);
/* This function does some minor reading to improve the results of
* recognize_eye(). Currently, it has two duties. One is to read
* .XXXX| with half eye with proper eye
* XO.O.| . (1 eye) . (2 eyes)
* 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:
* XOXX. !.! (second '!' is due to the halfeye)
* 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.
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 combination_halfeye
= NO_MOVE
;
int combination_attack
= NO_MOVE
;
int combination_defense
= NO_MOVE
;
int ko_halfeye
= NO_MOVE
;
struct vital_points ko_vp
;
struct vital_points
*best_vp
= &vp
;
eye_color
= recognize_eye(pos
, attack_point
, defense_point
, value
,
/* Find ko half eyes and "combination" half eyes if any. */
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
&& eye
[pos2
].origin
== pos
&& heye
[pos2
].type
== HALF_EYE
) {
if (combination_halfeye
== 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
];
for (k
= 0; k
< heye
[pos2
].num_defenses
; k
++) {
if (eye
[heye
[pos2
].defense_point
[k
]].origin
== pos
) {
dpos
= heye
[pos2
].defense_point
[k
];
combination_halfeye
= pos2
;
combination_attack
= apos
;
combination_defense
= dpos
;
if (heye
[pos2
].value
< 3.0) {
/* 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
) {
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_halfeye
].type
= HALF_EYE
;
&& 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
;
best_vp
->num_attacks
= 1;
best_vp
->attacks
[0] = combination_attack
;
&& 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
;
best_vp
->num_defenses
= 1;
best_vp
->defenses
[0] = combination_defense
;
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) {
struct eyevalue ko_value
;
heye
[ko_halfeye
].type
= 0;
result
= recognize_eye(pos
, &apos
, &dpos
, &ko_value
, eye
,
heye
[ko_halfeye
].type
= HALF_EYE
;
if (result
&& max_eyes(value
) < max_eyes(&ko_value
)) {
/* It is worthy to win the ko. */
struct vital_eye_points
*vital
;
vital
= white_vital_points
;
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
];
/* 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).
recognize_eye(int pos
, int *attack_point
, int *defense_point
,
struct eye_data eye
[BOARDMAX
],
struct half_eye_data heye
[BOARDMAX
],
signed char marginal
[MAXEYE
], edge
[MAXEYE
], neighbors
[MAXEYE
];
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)
if (eye
[pos
].msize
> MAXEYE
)
/* Create list of eye vertices */
for (pos2
= BOARDMIN
; pos2
< BOARDMAX
; pos2
++) {
if (eye
[pos2
].origin
== pos
) {
marginal
[eye_size
] = eye
[pos2
].marginal
;
neighbors
[eye_size
] = eye
[pos2
].neighbors
;
TRACE("(%1m)", vpos
[eye_size
]);
TRACE(" %1m ", vpos
[eye_size
]);
if (is_corner_vertex(pos2
))
else if (is_edge_vertex(pos2
))
if (is_halfeye(heye
, pos2
)) {
neighbors
[eye_size
]++; /* Increase neighbors of half eye. */
/* 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
;
/* 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
++) {
if (graphs
[graph
].esize
!= eye_size
|| graphs
[graph
].msize
!= num_marginals
)
struct eye_vertex
*gv
= &graphs
[graph
].vertex
[q
];
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
if (IS_STONE(board
[vpos
[mv
]])) {
if (!(gv
->flags
& CAN_CONTAIN_STONE
))
/* Virtual half eye marginals also fall here since they are off
else if (!(gv
->flags
& CAN_BE_EMPTY
))
for (k
= 0; k
< gv
->neighbors
; 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
])
|| heye
[vpos
[mv
]].type
!= HALF_EYE
)
|| heye
[vpos
[mn
]].type
!= HALF_EYE
)) {
gprintf(" q=%d, esize=%d: %d %d %d %d %d\n",
map
[0], map
[1], map
[2], map
[3], map
[4]);
/* We have found a match! Now sort out the vital moves. */
*value
= graphs
[graph
].value
;
if (eye_move_urgency(value
) > 0) {
/* Collect all attack and defense points in the pattern. */
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.
&& vpos
[map
[k
] - 1] != NO_MOVE
&& is_halfeye(heye
, vpos
[map
[k
] - 1])) {
/* Add all diagonals as vital. */
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
];
vp
->attacks
[vp
->num_attacks
++] = vpos
[map
[k
]];
if (ev
->flags
& EYE_DEFENSE_POINT
) {
/* Check for a half eye virtual marginal vertex. */
&& vpos
[map
[k
] - 1] != NO_MOVE
&& is_halfeye(heye
, vpos
[map
[k
] - 1])) {
/* Add all diagonals as vital. */
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
];
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
* 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
* 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
for (k
= 0; k
< vp
->num_attacks
; k
++) {
int apos
= vp
->attacks
[k
];
if (ON_BOARD(apos
+ delta
[r
])
&& eye
[apos
+ delta
[r
]].color
== eye
[pos
].color
&& !eye
[apos
+ delta
[r
]].marginal
) {
if (board
[apos
+ delta
[r
]] != EMPTY
)
/* 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,
* Playing this is probably a good idea.
gprintf("attack point %1m score %d\n", apos
, score
);
if (score
> best_score
) {
for (k
= 0; k
< vp
->num_defenses
; k
++) {
int dpos
= vp
->defenses
[k
];
if (ON_BOARD(dpos
+ delta
[r
])
&& eye
[dpos
+ delta
[r
]].color
== eye
[pos
].color
&& !eye
[dpos
+ delta
[r
]].marginal
) {
if (board
[dpos
+ delta
[r
]] != EMPTY
)
/* If possible, choose a non-sacrificial defense point.
* Compare white T8 and T6 in lazarus:21.
if (safe_move(dpos
, eye_color
) != WIN
)
/* See comment to the same code for attack points. */
gprintf("defense point %1m score %d\n", dpos
, score
);
if (score
> best_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
);
/* 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
memset(used_index
, 0, size
* sizeof(used_index
[0]));
/* The function first_map finds the smallest valid
* value of a map element.
first_map(int *map_value
)
/* 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.
next_map(int *q
, int map
[MAXEYE
])
for (k
= map
[*q
]; ++k
< map_size
;) {
/* add_false_eye() turns a proper eyespace into a margin. */
add_false_eye(int pos
, struct eye_data eye
[BOARDMAX
],
struct half_eye_data heye
[BOARDMAX
])
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)
eye
[eye
[pos
].origin
].msize
++;
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.
return (white_eye
[pos
].color
== WHITE
|| black_eye
[pos
].color
== BLACK
);
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
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
);
is_marginal_eye_space(int pos
)
return (white_eye
[pos
].marginal
|| black_eye
[pos
].marginal
);
is_halfeye(struct half_eye_data heye
[BOARDMAX
], int pos
)
return heye
[pos
].type
== HALF_EYE
;
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).
find_half_and_false_eyes(int color
, struct eye_data eye
[BOARDMAX
],
struct half_eye_data heye
[BOARDMAX
],
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))
/* skip every vertex which can't be a false or half eye */
if (eye
[pos
].color
!= eye_color
|| eye
[pos
].neighbors
> 1)
sum
= topological_eye(pos
, color
, eye
, heye
);
heye
[pos
].type
= FALSE_EYE
;
|| is_legal(pos
, OTHER_COLOR(color
))
|| board
[pos
] == OTHER_COLOR(color
))
add_false_eye(pos
, eye
, heye
);
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
* my_eye is the eye space information with respect to (color).
topological_eye(int pos
, int color
,
struct eye_data my_eye
[BOARDMAX
],
struct half_eye_data heye
[BOARDMAX
])
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
,
* Eyespaces with cutting points are problematic. In this position
* 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
* 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
* 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,
* 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
* 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
if (val
< 2.0 && board
[pos
] == EMPTY
&& board
[diag
] == OTHER_COLOR(color
)
&& !is_edge_vertex(pos
) && neighbor_of_string(pos
, diag
)
&& countstones(diag
) >= 3) {
for (r
= 0; r
< 4; r
++) {
ASSERT1(string_count
< 3, pos
);
for (s
= 0; s
< string_count
; s
++)
if (same_string(str
, strings
[s
]))
strings
[string_count
++] = str
;
for (s
= 0; s
< string_count
; s
++) {
lib_count
= findlib(strings
[s
], MAX_LIBERTIES
, libs
);
if (lib_count
> MAX_LIBERTIES
)
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
)
if (val
> 0.0 && val
< 2.0) {
/* Diagonals off the edge has value 1.0 but no attack or defense
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
* --- ------------ -------------
* 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.
for (r
= 0; r
< 4; r
++) {
if (attack_values
[r
] < attack_value
) {
int tmp_value
= attack_values
[r
];
tmp_point
= heye
[pos
].attack_point
[r
];
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
];
tmp_point
= heye
[pos
].defense_point
[r
];
defense_values
[r
] = defense_value
;
heye
[pos
].defense_point
[r
] = defense_point
;
defense_value
= tmp_value
;
defense_point
= tmp_point
;
/* 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]) {
for (r
= 0; r
< num_defenses
; r
++) {
if (defense_values
[r
] < defense_values
[0]) {
heye
[pos
].num_attacks
= num_attacks
;
heye
[pos
].num_defenses
= num_defenses
;
/* Evaluate an intersection (m, n) which is diagonal to an eye space,
* as described in the Texinfo documentation (Eyes/Eye Topology).
* 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
* 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.
evaluate_diagonal_intersection(int m
, int n
, int color
,
int *attack_point
, int *defense_point
,
struct eye_data my_eye
[BOARDMAX
])
int other
= OTHER_COLOR(color
);
*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"
if (m
< 0 || m
>= board_size
)
if (n
< 0 || n
>= board_size
)
/* Must return 0 if both coordinates out of bounds. */
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,
* 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:
* 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
if (my_eye
[pos
].color
== color
&& my_eye
[pos
].marginal_neighbors
< 2
&& !(board
[pos
] == EMPTY
&& does_capture_something(pos
, other
)))
if (board
[pos
] == EMPTY
) {
int your_safety
= safe_move(pos
, other
);
/* 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:
* Therefore we ignore our own safety if opponent's safety depends
else if (your_safety
!= WIN
)
else { /* So your_safety == WIN. */
int our_safety
= safe_move(pos
, color
);
/* 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:
* Without this check, the corner eye is considered false, not half-
* eye. Thus, owl thinks that the capture gains at most one eye and
for (k
= 4; k
< 8; k
++) {
int diagonal
= pos
+ delta
[k
];
if (board
[diagonal
] == other
&& findlib(diagonal
, 1, &lib
) == 1) {
if (lib
!= pos
&& does_secure(color
, lib
, pos
)) {
else if (our_safety
== WIN
)
else /* our_safety depends on ko. */
else if (board
[pos
] == color
) {
/* This stone had better be safe, otherwise we wouldn't have an
* eyespace in the first place.
else if (board
[pos
] == other
) {
acode
= worm
[pos
].attack_codes
[0];
apos
= worm
[pos
].attack_points
[0];
dcode
= worm
[pos
].defense_codes
[0];
dpos
= worm
[pos
].defense_points
[0];
attack_and_defend(pos
, &acode
, &apos
, &dcode
, &dpos
);
/* Must test acode first since dcode only is reliable if acode is
else if (acode
== WIN
&& dcode
== WIN
)
else if (acode
== WIN
&& dcode
!= WIN
)
else if (acode
!= WIN
&& dcode
== WIN
)
else if (acode
!= WIN
&& dcode
!= WIN
)
value
= 1.0; /* Both contingent on ko. Probably can't happen. */
if (value
> 0.0 && value
< 2.0) {
* Usually there are several attack and defense moves that would
* be equally valid. It's not good that we make an arbitrary
* 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
/* 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.
obvious_false_eye(int pos
, int color
)
for (k
= 4; k
< 8; k
++) {
if (!ON_BOARD2(i
+di
, j
) && !ON_BOARD2(i
, j
+dj
))
if (!ON_BOARD2(i
+di
, j
+dj
))
else if (BOARD(i
+di
, j
+dj
) == OTHER_COLOR(color
)
&& !attack(POS(i
+di
, j
+dj
), NULL
))
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
set_eyevalue(struct eyevalue
*e
, int a
, int b
, int c
, int d
)
/* Number of eyes if attacker plays first twice (the threat of the first
min_eye_threat(struct eyevalue
*e
)
/* Number of eyes if attacker plays first followed by alternating play. */
min_eyes(struct eyevalue
*e
)
/* Number of eyes if defender plays first followed by alternating play. */
max_eyes(struct eyevalue
*e
)
/* Number of eyes if defender plays first twice (the threat of the first
max_eye_threat(struct eyevalue
*e
)
/* Add the eyevalues *e1 and *e2, leaving the result in *sum. It is
* safe to let sum be the same as e1 or e2.
add_eyevalues(struct eyevalue
*e1
, struct eyevalue
*e2
, struct eyevalue
*sum
)
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
/* 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)
eye_move_urgency(struct eyevalue
*e
)
/* 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.
eyevalue_to_string(struct eyevalue
*e
)
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
);
gg_snprintf(result
, 29, "[%d,%d,%d,%d]", e
->a
, e
->b
, e
->c
, e
->d
);
/* Test whether the optics code evaluates an eyeshape consistently. */
test_eyeshape(int eyesize
, int *eye_vertices
)
struct board_state starting_position
;
/* Clear the board and initialize the engine properly. */
/* Mark the eyespace in the mx array. */
memset(mx
, 0, sizeof(mx
));
for (k
= 0; k
< eyesize
; k
++) {
ASSERT_ON_BOARD1(eye_vertices
[k
]);
/* Play white stones surrounding the eyespace, including diagonals. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (!ON_BOARD(pos
) || mx
[pos
] == 1)
for (k
= 0; k
< 8; k
++) {
if (ON_BOARD(pos
+ delta
[k
]) && mx
[pos
+ delta
[k
]] == 1) {
/* Play black stones surrounding the white group, but leaving all
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (mx
[pos
] == 1 || board
[pos
] != EMPTY
|| liberty_of_string(pos
, str
))
for (k
= 0; k
< 8; k
++) {
if (ON_BOARD(pos
+ delta
[k
])
&& liberty_of_string(pos
+ delta
[k
], str
)) {
/* 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.
/* 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.
for (n
= 0; n
< N
; n
++) {
restore_board(&starting_position
);
/* Play the stones for this configuration. */
for (k
= 0; k
< eyesize
; k
++) {
if (!is_legal(eye_vertices
[k
], BLACK
)) {
play_move(eye_vertices
[k
], BLACK
);
/* Now we are ready to test the consistency. This is most easily
* done with help from the owl code. First we must prepare for
examine_position(EXAMINE_DRAGONS_WITHOUT_OWL
, 0);
attack_code
= owl_attack(str
, &attack_point
, NULL
, NULL
);
/* 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
]);
/* Furthermore, if the eyespace is almost filled, white should
* be able to play on the remaining eyespace point and still be
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
);
defense_code
= owl_defend(str
, &defense_point
, NULL
, NULL
);
/* 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
]);
/* 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
);
else if (!owl_does_attack(attack_point
, str
, NULL
)) {
gprintf("Attack point %1m failed:\n", attack_point
);
if (board
[defense_point
] != EMPTY
|| !is_legal(defense_point
, WHITE
)) {
gprintf("Bad defense point %1m:\n", defense_point
);
else if (!owl_does_defend(defense_point
, str
, NULL
)) {
gprintf("Defense point %1m failed:\n", defense_point
);
/********************************************************************
* 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
* 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
* white_area() is a helper to add a small invincible black group on
* 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
* tactical_life_attack() and tactical_life_defend() are two mutually
* recursive functions which perform the actual reading for
* 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
* 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:
* 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.
eyegraph_trymove(int pos
, int color
, const char *message
, int str
)
static Hash_data remembered_board_hashes
[MAXSTACK
];
int does_capture
= does_capture_something(pos
, color
);
remembered_board_hashes
[stackp
] = board_hash
;
if (!trymove(pos
, color
, message
, str
))
for (k
= 0; k
< stackp
; k
++)
if (hashdata_is_equal(board_hash
, remembered_board_hashes
[k
])) {
eyegraph_is_margin_or_outer_liberty(int vertex
)
for (k
= 0; k
< 4; k
++) {
if (board
[vertex
+ delta
[k
]] == BLACK
) {
num_libs
= findlib(vertex
+ delta
[k
], MAXLIBS
, libs
);
for (r
= 0; r
< num_libs
; r
++)
if (is_suicide(libs
[r
], WHITE
))
eyegraph_order_moves(int num_vertices
, int *vertices
, int color_to_move
, int *moves
)
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
)
/* No use playing the second outer liberty before the first one. */
if (k
== num_vertices
- 2 && board
[vertices
[num_vertices
- 3]] == EMPTY
)
if (board
[move
] != EMPTY
)
if (eyegraph_is_margin_or_outer_liberty(move
)) {
if (k
< num_vertices
- 3)
score
= -10; /* outer liberty */
if (accuratelib(move
, color_to_move
, 2, NULL
) == 1)
for (r
= 0; r
< 4; r
++) {
if (board
[move
+ delta
[r
]] == EMPTY
)
else if (board
[move
+ delta
[r
]] == BLACK
)
scores
[num_moves
] = score
;
for (k
= 0; k
< num_moves
; k
++) {
int maxscore
= scores
[k
];
/* Find the move with the biggest score. */
for (r
= k
+ 1; r
< num_moves
; r
++) {
if (scores
[r
] > maxscore
) {
/* Now exchange the move at k with the move at max_at.
* Don't forget to exchange the scores as well.
int temp
= moves
[max_at
];
moves
[max_at
] = moves
[k
];
scores
[max_at
] = scores
[k
];
/* 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.
white_area(int mx
[BOARDMAX
], int pos
, int up
, int right
, int marginpos
,
int edge
= is_edge_vertex(marginpos
);
for (k
= 1; k
< distance
; k
++)
if (!ON_BOARD(marginpos
+ k
* up
)
|| mx
[marginpos
+ k
* up
] != WHITE
)
for (u
= -1; u
<= 4; u
++)
for (v
= -1; v
<= 4; v
++) {
int pos2
= pos
+ u
* up
+ v
* right
;
else if (u
>= 0 && u
<= 3 && v
>= 0 && v
<= 3)
else if (I(pos2
) != I(NORTH(marginpos
))
&& I(pos2
) != I(SOUTH(marginpos
))
&& J(pos2
) != J(WEST(marginpos
))
&& J(pos2
) != J(EAST(marginpos
)))
else if (mx
[pos2
] != WHITE
)
for (v
= 0; v
<= 3; v
++) {
int pos2
= pos
+ u
* up
+ v
* right
;
mx
[pos
+ up
+ right
] = EMPTY
;
mx
[pos
+ 2 * up
+ 2 * right
] = EMPTY
;
#define EYEGRAPH_RETURN(result, trace) \
sgftreeAddComment(sgf_dumptree, (trace)); \
static int tactical_life_defend(int str
, int num_vertices
, int *vertices
,
/* Determine whether black can capture all white stones. */
tactical_life_attack(int str
, int num_vertices
, int *vertices
,
/* Compute hash value to index the result cache with. */
for (k
= 0; k
< num_vertices
; k
++) {
hash
+= board
[vertices
[k
]];
hash
+= (board_ko_pos
!= NO_MOVE
);
/* Is the result known from the cache? */
cached_result
= results
[hash
] & 3;
gprintf("%d %d (%d)\n", hash
, cached_result
, results
[hash
]);
EYEGRAPH_RETURN(0, "tactical_life_attack: 0 (cached)");
EYEGRAPH_RETURN(1, "tactical_life_attack: win (cached)");
EYEGRAPH_RETURN(1, "tactical_life_attack: win (open node in cache)");
/* Mark this entry in the cache as currently being computed. */
/* 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
++) {
if (eyegraph_trymove(move
, OTHER_COLOR(board
[str
]),
"tactical_life_attack", str
)) {
/* We were successful if the white stones were captured or if no
result
= !tactical_life_defend(str
, num_vertices
, vertices
, results
);
/* 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. */
tactical_life_defend(int str
, int num_vertices
, int *vertices
,
/* Compute hash value to index the result cache with. */
for (k
= 0; k
< num_vertices
; k
++) {
ASSERT1(board
[vertices
[k
]] <= 2, vertices
[k
]);
hash
+= board
[vertices
[k
]];
hash
+= (board_ko_pos
!= NO_MOVE
);
/* Is the result known from the cache? */
cached_result
= (results
[hash
] >> 2) & 3;
gprintf("%d %d (%d)\n", hash
, cached_result
, results
[hash
]);
EYEGRAPH_RETURN(0, "tactical_life_defend: 0 (cached)");
EYEGRAPH_RETURN(1, "tactical_life_defend: win (cached)");
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
++) {
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
);
/* 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.
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
,
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
if (board
[str
] == EMPTY
) {
/* The stones have already been captured, too late to defend. */
/* Fill in the extra eye if have_eye is 0. If filling in would be
* suicide the white stones can be considered dead.
if (!eyegraph_trymove(POS(0, 0), WHITE
, "tactical_life-A", NO_MOVE
)) {
/* Call tactical_life_attack() and tactical_life_defend() to
if (tactical_life_attack(str
, num_vertices
, vertices
, results
)) {
if (tactical_life_defend(str
, num_vertices
, vertices
, results
))
/* 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_moves
= eyegraph_order_moves(num_vertices
, vertices
,
OTHER_COLOR(board
[str
]), moves
);
for (k
= 0; k
< num_moves
; k
++) {
if (eyegraph_trymove(move
, OTHER_COLOR(board
[str
]), "tactical_life-B",
|| !tactical_life_defend(str
, num_vertices
, vertices
, results
))
attack_points
[(*num_attacks
)++] = move
;
if (num_defenses
!= NULL
&& defense_points
!= NULL
) {
num_moves
= eyegraph_order_moves(num_vertices
, vertices
, board
[str
],
for (k
= 0; k
< num_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
;
/* Unfill the extra eye if we didn't use it. */
/* 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.
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 attack_points
[BOARDMAX
];
int defense_points
[BOARDMAX
];
int attack_points2
[BOARDMAX
];
int vital_attacks2
[BOARDMAX
];
int vital_defenses2
[BOARDMAX
];
/* 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
,
/* Alive without extra eye.
* Possible results: 0222, 1222, 2222
* Determine whether there are ko threats and how serious.
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
++) {
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
);
tactical_life(1, num_vertices
, vertices
, &acode
, NULL
, NULL
,
&dcode
, NULL
, NULL
, tactical_life_results
);
vital_attacks
[(*num_vital_attacks
)++] = move
;
sgftreeAddComment(sgf_dumptree
,
"Ko threat to remove both eyes.\n");
vital_attacks
[(*num_vital_attacks
)++] = move
;
sgftreeAddComment(sgf_dumptree
, "Ko threat to remove one eye.\n");
set_eyevalue(result
, a
, 2, 2, 2);
sgftreeAddComment(sgf_dumptree
, "Eyevalue 0222.\n");
sgftreeAddComment(sgf_dumptree
, "Eyevalue 1222.\n");
sgftreeAddComment(sgf_dumptree
, "Eyevalue 2222.\n");
else if (defense_code
!= 0) {
/* Critical without extra eye.
* Possible results: 0022, 0122, 1122
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
) {
set_eyevalue(result
, 0, 0, 2, 2);
for (k
= 0; k
< num_attacks2
; k
++)
vital_attacks
[(*num_vital_attacks
)++] = attack_points2
[k
];
sgftreeAddComment(sgf_dumptree
, "Eyevalue: 0022.\n");
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
,
/* 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) {
vital_attacks
[(*num_vital_attacks
)++] = move
;
vital_attacks
[(*num_vital_attacks
)++] = move
;
set_eyevalue(result
, a
, 1, 2, 2);
sgftreeAddComment(sgf_dumptree
, "Eyevalue: 0122.\n");
sgftreeAddComment(sgf_dumptree
, "Eyevalue: 1122.\n");
/* Dead without extra eye.
* Possible results: 0000, 0001, 0002, 0011, 0012, 0111, 0112, 1111, 1112
* Now determine tactical life with an extra eye.
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
,
* Possible results: 0111, 0112, 1111, 1112
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
++) {
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
);
evaluate_eyespace(&result2
, num_vertices
, vertices
,
&num_vital_attacks2
, vital_attacks2
,
&num_vital_defenses2
, vital_defenses2
,
/* This is either 0011 or 0012. Only the first is acceptable. */
if (max_eye_threat(&result2
) == 1) {
vital_attacks
[(*num_vital_attacks
)++] = move
;
sgftreeAddComment(sgf_dumptree
, "Attacking ko threat.\n");
num_moves
= eyegraph_order_moves(num_vertices
, vertices
, WHITE
, moves
);
for (k
= 0; k
< num_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
);
evaluate_eyespace(&result2
, num_vertices
, vertices
,
&num_vital_attacks2
, vital_attacks2
,
&num_vital_defenses2
, vital_defenses2
,
/* This is either 1122 or 0122. Only the first is acceptable. */
if (min_eye_threat(&result2
) == 1) {
vital_defenses
[(*num_vital_defenses
)++] = move
;
sgftreeAddComment(sgf_dumptree
, "Defending ko threat.\n");
set_eyevalue(result
, a
, 1, 1, d
);
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");
sgftreeAddComment(sgf_dumptree
, "Eyevalue 1112.\n");
else if (defense_code
!= 0) {
/* Critical with extra eye.
* Possible results: 0011, 0012
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
,
/* 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) {
vital_defenses
[(*num_vital_defenses
)++] = move
;
vital_defenses
[(*num_vital_defenses
)++] = move
;
set_eyevalue(result
, 0, 0, 1, d
);
sgftreeAddComment(sgf_dumptree
, "Eyevalue: 0011.\n");
sgftreeAddComment(sgf_dumptree
, "Eyevalue: 0012.\n");
* Possible results: 0000, 0001, 0002
* Determine whether there are ko threats and how serious.
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
++) {
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
);
tactical_life(0, num_vertices
, vertices
, &acode
, NULL
, NULL
,
&dcode
, NULL
, NULL
, tactical_life_results
);
vital_defenses
[(*num_vital_defenses
)++] = move
;
sgftreeAddComment(sgf_dumptree
,
"Ko threat to make two eyes.\n");
vital_defenses
[(*num_vital_defenses
)++] = move
;
sgftreeAddComment(sgf_dumptree
,
"Ko threat to make one eye.\n");
set_eyevalue(result
, 0, 0, 0, d
);
sgftreeAddComment(sgf_dumptree
, "Eyevalue 0000.\n");
sgftreeAddComment(sgf_dumptree
, "Eyevalue 0001.\n");
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.
add_margins(int num_margins
, int *margins
, int mx
[BOARDMAX
])
memcpy(old_mx
, mx
, sizeof(old_mx
));
pos
= margins
[num_margins
- 1];
for (k
= 0; k
< 4; k
++) {
int right
= delta
[(k
+ 1) % 4];
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
)) {
while (mx
[pos
+ s
* up
] == WHITE
) {
mx
[pos
+ s
* up
] = BLACK
;
if (add_margins(num_margins
- 1, margins
, mx
))
memcpy(mx
, old_mx
, sizeof(old_mx
));
/* 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
* 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)
* If the eye graph cannot be realized, 0 is returned, 1 otherwise.
analyze_eyegraph(const char *coded_eyegraph
, struct eyevalue
*value
,
int vital_attacks
[BOARDMAX
]; /* Way larger than necessary. */
int vital_defenses
[BOARDMAX
]; /* Way larger than necessary. */
int margins
[BOARDMAX
]; /* Way larger than necessary. */
int vertices
[BOARDMAX
]; /* Way larger than necessary. */
unsigned char *tactical_life_results
;
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
++)
/* Find out the size of the eye graph pattern so that we can center
for (k
= 0; k
< (int) strlen(coded_eyegraph
); k
++) {
if (coded_eyegraph
[k
] == '\n')
if (coded_eyegraph
[k
] == '%') {
if (current_width
> maxwidth
)
maxwidth
= current_width
;
if (coded_eyegraph
[k
] == '-')
horizontal_edge
= num_rows
- 1;
else if (coded_eyegraph
[k
] == '|')
vertical_edge
= current_width
;
if (current_width
> maxwidth
)
maxwidth
= current_width
;
/* Cut out the eyespace from the solid white string. */
if (horizontal_edge
== 0)
else if (horizontal_edge
> 0)
mini
= board_size
- num_rows
+ 1;
mini
= (board_size
- num_rows
) / 2;
else if (vertical_edge
> 0)
minj
= board_size
- maxwidth
+ 1;
minj
= (board_size
- maxwidth
) / 2;
for (k
= 0; k
< (int) strlen(coded_eyegraph
); k
++) {
char c
= coded_eyegraph
[k
];
else if (c
== 'X' || c
== '$')
else if (c
== '.' || c
== '*' || c
== '<' || c
== '>'
|| c
== '!' || c
== '@' || c
== '(' || c
== ')')
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
);
/* 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
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);
/* Add the two outer liberties in the lower left or upper right to
vertices
[num_vertices
++] = NE(pos
);
vertices
[num_vertices
++] = NN(pos
);
vertices
[num_vertices
++] = SW(pos
);
vertices
[num_vertices
++] = SS(pos
);
/* Add an extra eye in the upper left corner. */
vertices
[num_vertices
++] = POS(0, 0);
if (!add_margins(num_margins
, margins
, mx
))
/* Copy the mx array over to the board. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
else if (mx
[pos
] == BLACK
)
/* If there are any isolated O stones, those should also be added to
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
;
gprintf("\nPlayable vertices:\n");
for (k
= 0; k
< num_vertices
; k
++)
gprintf("%1m ", vertices
[k
]);
/* Disable this test if you need to evaluate larger eyespaces, have
* no shortage of memory, and know what you're doing.
gprintf("analyze_eyegraph: too large eyespace, %d vertices\n",
gg_assert(num_vertices
<= 17);
/* The cache must have 2*3^num_vertices entries. */
for (k
= 0; k
< num_vertices
; k
++)
/* 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
);
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
,
/* Return the cache memory. */
free(tactical_life_results
);
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
];
/* Return the central part of the mg[] array (corresponding to the
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
++] = '|';
analyzed_eyegraph
[k
++] = mg
[POS(i
, j
)];
analyzed_eyegraph
[k
++] = '\n';
analyzed_eyegraph
[k
- 1] = 0;