[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] nando_3_17.6
|
From: |
Nando |
|
Subject: |
[gnugo-devel] nando_3_17.6 |
|
Date: |
Fri, 14 Feb 2003 22:39:29 +0100 |
The appended patch implements a resignation policy in the GnuGO engine.
The details about the conditions which can generate such decisions
can be found in the new static should_resign() function in genmove.c
Rather than adding a new parameter to the interfaces, I chose
the convention that do_genmove() signals a resignation decision by
returning a negatively valued move which is not PASS. After looking
at all the genmove() calls, I finally judged this is univoque enough
and rather simple to implement. It is possibly arguable that this is
a good choice though, comments/rants are of course welcome.
Resignation is implemented over GTP and in replay mode only, in other
playing modes the feature is simply disabled. By default, resignation
is disabled and can only be activated with a new command-line option
--resign-allowed. I was actually wanting to implement it the other
way around, e.g. active by default with a --noresign option, but I
thought it wouldn't be easily accepted.
I'm not very familiar with Perl, but I updated the twogtp script and
luckily, it seems to work fairly well. Review is possibly needed
though.
There's a couple unrelated minor changes included in this patch.
I moved some timing variables to globals, so that it is possible to
get these statistics even when GG still wants to play a move. I also
added a small debugging feature in play_test.c. The idea is to be able
to feed a perfect sequence into the engine and get a global engine
performance indicator (see implementation for details). I'm planning
to use it for endgame tuning.
A final note: some worries have been expressed about handicap games.
The testings I did showed that GG "understands" that the game is not
yet over, even if more than 50 points behind. For instance,
gnugo-3.3.16-mgoetze-200302081620.sgf is a game that GG recently lost
by 140.5 points. When replaying it with --resign-allowed, GG gives up
at move 155 instead of playing out the yose until the last move (169).
gnugo-3.3.16-mgoetze-200302082108.sgf is another 9 stones game that
GG lost this time by 10.5 only. Even with --resign-allowed GG doesn't
give up until the end.
In conclusion, the game_status() function in influence.c seems to work
well enough in order to prevent GG from resigning too early in high
handicap games where it holds the white stones, without the need for
specific additional code to take handicap stones into account.
/nando
- resigning of hopeless games implemented (over GTP and in replay mode)
- new command-line option --resign-allowed
- twogtp script updated
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.65
diff -u -r1.65 genmove.c
--- engine/genmove.c 28 Jan 2003 16:54:04 -0000 1.65
+++ engine/genmove.c 12 Feb 2003 09:37:32 -0000
@@ -40,11 +40,6 @@
static int do_genmove(int *move, int color, float pure_threat_value,
int allowed_moves[BOARDMAX]);
-static double slowest_time = 0.0;
-static int slowest_move = NO_MOVE;
-static int slowest_movenum = 0;
-static double total_time = 0.0;
-
/* Position numbers for which various examinations were last made. */
static int worms_examined = -1;
static int initial_influence_examined = -1;
@@ -58,6 +53,7 @@
static int find_mirror_move(int *move, int color);
static int test_symmetry_after_move(int move, int color);
+static int should_resign(int color, float score);
void sgfShowConsideredMoves(void);
@@ -293,6 +289,9 @@
* 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
* overlooks them).
+ *
+ * Resignation is indicated by a negatively valued move (which is not
+ * a pass)
*/
static int
@@ -537,8 +536,16 @@
TRACE("I pass.\n");
*move = NO_MOVE;
}
- else
+ else {
TRACE("genmove() recommends %1m with value %f\n", *move, val);
+ /* Maybe time to resign...
+ */
+ if (resign_allowed && val < 10.0 && should_resign(color, score)) {
+ TRACE("... though, genmove() thinks the position is hopeless\n" );
+ /* Signal resignation by negating the move value */
+ val = -val;
+ }
+ }
/* If statistics is turned on, this is the place to show it. */
if (showstatistics) {
@@ -558,15 +565,6 @@
slowest_move = *move;
slowest_movenum = movenum + 1;
}
- if (*move == NO_MOVE) {
- gprintf("\nSLOWEST MOVE: %d at %1m ", slowest_movenum, slowest_move);
- fprintf(stderr, "(%.2f seconds)\n", slowest_time);
- fprintf(stderr, "\nAVERAGE TIME: %.2f seconds per move\n",
- total_time / movenum);
- fprintf(stderr, "\nTOTAL TIME: %.2f seconds\n",
- total_time);
-
- }
}
/* Some consistency checks to verify that things are properly
@@ -749,6 +747,53 @@
return result;
}
+
+/* Helper to decide whether GG should resign a game
+ */
+static int
+should_resign(int color, float score)
+{
+ float status;
+ int d;
+ /* 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
+ * behind (of course).
+ */
+ if (board_size < 19
+ || gg_abs(score) < 45
+ || (color == WHITE && score >= 0.0)
+ || (color == BLACK && score <= 0.0))
+ return 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
+ * if we can kill it.
+ */
+ for (d = 0; d < number_of_dragons; d++) {
+ /* any friendly critical dragon ? */
+ if (board[dragon2[d].origin] == color
+ && DRAGON(d).status == CRITICAL)
+ return 0;
+ /* 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))
+ return 0;
+ }
+ /* Is it already too late to try something ? */
+ status = game_status(color);
+ if (status < 0.8)
+ /* Still "too early".
+ * Note: the 0.8 constant is very conservative, we actually could give
+ * up a bit earlier.
+ */
+ return 0;
+
+ /* well, it is probably reasonable and polite to give up this game */
+ return 1;
+}
+
/*********************************************************************\
* Mark a limited search area *
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.41
diff -u -r1.41 globals.c
--- engine/globals.c 28 Jan 2003 16:54:04 -0000 1.41
+++ engine/globals.c 12 Feb 2003 09:37:33 -0000
@@ -141,6 +141,7 @@
int allow_suicide = 0; /* allow opponent to make suicide moves */
int capture_all_dead = 0; /* capture all dead opponent stones */
int play_out_aftermath = 0; /* make everything unconditionally settled */
+int resign_allowed = 0; /* allows GG to resign hopeless games */
int play_mirror_go = 0; /* try to play mirror go if possible */
int mirror_stones_limit = -1; /* but stop at this number of stones */
@@ -174,3 +175,8 @@
struct eye_data owl_white_eye[BOARDMAX];
struct surround_data surroundings[MAX_SURROUND];
int surround_pointer;
+
+double slowest_time = 0.0;
+int slowest_move = NO_MOVE;
+int slowest_movenum = 0;
+double total_time = 0.0;
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.89
diff -u -r1.89 gnugo.h
--- engine/gnugo.h 28 Jan 2003 16:54:04 -0000 1.89
+++ engine/gnugo.h 12 Feb 2003 09:37:33 -0000
@@ -286,6 +286,7 @@
extern int allow_suicide; /* allow opponent to make suicide moves */
extern int capture_all_dead; /* capture all dead opponent stones */
extern int play_out_aftermath; /* make everything unconditionally settled */
+extern int resign_allowed; /* allows GG to resign hopeless games */
extern int play_mirror_go; /* try to play mirror go if possible */
extern int mirror_stones_limit; /* but stop at this number of stones */
extern int gtp_version; /* version of Go Text Protocol */
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.74
diff -u -r1.74 influence.c
--- engine/influence.c 2 Jan 2003 00:23:28 -0000 1.74
+++ engine/influence.c 12 Feb 2003 09:37:34 -0000
@@ -1688,6 +1688,79 @@
return score;
}
+
+/* Uses initial_influence to estimate :
+ *
+ * - the score (balance in terms of solid territory)
+ * - the "power" (balance in terms of influence)
+ * - the game advancement (fuseki, chuban, yose)
+ * returned as a value between 0.0 (start) and 1.0 (game over)
+ *
+ * The algorythm uses a 'chinese rules'-like method to estimate the
+ * score, so prisoners and dead stones are just ignored.
+ */
+static float
+influence_evaluate_position(int color, float *power, float *game_status)
+{
+ struct influence_data *iq = INITIAL_INFLUENCE(color);
+ struct influence_data *oq = OPPOSITE_INFLUENCE(color);
+ float score = 0.0;
+ float power_balance = 0.0;
+ int count = 0;
+ int non_territory = 0;
+ int ii;
+
+ for (ii = BOARDMIN; ii < BOARDMAX; ii++)
+ if (ON_BOARD(ii)) {
+ if (iq->safe[ii]) {
+ /* chinese-style scoring, a safe stone is 1 point */
+ score += (board[ii] == WHITE ? 1 : -1);
+ count += WEIGHT_TERRITORY;
+ }
+ else if (whose_territory(iq, ii) != EMPTY
+ && whose_territory(oq, ii) != EMPTY) {
+ /* chinese-style scoring, add 1 point max, not 2 */
+ score += (iq->territory_value[ii] > 0 ? 1 : -1);
+ count += WEIGHT_TERRITORY;
+ }
+ else if (whose_moyo(oq, ii) != EMPTY) {
+ power_balance += oq->white_influence[ii] - oq->black_influence[ii];
+ non_territory++;
+ count += WEIGHT_MOYO;
+ }
+ else if (whose_area(oq, ii) != EMPTY) {
+ power_balance += oq->white_influence[ii] - oq->black_influence[ii];
+ non_territory++;
+ count += WEIGHT_AREA;
+ }
+ else {
+ power_balance += oq->white_influence[ii] - oq->black_influence[ii];
+ non_territory++;
+ }
+ }
+
+ score += komi;
+
+ if (power)
+ *power = power_balance / non_territory;
+ if (game_status)
+ *game_status = (float) count
+ / (WEIGHT_TERRITORY * board_size * board_size);
+
+ return score;
+}
+
+/* Export game advancement status (fuseki, chuban, yose)
+ * Returned as a value between 0.0 (start) and 1.0 (game over)
+ */
+float game_status(int color)
+{
+ float status;
+ influence_evaluate_position(color, NULL, &status);
+ return status;
+}
+
+
/* Print the influence map when we have computed influence for the
* move at (i, j).
*/
Index: engine/influence.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.h,v
retrieving revision 1.15
diff -u -r1.15 influence.h
--- engine/influence.h 2 Jan 2003 00:23:28 -0000 1.15
+++ engine/influence.h 12 Feb 2003 09:37:34 -0000
@@ -120,6 +120,11 @@
*/
typedef int (*owner_function_ptr)(const struct influence_data *q, int pos);
+/* Used for tuning game advancement algorythm */
+#define WEIGHT_TERRITORY 10
+#define WEIGHT_MOYO 3
+#define WEIGHT_AREA 1
+
/*
* Local Variables:
* tab-width: 8
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.156
diff -u -r1.156 liberty.h
--- engine/liberty.h 3 Feb 2003 23:33:05 -0000 1.156
+++ engine/liberty.h 12 Feb 2003 09:37:35 -0000
@@ -692,6 +692,7 @@
float black_influence[BOARDMAX],
int regions[BOARDMAX]);
float influence_score(const struct influence_data *q);
+float game_status(int color);
void resegment_initial_influence(void);
void influence_mark_non_territory(int pos, int color);
@@ -817,6 +818,11 @@
};
extern struct stats_data stats;
+
+extern double slowest_time; /* Timing statistics */
+extern int slowest_move;
+extern int slowest_movenum;
+extern double total_time;
struct eyevalue {
Index: interface/main.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v
retrieving revision 1.64
diff -u -r1.64 main.c
--- interface/main.c 2 Feb 2003 09:09:52 -0000 1.64
+++ interface/main.c 12 Feb 2003 09:37:38 -0000
@@ -129,7 +129,8 @@
OPT_DEFEND_BY_PATTERN,
OPT_MIRROR,
OPT_MIRROR_LIMIT,
- OPT_METAMACHINE
+ OPT_METAMACHINE,
+ OPT_RESIGN_ALLOWED
};
/* names of playing modes */
@@ -261,6 +262,7 @@
{"mirror", no_argument, 0, OPT_MIRROR},
{"mirror-limit", required_argument, 0, OPT_MIRROR_LIMIT},
{"metamachine", no_argument, 0, OPT_METAMACHINE},
+ {"resign-allowed", no_argument, 0, OPT_RESIGN_ALLOWED},
{NULL, 0, NULL, 0}
};
@@ -553,6 +555,10 @@
play_out_aftermath = 1;
break;
+ case OPT_RESIGN_ALLOWED:
+ resign_allowed = 1;
+ break;
+
case OPT_MODE:
if (strcmp(gg_optarg, "ascii") == 0)
playmode = MODE_ASCII;
@@ -945,6 +951,9 @@
switch (playmode) {
case MODE_GMP:
+ /* not supported by the protocol */
+ resign_allowed = 0;
+
#if ORACLE
if (metamachine)
summon_oracle();
@@ -960,6 +969,9 @@
break;
case MODE_SOLO:
+ /* not yet implemented */
+ resign_allowed = 0;
+
play_solo(&gameinfo, benchmark);
break;
@@ -1254,6 +1266,9 @@
if (mandated_color != EMPTY)
gameinfo.computer_player = OTHER_COLOR(mandated_color);
+ /* not yet implemented */
+ resign_allowed = 0;
+
play_ascii_emacs(&sgftree, &gameinfo, infilename, untilstring);
break;
@@ -1261,6 +1276,9 @@
default:
if (mandated_color != EMPTY)
gameinfo.computer_player = OTHER_COLOR(mandated_color);
+
+ /* not yet implemented */
+ resign_allowed = 0;
play_ascii(&sgftree, &gameinfo, infilename, untilstring);
break;
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.111
diff -u -r1.111 play_gtp.c
--- interface/play_gtp.c 3 Jan 2003 15:26:52 -0000 1.111
+++ interface/play_gtp.c 12 Feb 2003 09:37:39 -0000
@@ -2040,15 +2040,19 @@
gtp_genmove_black(char *s)
{
int i, j;
+ float val;
UNUSED(s);
if (stackp > 0)
return gtp_failure("genmove cannot be called when stackp > 0");
- if (genmove(&i, &j, BLACK) >= 0)
- play_move(POS(i, j), BLACK);
- else
- play_move(NO_MOVE, BLACK);
+ val = genmove(&i, &j, BLACK);
+
+ if (resign_allowed && val < 0.0 && ON_BOARD(POS(i, j))) {
+ return gtp_echo("resign");
+ }
+
+ play_move(POS(i, j), BLACK);
gtp_start_response(GTP_SUCCESS);
gtp_print_vertex(i, j);
@@ -2066,15 +2070,19 @@
gtp_genmove_white(char *s)
{
int i, j;
+ float val;
UNUSED(s);
if (stackp > 0)
return gtp_failure("genmove cannot be called when stackp > 0");
- if (genmove(&i, &j, WHITE) >= 0)
- play_move(POS(i, j), WHITE);
- else
- play_move(NO_MOVE, WHITE);
+ val = genmove(&i, &j, WHITE);
+
+ if (resign_allowed && val < 0.0 && ON_BOARD(POS(i, j))) {
+ return gtp_echo("resign");
+ }
+
+ play_move(POS(i, j), WHITE);
gtp_start_response(GTP_SUCCESS);
gtp_print_vertex(i, j);
@@ -2094,6 +2102,7 @@
int i, j;
int color;
int n;
+ float val;
n = gtp_decode_color(s, &color);
if (!n)
@@ -2102,7 +2111,12 @@
if (stackp > 0)
return gtp_failure("genmove cannot be called when stackp > 0");
- genmove(&i, &j, color);
+ val = genmove(&i, &j, color);
+
+ if (resign_allowed && val < 0.0 && ON_BOARD(POS(i, j))) {
+ return gtp_echo("resign");
+ }
+
play_move(POS(i, j), color);
gtp_start_response(GTP_SUCCESS);
Index: interface/play_test.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_test.c,v
retrieving revision 1.13
diff -u -r1.13 play_test.c
--- interface/play_test.c 2 Jan 2003 00:23:29 -0000 1.13
+++ interface/play_test.c 12 Feb 2003 09:37:40 -0000
@@ -34,6 +34,9 @@
static void replay_node(SGFNode *node, int color_to_test);
+static float replay_score;
+static float total_score;
+
/* --------------------------------------------------------------*/
/* replay a game */
@@ -78,6 +81,9 @@
printf("White Player: %s\n", tmpc);
gameinfo_print(gameinfo);
+
+ replay_score = 0.0;
+ total_score = 0.0;
}
/*
@@ -90,6 +96,19 @@
sgffile_output(&tree);
node = node->child;
}
+
+ if (!quiet) {
+ printf("\nGlobal score: %.2f / %.2f", replay_score, total_score);
+ }
+
+ if (showtime) {
+ gprintf("\nSLOWEST MOVE: %d at %1m ", slowest_movenum, slowest_move);
+ fprintf(stderr, "(%.2f seconds)\n", slowest_time);
+ fprintf(stderr, "\nAVERAGE TIME: %.2f seconds per move\n",
+ total_time / movenum);
+ fprintf(stderr, "\nTOTAL TIME: %.2f seconds\n",
+ total_time);
+ }
}
@@ -144,27 +163,45 @@
if (color == color_to_replay || color_to_replay == GRAY) {
/* Get a move from the engine for color. */
- gnugo_genmove(&i, &j, color);
+ float move_val = gnugo_genmove(&i, &j, color);
/* Now report on how well the computer generated the move. */
if (i != m || j != n || !quiet) {
mprintf("Move %d (%C): ", movenum + 1, color);
- mprintf("GNU Go plays %m ", i, j);
- if (!gnugo_is_pass(i, j))
- printf("(%.2f) ", potential_moves[i][j]);
+ if (move_val < 0.0 && !gnugo_is_pass(i, j))
+ printf("GNU Go resigns ");
+ else {
+ mprintf("GNU Go plays %m ", i, j);
+ if (!gnugo_is_pass(i, j))
+ printf("(%.2f) ", potential_moves[i][j]);
+ }
mprintf("- Game move %m ", m, n);
if (!gnugo_is_pass(m, n) && potential_moves[m][n] > 0.0)
printf("(%.2f) ", potential_moves[m][n]);
printf("\n");
+
+ if (!quiet) {
+ replay_score += (potential_moves[i][j] - potential_moves[m][n]);
+ total_score += potential_moves[i][j];
+ }
}
if (i != m || j != n) {
- gg_snprintf(buf, 127, "GNU Go plays %s (%.2f) - Game move %s (%.2f)",
- location_to_string(POS(i, j)),
- gnugo_is_pass(i, j) ? 0 : potential_moves[i][j],
- location_to_string(POS(m, n)),
- gnugo_is_pass(m, n)
- && potential_moves[m][n] < 0.0 ? 0 : potential_moves[m][n]);
- sgfCircle(node, i, j);
+ if (move_val < 0.0 && !gnugo_is_pass(i, j))
+ gg_snprintf(buf, 127, "GNU Go resigns - Game move %s (%.2f)",
+ location_to_string(POS(m, n)),
+ gnugo_is_pass(m, n)
+ && potential_moves[m][n] < 0.0 ?
+ 0 : potential_moves[m][n]);
+ else {
+ gg_snprintf(buf, 127, "GNU Go plays %s (%.2f) - Game move %s (%.2f)",
+ location_to_string(POS(i, j)),
+ gnugo_is_pass(i, j) ? 0 : potential_moves[i][j],
+ location_to_string(POS(m, n)),
+ gnugo_is_pass(m, n)
+ && potential_moves[m][n] < 0.0 ?
+ 0 : potential_moves[m][n]);
+ sgfCircle(node, i, j);
+ }
}
else
gg_snprintf(buf, 127, "GNU Go plays the same move %s (%.2f)",
Index: interface/gtp_examples/twogtp
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/gtp_examples/twogtp,v
retrieving revision 1.8
diff -u -r1.8 twogtp
--- interface/gtp_examples/twogtp 29 Oct 2002 14:41:17 -0000 1.8
+++ interface/gtp_examples/twogtp 12 Feb 2003 09:37:40 -0000
@@ -305,6 +305,7 @@
$self->white->komi($komi);
my $pass = 0;
+ my $resign = 0;
my ($move, $toplay, $sgfmove);
$pass = 0;
@@ -324,25 +325,30 @@
}
$#{$self->moves} = -1;
- while ($pass < 2) {
+ while ($pass < 2 and $resign eq 0) {
if ($toplay eq 'B') {
$move = $self->black->genmove("black");
if ($move eq "ERROR") {
- $self->writesgf($sgffile) if defined $sgffile;
+ $self->writesgf($sgffile) if defined $sgffile;
die "No response!";
}
- push @{$self->moves}, $move;
- print "Black plays $move\n" if $verbose;
- $pass = ($move =~ /PASS/i) ? $pass + 1 : 0;
- $self->white->black($move);
+ $resign = ($move =~ /resign/i) ? 1 : 0;
+ if ($resign) {
+ print "Black resigns\n" if $verbose;
+ } else {
+ push @{$self->moves}, $move;
+ print "Black plays $move\n" if $verbose;
+ $pass = ($move =~ /PASS/i) ? $pass + 1 : 0;
+ $self->white->black($move);
+ }
if ($verbose == 3) {
my $black_seed = $self->black->get_random_seed;
printf "Black seed $black_seed\n";
}
if ($verbose == 2) {
- $self->white->showboard;
+ $self->white->showboard;
}
$toplay = 'W';
@@ -351,31 +357,42 @@
$move = $self->white->genmove("white");
if ($move eq "ERROR") {
- $self->writesgf($sgffile) if defined $sgffile;
+ $self->writesgf($sgffile) if defined $sgffile;
die "No response!";
}
- push @{$self->moves}, $move;
- print "White plays $move\n" if $verbose;
- $pass = ($move =~ /PASS/i) ? $pass + 1 : 0;
- $self->black->white($move);
+ $resign = ($move =~ /resign/i) ? 1 : 0;
+ if ($resign) {
+ print "White resigns\n" if $verbose;
+ } else {
+ push @{$self->moves}, $move;
+ print "White plays $move\n" if $verbose;
+ $pass = ($move =~ /PASS/i) ? $pass + 1 : 0;
+ $self->black->white($move);
+ }
if ($verbose == 3) {
my $white_seed = $self->white->get_random_seed;
printf "White seed $white_seed\n";
}
if ($verbose == 2) {
- $self->black->showboard;
+ $self->black->showboard;
}
$toplay = 'B';
}
}
- my $resultw = $self->white->estimate_score;
- my $resultb = $self->black->estimate_score;
+ my $resultb;
+ my $resultw;
+ if ($resign) {
+ $resultb = $toplay eq 'B' ? 'B+R' : 'W+R';
+ $resultw = $resultb;
+ } else {
+ $resultw = $self->white->estimate_score;
+ $resultb = $self->black->estimate_score;
+ }
if ($resultb eq $resultw) {
print "Result: $resultw\n";
- }
- else {
+ } else {
print "Result according to W: $resultw\n";
print "****** according to B: $resultb\n";
}
- [gnugo-devel] nando_3_17.6,
Nando <=