[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] more joseki preparations
|
From: |
Paul Pogonyshev |
|
Subject: |
[gnugo-devel] more joseki preparations |
|
Date: |
Thu, 2 Jan 2003 23:00:43 +0200 |
this patch does quite a lot of things, though the new matcher is
still not completed. here is the full list of changes:
- it is now possible to reduce MAX_BOARD and still get working
gnu go
- mkpat now has an ugly mechanism for dropping patterns
- corner database creation implemented
- corner database pattern matcher implemented but not connected
to the rest of the engine
- yet another bugfix in play_ascii.c: allow changing handicap/
komi etc. in new games
- fixed broken indentation in play_ascii.c
the new pattern matcher is not going to work with patterns larger
than the maximal supported board. it would corrupt memory or even
crash if fed with such patterns. so, i decided to ensure that it
would be impossible (without hacking the code ;). i discovered
that gnu go doesn't compile if MAX_BOARD is reduced. i remember
Arend suggested somebody (author of neurogo?) to reduce MAX_BOARD
to 13. looks like he have never tried that ;)
the main changes regarding the issue are in joseki.c and mkpat.c.
extract_fuseki probably has the same problems, but those can be
fixed as soon as anybody decides to refresh the fuseki databases.
now, mkpat just silently drops all patterns which can't ever match
since they are larger than the maximal supported board.
the bug in the ascii interface was discovered while i was checking
that gnu go worked properly with MAX_BOARD = 9.
the new matcher itself is written but most certainly won't work
for i haven't even tested it and there must be many bugs. it is
#if'ed and disabled for now. database creation stuff, on the
contrary, seems to work properly. the current size of joseki
corner database is 119 kB, but will probably increase by several
kilobytes by the time the matcher is completed. still it must be
much less than the size of general patterns database and the new
matcher must be much faster.
mkpat -C reports that there are several duplicated patterns in
hoshi.db. i haven't fixed that issue yet. while in -C mode, it
discards duplicated patterns.
the new code is almost not commented yet. still, if anyone can
read it, comments and suggestions are welcome.
Paul
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.38
diff -u -p -r1.38 globals.c
--- engine/globals.c 1 Jan 2003 12:41:25 -0000 1.38
+++ engine/globals.c 2 Jan 2003 20:19:10 -0000
@@ -33,7 +33,7 @@
/* The go board and position. */
-int board_size = 19; /* board size */
+int board_size = DEFAULT_BOARD_SIZE; /* board size */
Intersection board[BOARDSIZE];
int board_ko_pos;
int white_captured; /* number of black and white stones captured */
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.147
diff -u -p -r1.147 liberty.h
--- engine/liberty.h 1 Jan 2003 12:41:25 -0000 1.147
+++ engine/liberty.h 2 Jan 2003 20:19:16 -0000
@@ -257,6 +257,8 @@ void restore_board(struct board_state *s
struct pattern;
struct pattern_db;
struct fullboard_pattern;
+struct corner_pattern;
+struct corner_db;
struct half_eye_data;
struct movelist;
struct tree_node_list;
@@ -272,6 +274,9 @@ typedef void (*matchpat_callback_fn_ptr)
typedef void (*fullboard_matchpat_callback_fn_ptr)(int move,
struct fullboard_pattern *,
int rotation);
+typedef void (*corner_matchpat_callback_fn_ptr)(int move, int color,
+ struct corner_pattern *pattern,
+ int rotation);
void matchpat(matchpat_callback_fn_ptr callback, int color,
struct pattern_db *pdb, void *callback_data,
char goal[BOARDMAX]);
@@ -280,6 +285,8 @@ void matchpat_goal_anchor(matchpat_callb
char goal[BOARDMAX], int anchor_in_goal);
void fullboard_matchpat(fullboard_matchpat_callback_fn_ptr callback,
int color, struct fullboard_pattern *pattern);
+void corner_matchpat(corner_matchpat_callback_fn_ptr callback, int color,
+ struct corner_db *database);
void dfa_match_init(void);
void tree_match_init(void);
void tree_initialize_pointers(struct tree_node_list *tnl,
Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.48
diff -u -p -r1.48 matchpat.c
--- engine/matchpat.c 1 Jan 2003 12:41:25 -0000 1.48
+++ engine/matchpat.c 2 Jan 2003 20:19:24 -0000
@@ -1256,6 +1256,123 @@ fullboard_matchpat(fullboard_matchpat_ca
}
+/**************************************************************************/
+/* Corner matcher */
+/**************************************************************************/
+
+#if 0
+/* These arrays specify anchor corner for each transformation. They _must_
+ * be in line with transformation2[][] array in patterns/transform.c.
+ */
+static const int corner_x[8] = {0, 1, 1, 0, 1, 0, 0, 1};
+static const int corner_y[8] = {0, 0, 1, 1, 1, 1, 0, 0};
+
+static int num_stones[BOARDMAX];
+
+
+static void
+do_corner_matchpat(int num_variations, struct corner_variation *variation,
+ int match_color, corner_matchpat_callback_fn_ptr callback,
+ int callback_color, int trans, int anchor, int stones)
+{
+ for (; --num_variations >= 0; variation++) {
+ int move = AFFINE_TRANSFORM(variation->move_offset, trans, anchor);
+ char color_check = match_color ^ variation->xor_att;
+ struct corner_pattern *pattern = variation->pattern;
+
+ if (pattern && color_check == callback_color) {
+ int second_corner
+ = AFFINE_TRANSFORM(pattern->second_corner_offset, trans, anchor);
+
+ if (num_stones[second_corner] == stones) {
+ ASSERT1(board[move] == EMPTY, move);
+
+ callback(move, callback_color, pattern, trans);
+ }
+ }
+
+ if (variation->num_variations
+ && num_stones[move] == variation->num_stones
+ && board[move] == color_check) {
+ do_corner_matchpat(variation->num_variations, variation->variations,
+ match_color, callback, callback_color,
+ trans, anchor, stones + 1);
+ }
+ }
+}
+
+
+void
+corner_matchpat(corner_matchpat_callback_fn_ptr callback, int color,
+ struct corner_db *database)
+{
+ int k;
+
+ for (k = 0; k < 8; k++) {
+ int anchor = POS(corner_x[k] * (board_size - 1),
+ corner_y[k] * (board_size - 1));
+ int i;
+ int j;
+ int dx = TRANSFORM(OFFSET(1, 0), k);
+ int dy = TRANSFORM(OFFSET(0, 1), k);
+ int pos;
+ struct corner_variation *variation = database->top_variations;
+
+ num_stones[anchor] = IS_STONE(board[anchor]);
+
+ pos = anchor;
+ for (i = 1; i < database->max_height; i++) {
+ pos += dx;
+ if (!ON_BOARD1(pos)) {
+ do {
+ num_stones[pos] = BOARDMAX;
+ pos += dx;
+ } while (++i < database->max_height);
+
+ break;
+ }
+
+ num_stones[pos] = num_stones[pos - dx] + IS_STONE(board[pos]);
+ }
+
+ pos = anchor;
+ for (j = 1; j < database->max_width; j++) {
+ pos += dy;
+ if (!ON_BOARD1(pos)) {
+ do {
+ num_stones[pos] = BOARDMAX;
+ pos += dy;
+ } while (++j < database->max_width);
+
+ break;
+ }
+
+ num_stones[pos] = num_stones[pos - dy] + IS_STONE(board[pos]);
+ }
+
+ for (i = 1; i < database->max_height; i++) {
+ pos = anchor + i * dy;
+ for (j = 1; j < database->max_width; j++) {
+ pos += dx;
+ num_stones[pos] = num_stones[pos - dx] + num_stones[pos - dy]
+ - num_stones[pos - dx - dy] + IS_STONE(board[pos]);
+ }
+ }
+
+ for (i = 0; i < database->num_top_variations; i++) {
+ int move = AFFINE_TRANSFORM(variation->move_offset, k, anchor);
+
+ if (num_stones[move] == 1 && IS_STONE(board[move]))
+ do_corner_matchpat(variation->num_variations, variation->variations,
+ board[move], callback, color, k, anchor, 1);
+
+ variation++;
+ }
+ }
+}
+#endif
+
+
/*
* Local Variables:
* tab-width: 8
Index: interface/main.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v
retrieving revision 1.60
diff -u -p -r1.60 main.c
--- interface/main.c 26 Dec 2002 04:33:48 -0000 1.60
+++ interface/main.c 2 Jan 2003 20:19:58 -0000
@@ -300,8 +300,6 @@ main(int argc, char *argv[])
*/
int seed = 0;
- board_size = gg_min(19, MAX_BOARD);
-
komi = 0.0;
level = DEFAULT_LEVEL;
Index: interface/play_ascii.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_ascii.c,v
retrieving revision 1.31
diff -u -p -r1.31 play_ascii.c
--- interface/play_ascii.c 31 Dec 2002 12:41:09 -0000 1.31
+++ interface/play_ascii.c 2 Jan 2003 20:20:00 -0000
@@ -335,7 +335,7 @@ enum commands {INVALID=-1, END, EXIT, QU
CMD_CAPTURE, CMD_DEFEND,
CMD_HELPDEBUG, CMD_SHOWAREA, CMD_SHOWMOYO, CMD_SHOWTERRI,
CMD_GOTO, CMD_SAVE, CMD_LOAD, CMD_SHOWDRAGONS, CMD_LISTDRAGONS,
- SETHURRY, SETLEVEL, NEW, COUNT, FREEHANDICAP
+ SETHURRY, SETLEVEL, NEW, COUNT, FREEHANDICAP
};
@@ -679,15 +679,15 @@ play_ascii(SGFTree *tree, Gameinfo *game
printf("\nSet handicap to %d\n", gameinfo->handicap);
gameinfo->to_move = (gameinfo->handicap ? WHITE : BLACK);
break;
- case FREEHANDICAP:
- if (sgf_initialized) {
- printf("Handicap cannot be changed after game is started!\n");
- break;
- }
- while (*command && *command != ' ')
- command++;
- ascii_free_handicap(gameinfo, command);
- break;
+ case FREEHANDICAP:
+ if (sgf_initialized) {
+ printf("Handicap cannot be changed after game is started!\n");
+ break;
+ }
+ while (*command && *command != ' ')
+ command++;
+ ascii_free_handicap(gameinfo, command);
+ break;
case SETKOMI:
if (sgf_initialized) {
printf("Komi cannot be modified after game record is started!\n");
@@ -971,7 +971,6 @@ play_ascii(SGFTree *tree, Gameinfo *game
}
sgffile_output(&sgftree);
passes = 0;
- showdead = 0;
/* Play a different game next time. */
update_random_seed();
@@ -980,6 +979,7 @@ play_ascii(SGFTree *tree, Gameinfo *game
sgfFreeNode(sgftree.root);
sgftree_clear(&sgftree);
sgftreeCreateHeaderNode(&sgftree, board_size, komi);
+ sgf_initialized = 0;
gameinfo_clear(gameinfo, board_size, komi);
}
@@ -1161,40 +1161,41 @@ ascii_free_handicap(Gameinfo *gameinfo,
if (!strncmp(line, "undo", 4)) {
if (!handi)
- printf("\nNothing to undo.\n");
- else {
- remove_stone(stones[--handi]);
- gprintf("\nRemoved the stone at %m.\n", I(stones[handi]),
- J(stones[handi]));
- }
+ printf("\nNothing to undo.\n");
+ else {
+ remove_stone(stones[--handi]);
+ gprintf("\nRemoved the stone at %m.\n", I(stones[handi]),
+ J(stones[handi]));
+ }
}
else if (!strncmp(line, "clear", 5)) {
gnugo_clear_board(board_size);
handi = 0;
}
else if (!strncmp(line, "done", 4)) {
- if (handi == 1) /* Don't bother with checks later */
- printf ("\nHandicap cannot be one stone. Either add "
- "some more, or delete the only stone.\n");
- else
- break;
+ if (handi == 1) /* Don't bother with checks later */
+ printf ("\nHandicap cannot be one stone. Either add "
+ "some more, or delete the only stone.\n");
+ else
+ break;
}
else if (string_to_location(board_size, line, &x, &y)) {
- pos = POS(x,y);
- if (board[pos] != EMPTY)
- printf("\nThere's already a stone there.\n");
- else {
- add_stone(pos, BLACK);
- stones[handi++] = pos;
- }
+ pos = POS(x,y);
+ if (board[pos] != EMPTY)
+ printf("\nThere's already a stone there.\n");
+ else {
+ add_stone(pos, BLACK);
+ stones[handi++] = pos;
+ }
}
else
- printf("\nInvalid command: %s", line);
+ printf("\nInvalid command: %s", line);
}
}
gameinfo->handicap = handi;
gameinfo->to_move = (handi ? WHITE : BLACK);
}
+
/*
* Local Variables:
Index: patterns/joseki.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/joseki.c,v
retrieving revision 1.14
diff -u -p -r1.14 joseki.c
--- patterns/joseki.c 31 Dec 2002 15:33:48 -0000 1.14
+++ patterns/joseki.c 2 Jan 2003 20:20:06 -0000
@@ -41,6 +41,16 @@ Usage : joseki prefix filename\n\
#define ANTISUJI 4
#define TENUKI_OK 5
+
+/* We don't want to play moves on edges of board which might have been
+ * cropped, since there might appear an accidential capture.
+ */
+#define SAFE_ON_BOARD(i, j) ((i) >= 0 && (j) >= 0\
+ && (i) < MAX_BOARD - 1 && (j) < MAX_BOARD - 1)
+
+static int boardsize;
+
+
/* Identify the type of joseki move.
* FIXME: We might want the relax the requirement that this info comes
* as the very first character.
@@ -131,7 +141,7 @@ write_diagram(int movei, int movej, int
int i, j;
for (i = -1; i <= marki; i++) {
- for (j = markj; j < board_size; j++) {
+ for (j = markj; j >= 0; j--) {
if (i == -1)
printf("-");
else if (labels && labels[i][j])
@@ -141,7 +151,7 @@ write_diagram(int movei, int movej, int
else if (BOARD(i, j) == color)
printf("O");
else if (BOARD(i, j) == OTHER_COLOR(color))
- printf("X");
+ printf("X");
else
printf(".");
}
@@ -186,7 +196,9 @@ write_colon_line(int move_type, char *te
case TENUKI_OK:
printf("t");
break;
- /* Antisuji moves handled elsewhere. */
+ case ANTISUJI:
+ printf("N");
+ break;
}
if (p) {
@@ -243,6 +255,9 @@ make_pattern(int movei, int movej, int c
/* Write constraint and action lines. */
write_selected_lines(text, ';');
write_selected_lines(text, '>');
+ /* FIXME: Remove these antisuji autohelper lines once the joseki callback
+ * handles antisuji moves itself.
+ */
if (move_type == ANTISUJI)
printf(">antisuji(*);\n");
printf("\n");
@@ -295,26 +310,32 @@ analyze_node(SGFNode *node, const char *
case SGFMA: /* Mark */
if (marki != -1)
multiple_marks = 1;
- else
- get_moveXY(prop, &marki, &markj, board_size);
+ else {
+ get_moveXY(prop, &marki, &markj, boardsize);
+ markj = boardsize - 1 - markj;
+ }
break;
case SGFW: /* White move */
color = WHITE;
- get_moveXY(prop, &movei, &movej, board_size);
+ get_moveXY(prop, &movei, &movej, boardsize);
+ movej = boardsize - 1 - movej;
break;
case SGFB: /* Black move */
color = BLACK;
- get_moveXY(prop, &movei, &movej, board_size);
+ get_moveXY(prop, &movei, &movej, boardsize);
+ movej = boardsize - 1 - movej;
break;
case SGFLB: /* Label, with value like "mh:A" */
- get_moveXY(prop, &i, &j, board_size);
- gg_assert(i >= 0 && i < board_size && j >= 0 && j < board_size);
+ get_moveXY(prop, &i, &j, boardsize);
+ j = boardsize - 1 - j;
gg_assert(prop->value[2] == ':');
- labels[i][j] = prop->value[3];
- label_found = 1;
+ if (ON_BOARD2(i, j)) {
+ labels[i][j] = prop->value[3];
+ label_found = 1;
+ }
break;
case SGFC: /* Comment */
@@ -324,16 +345,16 @@ analyze_node(SGFNode *node, const char *
}
/* If we have a move and a square mark, produce a pattern. */
- if (movei != -1 && marki != -1)
+ if (SAFE_ON_BOARD(movei, movej) && ON_BOARD2(marki, markj))
make_pattern(movei, movej, color, marki, markj, multiple_marks,
(label_found ? labels : NULL), comment, prefix);
/* Traverse child, if any. */
if (node->child) {
- if (movei != -1)
+ if (SAFE_ON_BOARD(movei, movej))
tryko(POS(movei, movej), color, NULL, EMPTY, NO_MOVE);
analyze_node(node->child, prefix);
- if (movei != -1)
+ if (SAFE_ON_BOARD(movei, movej))
popgo();
}
@@ -385,7 +406,7 @@ main(int argc, char *argv[])
# License along with this program; if not, write to the Free #\n\
# Software Foundation, Inc., 59 Temple Place - Suite 330, #\n\
# Boston, MA 02111, USA. #\n\
-# #\n\
+# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #\n\
# This file is automatically generated by joseki. Do not edit #\n\
# it directly. Instead, edit the corresponding sgf file. #\n\
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #\n\
@@ -394,13 +415,15 @@ main(int argc, char *argv[])
printf(PREAMBLE);
- if (board_size > MAX_BOARD) {
- fprintf(stderr, "Board too big\n");
- return -1;
- }
-
/* Call the engine to setup and clear the board. */
+ board_size = MAX_BOARD;
clear_board();
+
+ /* Determine board size of the file. */
+ if (!sgfGetIntProperty(sgf, "SZ", &boardsize)) {
+ fprintf(stderr, "joseki: error: can't determine file board size\n");
+ return 1;
+ }
/* Walk through the tree and make patterns. */
analyze_node(sgf, prefix);
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.105
diff -u -p -r1.105 mkpat.c
--- patterns/mkpat.c 1 Jan 2003 12:41:26 -0000 1.105
+++ patterns/mkpat.c 2 Jan 2003 20:20:17 -0000
@@ -65,7 +65,7 @@ Usage : mkpat [options] <prefix>\n\
-a = require anchor in all patterns. Sets fixed_anchor flag in db\n\
-r = pre-rotate patterns before storing in database\n\
If no input files specified, reads from stdin.\n\
-If outpuf file is not specified, writes to stdout.\n\
+If output file is not specified, writes to stdout.\n\
"
@@ -134,7 +134,7 @@ const char VALID_CONSTRAINT_LABELS[] = "
* Modify them using `goal_elements ...' and `callback_data ..'
* commands in a database. By default, we don't drop any elements.
*/
-int nongoal[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+int nongoal[8] = {0, 0, 0, 0, 0, 0, 0, 0};
int callback_unneeded[8] = {0, 0, 0, 0, 0, 0, 0, 0};
/* stuff used in reading/parsing pattern rows */
@@ -149,11 +149,11 @@ int num_stars;
int ci = -1, cj = -1; /* position of origin (first piece element)
relative to top-left */
int patno; /* current pattern */
+int discard_pattern = 0; /* Set to nonzero to discard a pattern (if e.g.
+ * it is too large or duplicated). */
int pats_with_constraints = 0; /* just out of interest */
int label_coords[256][2]; /* Coordinates for labeled stones in the
autohelper patterns. */
-int current_i; /* Counter for the line number of the
- diagram */
int current_c_i; /* Counter for the line number of a
constraint diagram. */
char constraint[MAXCONSTRAINT]; /* Store constraint lines. */
@@ -443,7 +443,7 @@ check_constraint_diagram(void)
if (0)
fprintf(stderr, "have_constraint: %d\n", have_constraint);
- if (have_constraint) {
+ if (have_constraint && el) {
for (i = ino; i <= maxi+ino; i++)
for (j = jwo; j <= maxj+jwo; j++) {
if (0)
@@ -482,7 +482,6 @@ reset_pattern(void)
strcpy(helper_fn_names[patno], "NULL");
for (i = 0; i < 256; i++)
label_coords[i][0] = -1;
- current_i = 0;
current_c_i = 0;
constraint[0] = 0;
action[0] = 0;
@@ -492,18 +491,16 @@ reset_pattern(void)
constraint_diagram[i][j] = '\0';
}
}
+ memset(&pattern[patno], 0, sizeof(struct pattern));
}
-
-/* this is called to compute the extents of the pattern, applying
- * edge constraints as necessary
+/* This is called to compute the extents of the pattern, applying
+ * edge constraints as necessary.
*/
-
static void
find_extents(void)
{
-
/* When this is called, elements go from (mini,minj) inclusive to
* (maxi-1, maxj-1) [ie exclusive]. Make them inclusive.
* Ie maximum element lies on (maxi,maxj).
@@ -637,12 +634,11 @@ compute_grids(void)
}
-
-/* We've just read a line that looks like a pattern line.
- * Now process it.
+/* We've just read a line that looks like a pattern line. Now process it.
+ * If the pattern becomes larger than maximal supported board, the function
+ * returns zero, so that the pattern can be discarded.
*/
-
-static void
+static int
read_pattern_line(char *p)
{
const char *char_offset;
@@ -690,7 +686,7 @@ read_pattern_line(char *p)
if (maxi > 0 && width != maxj)
goto notrectangle;
- return;
+ return 1;
}
/* get here => its a real pattern entry,
@@ -778,6 +774,7 @@ read_pattern_line(char *p)
elements[el].x = maxi;
elements[el].y = j;
elements[el].att = off; /* '*' mapped to '.' and 'Q' to 'O' above */
+
++el;
}
@@ -807,22 +804,23 @@ read_pattern_line(char *p)
jwo = 1;
if (where & EAST_EDGE)
jeo = 1;
- strncpy(diagram[maxi], pcopy, maxj + jwo + jeo);
+ if (maxi <= MAX_BOARD)
+ strncpy(diagram[maxi], pcopy, maxj + jwo + jeo);
maxi++;
- return;
+ return maxi <= MAX_BOARD && maxj <= MAX_BOARD;
fatal:
fprintf(stderr, "%s(%d) : error : Illegal pattern %s\n",
current_file, current_line_number, pattern_names[patno]);
fatal_errors = 1;
- return;
+ return 0;
notrectangle:
fprintf(stderr, "%s(%d) : error : Pattern %s not rectangular\n",
current_file, current_line_number, pattern_names[patno]);
fatal_errors++;
- return;
+ return 0;
}
@@ -874,7 +872,8 @@ read_constraint_diagram_line(char *p)
jwo = 1;
if (where & EAST_EDGE)
jeo = 1;
- strncpy(constraint_diagram[current_c_i], pcopy, maxj+jwo+jeo+1);
+ if (el)
+ strncpy(constraint_diagram[current_c_i], pcopy, maxj+jwo+jeo+1);
current_c_i++;
return;
@@ -917,6 +916,10 @@ finish_pattern(char *line)
ci = (maxi-1)/2;
cj = (maxj-1)/2;
}
+ else if (database_type == DB_CORNER) {
+ ci = 0;
+ cj = 0;
+ }
else if (choose_best_anchor) {
/* Try to find a better anchor if
@@ -948,7 +951,7 @@ finish_pattern(char *line)
}
else if (ci == -1 || cj == -1) {
fprintf(stderr, "%s(%d) : No origin for pattern %s\n",
- current_file, current_line_number, pattern_names[patno]);
+ current_file, current_line_number, pattern_names[patno]);
fatal_errors = 1;
ci = 0;
cj = 0;
@@ -1067,6 +1070,7 @@ finish_pattern(char *line)
case 'U': pattern[patno].class |= CLASS_U; break;
case 'W': pattern[patno].class |= CLASS_W; break;
case 'F': pattern[patno].class |= CLASS_F; break;
+ case 'N': pattern[patno].class |= CLASS_N; break;
case 'Y': pattern[patno].class |= CLASS_Y; break;
case '-': break;
default:
@@ -1235,6 +1239,7 @@ generate_autohelper_code(int funcno, int
fatal_errors++;
}
break;
+
case 1:
/* This is a very special case where there is assumed to be a
* variable number of parameters and these constitute a series of
@@ -2119,6 +2124,316 @@ tree_write_patterns(FILE *outfile)
#endif
+
+/* ================================================================ */
+/* Corner database creation stuff */
+/* ================================================================ */
+
+#define CORNER_DB_SIZE(patterns, variations)\
+ (( patterns * sizeof(struct corner_pattern)\
+ + variations * sizeof(struct corner_variation)) / 1024)
+
+static struct corner_variation_b corner_root;
+static int second_corner_offset[MAXPATNO];
+
+static int total_variations = 0;
+static int variations_written = 0;
+
+static int corner_max_width = 0;
+static int corner_max_height = 0;
+
+/* This structure is used by corner_add_pattern() */
+struct corner_element {
+ int x;
+ int y;
+ int color;
+};
+
+
+static void
+corner_init(void)
+{
+ corner_root.num_variations = 0;
+ corner_root.child = NULL;
+}
+
+
+static int corner_best_element(struct corner_element *el, int n, int x, int y,
+ struct corner_variation_b *variations,
+ int color)
+{
+ int k;
+ int i;
+ int best = 0;
+ int best_value = 0;
+
+ int candidate[MAX_BOARD * MAX_BOARD];
+ int candidates = 0;
+ int existing_variation[MAX_BOARD * MAX_BOARD];
+ int have_existing_variation = 0;
+
+ for (k = 0; k < n; k++) {
+ for (i = 0; i < n; i++) {
+ if (i == k)
+ continue;
+
+ if (el[k].x >= el[i].x && el[k].y >= el[i].y)
+ break;
+ }
+
+ if (i == n) {
+ struct corner_variation_b *v;
+ int move_offset = OFFSET(el[k].x, el[k].y);
+ int xor_att = (el[k].color == color ? ATT_O ^ ATT_O : ATT_O ^ ATT_X);
+
+ candidate[candidates] = k;
+ existing_variation[candidates] = 0;
+
+ for (v = variations; v != NULL; v = v->next) {
+ if (v->move_offset == move_offset
+ && (v->xor_att == xor_att || color == 0)) {
+ existing_variation[candidates] = 1;
+ have_existing_variation = 1;
+ break;
+ }
+ }
+
+ candidates++;
+ }
+ }
+
+ for (k = 0; k < candidates; k++) {
+ int m = candidate[k];
+ int value = 2 * MAX_BOARD * ((el[m].x + 1) * (el[m].y + 1)
+ - (gg_min(el[m].x, x) + 1) * (gg_min(el[m].y, y) + 1))
+ - 2 * gg_abs(el[m].x - el[m].y) + (el[m].x < el[m].y ? 1 : 0);
+
+ if (existing_variation[k] == have_existing_variation
+ && value > best_value) {
+ best = k;
+ best_value = value;
+ }
+ }
+
+ return candidate[best];
+}
+
+
+static struct corner_variation_b*
+corner_variation_new(int move_offset, char xor_att, char num_stones)
+{
+ struct corner_variation_b *variation;
+
+ variation = malloc(sizeof(struct corner_variation_b));
+
+ variation->move_offset = move_offset;
+ variation->xor_att = xor_att;
+ variation->num_stones = num_stones;
+ variation->num_variations = 0;
+ variation->next = NULL;
+ variation->child = NULL;
+ variation->child_num = -1;
+ variation->pattern_num = -1;
+
+ total_variations++;
+
+ return variation;
+}
+
+
+static struct corner_variation_b*
+corner_follow_variation(struct corner_variation_b *variation,
+ int offset, int color, char num_stones)
+{
+ char xor_att = color ? ATT_O ^ ATT_O : ATT_O ^ ATT_X;
+ struct corner_variation_b *subvariation = variation->child;
+ struct corner_variation_b **link = &(variation->child);
+
+ while (subvariation) {
+ if (subvariation->move_offset == offset
+ && subvariation->xor_att == xor_att) {
+ assert(subvariation->num_stones == num_stones);
+ return subvariation;
+ }
+
+ link = &(subvariation->next);
+ subvariation = subvariation->next;
+ }
+
+ variation->num_variations++;
+ *link = corner_variation_new(offset, xor_att, num_stones);
+
+ return *link;
+}
+
+
+static void
+corner_add_pattern(void)
+{
+ int k;
+ struct corner_element stone[MAX_BOARD * MAX_BOARD];
+ int stones = 0;
+ int trans;
+ int corner_x = 0;
+ int corner_y = 0;
+ int color = 0;
+ int move_pos;
+ int move_x;
+ int move_y;
+ char num_stones;
+ struct corner_variation_b *variation = &corner_root;
+
+ switch (where) {
+ case SOUTH_EDGE | WEST_EDGE: trans = 5; corner_x = maxi; break;
+ case WEST_EDGE | NORTH_EDGE: trans = 0; break;
+ case NORTH_EDGE | EAST_EDGE: trans = 7; corner_y = maxj; break;
+ case EAST_EDGE | SOUTH_EDGE:
+ trans = 2; corner_x = maxi; corner_y = maxj; break;
+
+ default:
+ fprintf(stderr, "%s(%d) : error : Illegal edge constraint in pattern
%s\n",
+ current_file, current_line_number, pattern_names[patno]);
+ return;
+ }
+
+ move_pos = AFFINE_TRANSFORM(pattern[patno].move_offset
+ - OFFSET_DELTA(corner_x, corner_y), trans, POS(0, 0));
+ move_x = I(move_pos);
+ move_y = J(move_pos);
+
+ for (k = 0; k < el; k++) {
+ if (elements[k].att == ATT_X || elements[k].att == ATT_O) {
+ TRANSFORM2(elements[k].x, elements[k].y,
+ &stone[stones].x, &stone[stones].y, trans);
+ stone[stones].x += corner_x;
+ stone[stones].y += corner_y;
+ stone[stones].color = elements[k].att;
+ stones++;
+ }
+ else if (elements[k].att != ATT_dot) {
+ fprintf(stderr, "%s(%d) : error : Illegal element in pattern %s\n",
+ current_file, current_line_number, pattern_names[patno]);
+ return;
+ }
+ }
+
+ for (k = 0; k < stones; k++) {
+ int i;
+ int best;
+ struct corner_element stone_t;
+
+ if (k > 0) {
+ best = k + corner_best_element(stone + k, stones - k, stone[k-1].x,
+ stone[k-1].y, variation->child, color);
+ stone_t = stone[k];
+ stone[k] = stone[best];
+ stone[best] = stone_t;
+ }
+ else {
+ best = corner_best_element(stone, stones, 0, 0, variation->child, color);
+ stone_t = stone[0];
+ stone[0] = stone[best];
+ stone[best] = stone_t;
+ color = stone[0].color;
+
+ if (stone[0].x > stone[0].y) {
+ int t;
+
+ t = maxi;
+ maxi = maxj;
+ maxj = t;
+
+ t = move_x;
+ move_x = move_y;
+ move_y = t;
+
+ for (i = 0; i < stones; i++) {
+ t = stone[i].x;
+ stone[i].x = stone[i].y;
+ stone[i].y = t;
+ }
+ }
+ }
+
+ num_stones = 0;
+ for (i = 0; i < k; i++) {
+ if (stone[i].x <= stone[k].x && stone[i].y <= stone[k].y)
+ num_stones++;
+ }
+
+ variation = corner_follow_variation(variation,
+ OFFSET(stone[k].x, stone[k].y), stone[k].color == color,
+ num_stones);
+ }
+
+ num_stones = 0;
+ for (k = 0; k < stones; k++) {
+ if (stone[k].x <= move_x && stone[k].y <= move_y)
+ num_stones++;
+ }
+
+ variation = corner_follow_variation(variation, OFFSET(move_x, move_y),
+ ATT_O == color, num_stones);
+ if (variation->pattern_num == -1) {
+ variation->pattern_num = patno;
+ second_corner_offset[patno] = OFFSET(maxi, maxj);
+ if (maxi > corner_max_height)
+ corner_max_height = maxi;
+ if (maxj > corner_max_width)
+ corner_max_width = maxj;
+ }
+ else {
+ fprintf(stderr, "%s(%d) : warning : duplicated patterns encountered (%s
and %s)\n",
+ current_file, current_line_number,
+ pattern_names[variation->pattern_num], pattern_names[patno]);
+ discard_pattern = 1;
+ }
+}
+
+
+static int
+corner_pack_variations(struct corner_variation_b *variation, int counter)
+{
+ counter++;
+ if (variation->next)
+ counter = corner_pack_variations(variation->next, counter);
+ if (variation->child) {
+ variation->child_num = counter;
+ counter = corner_pack_variations(variation->child, counter);
+ }
+
+ return counter;
+}
+
+
+static void
+corner_write_variations(struct corner_variation_b *variation, FILE *outfile)
+{
+ fprintf(outfile, " {%d,%d,%d,%d,", variation->move_offset,
+ variation->xor_att, variation->num_stones,
+ variation->num_variations);
+ if (variation->child)
+ fprintf(outfile, "&%s_variations[%d],", prefix, variation->child_num);
+ else
+ fprintf(outfile, "NULL,");
+ if (variation->pattern_num != -1)
+ fprintf(outfile, "&%s[%d]", prefix, variation->pattern_num);
+ else
+ fprintf(outfile, "NULL");
+
+ variations_written++;
+ if (variations_written != total_variations)
+ fprintf(outfile, "},\n");
+ else
+ fprintf(outfile, "}\n};\n\n\n");
+
+ if (variation->next)
+ corner_write_variations(variation->next, outfile);
+ if (variation->child)
+ corner_write_variations(variation->child, outfile);
+}
+
+
/* sort and write out the patterns */
static void
write_patterns(FILE *outfile)
@@ -2137,8 +2452,10 @@ write_patterns(FILE *outfile)
/* Write out the patterns. */
if (database_type == DB_FULLBOARD)
fprintf(outfile, "struct fullboard_pattern %s[] = {\n", prefix);
+ else if (database_type == DB_CORNER)
+ fprintf(outfile, "static struct corner_pattern %s[] = {\n", prefix);
else
- fprintf(outfile, "struct pattern %s[] = {\n", prefix);
+ fprintf(outfile, "static struct pattern %s[] = {\n", prefix);
for (j = 0; j < patno; ++j) {
struct pattern *p = pattern + j;
@@ -2148,7 +2465,24 @@ write_patterns(FILE *outfile)
pattern_names[j], p->move_offset, p->value);
continue;
}
-
+
+ if (database_type == DB_CORNER) {
+ fprintf(outfile, " {%d,0x%x,\"%s\",%f,%d,", second_corner_offset[j],
+ p->class, pattern_names[j], p->value, p->autohelper_flag);
+ if (p->autohelper)
+ fprintf(outfile, "autohelper%s%d", prefix, j);
+ else
+ fprintf(outfile, "NULL");
+ fprintf(outfile, ",%f}", p->constraint_cost);
+
+ if (j != patno - 1)
+ fprintf(outfile, ",\n");
+ else
+ fprintf(outfile, "\n};\n\n\n");
+
+ continue;
+ }
+
/* p->min{i,j} and p->max{i,j} are the maximum extent of the elements,
* including any rows of '?' which do not feature in the elements list.
* ie they are the positions of the topleft and bottomright corners of
@@ -2208,6 +2542,9 @@ write_patterns(FILE *outfile)
fprintf(outfile, "},\n");
}
+ if (database_type == DB_CORNER)
+ return;
+
if (database_type == DB_FULLBOARD) {
fprintf(outfile, " {NULL,0,NULL,0,0.0}\n};\n");
return;
@@ -2233,7 +2570,18 @@ write_pattern_db(FILE *outfile)
/* Don't want this for fullboard patterns. */
if (database_type == DB_FULLBOARD)
return;
-
+
+ if (database_type == DB_CORNER) {
+ fprintf(outfile, "struct corner_db %s_db = {\n", prefix);
+ fprintf(outfile, " %d,\n", corner_max_width);
+ fprintf(outfile, " %d,\n", corner_max_height);
+ fprintf(outfile, " %d,\n", corner_root.num_variations);
+ fprintf(outfile, " %s_variations\n", prefix);
+ fprintf(outfile, "};\n");
+
+ return;
+ }
+
/* Write out the pattern database. */
fprintf(outfile, "\n");
fprintf(outfile, "struct pattern_db %s_db = {\n", prefix);
@@ -2266,6 +2614,7 @@ main(int argc, char *argv[])
FILE *input_FILE = stdin;
FILE *output_FILE = stdout;
int state = 0;
+ char *save_code_pos = autohelper_code;
transformation_init();
@@ -2376,11 +2725,10 @@ main(int argc, char *argv[])
dfa.pre_rotated = pre_rotate;
}
- fprintf(output_FILE, PREAMBLE);
+ if (database_type == DB_CORNER)
+ corner_init();
- /* Parse the input file, output pattern elements as as we find them,
- * and store pattern entries for later output.
- */
+ fprintf(output_FILE, PREAMBLE);
/* Initialize pattern number and buffer for automatically generated
* helper code.
@@ -2388,8 +2736,11 @@ main(int argc, char *argv[])
patno = -1;
autohelper_code[0] = 0;
code_pos = autohelper_code;
-
- /* We do this parsing too with the help of a state machine.
+
+ /* Parse the input file, output pattern elements as as we find them,
+ * and store pattern entries for later output.
+ *
+ * We do this parsing too with the help of a state machine.
* state
* 0 Waiting for a Pattern line.
* 1 Pattern line found, waiting for a position diagram.
@@ -2436,7 +2787,7 @@ main(int argc, char *argv[])
int i = strlen(line) - 2; /* Start removing backwards just before
newline */
while (i >= 0 && isspace(line[i]))
i--;
- line[i+1] = '\n';
+ line[i+1] = '\n';
line[i+2] = '\0';
}
@@ -2482,7 +2833,10 @@ main(int argc, char *argv[])
}
if (command == 1) { /* Pattern `name' */
- patno++;
+ if (!discard_pattern)
+ patno++;
+ else
+ code_pos = save_code_pos;
reset_pattern();
if (strlen(command_data) > 79) {
@@ -2493,6 +2847,7 @@ main(int argc, char *argv[])
strcpy(pattern_names[patno], command_data);
state = 1;
+ discard_pattern = 0;
}
else {
int *sort_out = (command == 2 ? nongoal : callback_unneeded);
@@ -2562,8 +2917,10 @@ main(int argc, char *argv[])
case 1:
state++; /* fall through */
case 2:
- read_pattern_line(line);
- current_i++;
+ if (!read_pattern_line(line)) {
+ discard_pattern = 1;
+ el = 0;
+ }
break;
case 4:
state++; /* fall through */
@@ -2576,11 +2933,17 @@ main(int argc, char *argv[])
if (state == 2 || state == 3) {
finish_pattern(line);
- if (database_type == DB_DFA)
- write_to_dfa(patno);
- write_elements(output_FILE);
+ if (!discard_pattern) {
+ if (database_type == DB_DFA)
+ write_to_dfa(patno);
+ if (database_type != DB_CORNER)
+ write_elements(output_FILE);
+ else
+ corner_add_pattern();
+ }
state = 4;
+ save_code_pos = code_pos;
}
else {
fprintf(stderr,
@@ -2654,14 +3017,25 @@ main(int argc, char *argv[])
reset_pattern();
}
}
-
+
+ if (discard_pattern) {
+ patno--;
+ code_pos = save_code_pos;
+ }
+
+ *code_pos = 0;
+
if (verbose)
fprintf(stderr, "%d / %d patterns have edge-constraints\n",
pats_with_constraints, patno);
/* Forward declaration, which autohelpers might need. */
- if (database_type != DB_FULLBOARD && database_type != DB_CORNER)
- fprintf(output_FILE, "extern struct pattern %s[];\n\n", prefix);
+ if (database_type != DB_FULLBOARD) {
+ if (database_type != DB_CORNER)
+ fprintf(output_FILE, "static struct pattern %s[];\n\n", prefix);
+ else
+ fprintf(output_FILE, "static struct corner_pattern %s[];\n\n", prefix);
+ }
/* Write the autohelper code. */
fprintf(output_FILE, "%s", autohelper_code);
@@ -2693,6 +3067,19 @@ main(int argc, char *argv[])
dfa_end();
}
+ if (database_type == DB_CORNER) {
+ fprintf(stderr, "---------------------------\n");
+
+ corner_pack_variations(corner_root.child, 0);
+ fprintf(output_FILE, "static struct corner_variation %s_variations[] =
{\n",
+ prefix);
+ corner_write_variations(corner_root.child, output_FILE);
+
+ fprintf(stderr, "corner database for %s\n", prefix);
+ fprintf(stderr, "size: %d kB for %d patterns (%d variations)\n",
+ CORNER_DB_SIZE(patno, total_variations), patno, total_variations);
+ fprintf(stderr, "---------------------------\n");
+ }
write_pattern_db(output_FILE);
Index: patterns/patterns.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.h,v
retrieving revision 1.46
diff -u -p -r1.46 patterns.h
--- patterns/patterns.h 31 Dec 2002 12:41:09 -0000 1.46
+++ patterns/patterns.h 2 Jan 2003 20:20:23 -0000
@@ -118,31 +118,32 @@ typedef int (*autohelper_fn_ptr)(int rot
* databases. The descriptions here mostly relate to patterns in
* patterns.db and other databases which are handled by shapes.c.
*/
-#define CLASS_O 0x0001 /* O stones must be alive or unknown */
-#define CLASS_o 0x0002 /* O stones must be dead or unknown */
-#define CLASS_X 0x0004 /* X stones must be alive or unknown */
-#define CLASS_x 0x0008 /* X stones must be dead or unknown */
-#define CLASS_s 0x0010 /* move is a sacrifice */
-#define CLASS_n 0x0020 /* X could also make this move if we do not */
-#define CLASS_D 0x0040 /* defense pattern */
-#define CLASS_C 0x0080 /* move connects two worms */
-#define CLASS_c 0x0100 /* move weakly connects two worms */
-#define CLASS_B 0x0200 /* move breaks connection between enemy worms */
-#define CLASS_A 0x0400 /* attack pattern */
-#define CLASS_b 0x0800 /* move is intended to block opponent */
-#define CLASS_e 0x1000 /* move is intended to expand territory */
-#define CLASS_E 0x2000 /* move is intended to expand moyo */
-#define CLASS_a 0x4000 /* strategical level attack */
-#define CLASS_d 0x8000 /* strategical level defense */
-#define CLASS_I 0x10000 /* invasions patterns (influence.db) */
-#define CLASS_J 0x20000 /* joseki standard move */
-#define CLASS_j 0x40000 /* joseki move, slightly less urgent */
-#define CLASS_t 0x80000 /* minor joseki move (tenuki OK) */
-#define CLASS_U 0x100000 /* very urgent joseki move */
-#define CLASS_T 0x200000 /* joseki trick move */
-#define CLASS_W 0x400000 /* worthwhile threat move */
-#define CLASS_F 0x800000 /* for joseki moves: a fuseki pattern */
-#define CLASS_Y 0x80000000 /* used for experimental patterns */
+#define CLASS_O 0x0001 /* O stones must be alive or unknown */
+#define CLASS_o 0x0002 /* O stones must be dead or unknown */
+#define CLASS_X 0x0004 /* X stones must be alive or unknown */
+#define CLASS_x 0x0008 /* X stones must be dead or unknown */
+#define CLASS_s 0x0010 /* move is a sacrifice */
+#define CLASS_n 0x0020 /* X could also make this move if we do not */
+#define CLASS_D 0x0040 /* defense pattern */
+#define CLASS_C 0x0080 /* move connects two worms */
+#define CLASS_c 0x0100 /* move weakly connects two worms */
+#define CLASS_B 0x0200 /* move breaks connection between enemy worms */
+#define CLASS_A 0x0400 /* attack pattern */
+#define CLASS_b 0x0800 /* move is intended to block opponent */
+#define CLASS_e 0x1000 /* move is intended to expand territory */
+#define CLASS_E 0x2000 /* move is intended to expand moyo */
+#define CLASS_a 0x4000 /* strategical level attack */
+#define CLASS_d 0x8000 /* strategical level defense */
+#define CLASS_I 0x00010000 /* invasions patterns (influence.db) */
+#define CLASS_J 0x00020000 /* joseki standard move */
+#define CLASS_j 0x00040000 /* joseki move, slightly less urgent */
+#define CLASS_t 0x00080000 /* minor joseki move (tenuki OK) */
+#define CLASS_U 0x00100000 /* very urgent joseki move */
+#define CLASS_T 0x00200000 /* joseki trick move */
+#define CLASS_W 0x00400000 /* worthwhile threat move */
+#define CLASS_F 0x00800000 /* for joseki moves: a fuseki pattern */
+#define CLASS_N 0x01000000 /* antisuji move (do _not_ play) */
+#define CLASS_Y 0x80000000 /* used for experimental patterns */
/* Collection of the classes inducing move reasons. */
#define CLASS_MOVE_REASONS (CLASS_C | CLASS_B | CLASS_b | \
@@ -377,16 +378,20 @@ struct corner_variation;
struct corner_pattern;
struct corner_db {
- int num_top_variations;
- struct corner_variation *variations;
+ int max_width;
+ int max_height;
+
+ char num_top_variations;
+ struct corner_variation *top_variations;
};
struct corner_variation {
- int att;
int move_offset;
+ char xor_att;
+ char num_stones;
- int num_variations;
- struct corner_variation *subvariations;
+ char num_variations;
+ struct corner_variation *variations;
struct corner_pattern *pattern;
};
@@ -402,6 +407,19 @@ struct corner_pattern {
int autohelper_flag;
autohelper_fn_ptr autohelper;
float constraint_cost;
+};
+
+struct corner_variation_b {
+ int move_offset;
+ char xor_att;
+ char num_stones;
+
+ char num_variations;
+ struct corner_variation_b *next;
+ struct corner_variation_b *child;
+ int child_num;
+
+ int pattern_num;
};
- [gnugo-devel] more joseki preparations,
Paul Pogonyshev <=