/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Forward declarations */
static int goal_dist(int pos
, signed char goal
[BOARDMAX
]);
static int compare_angles(const void *a
, const void *b
);
static void show_surround_map(signed char mf
[BOARDMAX
],
signed char mn
[BOARDMAX
]);
static int gg
; /* stores the gravity center of the goal */
/* Returns true if a dragon is enclosed within the convex hull of
* its hostile neighbor dragons. This is an indication that the dragon is
* in danger. Stones on the second and first lines are not tested.
* Normally NULL will be passed to the parameter apos. It can be
* an empty board location. If apos is non NULL it is marked and
* added to the the hull. Thus we can ask if adding a single stone
* to the board surrounds the dragon.
* A CORNER is a vertex of the polygon which comprises this convex
* hull. The algorithm proceeds by first finding the sequence of
* corners on the left side of the polyhedron, then the sequence
* of corners on the right side.
* The hull is marked in the array mn with the number 1. A slight
* expansion is marked with the number 2. Return code is SURROUNDED if
* the friendly dragon lies within the area marked 1,
* WEAKLY_SURROUNDED if it lies in the slightly larger area marked 1
* and 2, and 0 otherwise.
* The notion of weak surroundedness seems to be much less indicative
* of a dragon's immanent danger than surroundedness.
* An exception: if the larger area contains any stone of a different
* friendly dragon (which is not DEAD) the return code is 0, unless
* that allied dragon is ENTIRELY contained within the hull.
* Another exception: an ikken tobi (one space jump) is generally not
* a connection but in practice may be almost as good. If there is an
* ikken tobi out of the hull, then the dragon is not surrounded.
* If the parameter showboard is 1, the figure is drawn. If showboard
* is 2, the figure is only drawn if the region is surrounded.
* If (apos) is NULL, the result is saved in the surround_data cache.
* The assumption is that the function will only be called once
* with (apos) null, during make_dragons; thereafter the surroundedness
* will be accessed using the function is_surrounded().
* If *surround_size is not a NULL pointer, then surround_size
* returns the size of the surroundings.
compute_surroundings(int pos
, int apos
, int showboard
, int *surround_size
)
int left_corner
[MAX_BOARD
];
int right_corner
[MAX_BOARD
];
int left_corners
= 0, right_corners
= 0;
int other
= OTHER_COLOR(color
);
signed char mf
[BOARDMAX
]; /* friendly dragon */
signed char mn
[BOARDMAX
]; /* neighbor dragons */
int sd
[BOARDMAX
]; /* distances to the goal */
if (DRAGON2(pos
).hostile_neighbors
== 0)
memset(mf
, 0, sizeof(mf
));
memset(mn
, 0, sizeof(mn
));
memset(sd
, 0, sizeof(sd
));
/* mark hostile neighbors */
for (k
= 0; k
< DRAGON2(pos
).neighbors
; k
++) {
int nd
= DRAGON(DRAGON2(pos
).adjacent
[k
]).origin
;
if (board
[nd
] != color
) {
gprintf("neighbor: %1m\n", nd
);
/* descend markings from stones lying on the 2nd and third lines */
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
if (ON_BOARD(dpos
) && mn
[dpos
]) {
for (k
= 0; k
< 4; k
++) {
if (!ON_BOARD(dpos
+ 2*d
)) {
if (board
[dpos
+ d
] == EMPTY
)
else if (!ON_BOARD(dpos
+ 3*d
)) {
if (board
[dpos
+ d
] == EMPTY
&& board
[dpos
+ 2*d
] == EMPTY
)
/* compute minimum distances to the goal */
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
if (ON_BOARD(dpos
) && mn
[dpos
])
sd
[dpos
] = goal_dist(dpos
, mf
);
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
if (ON_BOARD(dpos
) && mn
[dpos
] && sd
[dpos
] > 8) {
/* discard markings if we can find 2 stones
* - it is closer to the goal than we are
* - it is closer to us than the goal is
* - they are closer to each other than we are to the goal
for (i
= BOARDMIN
; i
< BOARDMAX
; i
++)
if (ON_BOARD(i
) && mn
[i
] && i
!= dpos
&& square_dist(i
, dpos
) < sd
[dpos
]) {
for (j
= i
+ 1; j
< BOARDMAX
; j
++)
if (ON_BOARD(j
) && mn
[j
] && j
!= dpos
&& square_dist(j
, dpos
) < sd
[dpos
]
&& square_dist(i
, j
) < sd
[dpos
]) {
/* prepare corner array */
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
if (ON_BOARD(dpos
) && mn
[dpos
])
corner
[corners
++] = dpos
;
/* compute gravity center of the goal */
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
if (ON_BOARD(dpos
) && mf
[dpos
]) {
/* sort the corner array */
gg_sort(corner
, corners
, sizeof(int), compare_angles
);
/* if apos is not NO_MOVE, mark it. */
show_surround_map(mf
, mn
);
/* find top row of surrounding polyhedron */
for (m
= 0; m
< board_size
; m
++) {
for (n
= 0; n
< board_size
; n
++)
left_corner
[0] = POS(m
, n
);
for (m
= board_size
- 1; m
>= 0; m
--) {
for (n
= 0; n
< board_size
; n
++)
/* find the corners on the left side */
for (left_corners
= 1; I(left_corner
[left_corners
-1]) < bottom_row
;
int m
= I(left_corner
[left_corners
-1]);
int n
= J(left_corner
[left_corners
-1]);
for (i
= m
+ 1; i
<= bottom_row
; i
++)
for (j
= 0; j
< board_size
; j
++)
float slope
= ((float) (j
- n
))/((float) (i
- m
));
gprintf("(left) at %m, last %m, slope=%f\n", i
, j
, m
, n
, slope
);
if (!best_found
|| slope
< best_slope
) {
ASSERT_ON_BOARD1(best_found
);
left_corner
[left_corners
] = best_found
;
for (n
= board_size
-1; n
>= 0; n
--)
if (mn
[POS(top_row
, n
)]) {
right_corner
[0] = POS(top_row
, n
);
/* find the corners on the right side */
for (right_corners
= 1; I(right_corner
[right_corners
-1]) < bottom_row
;
int m
= I(right_corner
[right_corners
-1]);
int n
= J(right_corner
[right_corners
-1]);
for (i
= m
+ 1; i
<= bottom_row
; i
++) {
for (j
= board_size
- 1; j
>= 0; j
--) {
float slope
= ((float) (j
- n
))/((float) (i
- m
));
gprintf("(right) at %m, last %m, slope=%f\n", i
, j
, m
, n
, slope
);
if (!best_found
|| slope
> best_slope
) {
ASSERT_ON_BOARD1(best_found
);
right_corner
[right_corners
] = best_found
;
for (k
= 0; k
< left_corners
; k
++)
gprintf("left corner %d: %1m\n", k
, left_corner
[k
]);
for (k
= 0; k
< right_corners
; k
++)
gprintf("right corner %d: %1m\n", k
, right_corner
[k
]);
/* Now mark the interior of the convex hull */
for (n
= J(left_corner
[0]); n
<= J(right_corner
[0]); n
++)
for (n
= J(left_corner
[left_corners
-1]);
n
<= J(right_corner
[right_corners
-1]); n
++)
mn
[POS(bottom_row
, n
)] = 1;
for (m
= top_row
+1; m
< bottom_row
; m
++) {
int left_boundary
= -1, right_boundary
= -1;
for (k
= 1; k
< left_corners
; k
++) {
if (I(left_corner
[k
]) > m
) {
float ti
= I(left_corner
[k
-1]);
float tj
= J(left_corner
[k
-1]);
float bi
= I(left_corner
[k
]);
float bj
= J(left_corner
[k
]);
gprintf("(left) %d: %1m %1m\n",
m
, left_corner
[k
-1], left_corner
[k
]);
/* left edge in this row is on segment (ti,tj) -> (bi, bj) */
/* FIXME: Rewrite this to avoid floating point arithmetic */
left_boundary
= ceil(tj
+ (m
- ti
) * (bj
- tj
) / (bi
- ti
));
for (k
= 1; k
< right_corners
; k
++) {
if (I(right_corner
[k
]) > m
) {
float ti
= I(right_corner
[k
-1]);
float tj
= J(right_corner
[k
-1]);
float bi
= I(right_corner
[k
]);
float bj
= J(right_corner
[k
]);
gprintf("(right) %d: %1m %1m\n",
m
, right_corner
[k
-1], right_corner
[k
]);
/* FIXME: Rewrite this to avoid floating point arithmetic */
right_boundary
= floor(tj
+ (m
- ti
) * (bj
- tj
) / (bi
- ti
));
for (n
= left_boundary
; n
<= right_boundary
; n
++)
/* mark the expanded region */
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
if (ON_BOARD(dpos
) && mn
[dpos
] == 1)
if (ON_BOARD(dpos
+ delta
[k
]) && !mn
[dpos
+ delta
[k
]])
/* Mark allied dragons that intersect the (unexpanded) hull.
* These must all lie entirely within the hull for the
* dragon to be considered surrounded.
* Only neighbor dragons are considered since dragons that
* are not neighbors are less likely to be helpful.
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++) {
&& are_neighbor_dragons(pos
, dpos
)
for (mpos
= BOARDMIN
; mpos
< BOARDMAX
; mpos
++)
if (ON_BOARD(mpos
) && is_same_dragon(mpos
, dpos
))
* The O stone hasn't been amalgamated and the surround computations
* might think this single stone dragon is surrounded, which in turn
* can generate overvaluation of moves around this stone.
* Consequently, we allow inclusion of the stones at kosumi distance
* in the mf (friendly) array.
&& are_neighbor_dragons(pos
, dpos
)
if (ON_BOARD(dpos
+ delta
[k
]) && board
[dpos
+ delta
[k
]] == color
&& mn
[dpos
+ delta
[k
]] == 1
&& board
[dpos
+ delta
[k
-4]] == EMPTY
&& board
[dpos
+ delta
[(k
-3)%4]] == EMPTY
) {
for (mpos
= BOARDMIN
; mpos
< BOARDMAX
; mpos
++)
if (ON_BOARD(mpos
) && is_same_dragon(mpos
, dpos
))
/* determine the surround status of the dragon */
/* Compute the maximum surround status awarded
* If distances between enclosing stones are large, reduce to
* WEAKLY_SURROUNDED. If (really) too large, then reduce to 0
* FIXME: constants chosen completely ad hoc. Possibly better tunings
for (k
= 0; k
< corners
- 1; k
++) {
if (is_edge_vertex(corner
[k
])
&& is_edge_vertex(corner
[k
+1]))
if (square_dist(corner
[k
], corner
[k
+1]) > 60) {
else if (square_dist(corner
[k
], corner
[k
+1]) > 27)
surrounded
= WEAKLY_SURROUNDED
;
&& (!is_edge_vertex(corner
[0])
|| !is_edge_vertex(corner
[corners
-1]))) {
if (square_dist(corner
[0], corner
[corners
-1]) > 60)
else if (square_dist(corner
[0], corner
[corners
-1]) > 27)
surrounded
= WEAKLY_SURROUNDED
;
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
; dpos
++)
surrounded
= WEAKLY_SURROUNDED
;
/* revise the status for single stone dragons. */
&& surrounded
== WEAKLY_SURROUNDED
/* revise the status if an ikken tobi jumps out. */
for (dpos
= BOARDMIN
; dpos
< BOARDMAX
&& surrounded
; dpos
++) {
if (!ON_BOARD(dpos
) || !mf
[dpos
])
for (k
= 0; k
< 4; k
++) {
int right
= delta
[(k
+ 1) % 4];
if (board
[dpos
+ up
] == EMPTY
&& board
[dpos
+ 2*up
] == color
&& ON_BOARD(dpos
+ up
+ right
)
&& board
[dpos
+ up
+ right
] != other
&& ON_BOARD(dpos
+ up
- right
)
&& board
[dpos
+ up
- right
] != other
) {
if (showboard
== 1 || (showboard
== 2 && surrounded
)) {
show_surround_map(mf
, mn
);
if (!apos
&& surrounded
&& surround_pointer
< MAX_SURROUND
) {
memcpy(surroundings
[surround_pointer
].surround_map
, mn
, sizeof(mn
));
surroundings
[surround_pointer
].dragon_number
= dragon
[pos
].id
;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && mn
[pos
] == 1)
/* Computes the minimum distance to the goal
goal_dist(int pos
, signed char goal
[BOARDMAX
])
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (ON_BOARD(ii
) && goal
[ii
])
dist
= gg_min(dist
, square_dist(ii
, pos
));
/* Compares angles. Chosen convention:
* - ascending order is done clock-wise (WEST, NORTH, EAST)
compare_angles(const void *a
, const void *b
)
int aa
= *((const int *)a
);
int bb
= *((const int *)b
);
int di_a
= I(aa
) - I(gg
);
int dj_a
= J(aa
) - J(gg
);
int di_b
= I(bb
) - I(gg
);
int dj_b
= J(bb
) - J(gg
);
if (dj_b
!= 0 || di_b
<= 0)
else if (dj_b
< 0 || di_b
> 0)
sin_a
= (float)di_a
/ sqrt(di_a
*di_a
+ dj_a
*dj_a
);
sin_b
= (float)di_b
/ sqrt(di_b
*di_b
+ dj_b
*dj_b
);
else { /* if (dj_a < 0) */
show_surround_map(signed char mf
[BOARDMAX
], signed char mn
[BOARDMAX
])
for (m
= 0; m
< board_size
; m
++)
for (n
= 0; n
< board_size
; n
++) {
else if (mn
[POS(m
, n
)] == 2)
else if (mn
[POS(m
, n
)] == 1)
else if (mn
[POS(m
, n
)] == 2)
if (board
[POS(m
, n
)] == BLACK
)
else if (board
[POS(m
, n
)] == WHITE
)
draw_color_char(m
, n
, c
, col
);
return(DRAGON2(dr
).surround_status
);
/* Returns true if (dragon) is not surrounded, but (move) surrounds it.
does_surround(int move
, int dr
)
if (DRAGON2(dr
).surround_status
)
return compute_surroundings(dr
, move
, 0, NULL
);
/* Should be run once per genmove, before make_dragons. */
reset_surround_data(void)
/* Returns 1 (respectively 2) if pos is in the convex hull
* (respectively expanded hull boundary) of the surrounding
* dragons. Returns -1 if the dragon is not found.
surround_map(int dr
, int pos
)
for (k
= 0; k
< surround_pointer
; k
++)
if (surroundings
[k
].dragon_number
== dragon
[dr
].id
)
return surroundings
[k
].surround_map
[pos
];