/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* 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. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Return one if x doesn't equal position_number and 0 otherwise.
* After using this macro x will always have the value
#define NEEDS_UPDATE(x) (x != position_number ? (x = position_number, 1) : 0)
/* Mark a limited search area. If limit_search != 1, genmove
* will only return moves within the area marked by the array
static int limit_search
= 0;
static int search_mask
[BOARDMAX
];
static int do_genmove(int color
, float pure_threat_value
,
int allowed_moves
[BOARDMAX
], float *value
, int *resign
);
/* Position numbers for which various examinations were last made. */
static int worms_examined
= -1;
static int initial_influence_examined
= -1;
static int dragons_examined_without_owl
= -1;
static int dragons_examined
= -1;
static int initial_influence2_examined
= -1;
static int dragons_refinedly_examined
= -1;
static int revise_semeai(int color
);
static int revise_thrashing_dragon(int color
, float our_score
,
static void break_mirror_go(int color
);
static int find_mirror_move(int *move
, int color
);
static int should_resign(int color
, float optimistic_score
, int move
);
static void compute_scores(int use_chinese_rules
);
/* Reset some things in the engine.
* This prepares the hash table for the reading code for use. It
* should be called when we start examine a new position.
/* To improve the reproducability of games, we restart the random
* number generator with the same seed for each move. Thus we don't
* have to know how many previous moves have been played, nor
* actually play through them, in order to get the right random
/* Initialize things for hashing of positions. */
hashdata_recalc(&board_hash
, board
, board_ko_pos
);
initial_influence_examined
= -1;
dragons_examined_without_owl
= -1;
initial_influence2_examined
= -1;
dragons_refinedly_examined
= -1;
/* Prepare our table of move reasons. */
/* Set up depth values (see comments there for details). */
set_depth_values(get_level(), 0);
/* Initialize arrays of moves which are meaningless due to
* static analysis of unconditional status.
clear_unconditionally_meaningless_moves();
* Examine the position and try to gather as much information as possible.
* This is used mainly for move generation, but could also be called
* for debugging purposes (decidestring, etc).
* The parameter how_much tells us how much of the work we have to do.
* For move generation we have to do it all. For debugging we can
* sometimes stop a little earlier.
* aftermath_play indicates we are in aftermath playout phase. It's only
* effect is to always use chinese rules for the score estimates.
examine_position(int how_much
, int aftermath_play
)
int save_verbose
= verbose
;
purge_persistent_caches();
/* Don't print reading traces during make_worms and make_dragons unless
* the user really wants it (verbose == 3).
if (verbose
== 1 || verbose
== 2)
if (NEEDS_UPDATE(worms_examined
)) {
time_report(0, " make worms", NO_MOVE
, 1.0);
if (how_much
== EXAMINE_WORMS
) {
gg_assert(test_gray_border() < 0);
if (stones_on_board(BLACK
| WHITE
) != 0) {
if (NEEDS_UPDATE(initial_influence_examined
))
compute_worm_influence();
if (how_much
== EXAMINE_INITIAL_INFLUENCE
) {
gg_assert(test_gray_border() < 0);
if (how_much
== EXAMINE_DRAGONS_WITHOUT_OWL
) {
if (NEEDS_UPDATE(dragons_examined_without_owl
))
gg_assert(test_gray_border() < 0);
if (NEEDS_UPDATE(dragons_examined
)) {
compute_scores(chinese_rules
|| aftermath_play
);
/* We have automatically done a partial dragon analysis as well. */
dragons_examined_without_owl
= position_number
;
if (how_much
== EXAMINE_DRAGONS
) {
gg_assert(test_gray_border() < 0);
else if (how_much
== EXAMINE_INITIAL_INFLUENCE
|| how_much
== EXAMINE_DRAGONS
|| how_much
== EXAMINE_ALL
) {
initialize_dragon_data();
compute_scores(chinese_rules
|| aftermath_play
);
gg_assert(test_gray_border() < 0);
if (NEEDS_UPDATE(initial_influence2_examined
)) {
compute_dragon_influence();
if (how_much
== EXAMINE_INITIAL_INFLUENCE2
) {
gg_assert(test_gray_border() < 0);
if (NEEDS_UPDATE(dragons_refinedly_examined
)) {
compute_refined_dragon_weaknesses();
compute_strategic_sizes();
if (how_much
== FULL_EXAMINE_DRAGONS
) {
gg_assert(test_gray_border() < 0);
/* The same as examine_position(), except that all traces, debug
* output, and sgf traces are turned off.
silent_examine_position(int how_much
)
int save_verbose
= verbose
;
SGFTree
*save_sgf_dumptree
= sgf_dumptree
;
int save_count_variations
= count_variations
;
int save_printmoyo
= printmoyo
;
examine_position(how_much
, 0);
sgf_dumptree
= save_sgf_dumptree
;
count_variations
= save_count_variations
;
printmoyo
= save_printmoyo
;
* Generate computer move for color.
* Return the generated move.
genmove(int color
, float *value
, int *resign
)
move
= metamachine_genmove(color
, value
, limit_search
);
move
= do_genmove(color
, 0.4, search_mask
, value
, resign
);
move
= do_genmove(color
, 0.4, NULL
, value
, resign
);
gg_assert(move
== PASS_MOVE
|| ON_BOARD(move
));
* Same as above but doesn't generate pure threat moves. Useful when
* trying to score a game.
genmove_conservative(int color
, float *value
)
return do_genmove(color
, 0.0, NULL
, value
, NULL
);
genmove_restricted(int color
, int allowed_moves
[BOARDMAX
])
return do_genmove(color
, 0.0, allowed_moves
, NULL
, NULL
);
/* This function collects move reasons can be generated immediately from
* the data gathered in the examine_position() phase.
collect_move_reasons(int color
)
semeai_move_reasons(color
);
break_in_move_reasons(color
);
unconditional_move_reasons(color
);
/* Call Monte Carlo module to generate a move. */
monte_carlo_genmove(int color
, int allowed_moves
[BOARDMAX
],
float *value
, int *resign
)
int best_move
= PASS_MOVE
;
int best_uct_move
= PASS_MOVE
;
int unconditional_territory_black
[BOARDMAX
];
int unconditional_territory_white
[BOARDMAX
];
int forbidden_move
[BOARDMAX
];
float move_values
[BOARDMAX
];
int move_frequencies
[BOARDMAX
];
int number_of_simulations
;
memset(move_values
, 0, sizeof(move_values
));
memset(move_frequencies
, 0, sizeof(move_frequencies
));
simple_showboard(stderr
);
unconditional_life(unconditional_territory_black
, BLACK
);
unconditional_life(unconditional_territory_white
, WHITE
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
else if (unconditional_territory_black
[pos
])
forbidden_move
[pos
] = BLACK
;
else if (unconditional_territory_white
[pos
])
forbidden_move
[pos
] = WHITE
;
number_of_simulations
= mc_games_per_level
* gg_max(get_level(), 1);
uct_genmove(color
, &best_uct_move
, forbidden_move
, allowed_moves
,
number_of_simulations
, move_values
, move_frequencies
);
best_move
= best_uct_move
;
frequency_cutoff
= move_frequencies
[best_uct_move
] / 2;
frequency_cutoff2
= move_frequencies
[best_uct_move
] / 10;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& (move_frequencies
[pos
] > frequency_cutoff
|| (move_values
[pos
] > 0.9
&& move_frequencies
[pos
] > frequency_cutoff2
)
|| move_values
[best_uct_move
] < 0.1)
&& (!allowed_moves
|| allowed_moves
[pos
])
&& potential_moves
[pos
] > best_value
) {
best_value
= potential_moves
[pos
];
unconditionally_meaningless_move(best_move
, color
, &best_move
);
* Perform the actual move generation.
* The array allowed_moves restricts which moves may be considered. If
* NULL any move is allowed. Pass is always allowed and will be chosen
* if the move generation doesn't like any of the allowed moves (or
do_genmove(int color
, float pure_threat_value
,
int allowed_moves
[BOARDMAX
], float *value
, int *resign
)
float average_score
, pessimistic_score
, optimistic_score
;
int use_thrashing_dragon_heuristics
= 0;
/* Usually we would not recommend resignation. */
/* Prepare our table of moves considered. */
memset(potential_moves
, 0, sizeof(potential_moves
));
/* no move is found yet. */
/* Prepare pattern matcher and reading code. */
/* Store the depth value so we can check that it hasn't changed when
* we leave this function.
/* If in mirror mode, try to find a mirror move. */
&& (mirror_stones_limit
< 0
|| stones_on_board(WHITE
| BLACK
) <= mirror_stones_limit
)
&& find_mirror_move(&move
, color
)) {
TRACE("genmove() recommends mirror move at %1m\n", move
);
/* Find out information about the worms and dragons. */
examine_position(EXAMINE_ALL
, 0);
time_report(1, "examine position", NO_MOVE
, 1.0);
/* The score will be used to determine when we are safely
* ahead. So we want the most conservative score.
* We always want to have the score from our point of view. So
* negate it if we are black.
pessimistic_score
= black_score
;
optimistic_score
= white_score
;
pessimistic_score
= -white_score
;
optimistic_score
= -black_score
;
average_score
= (white_score
+ black_score
)/2.0;
average_score
= -(white_score
+ black_score
)/2.0;
choose_strategy(color
, average_score
, game_status(color
));
fprintf(stderr
, "\n dragon_status display:\n\n");
fprintf(stderr
, "\n eye display:\n\n");
fprintf(stderr
, "\n owl_status display:\n\n");
fprintf(stderr
, "\n matcher_status display:\n\n");
* Ok, information gathering is complete. Now start to find some moves!
/* Pick up moves that we know of already. */
collect_move_reasons(color
);
time_report(1, "generate move reasons", NO_MOVE
, 1.0);
/* Try to find empty corner moves. */
/* Look for moves to break mirror play by the opponent. */
/* If we are ahead by 5 points or more, consider a thrashing
* dragon dangerous and change its status from DEAD to
* UNKNOWN. Otherwise, pretend there is no thrashing dragon.
use_thrashing_dragon_heuristics
= revise_thrashing_dragon(color
, pessimistic_score
, 5.0);
/* The general pattern database. */
time_report(1, "shapes", NO_MOVE
, 1.0);
/* Look for combination attacks and defenses against them. */
time_report(1, "combinations", NO_MOVE
, 1.0);
/* Review the move reasons and estimate move values. */
if (review_move_reasons(&move
, value
, color
,
pure_threat_value
, pessimistic_score
, allowed_moves
,
use_thrashing_dragon_heuristics
))
TRACE("Move generation likes %1m with value %f\n", move
, *value
);
time_report(1, "review move reasons", NO_MOVE
, 1.0);
/* If the move value is 6 or lower, we look for endgame patterns too. */
if (*value
<= 6.0 && !disable_endgame_patterns
) {
if (review_move_reasons(&move
, value
, color
, pure_threat_value
,
pessimistic_score
, allowed_moves
,
use_thrashing_dragon_heuristics
))
TRACE("Move generation likes %1m with value %f\n", move
, *value
);
time_report(1, "endgame", NO_MOVE
, 1.0);
/* If no move found yet, revisit any semeai and change the
* status of the opponent group from DEAD to UNKNOWN, then
* run shapes and endgame_shapes again. This may turn up a move.
if (revise_semeai(color
)) {
if (review_move_reasons(&move
, value
, color
, pure_threat_value
,
pessimistic_score
, allowed_moves
,
use_thrashing_dragon_heuristics
)) {
TRACE("Upon reconsideration move generation likes %1m with value %f\n",
time_report(1, "move reasons with revised semeai status",
/* If Monte Carlo move generation is enabled, call it now. Do not
* override a fuseki move.
* FIXME: Identifying fuseki moves by checking the move value is
if (use_monte_carlo_genmove
&& move
!= PASS_MOVE
&& (*value
< 75.0 || *value
> 75.01) && !doing_scoring
) {
int allowed_moves2
[BOARDMAX
];
int num_allowed_moves2
= 0;
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
&& (!allowed_moves
|| allowed_moves
[pos
])
&& is_allowed_move(pos
, color
)) {
if (num_allowed_moves2
> 1)
move
= monte_carlo_genmove(color
, allowed_moves2
, value
, resign
);
/* If still no move, fill a remaining liberty. This should pick up
* all missing dame points.
&& fill_liberty(&move
, color
)) {
if (!allowed_moves
|| allowed_moves
[move
]) {
TRACE("Filling a liberty at %1m\n", move
);
record_top_move(move
, *value
);
move_considered(move
, *value
);
time_report(1, "fill liberty", NO_MOVE
, 1.0);
/* If we're instructed to play out the aftermath or capture all dead
* opponent stones, or if the opponent is trying to live inside
* our territory and we are clearly ahead, generate an aftermath move.
|| (!doing_scoring
&& thrashing_dragon
&& pessimistic_score
> 15.0))
move
= aftermath_genmove(color
, capture_all_dead
, allowed_moves
);
ASSERT1(is_legal(move
, color
), move
);
TRACE("Aftermath move at %1m\n", move
);
record_top_move(move
, *value
);
move_considered(move
, *value
);
time_report(1, "aftermath_genmove", NO_MOVE
, 1.0);
/* If we somehow have managed to generate an illegal move, pass instead. */
if (!is_allowed_move(move
, color
)) {
TRACE("ILLEGAL MOVE GENERATED. Passing instead.\n");
/* If no move is found then pass. */
TRACE("genmove() recommends %1m with value %f\n", move
, *value
);
/* Maybe time to resign...
if (resign
&& resign_allowed
&& *value
< 10.0 && should_resign(color
, optimistic_score
, move
)) {
TRACE("... though, genmove() thinks the position is hopeless\n");
/* If statistics is turned on, this is the place to show it. */
double spent
= time_report(0, "TIME to generate move at ", move
, 1.0);
if (spent
> slowest_time
) {
slowest_movenum
= movenum
+ 1;
/* Some consistency checks to verify that things are properly
* restored and/or have not been corrupted.
gg_assert(test_gray_border() < 0);
gg_assert(depth
== save_depth
);
/* This is called for each move which has been considered. For
* debugging purposes, we keep a table of all the moves we
move_considered(int move
, float value
)
if (value
> potential_moves
[move
])
potential_moves
[move
] = value
;
/* revise_semeai(color) changes the status of any DEAD dragon of
* OPPOSITE_COLOR(color) which occurs in a semeai to UNKNOWN.
* It returns true if such a dragon is found.
int other
= OTHER_COLOR(color
);
if (stones_on_board(BLACK
| WHITE
) == 0)
gg_assert(dragon2
!= NULL
);
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++) {
&& dragon
[pos
].color
== other
&& dragon
[pos
].status
== DEAD
) {
dragon
[pos
].status
= UNKNOWN
;
if (dragon
[pos
].origin
== pos
)
TRACE("revise_semeai: changed status of dragon %1m from DEAD to UNKNOWN\n",
/* If the opponent's last move added a stone to a dead dragon,
* revise it's status to UNKNOWN. This will cause genmove to
* generate moves restraining the dragon. We only do this if
* we are ahead by 'advantage', and no owl threat has been found.
revise_thrashing_dragon(int color
, float our_score
, float advantage
)
signed char safe_stones
[BOARDMAX
];
float strength
[BOARDMAX
];
/* Trust the owl code's opinion if we are behind. */
if (our_score
< advantage
)
if (disable_threat_computation
|| dragon
[thrashing_dragon
].status
!= DEAD
)
for (pos
= BOARDMIN
; pos
< BOARDMAX
; pos
++)
if (ON_BOARD(pos
) && thrashing_stone
[pos
]
&& worm
[pos
].unconditional_status
!= DEAD
) {
dragon
[pos
].status
= UNKNOWN
;
DRAGON2(pos
).safety
= ALIVE
;
set_strength_data(OTHER_COLOR(color
), safe_stones
, strength
);
compute_influence(OTHER_COLOR(color
), safe_stones
, strength
,
OPPOSITE_INFLUENCE(color
),
NO_MOVE
, "revised thrashing dragon");
compute_refined_dragon_weaknesses();
/* Look for a mirror move. First try the mirror of the last move. If
* none is available, test all moves to see if one makes the board
* To be able to deal with handicap stones we use a somewhat weak
* definition of symmetry.
find_mirror_move(int *move
, int color
)
int last_move
= get_last_move();
if (last_move
!= NO_MOVE
) {
mirror_move
= MIRROR_MOVE(last_move
);
if (test_symmetry_after_move(mirror_move
, color
, 0)) {
for (mirror_move
= BOARDMIN
; mirror_move
< BOARDMAX
; mirror_move
++) {
if (ON_BOARD(mirror_move
)
&& test_symmetry_after_move(mirror_move
, color
, 0)) {
/* Computer two territory estimates: for *upper, the status of all
* cricital stones gets resolved in White's favor; vice verso for
compute_scores(int use_chinese_rules
)
signed char safe_stones
[BOARDMAX
];
float strength
[BOARDMAX
];
set_strength_data(WHITE
, safe_stones
, strength
);
compute_influence(EMPTY
, safe_stones
, strength
, &move_influence
,
NO_MOVE
, "White territory estimate");
white_score
= influence_score(&move_influence
, use_chinese_rules
);
set_strength_data(BLACK
, safe_stones
, strength
);
compute_influence(EMPTY
, safe_stones
, strength
, &move_influence
,
NO_MOVE
, "White territory estimate");
black_score
= influence_score(&move_influence
, use_chinese_rules
);
if (verbose
|| showscore
) {
if (white_score
== black_score
)
gprintf("Score estimate: %s %f\n",
black_score
> 0 ? "W " : "B ", gg_abs(black_score
));
gprintf("Score estimate: %s %f to %s %f\n",
black_score
> 0 ? "W " : "B ", gg_abs(black_score
),
white_score
> 0 ? "W " : "B ", gg_abs(white_score
));
/* Detect if a white opponent has played mirror go for at least 10
* moves and if so play on tengen.
* Mirror breaking moves in other situations are handled by patterns
break_mirror_go(int color
)
int tengen
= POS((board_size
- 1) / 2, (board_size
- 1) / 2);
if (board
[tengen
] == EMPTY
&& stones_on_board(BLACK
| WHITE
) > 10
&& test_symmetry_after_move(tengen
, color
, 1)) {
set_minimum_move_value(tengen
, 30.0);
TRACE("Play %1m to break mirror go, value 30.\n", tengen
);
/* Helper to decide whether GG should resign a game
should_resign(int color
, float optimistic_score
, int move
)
/* We resign 19x19 games only, smaller board games are fast enough.
* We resign only if the margin is bigger than 45 pts and if we are
* As an exception to this rule, we resign on any board size if
* it looks like all our dragons are dead and the generated move
if (board_size
> 2 && move
== PASS_MOVE
&& !lively_dragon_exists(color
))
|| optimistic_score
> -45.0)
/* Check dragon statuses. If a friendly dragon is critical, we are
* possibly not that much behind after we save it. If some hostile
* dragon is at least weak, we possibly have a chance to come back
for (d
= 0; d
< number_of_dragons
; d
++) {
/* any friendly critical dragon ? */
if (board
[dragon2
[d
].origin
] == color
&& DRAGON(d
).status
== CRITICAL
)
/* any weak opponent dragon ? */
if (board
[dragon2
[d
].origin
] == OTHER_COLOR(color
)
&& DRAGON(d
).status
!= DEAD
&& DRAGON(d
).effective_size
>= 10
&& dragon_weak(dragon2
[d
].origin
))
/* Is it already too late to try something ? */
status
= game_status(color
);
* Note: the 0.8 constant is very conservative, we actually could give
/* well, it is probably reasonable and polite to give up this game */
/*********************************************************************\
* Mark a limited search area *
\*********************************************************************/
/* Activate or deactivate search limit. */
set_limit_search(int value
)
/* The following function marks a diamond of radius 6 with center pos. */
set_search_diamond(int pos
)
for (m
= 0; m
< board_size
; m
++)
for (n
= 0; n
< board_size
; n
++) {
if (gg_abs(m
- i
) + gg_abs(n
- j
) <= 6)
search_mask
[POS(m
, n
)] = 1;
search_mask
[POS(m
, n
)] = 0;
/* unmarks the entire board */
memset(search_mask
, 0, sizeof(search_mask
));
/* marks a single vertex */
set_search_mask(int pos
, int value
)
search_mask
[pos
] = value
;
/* displays the search area */
for (m
= 0; m
< board_size
; m
++)
for (n
= 0; n
< board_size
; n
++) {
if (search_mask
[POS(m
, n
)])
if (board
[POS(m
, n
)] == BLACK
)
else if (board
[POS(m
, n
)] == WHITE
)
else if (search_mask
[POS(m
, n
)])
draw_color_char(m
, n
, c
, col
);
/* returns true if the position is within the search area */
within_search_area(int pos
)