/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* A "dragon" is a union of strings of the same color which will be
* treated as a unit. The dragons are generated anew at each
* move. If two strings are in the dragon, it is GNU Go's working
* hypothesis that they will live or die together and are
static void initialize_supplementary_dragon_data(void);
static void find_lunches(void);
static void eye_computations(void);
static void revise_inessentiality(void);
static void find_neighbor_dragons(void);
static void add_adjacent_dragons(int a
, int b
);
static void add_adjacent_dragon(int a
, int b
);
static int dragon_invincible(int pos
);
static int dragon_looks_inessential(int origin
);
static void identify_thrashing_dragons(void);
static void analyze_false_eye_territory(void);
static int connected_to_eye(int pos
, int str
, int color
, int eye_color
,
static void connected_to_eye_recurse(int pos
, int str
, int color
,
int eye_color
, struct eye_data
*eye
,
signed char *mx
, signed char *me
,
static enum dragon_status
compute_crude_status(int pos
);
static int compute_escape(int pos
, int dragon_status_known
);
static void compute_surrounding_moyo_sizes(const struct influence_data
*q
);
static void clear_cut_list(void);
static int dragon2_initialized
;
static int lively_white_dragons
;
static int lively_black_dragons
;
/* This is a private array to obtain a list of worms belonging to each
* dragon. Public access is via first_worm_in_dragon() and
static int next_worm_list
[BOARDMAX
];
/* Alternative for DRAGON2 macro with asserts. */
&& dragon
[pos
].id
< number_of_dragons
, pos
);
return &dragon2
[dragon
[pos
].id
];
/* This basic function finds all dragons and collects some basic information
* about them in the dragon array.
* color is the player in turn to move. This does in no way affect the
* information collected about the dragons, but it does affect what
* information is passed on to the move generation code. If
* color == EMPTY no information at all is passed on to the move generation.
make_dragons(int stop_before_owl
)
initialize_dragon_data();
/* Find explicit connections patterns in database and amalgamate
memset(cutting_points
, 0, sizeof(cutting_points
));
/* At this time, all dragons have been finalized and we can
* initialize the dragon2[] array. After that we can no longer allow
* amalgamation of dragons.
initialize_supplementary_dragon_data();
make_domains(black_eye
, white_eye
, 0);
/* Find adjacent worms which can be easily captured: */
/* Find topological half eyes and false eyes. */
find_half_and_false_eyes(BLACK
, black_eye
, half_eye
, NULL
);
find_half_and_false_eyes(WHITE
, white_eye
, half_eye
, NULL
);
/* Compute the number of eyes, half eyes, determine attack/defense points
* etc. for all eye spaces. */
/* Try to determine whether topologically false and half eye points
* contribute to territory even if the eye doesn't solidify.
analyze_false_eye_territory();
/* Now we compute the genus. */
for (d
= 0; d
< number_of_dragons
; d
++)
compute_dragon_genus(dragon2
[d
].origin
, &dragon2
[d
].genus
, NO_MOVE
);
/* Compute the escape route measure. */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (IS_STONE(board
[str
]) && dragon
[str
].origin
== str
)
DRAGON2(str
).escape_route
= compute_escape(str
, 0);
/* Set dragon weaknesses according to initial_influence. */
compute_refined_dragon_weaknesses();
for (d
= 0; d
< number_of_dragons
; d
++)
dragon2
[d
].weakness_pre_owl
= dragon2
[d
].weakness
;
/* Determine status: ALIVE, DEAD, CRITICAL or UNKNOWN */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (dragon
[str
].origin
== str
&& board
[str
])
dragon
[str
].crude_status
= compute_crude_status(str
);
/* We must update the dragon status at every intersection before we
* call the owl code. This updates all fields.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (ON_BOARD(str
) && board
[str
] != EMPTY
)
dragon
[str
] = dragon
[dragon
[str
].origin
];
for (d
= 0; d
< number_of_dragons
; d
++) {
dragon2
[d
].surround_status
= compute_surroundings(dragon2
[d
].origin
, NO_MOVE
, 0,
&(dragon2
[d
].surround_size
));
if (dragon2
[d
].surround_status
== SURROUNDED
) {
dragon2
[d
].escape_route
= 0;
if (debug
& DEBUG_DRAGONS
)
gprintf("surrounded dragon found at %1m\n", dragon2
[d
].origin
);
else if (dragon2
[d
].surround_status
== WEAKLY_SURROUNDED
) {
dragon2
[d
].escape_route
/= 2;
if (debug
& DEBUG_DRAGONS
)
gprintf("weakly surrounded dragon found at %1m\n", dragon2
[d
].origin
);
/* Determine life and death status of each dragon using the owl code
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
int attack_point
= NO_MOVE
;
int defense_point
= NO_MOVE
;
set_eyevalue(&no_eyes
, 0, 0, 0, 0);
|| dragon
[str
].origin
!= str
)
/* Some dragons can be ignored but be extra careful with big dragons. */
if (crude_dragon_weakness(ALIVE
, &no_eyes
, 0,
DRAGON2(str
).moyo_territorial_value
,
DRAGON2(str
).escape_route
- 10)
< 0.00001 + gg_max(0.12, 0.32 - 0.01*dragon
[str
].effective_size
)) {
DRAGON2(str
).owl_status
= UNCHECKED
;
DRAGON2(str
).owl_attack_point
= NO_MOVE
;
DRAGON2(str
).owl_defense_point
= NO_MOVE
;
int owl_nodes_before
= get_owl_node_counter();
acode
= owl_attack(str
, &attack_point
,
&DRAGON2(str
).owl_attack_certain
, &kworm
);
DRAGON2(str
).owl_attack_node_count
= get_owl_node_counter() - owl_nodes_before
;
DRAGON2(str
).owl_attack_point
= attack_point
;
DRAGON2(str
).owl_attack_code
= acode
;
DRAGON2(str
).owl_attack_kworm
= kworm
;
if (attack_point
!= NO_MOVE
) {
dcode
= owl_defend(str
, &defense_point
,
&DRAGON2(str
).owl_defense_certain
, &kworm
);
if (defense_point
!= NO_MOVE
) {
DRAGON2(str
).owl_status
= (acode
== GAIN
? ALIVE
: CRITICAL
);
DRAGON2(str
).owl_defense_point
= defense_point
;
DRAGON2(str
).owl_defense_code
= dcode
;
DRAGON2(str
).owl_defense_kworm
= kworm
;
/* Due to irregularities in the owl code, it may
* occasionally happen that a dragon is found to be
* attackable but also alive as it stands. In this case
* we still choose to say that the owl_status is
* CRITICAL, although we don't have any defense move to
* propose. Having the status right is important e.g.
* for connection moves to be properly valued.
DRAGON2(str
).owl_status
= (acode
== GAIN
? ALIVE
: CRITICAL
);
DEBUG(DEBUG_OWL_PERFORMANCE
,
"Inconsistent owl attack and defense results for %1m.\n",
/* Let's see whether the attacking move might be the right
dcode
= owl_does_defend(DRAGON2(str
).owl_attack_point
,
DRAGON2(str
).owl_defense_point
= DRAGON2(str
).owl_attack_point
;
DRAGON2(str
).owl_defense_code
= dcode
;
DRAGON2(str
).owl_status
= DEAD
;
DRAGON2(str
).owl_defense_point
= NO_MOVE
;
DRAGON2(str
).owl_defense_code
= 0;
if (!DRAGON2(str
).owl_attack_certain
) {
dcode
= owl_defend(str
, &defense_point
,
&DRAGON2(str
).owl_defense_certain
, &kworm
);
/* If the result of owl_attack was not certain, we may
* still want the result of owl_defend */
DRAGON2(str
).owl_defense_point
= defense_point
;
DRAGON2(str
).owl_defense_code
= dcode
;
DRAGON2(str
).owl_defense_kworm
= kworm
;
DRAGON2(str
).owl_status
= ALIVE
;
DRAGON2(str
).owl_attack_point
= NO_MOVE
;
DRAGON2(str
).owl_attack_code
= 0;
time_report(2, " owl reading", NO_MOVE
, 1.0);
/* Compute the status to be used by the matcher. We most trust the
* owl status, if it is available. If it's not we assume that we are
* already confident that the dragon is alive, regardless of
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (IS_STONE(board
[str
])) {
if (DRAGON2(str
).owl_status
!= UNCHECKED
)
dragon
[str
].status
= DRAGON2(str
).owl_status
;
dragon
[str
].status
= ALIVE
;
/* The dragon data is now correct at the origin of each dragon but
* we need to copy it to every vertex.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (ON_BOARD(str
) && board
[str
] != EMPTY
)
dragon
[str
] = dragon
[dragon
[str
].origin
];
identify_thrashing_dragons();
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
&& dragon
[str
].origin
== str
) {
set_eyevalue(&no_eyes
, 0, 0, 0, 0);
if (crude_dragon_weakness(ALIVE
, &no_eyes
, 0,
DRAGON2(str
).moyo_territorial_value
,
DRAGON2(str
).escape_route
- 10)
< 0.00001 + gg_max(0.12, 0.32 - 0.01*dragon
[str
].effective_size
)) {
DRAGON2(str
).owl_threat_status
= UNCHECKED
;
DRAGON2(str
).owl_second_attack_point
= NO_MOVE
;
DRAGON2(str
).owl_second_defense_point
= NO_MOVE
;
int acode
= DRAGON2(str
).owl_attack_code
;
int dcode
= DRAGON2(str
).owl_defense_code
;
int defense_point
, second_defense_point
;
&& !disable_threat_computation
|| thrashing_stone
[str
])) {
if (acode
&& !dcode
&& DRAGON2(str
).owl_attack_point
!= NO_MOVE
) {
if (owl_threaten_defense(str
, &defense_point
,
&second_defense_point
)) {
DRAGON2(str
).owl_threat_status
= CAN_THREATEN_DEFENSE
;
DRAGON2(str
).owl_defense_point
= defense_point
;
DRAGON2(str
).owl_second_defense_point
= second_defense_point
;
DRAGON2(str
).owl_threat_status
= DEAD
;
int attack_point
, second_attack_point
;
if (owl_threaten_attack(str
,
&attack_point
, &second_attack_point
)) {
DRAGON2(str
).owl_threat_status
= CAN_THREATEN_ATTACK
;
DRAGON2(str
).owl_attack_point
= attack_point
;
DRAGON2(str
).owl_second_attack_point
= second_attack_point
;
DRAGON2(str
).owl_threat_status
= ALIVE
;
/* Once again, the dragon data is now correct at the origin of each dragon
* but we need to copy it to every vertex.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (ON_BOARD(str
) && board
[str
] != EMPTY
)
dragon
[str
] = dragon
[dragon
[str
].origin
];
time_report(2, " owl threats ", NO_MOVE
, 1.0);
/* Compute the safety value. */
for (d
= 0; d
< number_of_dragons
; d
++) {
int origin
= dragon2
[d
].origin
;
struct eyevalue
*genus
= &dragon2
[d
].genus
;
/* FIXME: We lose information when constructing true_genus. This
true_genus
= max_eyes(genus
) + min_eyes(genus
);
if (dragon_looks_inessential(origin
))
dragon2
[d
].safety
= INESSENTIAL
;
else if (dragon
[origin
].size
== worm
[origin
].size
&& worm
[origin
].attack_codes
[0] != 0
&& worm
[origin
].defense_codes
[0] == 0)
dragon2
[d
].safety
= TACTICALLY_DEAD
;
else if (0) /* Seki is detected by the call to semeai() below. */
dragon2
[d
].safety
= ALIVE_IN_SEKI
;
else if (dragon_invincible(origin
)) {
dragon2
[d
].safety
= INVINCIBLE
;
/* Sometimes the owl analysis may have misevaluated invincible
* dragons, typically if they live by topologically false eyes.
* Therefore we also set the status here.
DRAGON(d
).status
= ALIVE
;
else if (dragon2
[d
].owl_status
== DEAD
)
dragon2
[d
].safety
= DEAD
;
else if (dragon2
[d
].owl_status
== CRITICAL
)
dragon2
[d
].safety
= CRITICAL
;
else if (true_genus
>= 6 || dragon2
[d
].moyo_size
> 20)
dragon2
[d
].safety
= STRONGLY_ALIVE
;
dragon2
[d
].safety
= ALIVE
;
/* The status is now correct at the origin of each dragon
* but we need to copy it to every vertex.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
dragon
[str
].status
= dragon
[dragon
[str
].origin
].status
;
/* Revise inessentiality of critical worms and dragons. */
time_report(2, " semeai module", NO_MOVE
, 1.0);
/* Count the non-dead dragons. */
lively_white_dragons
= 0;
lively_black_dragons
= 0;
for (d
= 0; d
< number_of_dragons
; d
++)
if (DRAGON(d
).status
!= DEAD
) {
if (DRAGON(d
).color
== WHITE
)
/* Find capturable worms adjacent to each dragon. */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (worm
[str
].origin
!= str
|| worm
[str
].lunch
== NO_MOVE
)
/* In contrast to worm lunches, a dragon lunch must also be
if (worm
[food
].defense_codes
[0] == 0)
/* Tell the move generation code about the lunch. */
/* If several lunches are found, we pick the juiciest.
* First maximize cutstone, then minimize liberties.
int origin
= dragon
[str
].origin
;
int lunch
= DRAGON2(origin
).lunch
;
|| worm
[food
].cutstone
> worm
[lunch
].cutstone
|| (worm
[food
].cutstone
== worm
[lunch
].cutstone
&& (worm
[food
].liberties
< worm
[lunch
].liberties
))) {
DRAGON2(origin
).lunch
= worm
[food
].origin
;
TRACE("at %1m setting %1m.lunch to %1m (cutstone=%d)\n",
worm
[food
].origin
, worm
[food
].cutstone
);
/* Compute the value of each eye space. Store its attack and defense point.
* A more comlete list of attack and defense points is stored in the lists
* black_vital_points and white_vital_points.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
if (black_eye
[str
].color
== BLACK
&& black_eye
[str
].origin
== str
) {
int attack_point
, defense_point
;
compute_eyes(str
, &value
, &attack_point
, &defense_point
,
DEBUG(DEBUG_EYES
, "Black eyespace at %1m: %s\n", str
,
eyevalue_to_string(&value
));
black_eye
[str
].value
= value
;
propagate_eye(str
, black_eye
);
if (white_eye
[str
].color
== WHITE
&& white_eye
[str
].origin
== str
) {
int attack_point
, defense_point
;
compute_eyes(str
, &value
, &attack_point
, &defense_point
,
DEBUG(DEBUG_EYES
, "White eyespace at %1m: %s\n", str
,
eyevalue_to_string(&value
));
white_eye
[str
].value
= value
;
propagate_eye(str
, white_eye
);
/* This function revises the inessentiality of critical worms and dragons
* according to the criteria explained in the comments below.
/* Revise essentiality of critical worms. Specifically, a critical
* worm which is adjacent to no enemy dragon with status
* better than DEAD, is considered INESSENTIAL.
* A typical case of this is
* However, to be able to deal with the position
* we need to extend "adjacent" to "adjacent or shares a liberty",
* which is why we use extended_chainlinks() rather than
* Finally, if the position above is slightly modified to
* we have a position where the critical X stone doesn't share a
* liberty with any string at all. Thus the revised rule is:
* A critical worm which is adjacent to or share a liberty with at
* least one dead opponent dragon and no opponent dragon which is
* not dead, is considered inessential.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
if (is_worm_origin(str
, str
)
&& worm
[str
].attack_codes
[0] != 0
&& worm
[str
].defense_codes
[0] != 0
&& !worm
[str
].inessential
) {
neighbors
= extended_chainlinks(str
, adjs
, 0);
for (r
= 0; r
< neighbors
; r
++)
if (dragon
[adjs
[r
]].status
!= DEAD
) {
if (!essential
&& neighbors
> 0) {
DEBUG(DEBUG_WORMS
, "Worm %1m revised to be inessential.\n", str
);
worm
[str
].inessential
= 1;
/* Revise essentiality of critical dragons. Specifically, a critical
* dragon consisting entirely of inessential worms is considered
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
&& dragon
[str
].origin
== str
&& DRAGON2(str
).safety
== CRITICAL
) {
for (w
= first_worm_in_dragon(str
); w
!= NO_MOVE
;
w
= next_worm_in_dragon(w
)) {
if (!worm
[w
].inessential
)
DEBUG(DEBUG_DRAGONS
, "Dragon %1m revised to be inessential.\n", str
);
DRAGON2(str
).safety
= INESSENTIAL
;
/* Initialize the dragon[] array. */
initialize_dragon_data(void)
/* VALGRIND_MAKE_WRITABLE(dragon, BOARDMAX * sizeof(struct dragon_data)); */
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
dragon
[str
].size
= worm
[str
].size
;
dragon
[str
].effective_size
= worm
[str
].effective_size
;
dragon
[str
].color
= worm
[str
].color
;
dragon
[str
].origin
= worm
[str
].origin
;
dragon
[str
].crude_status
= UNKNOWN
;
dragon
[str
].status
= UNKNOWN
;
half_eye
[str
].value
= 10.0; /* Something big. */
if (IS_STONE(board
[str
]) && worm
[str
].origin
== str
)
"Initializing dragon from worm at %1m, size %d\n",
memset(next_worm_list
, 0, sizeof(next_worm_list
));
/* We need to reset this to avoid trouble on an empty board when
* moves have previously been generated for a non-empty board.
* Comment: The cause of this is that make_dragons() is not called
* for an empty board, only initialize_dragon_data(), so we never
* reach initialize_supplementary_dragon_data().
memset(black_vital_points
, 0, BOARDMAX
* sizeof(struct vital_eye_points
));
memset(white_vital_points
, 0, BOARDMAX
* sizeof(struct vital_eye_points
));
/* Initialize the dragon2[] array. */
initialize_supplementary_dragon_data(void)
/* Give each dragon (caves excluded) an id number for indexing into
* the dragon2 array. After this the DRAGON2 macro can be used.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
origin
= dragon
[str
].origin
;
if (dragon
[origin
].id
== -1)
dragon
[origin
].id
= number_of_dragons
++;
dragon
[str
].id
= dragon
[origin
].id
;
/* Now number_of_dragons contains the number of dragons and we can
* allocate a dragon2 array of the appropriate size. First throw
* FIXME: As a future optimization we should only allocate a new
* array if the old one is too small.
dragon2
= malloc(number_of_dragons
* sizeof(*dragon2
));
gg_assert(dragon2
!= NULL
);
/* Find the origins of the dragons to establish the mapping back to
* the board. After this the DRAGON macro can be used.
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++) {
&& dragon
[str
].origin
== str
) {
DRAGON2(str
).origin
= str
;
/* Initialize the rest of the dragon2 data. */
for (d
= 0; d
< number_of_dragons
; d
++) {
dragon2
[d
].neighbors
= 0;
dragon2
[d
].hostile_neighbors
= 0;
dragon2
[d
].moyo_size
= -1;
dragon2
[d
].moyo_territorial_value
= 0.0;
dragon2
[d
].escape_route
= 0;
dragon2
[d
].heye
= NO_MOVE
;
dragon2
[d
].lunch
= NO_MOVE
;
dragon2
[d
].surround_status
= 0;
set_eyevalue(&dragon2
[d
].genus
, 0, 0, 0, 0);
dragon2
[d
].semeai_defense_code
= 0;
dragon2
[d
].semeai_defense_point
= NO_MOVE
;
dragon2
[d
].semeai_attack_code
= 0;
dragon2
[d
].semeai_attack_point
= NO_MOVE
;
dragon2
[d
].owl_attack_point
= NO_MOVE
;
dragon2
[d
].owl_attack_code
= 0;
dragon2
[d
].owl_attack_certain
= 1;
dragon2
[d
].owl_defense_point
= NO_MOVE
;
dragon2
[d
].owl_defense_code
= 0;
dragon2
[d
].owl_defense_certain
= 1;
dragon2
[d
].owl_status
= UNCHECKED
;
dragon2
[d
].owl_threat_status
= UNCHECKED
;
dragon2
[d
].owl_second_attack_point
= NO_MOVE
;
dragon2
[d
].owl_second_defense_point
= NO_MOVE
;
/* Examine which dragons are adjacent to each other. This is
* complicated by the fact that adjacency may involve a certain
* The approach we use is to extend the dragons into their
* surrounding influence areas until they collide. We also accept
* one step extensions into neutral regions. After having done this
* we can look for immediate adjacencies.
gg_assert(dragon2_initialized
);
/* Initialize the arrays. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (IS_STONE(board
[pos
])) {
dragons
[pos
] = dragon
[pos
].id
;
else if (ON_BOARD(pos
)) {
/* Expand from dist-1 to dist. Break out of the loop at the end if
* we couldn't expand anything. Never expand more than five steps.
for (dist
= 1; dist
<= 5; dist
++) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (distances
[pos
] != dist
-1 || dragons
[pos
] < 0)
color
= DRAGON(dragons
[pos
]).color
;
for (k
= 0; k
< 4; k
++) {
/* Consider expansion from (pos) to adjacent intersection
if (distances
[pos2
] >= 0 && distances
[pos2
] < dist
)
continue; /* (pos2) already occupied. */
/* We can always expand the first step, regardless of influence. */
|| (whose_area(INITIAL_INFLUENCE(color
), pos
) == color
&& whose_area(INITIAL_INFLUENCE(color
), pos2
)
!= OTHER_COLOR(color
))) {
/* Expansion ok. Now see if someone else has tried to
* expand here. In that case we indicate a collision by
* setting the dragon number to -2.
if (distances
[pos2
] == dist
) {
if (dragons
[pos2
] != dragons
[pos
])
dragons
[pos2
] = dragons
[pos
];
for (m
= 0; m
< board_size
; m
++) {
for (n
= 0; n
< board_size
; n
++)
fprintf(stderr
, "%3d", dragons
[POS(m
, n
)]);
for (m
= 0; m
< board_size
; m
++) {
for (n
= 0; n
< board_size
; n
++)
fprintf(stderr
, "%3d", distances
[POS(m
, n
)]);
/* Now go through dragons to find neighbors. It suffices to look
* south and east for neighbors. In the case of a collision zone
* where dragons==-2 we set all the neighbors of this intersection
* as adjacent to each other.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (dragons
[pos
] == -2) {
for (k
= 0; k
< 4; k
++) {
if (ON_BOARD1(pos2
) && dragons
[pos2
] >= 0)
adjacent
[neighbors
++] = dragons
[pos2
];
for (i
= 0; i
< neighbors
; i
++)
for (j
= i
+1; j
< neighbors
; j
++)
add_adjacent_dragons(adjacent
[i
], adjacent
[j
]);
else if (dragons
[pos
] >= 0) {
if (ON_BOARD(NORTH(pos
))) {
if (dragons
[NORTH(pos
)] >= 0
&& dragons
[NORTH(pos
)] != dragons
[pos
])
add_adjacent_dragons(dragons
[pos
], dragons
[NORTH(pos
)]);
if (ON_BOARD(EAST(pos
))) {
if (dragons
[EAST(pos
)] >= 0
&& dragons
[EAST(pos
)] != dragons
[pos
])
add_adjacent_dragons(dragons
[pos
], dragons
[EAST(pos
)]);
for (d
= 0; d
< number_of_dragons
; d
++) {
gprintf("dragon %d at %1m:", d
, dragon2
[d
].origin
);
for (i
= 0; i
< dragon2
[d
].neighbors
; i
++)
gprintf(" %1m(%d)", dragon2
[dragon2
[d
].adjacent
[i
]].origin
,
/* Add the dragons with id a and b as adjacent to each other. */
add_adjacent_dragons(int a
, int b
)
gg_assert(a
>= 0 && a
< number_of_dragons
&& b
>= 0 && b
< number_of_dragons
);
add_adjacent_dragon(a
, b
);
add_adjacent_dragon(b
, a
);
/* Add the dragon with id b as adjacent to a. */
add_adjacent_dragon(int a
, int b
)
gg_assert(a
>= 0 && a
< number_of_dragons
&& b
>= 0 && b
< number_of_dragons
);
/* If the array of adjacent dragons already is full, ignore
if (dragon2
[a
].neighbors
== MAX_NEIGHBOR_DRAGONS
)
for (i
= 0; i
< dragon2
[a
].neighbors
; i
++)
if (dragon2
[a
].adjacent
[i
] == b
)
dragon2
[a
].adjacent
[dragon2
[a
].neighbors
++] = b
;
if (DRAGON(a
).color
== OTHER_COLOR(DRAGON(b
).color
))
dragon2
[a
].hostile_neighbors
++;
/* A dragon is considered invincible if it satisfies either of the two
* a) At least two distinct eyespaces without topological halfeyes,
* marginal vertices, or tactically critical or alive opponent strings.
* Furthermore there may not be an owl attack of the dragon.
* b) At least one string which is unconditionally alive according to the
* unconditional_life() function in utils.c.
* For the requirement on opponent strings in a), see e.g.
* seki:404,408,409,413,504,604,908.
dragon_invincible(int dr
)
ASSERT1(IS_STONE(board
[dr
]), dr
);
/* First look for invincible strings in the dragon. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (ON_BOARD(pos
) && is_same_dragon(pos
, dr
) && worm
[pos
].invincible
)
/* Can the dragon be owl attacked? */
if (DRAGON2(dr
).owl_status
!= UNCHECKED
&& DRAGON2(dr
).owl_status
!= ALIVE
)
/* Examine the eye spaces. */
if (board
[dr
] == BLACK
) {
memset(mx
, 0, sizeof(mx
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (board
[pos
] == board
[dr
] && is_same_dragon(pos
, dr
)) {
for (k
= 0; k
< 4; k
++) {
int pos2
= pos
+ delta
[k
];
&& eye
[pos2
].color
== eye_color
&& eye
[pos2
].origin
!= NO_MOVE
) {
|| is_halfeye(half_eye
, pos2
))
mx
[eye
[pos2
].origin
] = 2; /* bad eye */
else if (mx
[eye
[pos2
].origin
] == 0)
mx
[eye
[pos2
].origin
] = 1; /* good eye */
if (board
[pos2
] == OTHER_COLOR(board
[dr
])
&& (!attack(pos2
, NULL
) || find_defense(pos2
, NULL
)))
mx
[eye
[pos2
].origin
] = 2; /* bad eye */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
/* Necessary to check eye margins here since the loop above only
* considers margins which are directly adjacent to some stone of
/* A dragon looks inessential if it satisfies all of
* 2. Is not owl substantial.
* FIXME: Probably need a better definition of INESSENTIAL dragons.
* There are cases where a string is owl insubstantial
* yet allowing it to be captured greatly weakens our
dragon_looks_inessential(int origin
)
if (dragon
[origin
].size
!= worm
[origin
].size
)
if (owl_substantial(origin
))
/* This is a proposed modification which solves 13x13:72 but
* breaks buzco:5. It adds the two requirements:
* 3. Has no opponent neighbor with status better than DEAD.
* 4. Has no opponent neighbor with escape value bigger than 0.
* This probably needs to be revised before it's enabled.
for (k
= 0; k
< DRAGON2(origin
).neighbors
; k
++) {
d
= DRAGON2(origin
).adjacent
[k
];
if (DRAGON(d
).color
!= board
[origin
]
&& (DRAGON(d
).status
!= DEAD
|| dragon2
[d
].escape_route
> 0))
/* Report which stones are alive if it's (color)'s turn to move. I.e.
* critical stones belonging to (color) are considered alive.
* A stone is dead resp. critical if the tactical reading code _or_ the
get_alive_stones(int color
, signed char safe_stones
[BOARDMAX
])
get_lively_stones(color
, safe_stones
);
for (d
= 0; d
< number_of_dragons
; d
++) {
if (dragon2
[d
].safety
== DEAD
|| (dragon2
[d
].safety
== CRITICAL
&& board
[dragon2
[d
].origin
] == OTHER_COLOR(color
))) {
mark_dragon(dragon2
[d
].origin
, safe_stones
, 0);
/* If the opponent's last move is a dead dragon, this is called a
* *thrashing dragon*. We must be careful because the opponent may be
* trying to trick us, so even though GNU Go thinks the stone is dead,
* we should consider attacking it, particularly if we are ahead.
* This function determines whether the last played move is part of a
* dead dragon. It also looks for dead friendly neighbors of the
* thrashing dragon, which are also considered as thrashing. The
* stones of the primary thrashing dragon are marked by 1 in the
* thrashing_stone[] array and its neighbors are marked by 2.
* Neighbors of neighbors are marked 3, and so on, up to at most
identify_thrashing_dragons()
memset(thrashing_stone
, 0, sizeof(thrashing_stone
));
last_move
= get_last_move();
|| dragon
[last_move
].status
!= DEAD
)
thrashing_dragon
= dragon
[last_move
].origin
;
DEBUG(DEBUG_DRAGONS
, "thrashing dragon found at %1m\n", thrashing_dragon
);
mark_dragon(thrashing_dragon
, thrashing_stone
, 1);
color
= board
[thrashing_dragon
];
for (dist
= 1; dist
< 5; dist
++) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
|| dragon
[pos
].origin
!= pos
|| thrashing_stone
[pos
] != dist
)
for (k
= 0; k
< DRAGON2(pos
).neighbors
; k
++) {
int d
= DRAGON2(pos
).adjacent
[k
];
if (DRAGON(d
).color
== color
&& DRAGON(d
).status
== DEAD
&& thrashing_stone
[dragon2
[d
].origin
] == 0) {
"neighbor at distance %d of thrashing dragon found at %1m\n",
dist
+ 1, DRAGON(d
).origin
);
mark_dragon(DRAGON(d
).origin
, thrashing_stone
,
(signed char)(dist
+ 1));
set_dragon_strengths(const signed char safe_stones
[BOARDMAX
],
float strength
[BOARDMAX
])
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
ASSERT1(IS_STONE(board
[ii
]), ii
);
strength
[ii
] = DEFAULT_STRENGTH
* (1.0 - 0.3 * DRAGON2(ii
).weakness_pre_owl
);
/* Marks all inessential stones with INFLUENCE_SAFE_STONE, leaves
* everything else unchanged.
mark_inessential_stones(int color
, signed char safe_stones
[BOARDMAX
])
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
&& (DRAGON2(ii
).safety
== INESSENTIAL
/* FIXME: Why is the check below needed?
* Why does it use .safety, not .status? /ab
&& ((DRAGON2(ii
).safety
!= DEAD
&& DRAGON2(ii
).safety
!= TACTICALLY_DEAD
&& DRAGON2(ii
).safety
!= CRITICAL
)
|| (DRAGON2(ii
).safety
== CRITICAL
&& board
[ii
] == color
)))))
safe_stones
[ii
] = INFLUENCE_SAFE_STONE
;
set_strength_data(int color
, signed char safe_stones
[BOARDMAX
],
float strength
[BOARDMAX
])
gg_assert(IS_STONE(color
) || color
== EMPTY
);
get_alive_stones(color
, safe_stones
);
set_dragon_strengths(safe_stones
, strength
);
mark_inessential_stones(color
, safe_stones
);
compute_dragon_influence()
signed char safe_stones
[BOARDMAX
];
float strength
[BOARDMAX
];
set_strength_data(BLACK
, safe_stones
, strength
);
compute_influence(BLACK
, safe_stones
, strength
, &initial_black_influence
,
NO_MOVE
, "initial black influence, dragons known");
break_territories(BLACK
, &initial_black_influence
, 1, NO_MOVE
);
set_strength_data(WHITE
, safe_stones
, strength
);
compute_influence(WHITE
, safe_stones
, strength
, &initial_white_influence
,
NO_MOVE
, "initial white influence, dragons known");
break_territories(WHITE
, &initial_white_influence
, 1, NO_MOVE
);
/* Compute dragon's genus, possibly excluding one given eye. To
* compute full genus, just set `eye_to_exclude' to NO_MOVE.
compute_dragon_genus(int d
, struct eyevalue
*genus
, int eye_to_exclude
)
ASSERT1(IS_STONE(board
[d
]), d
);
gg_assert(eye_to_exclude
== NO_MOVE
|| ON_BOARD1(eye_to_exclude
));
set_eyevalue(genus
, 0, 0, 0, 0);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (black_eye
[pos
].color
== BLACK
&& black_eye
[pos
].origin
== pos
&& (eye_to_exclude
== NO_MOVE
|| black_eye
[eye_to_exclude
].origin
!= pos
)
&& find_eye_dragons(pos
, black_eye
, BLACK
, &dr
, 1) == 1
&& is_same_dragon(dr
, d
)) {
TRACE("eye at %1m (%s) found for dragon at %1m--augmenting genus\n",
pos
, eyevalue_to_string(&black_eye
[pos
].value
), dr
);
if (eye_to_exclude
== NO_MOVE
&& (eye_move_urgency(&black_eye
[pos
].value
)
> eye_move_urgency(genus
)))
DRAGON2(d
).heye
= black_vital_points
[pos
].defense_points
[0];
add_eyevalues(genus
, &black_eye
[pos
].value
, genus
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
if (white_eye
[pos
].color
== WHITE
&& white_eye
[pos
].origin
== pos
&& (eye_to_exclude
== NO_MOVE
|| white_eye
[eye_to_exclude
].origin
!= pos
)
&& find_eye_dragons(pos
, white_eye
, WHITE
, &dr
, 1) == 1
&& is_same_dragon(dr
, d
)) {
TRACE("eye at %1m (%s) found for dragon at %1m--augmenting genus\n",
pos
, eyevalue_to_string(&white_eye
[pos
].value
), dr
);
if (eye_to_exclude
== NO_MOVE
&& (eye_move_urgency(&white_eye
[pos
].value
)
> eye_move_urgency(genus
)))
DRAGON2(d
).heye
= white_vital_points
[pos
].defense_points
[0];
add_eyevalues(genus
, &white_eye
[pos
].value
, genus
);
/* Try to determine whether topologically false and half eye points
* contribute to territory even if the eye doesn't solidify. The purpose
* is to be able to distinguish between, e.g., these positions:
* In the left one the move at * is a pure dame point while in the
* right one it is worth one point of territory for either player.
* In general the question is whether a topologically false eye vertex
* counts as territory or not and the answer depends on whether each
* string adjoining the eye is externally connected to at least one
* This function loops over the topologically false and half eye
* vertices and calls connected_to_eye() for each adjoining string to
* determine whether they all have external connection to an eye. The
* result is stored in the false_eye_territory[] array.
analyze_false_eye_territory(void)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
false_eye_territory
[pos
] = 0;
/* The analysis only applies to false and half eyes. */
if (half_eye
[pos
].type
== 0)
/* Determine the color of the eye. */
if (white_eye
[pos
].color
== WHITE
) {
else if (black_eye
[pos
].color
== BLACK
) {
/* Make sure we have a "closed" position. Positions like
* disqualify without further analysis. (* is a false eye vertex)
if (ON_BOARD(pos
+ delta
[k
])
&& board
[pos
+ delta
[k
]] != color
&& eye
[pos
+ delta
[k
]].color
!= eye_color
)
/* Check that all adjoining strings have external connection to an
if (ON_BOARD(pos
+ delta
[k
])
&& board
[pos
+ delta
[k
]] == color
&& !connected_to_eye(pos
, pos
+ delta
[k
], color
, eye_color
, eye
))
false_eye_territory
[pos
] = 1;
gprintf("False eye territory at %1m\n", pos
);
/* FIXME: This initialization doesn't really belong here but must be
* done somewhere within examine_position().
* The array is eventually filled by the endgame() function.
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
forced_backfilling_moves
[pos
] = 0;
* This function (implicitly) finds the connected set of strings of a
* dragon, starting from (str) which is next to the analyzed halfeye
* at (pos). Strings are for this purpose considered connected if and
* only if they have a common liberty, which is not allowed to be the
* half eye itself or one of its diagonal neighbors. For these strings
* it is examined whether their liberties are parts of eyespaces worth
* at least two halfeyes (again not counting the eyespace at (pos)).
* The real work is done by the recursive function
* connected_to_eye_recurse() below.
connected_to_eye(int pos
, int str
, int color
, int eye_color
,
signed char mx
[BOARDMAX
];
signed char me
[BOARDMAX
];
/* mx marks strings and liberties which have already been investigated.
* me marks the origins of eyespaces which have already been counted.
* Start by marking (pos) and the surrounding vertices in mx.
memset(mx
, 0, sizeof(mx
));
memset(me
, 0, sizeof(me
));
if (ON_BOARD(pos
+ delta
[k
]))
connected_to_eye_recurse(pos
, str
, color
, eye_color
, eye
, mx
, me
, &halfeyes
);
/* Recursive helper for connected_to_eye(). Stop searching when we
* have found at least two halfeyes.
connected_to_eye_recurse(int pos
, int str
, int color
, int eye_color
,
struct eye_data
*eye
, signed char *mx
,
signed char *me
, int *halfeyes
)
liberties
= findlib(str
, MAXLIBS
, libs
);
/* Search the liberties of (str) for eyespaces. */
for (r
= 0; r
< liberties
; r
++) {
if (eye
[libs
[r
]].color
== eye_color
&& !me
[eye
[libs
[r
]].origin
]) {
me
[eye
[libs
[r
]].origin
] = 1;
*halfeyes
+= (min_eyes(&eye
[libs
[r
]].value
)
+ max_eyes(&eye
[libs
[r
]].value
));
/* Search for new strings in the same dragon with a liberty in
* common with (str), and recurse.
for (r
= 0; r
< liberties
; r
++) {
for (k
= 0; k
< 4; k
++) {
if (ON_BOARD(libs
[r
] + delta
[k
])
&& board
[libs
[r
] + delta
[k
]] == color
&& is_same_dragon(str
, libs
[r
] + delta
[k
])
&& !mx
[libs
[r
] + delta
[k
]])
connected_to_eye_recurse(pos
, libs
[r
] + delta
[k
], color
, eye_color
,
/* print status info on all dragons. (Can be invoked from gdb)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
struct worm_data
*w
= &(worm
[pos
]);
if (!IS_STONE(board
[pos
]))
gprintf("%1m : (dragon %1m) %s string of size %d (%f), genus %d: (%d,%d,%d,%d)",
color_to_string(board
[pos
]),
gprintf("%o - is a potential cutting stone\n");
else if (w
->cutstone
== 2)
gprintf("%o - is a cutting stone\n");
gprintf("- cutstone2 = %d\n", w
->cutstone2
);
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
if (w
->attack_codes
[k
] == 0)
gprintf("- attackable at %1m, attack code = %d\n",
w
->attack_points
[k
], w
->attack_codes
[k
]);
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
if (w
->defense_codes
[k
] == 0)
gprintf("- defendable at %1m, defend code = %d\n",
w
->defense_points
[k
], w
->defense_codes
[k
]);
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
if (w
->attack_threat_codes
[k
] == 0)
gprintf("- attack threat at %1m, attack threat code = %d\n",
w
->attack_threat_points
[k
], w
->attack_threat_codes
[k
]);
for (k
= 0; k
< MAX_TACTICAL_POINTS
; k
++) {
if (w
->defense_threat_codes
[k
] == 0)
gprintf("- defense threat at %1m, defense threat code = %d\n",
w
->defense_threat_points
[k
], w
->defense_threat_codes
[k
]);
gprintf("... adjacent worm %1m is lunch\n", w
->lunch
);
gprintf("- is inessential\n");
gprintf("- is invincible\n");
gprintf("- is a ko stone\n");
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
struct dragon_data
*dd
= &(dragon
[pos
]);
if (!IS_STONE(board
[pos
]))
gprintf("%1m : %s dragon size %d (%f), genus %s, escape factor %d, crude status %s, status %s, moyo size %d, moyo territory value %f, safety %s, weakness pre owl %f, weakness %f",
board
[pos
] == BLACK
? "B" : "W",
eyevalue_to_string(&d2
->genus
),
status_to_string(dd
->crude_status
),
status_to_string(dd
->status
),
d2
->moyo_territorial_value
,
status_to_string(d2
->safety
),
gprintf(", owl status %s\n", status_to_string(d2
->owl_status
));
if (d2
->owl_status
== CRITICAL
) {
gprintf("... owl attackable at %1m, code %d\n",
d2
->owl_attack_point
, d2
->owl_attack_code
);
gprintf("... owl defendable at %1m, code %d\n",
d2
->owl_defense_point
, d2
->owl_defense_code
);
if (dd
->status
== CRITICAL
&& d2
->semeais
) {
if (d2
->semeai_defense_point
)
gprintf("... semeai defense move at %1m, result code %s\n",
d2
->semeai_defense_point
,
result_to_string(d2
->semeai_defense_code
));
if (d2
->semeai_attack_point
)
gprintf("... semeai attack move at %1m, result code %s\n",
result_to_string(d2
->semeai_attack_code
));
gprintf("... neighbors");
for (k
= 0; k
< d2
->neighbors
; k
++) {
gprintf(" %1m", dragon2
[d
].origin
);
if (d2
->lunch
!= NO_MOVE
)
gprintf("... adjacent worm %1m is lunch\n", d2
->lunch
);
static int new_dragon_origins
[BOARDMAX
];
/* Compute new dragons, e.g. after having made a move. This will not
* affect any global state.
compute_new_dragons(int dragon_origins
[BOARDMAX
])
int saved_cutting_points
[BOARDMAX
];
/* This is currently necessary in order not to mess up the
* worm[].cutstone2 field. See cutstone2_helper in
* patterns/helpers.c. On the other hand it shouldn't be very
* interesting to recompute dragons in the original position.
memcpy(saved_cutting_points
, cutting_points
, sizeof(cutting_points
));
memset(cutting_points
, 0, sizeof(cutting_points
));
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
new_dragon_origins
[pos
] = NO_MOVE
;
new_dragon_origins
[pos
] = find_origin(pos
);
memcpy(cutting_points
, saved_cutting_points
, sizeof(cutting_points
));
memcpy(dragon_origins
, new_dragon_origins
, sizeof(new_dragon_origins
));
/* This gets called if we are trying to compute dragons outside of
* make_dragons(), typically after a move has been made.
join_new_dragons(int d1
, int d2
)
/* Normalize dragon coordinates. */
d1
= new_dragon_origins
[d1
];
d2
= new_dragon_origins
[d2
];
/* If d1 and d2 are the same dragon, we do nothing. */
ASSERT1(board
[d1
] == board
[d2
], d1
);
ASSERT1(IS_STONE(board
[d1
]), d1
);
/* Don't bother to do anything fancy with dragon origins. */
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && new_dragon_origins
[pos
] == d2
)
new_dragon_origins
[pos
] = d1
;
* join_dragons amalgamates the dragon at (d1) to the
join_dragons(int d1
, int d2
)
int origin
; /* new origin */
/* If not called from make_dragons(), we don't work on the main
join_new_dragons(d1
, d2
);
/* Normalize dragon coordinates. */
/* If d1 and d2 are the same dragon, we do nothing. */
ASSERT1(board
[d1
] == board
[d2
], d1
);
gg_assert(dragon2_initialized
== 0);
ASSERT1(IS_STONE(board
[d1
]), d1
);
/* We want to have the origin pointing to the largest string of
* the dragon. If this is not unique, we take the "upper
if (worm
[d1
].size
> worm
[d2
].size
|| (worm
[d1
].size
== worm
[d2
].size
DEBUG(DEBUG_DRAGONS
, "joining dragon at %1m to dragon at %1m\n", d2
, d1
);
DEBUG(DEBUG_DRAGONS
, "joining dragon at %1m to dragon at %1m\n", d1
, d2
);
dragon
[origin
].size
= dragon
[d2
].size
+ dragon
[d1
].size
;
dragon
[origin
].effective_size
= (dragon
[d2
].effective_size
+ dragon
[d1
].effective_size
);
/* Join the second next_worm_in_dragon chain at the end of the first one. */
int last_worm_origin_dragon
= origin
;
while (next_worm_list
[last_worm_origin_dragon
] != NO_MOVE
)
last_worm_origin_dragon
= next_worm_list
[last_worm_origin_dragon
];
next_worm_list
[last_worm_origin_dragon
] = d2
;
next_worm_list
[last_worm_origin_dragon
] = d1
;
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++) {
&& (dragon
[ii
].origin
== d1
|| dragon
[ii
].origin
== d2
))
dragon
[ii
].origin
= origin
;
* compute_crude_status(pos) tries to determine whether the dragon
* at (pos) is ALIVE, DEAD, or UNKNOWN. The algorithm is not perfect
* and can give incorrect answers.
* The dragon is judged alive if its genus is >1. It is judged dead if
* the genus is <2, it has no escape route, and no adjoining string can
* be easily captured. Otherwise it is judged UNKNOWN. */
static enum dragon_status
compute_crude_status(int pos
)
/* FIXME: We lose information when constructing true_genus. This
struct eyevalue
*genus
= &DRAGON2(pos
).genus
;
int true_genus
= max_eyes(genus
) + min_eyes(genus
);
int lunch
= DRAGON2(pos
).lunch
;
gg_assert(dragon2_initialized
);
/* If it has two sure eyes, everything is just dandy. */
/* If the dragon consists of one worm, there is an attack, but
* no defense and there is less than one eye and one half eye,
* the situation is hopeless.
if (dragon
[pos
].size
== worm
[pos
].size
&& worm
[pos
].attack_codes
[0] != 0
&& worm
[pos
].defense_codes
[0] == 0
&& worm
[lunch
].defense_codes
[0] != 0
&& DRAGON2(pos
).escape_route
< 5)
if (true_genus
== 2 || worm
[lunch
].size
> 2)
if (lunch
== NO_MOVE
|| worm
[lunch
].cutstone
< 2) {
&& DRAGON2(pos
).escape_route
== 0
&& DRAGON2(pos
).moyo_size
< 5)
&& DRAGON2(pos
).escape_route
< 5)
if (DRAGON2(pos
).moyo_territorial_value
> 9.99)
/* The dragon escape measure. This is defined as follows.
* Let a PATH be a sequence of adjacent intersections that do nowhere
* touch or include an opponent stone or touch the border. It may
* include friendly stones and those are allowed to touch opponent
* stones or the border). Let a DISTANCE N INTERSECTION be an
* intersection connected to a dragon by a path of length N, but by no
* shorter path. The connection of the path to the dragon may either
* be by direct adjacency or, in the first step, diagonally if both
* adjoining intersections are empty.
* It is assumed that each intersection has an escape value, which
* would typically depend on influence and (preliminary) dragon
* status. We define the escape potential as the sum of the escape
* values over the distance four intersections of the dragon.
* Example of distance N intersections, 1 <= N <= 4:
* . . . . . . . . . . . . . . . . . .
* . . . . . X . . O . . . . . X . . O
* . . X . . . . . O . . X . 2 . 4 . O
* X . . . . . . . . X . . 1 1 2 3 4 .
* X O . O . . . . O X O 1 O 1 2 3 4 O
* X O . O . . . . . X O 1 O 1 . 4 . .
* X O . . . X . O O X O 1 . . X . . O
* . . . X . . . . . . 1 . X . . . . .
* X . . . . X . . . X . . . . X . . .
* . . . . . . . . . . . . . . . . . .
* Additionally, a path may not pass a connection inhibited
#define ENQUEUE(pos) (queue[queue_end++] = (pos),\
/* Compute the escape potential described above. The dragon is marked
dragon_escape(signed char goal
[BOARDMAX
], int color
,
signed char escape_value
[BOARDMAX
])
static int mx_initialized
= 0;
int queue
[MAX_BOARD
* MAX_BOARD
];
int other
= OTHER_COLOR(color
);
int escape_potential
= 0;
gg_assert(IS_STONE(color
));
memset(mx
, 0, sizeof(mx
));
/* Enter the stones of the dragon in the queue. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
if (ON_BOARD(ii
) && goal
[ii
])
/* Find points at increasing distances from the dragon. At distance
* four, sum the escape values at those points to get the escape
for (distance
= 0; distance
<= 4; distance
++) {
int save_queue_end
= queue_end
;
while (queue_start
< save_queue_end
) {
/* Do not pass connection inhibited intersections. */
if (cut_possible(ii
, OTHER_COLOR(color
)))
escape_potential
+= escape_value
[ii
];
&& (board
[SOUTH(ii
)] == color
|| (board
[SOUTH(ii
)] == EMPTY
&& ON_BOARD(SE(ii
)) && board
[SE(ii
)] != other
&& ON_BOARD(SS(ii
)) && board
[SS(ii
)] != other
&& ON_BOARD(SW(ii
)) && board
[SW(ii
)] != other
)))
&& (board
[WEST(ii
)] == color
|| (board
[WEST(ii
)] == EMPTY
&& ON_BOARD(SW(ii
)) && board
[SW(ii
)] != other
&& ON_BOARD(WW(ii
)) && board
[WW(ii
)] != other
&& ON_BOARD(NW(ii
)) && board
[NW(ii
)] != other
)))
&& (board
[NORTH(ii
)] == color
|| (board
[NORTH(ii
)] == EMPTY
&& ON_BOARD(NW(ii
)) && board
[NW(ii
)] != other
&& ON_BOARD(NN(ii
)) && board
[NN(ii
)] != other
&& ON_BOARD(NE(ii
)) && board
[NE(ii
)] != other
)))
&& (board
[EAST(ii
)] == color
|| (board
[EAST(ii
)] == EMPTY
&& ON_BOARD(NE(ii
)) && board
[NE(ii
)] != other
&& ON_BOARD(EE(ii
)) && board
[EE(ii
)] != other
&& ON_BOARD(SE(ii
)) && board
[SE(ii
)] != other
)))
/* For distance one intersections, allow kosumi to move out. I.e.
if (board
[SOUTH(ii
)] == EMPTY
&& board
[WEST(ii
)] == EMPTY
&& (board
[SW(ii
)] == color
|| (board
[SW(ii
)] == EMPTY
&& ON_BOARD(SOUTH(SW(ii
)))
&& board
[SOUTH(SW(ii
))] != other
&& ON_BOARD(WEST(SW(ii
)))
&& board
[WEST(SW(ii
))] != other
)))
if (board
[WEST(ii
)] == EMPTY
&& board
[NORTH(ii
)] == EMPTY
&& (board
[NW(ii
)] == color
|| (board
[NW(ii
)] == EMPTY
&& ON_BOARD(WEST(NW(ii
)))
&& board
[WEST(NW(ii
))] != other
&& ON_BOARD(NORTH(NW(ii
)))
&& board
[NORTH(NW(ii
))] != other
)))
if (board
[NORTH(ii
)] == EMPTY
&& board
[EAST(ii
)] == EMPTY
&& (board
[NE(ii
)] == color
|| (board
[NE(ii
)] == EMPTY
&& ON_BOARD(NORTH(NE(ii
)))
&& board
[NORTH(NE(ii
))] != other
&& ON_BOARD(EAST(NE(ii
)))
&& board
[EAST(NE(ii
))] != other
)))
if (board
[EAST(ii
)] == EMPTY
&& board
[SOUTH(ii
)] == EMPTY
&& (board
[SE(ii
)] == color
|| (board
[SE(ii
)] == EMPTY
&& ON_BOARD(EAST(SE(ii
)))
&& board
[EAST(SE(ii
))] != other
&& ON_BOARD(SOUTH(SE(ii
)))
&& board
[SOUTH(SE(ii
))] != other
)))
/* Reset used mx cells. */
for (k
= 0; k
< queue_end
; k
++) {
/* The assertion fails if the same element should have been queued
* twice, which might happen if ENQUEUE() is called without
ASSERT1(mx
[queue
[k
]] == 1, queue
[k
]);
/* Wrapper to call the function above and compute the escape potential
* for the dragon at (pos).
compute_escape(int pos
, int dragon_status_known
)
signed char goal
[BOARDMAX
];
signed char escape_value
[BOARDMAX
];
signed char safe_stones
[BOARDMAX
];
ASSERT1(IS_STONE(board
[pos
]), pos
);
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++)
goal
[ii
] = is_same_dragon(ii
, pos
);
/* Compute escape_value array. Points are awarded for moyo (4),
* area (2) or EMPTY (1). Values may change without notice.
get_lively_stones(OTHER_COLOR(board
[pos
]), safe_stones
);
compute_escape_influence(board
[pos
], safe_stones
, NULL
, 0, escape_value
);
/* If we can reach a live group, award 6 points. */
for (ii
= BOARDMIN
; ii
< BOARDMAX
; ii
++) {
if (dragon_status_known
) {
if (dragon
[ii
].crude_status
== ALIVE
)
else if (dragon
[ii
].crude_status
== UNKNOWN
&& (DRAGON2(ii
).escape_route
> 5
|| DRAGON2(ii
).moyo_size
> 5))
if (board
[ii
] == board
[pos
]
&& worm
[ii
].attack_codes
[0] == 0)
return dragon_escape(goal
, board
[pos
], escape_value
);
* Sum up the surrounding moyo sizes for each dragon. For this
* we retrieve the moyo data stored in influence_data (*q) (which must
* have been computed previously) from the influence module.
* We set dragon2[].moyo_size and .moyo_value if it is smaller than the
* Currently this is implemented differently depending on whether
* experimental connections are used or not. The reason why this is
* needed is that most of the B patterns in conn.db are disabled for
* experimental connections, which may cause the moyo segmentation to
* pass through cutting points between dragons, making the surrounding
* moyo size mostly useless. Instead we only use the part of the
* surrounding moyo which is closest to some worm of the dragon.
compute_surrounding_moyo_sizes(const struct influence_data
*q
)
float moyo_sizes
[BOARDMAX
];
float moyo_values
[BOARDMAX
];
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
moyo_color
= whose_moyo_restricted(q
, pos
);
if (moyo_color
== board
[pos
])
if (moyo_color
== WHITE
) {
for (k
= 0; k
< number_close_white_worms
[pos
]; k
++) {
int w
= close_white_worms
[pos
][k
];
int dr
= dragon
[w
].origin
;
moyo_sizes
[dr
] += 1.0 / number_close_white_worms
[pos
];
moyo_values
[dr
] += (gg_min(influence_territory(q
, pos
, WHITE
), 1.0)
/ number_close_white_worms
[pos
]);
if (moyo_color
== BLACK
) {
for (k
= 0; k
< number_close_black_worms
[pos
]; k
++) {
int w
= close_black_worms
[pos
][k
];
int dr
= dragon
[w
].origin
;
moyo_sizes
[dr
] += 1.0 / number_close_black_worms
[pos
];
moyo_values
[dr
] += (gg_min(influence_territory(q
, pos
, BLACK
), 1.0)
/ number_close_black_worms
[pos
]);
for (d
= 0; d
< number_of_dragons
; d
++) {
int this_moyo_size
= (int) moyo_sizes
[dragon2
[d
].origin
];
float this_moyo_value
= moyo_values
[dragon2
[d
].origin
];
if (this_moyo_size
< dragon2
[d
].moyo_size
) {
dragon2
[d
].moyo_size
= this_moyo_size
;
dragon2
[d
].moyo_territorial_value
= this_moyo_value
;
static struct interpolation_data moyo_value2weakness
=
{ 5, 0.0, 15.0, {1.0, 0.65, 0.3, 0.15, 0.05, 0.0}};
static struct interpolation_data escape_route2weakness
=
{ 5, 0.0, 25.0, {1.0, 0.6, 0.3, 0.1, 0.05, 0.0}};
static struct interpolation_data genus2weakness
=
{ 6, 0.0, 3.0, {1.0, 0.95, 0.8, 0.5, 0.2, 0.1, 0.0}};
crude_dragon_weakness(int safety
, struct eyevalue
*genus
, int has_lunch
,
float moyo_value
, float escape_route
)
/* FIXME: We lose information when constructing true_genus. This
float true_genus
= 0.5 * (max_eyes(genus
) + min_eyes(genus
)
if (safety
== INVINCIBLE
|| safety
== INESSENTIAL
)
if (safety
== TACTICALLY_DEAD
|| safety
== DEAD
|| safety
== CRITICAL
)
weakness_value
[0] = gg_interpolate(&moyo_value2weakness
, moyo_value
);
weakness_value
[1] = gg_interpolate(&escape_route2weakness
, escape_route
);
weakness_value
[2] = gg_interpolate(&genus2weakness
, true_genus
);
" moyo value %f -> %f, escape %f -> %f, eyes %f -> %f\n",
moyo_value
, weakness_value
[0],
escape_route
, weakness_value
[1],
true_genus
, weakness_value
[2]);
for (j
= i
+ 1; j
< 3; j
++)
if (weakness_value
[j
] < weakness_value
[i
]) {
float tmp
= weakness_value
[i
];
weakness_value
[i
] = weakness_value
[j
];
/* The overall weakness is mostly, but not completely determined by the
* best value found so far:
weakness
= gg_min(0.7 * weakness_value
[0] + 0.3 * weakness_value
[1],
1.3 * weakness_value
[0]);
gg_assert(weakness
>= 0.0 && weakness
<= 1.0);
/* This function tries to guess a coefficient measuring the weakness of
* a dragon. This coefficient * the effective size of the dragon can be
* used to award a strategic penalty for weak dragons.
compute_dragon_weakness_value(int d
)
int origin
= dragon2
[d
].origin
;
/* Possible ingredients for the computation:
* '+' means currently used, '-' means not (yet?) used
* + post-owl moyo_size and its territory value
* - minus number of vital attack moves?
* - maybe reading shadow?
* - possible connections to neighbour dragons
DEBUG(DEBUG_DRAGONS
, "Computing weakness of dragon at %1m:\n", origin
);
weakness
= crude_dragon_weakness(dragon2
[d
].safety
, &dragon2
[d
].genus
,
dragon2
[d
].lunch
!= NO_MOVE
,
dragon2
[d
].moyo_territorial_value
,
(float) dragon2
[d
].escape_route
);
/* Now corrections due to (uncertain) owl results resp. owl threats. */
if (!dragon2
[d
].owl_attack_certain
)
weakness
+= gg_min(0.25 * (1.0 - weakness
), 0.25 * weakness
);
if (!dragon2
[d
].owl_defense_certain
)
weakness
+= gg_min(0.25 * (1.0 - weakness
), 0.25 * weakness
);
if (dragon2
[d
].owl_threat_status
== CAN_THREATEN_ATTACK
)
weakness
+= 0.15 * (1.0 - weakness
);
DEBUG(DEBUG_DRAGONS
, " result: %f.\n", weakness
);
/* This function has to be called _after_ the owl analysis and the
* subsequent re-run of the influence code.
compute_refined_dragon_weaknesses()
/* Compute the surrounding moyo sizes. */
for (d
= 0; d
< number_of_dragons
; d
++)
dragon2
[d
].moyo_size
= 2 * BOARDMAX
;
/* Set moyo sizes according to initial_influence. */
compute_surrounding_moyo_sizes(&initial_black_influence
);
compute_surrounding_moyo_sizes(&initial_white_influence
);
for (d
= 0; d
< number_of_dragons
; d
++)
dragon2
[d
].weakness
= compute_dragon_weakness_value(d
);
/* The strategic size is the effective size, plus a bonus for all weak
* neighbouring dragons of the opponent.
compute_strategic_sizes()
float *bonus
= calloc(number_of_dragons
, sizeof(float));
for (d
= 0; d
< number_of_dragons
; d
++) {
/* Compute bonus for all neighbors of dragon (d). The total bonus for
* all neighbors is effective_size(d) * weakness(d), and it is given
* to a neighbor d2 proportionally to the value of
* effective_size(d2) * weakness(d2).
if (dragon2
[d
].safety
== INESSENTIAL
)
for (k
= 0; k
< dragon2
[d
].neighbors
; k
++) {
int d2
= dragon2
[d
].adjacent
[k
];
if (board
[dragon2
[d2
].origin
] == OTHER_COLOR(board
[dragon2
[d
].origin
])
&& dragon2
[d2
].safety
!= INESSENTIAL
)
sum
+= DRAGON(d2
).effective_size
* dragon2
[d2
].weakness
;
for (k
= 0; k
< dragon2
[d
].neighbors
; k
++) {
int d2
= dragon2
[d
].adjacent
[k
];
if (board
[dragon2
[d2
].origin
] == OTHER_COLOR(board
[dragon2
[d
].origin
])
&& dragon2
[d2
].safety
!= INESSENTIAL
) {
bonus
[d2
] += ((DRAGON(d2
).effective_size
* dragon2
[d2
].weakness
) / sum
)
* DRAGON(d
).effective_size
* dragon2
[d
].weakness
;
gprintf("Dragon %1m receives %f effective size bonus from %1m.\n",
((DRAGON(d2
).effective_size
* dragon2
[d2
].weakness
) / sum
)
* DRAGON(d
).effective_size
* dragon2
[d
].weakness
,
for (d
= 0; d
< number_of_dragons
; d
++) {
gprintf("Dragon %1m gets effective size bonus of %f.\n",
dragon2
[d
].origin
, bonus
[d
]);
/* We cap strategic size at 3 * effective_size. (This is ad hoc.) */
dragon2
[d
].strategic_size
= gg_min(bonus
[d
] + DRAGON(d
).effective_size
,
3 * DRAGON(d
).effective_size
);
* Test whether two dragons are the same. Used by autohelpers and elsewhere.
is_same_dragon(int d1
, int d2
)
if (d1
== NO_MOVE
|| d2
== NO_MOVE
)
return (dragon
[d1
].origin
== dragon
[d2
].origin
);
/* Test whether two dragons are neighbors. */
are_neighbor_dragons(int d1
, int d2
)
for (k
= 0; k
< DRAGON2(d1
).neighbors
; k
++)
if (dragon2
[DRAGON2(d1
).adjacent
[k
]].origin
== d2
)
/* Just to be make sure that this function is always symmetric, we
* do it the other way round too.
for (k
= 0; k
< DRAGON2(d2
).neighbors
; k
++)
if (dragon2
[DRAGON2(d2
).adjacent
[k
]].origin
== d1
)
/* Mark the stones of a dragon. */
mark_dragon(int pos
, signed char mx
[BOARDMAX
], signed char mark
)
for (w
= first_worm_in_dragon(dragon
[pos
].origin
); w
!= NO_MOVE
;
w
= next_worm_in_dragon(w
))
mark_string(w
, mx
, mark
);
/* The following two functions allow to traverse all worms in a dragon:
* for (ii = first_worm_in_dragon(pos); ii != NO_MOVE;
* ii = next_worm_in_dragon(ii);)
* At the moment first_worm_in_dragon(pos) will always be the origin
* of the dragon, but you should not rely on that.
first_worm_in_dragon(int d
)
next_worm_in_dragon(int w
)
ASSERT1(worm
[w
].origin
== w
, w
);
return next_worm_list
[w
];
/* ================================================================ */
/* A few status functions */
/* ================================================================ */
* These functions are only here because then we don't need to expose
* the dragon structure to the external program.
return dragon
[pos
].crude_status
;
return dragon
[pos
].status
;
lively_dragon_exists(int color
)
return lively_white_dragons
> 0;
return lively_black_dragons
> 0;
/* Is this dragon weak? */
/* FIXME: This should not happen, but avoids a crash. What is
* the proper fix for calling this at stackp != 0 ?
if (dragon
[pos
].id
< 0 || dragon
[pos
].id
>= number_of_dragons
)
return (DRAGON2(pos
).weakness
> 0.40001);
/* Returns the size of the biggest critical dragon on the board. */
size_of_biggest_critical_dragon(void)
for (str
= BOARDMIN
; str
< BOARDMAX
; str
++)
|| dragon
[str
].origin
!= str
)
/* Get the best available status for the dragon */
if (dragon
[str
].status
== CRITICAL
) {
if (dragon
[str
].size
>= max_size
)
max_size
= dragon
[str
].size
;
/************************************************************************
* A list of all cuts found during connection matching *
************************************************************************/
#define MAX_CUTS 3 * MAX_BOARD * MAX_BOARD
static struct cut_data cut_list
[MAX_CUTS
];
/* Store in the list that (move) disconnects the two strings at
add_cut(int apos
, int bpos
, int move
)
gg_assert(board
[apos
] == board
[bpos
]);
if (num_cuts
== MAX_CUTS
)
cut_list
[num_cuts
].apos
= apos
;
cut_list
[num_cuts
].bpos
= bpos
;
cut_list
[num_cuts
].move
= move
;
gprintf("Added %d-th cut at %1m between %1m and %1m.\n", num_cuts
,
/* For every move in the cut list disconnecting two of opponent's strings,
* test whether the two strings can be connected at all. If so, add a
for (k
= 0; k
< num_cuts
; k
++)
if (board
[cut_list
[k
].apos
] == OTHER_COLOR(color
)
&& !is_same_dragon(cut_list
[k
].apos
, cut_list
[k
].bpos
)
&& string_connect(cut_list
[k
].apos
, cut_list
[k
].bpos
, NULL
) == WIN
)
add_cut_move(cut_list
[k
].move
, cut_list
[k
].apos
, cut_list
[k
].bpos
);
/* ================================================================ */
/* ================================================================ */
/* For use in gdb, print details of the dragon at (m, n).
* Add this to your .gdbinit file:
* set ascii_report_dragon("$arg0")
* Now 'dragon S8' will report the details of the S8 dragon.
ascii_report_dragon(char *string
)
int pos
= string_to_location(board_size
, string
);
fprintf(stderr
, "unknown position %s\n", string
);
report_dragon(stderr
, pos
);
report_dragon(FILE *outfile
, int pos
)
struct dragon_data
*d
= &(dragon
[pos
]);
struct dragon_data2
*d2
= &(dragon2
[d
->id
]);
if (board
[pos
] == EMPTY
) {
gprintf("There is no dragon at %1m\n", pos
);
gprintf("Dragon data not available at %1m\n", pos
);
gfprintf(outfile
, "color %s\n", color_to_string(d
->color
));
gfprintf(outfile
, "origin %1m\n", d
->origin
);
gfprintf(outfile
, "size %d\n", d
->size
);
gfprintf(outfile
, "effective_size %f\n", d
->effective_size
);
gfprintf(outfile
, "strategic_size %f\n", d2
->strategic_size
);
gfprintf(outfile
, "genus %s\n",
eyevalue_to_string(&d2
->genus
));
gfprintf(outfile
, "heye %1m\n", d2
->heye
);
gfprintf(outfile
, "escape_route %d\n", d2
->escape_route
);
gfprintf(outfile
, "lunch %1m\n", d2
->lunch
);
gfprintf(outfile
, "crude_status %s\n",
status_to_string(d
->crude_status
));
gfprintf(outfile
, "owl_status %s\n",
status_to_string(d2
->owl_status
));
gfprintf(outfile
, "status %s\n",
status_to_string(d
->status
));
gfprintf(outfile
, "safety %s\n",
status_to_string(d2
->safety
));
gfprintf(outfile
, "weakness %f\n", d2
->weakness
);
gfprintf(outfile
, "weakness_pre_owl %f\n", d2
->weakness_pre_owl
);
gfprintf(outfile
, "surround_status %d\n", d2
->surround_status
);
gfprintf(outfile
, "surround_size %d\n", d2
->surround_size
);
gfprintf(outfile
, "moyo_size %d\n", d2
->moyo_size
);
gfprintf(outfile
, "moyo_territorial_value %f\n",
d2
->moyo_territorial_value
);
gfprintf(outfile
, "neighbors ");
for (k
= 0; k
< d2
->neighbors
; k
++)
gfprintf(outfile
, "%1m ", DRAGON(d2
->adjacent
[k
]).origin
);
gfprintf(outfile
, "\nhostile_neighbors %d\n", d2
->hostile_neighbors
);
gfprintf(outfile
, "owl_attack_code %d\n", d2
->owl_attack_code
);
gfprintf(outfile
, "owl_attack_point %1m\n", d2
->owl_attack_point
);
gfprintf(outfile
, "owl_attack_certain %s\n",
(d2
->owl_attack_certain
) ? "YES" : "NO");
gfprintf(outfile
, "owl_2nd_attack_point %1m\n",
d2
->owl_second_attack_point
);
gfprintf(outfile
, "owl_threat_status %s\n",
status_to_string(d2
->owl_threat_status
));
gfprintf(outfile
, "owl_defense_code %d\n", d2
->owl_defense_code
);
gfprintf(outfile
, "owl_defense_point %1m\n", d2
->owl_defense_point
);
gfprintf(outfile
, "owl_defense_certain %s\n",
(d2
->owl_defense_certain
) ? "YES" : "NO");
gfprintf(outfile
, "owl_2nd_defense_point %1m\n",
d2
->owl_second_defense_point
);
gfprintf(outfile
, "owl_attack_kworm %1m\n", d2
->owl_attack_kworm
);
gfprintf(outfile
, "owl_defense_kworm %1m\n", d2
->owl_defense_kworm
);
gfprintf(outfile
, "semeais %d\n", d2
->semeais
);
gfprintf(outfile
, "semeai_defense_code %d\n", d2
->semeai_defense_code
);
gfprintf(outfile
, "semeai_defense_point %1m\n", d2
->semeai_defense_point
);
gfprintf(outfile
, "semeai_defense_certain %d\n",
d2
->semeai_defense_certain
);
gfprintf(outfile
, "semeai_defense_target %1m\n",
d2
->semeai_defense_target
);
gfprintf(outfile
, "semeai_attack_code %d\n", d2
->semeai_attack_code
);
gfprintf(outfile
, "semeai_attack_point %1m\n", d2
->semeai_attack_point
);
gfprintf(outfile
, "semeai_attack_certain %d\n", d2
->semeai_attack_certain
);
gfprintf(outfile
, "semeai_attack_target %1m\n", d2
->semeai_attack_target
);
gfprintf(outfile
, "strings ");
for (w
= first_worm_in_dragon(pos
); w
!= NO_MOVE
; w
= next_worm_in_dragon(w
))
gfprintf(outfile
, "%1m ", w
);