[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] corner matcher
|
From: |
Paul Pogonyshev |
|
Subject: |
[gnugo-devel] corner matcher |
|
Date: |
Mon, 6 Jan 2003 19:46:13 +0200 |
now the matcher itself is mostly completed and seems to work
properly (it turned out that i still have some time to spare :).
it is still not connected to the engine, mainly because i
haven't started investigating shapes_callback yet.
attached are two patches. the first fixes the matcher, slightly
improves database generation (it is now 117k) and adds some
comments (still quite intricate). the second is a quick hack i
used to test the matcher and is certainly not for cvs. you may
want to use it to see how it works.
the second patch adds two gtp commands, `match' and `match_c'
to search for joseki patterns with standard and corner matchers
correspondingly. enter them without parameters to see which
patterns match (the order for in which they are matched almost
always differ for the two matchers). enter `match[_c] num' to
run a matcher `num' times for both black and white player. i
used this in performance measurement.
the new matcher is about 60 times faster on a typical board
after 20 moves. however, taking into account that the standard
matcher is completely not optimized for joseki patterns, that
must not look very astonishing. unless we write a joseki
reader, this will hardly be noticeable, since pattern matching
doesn't take much time (except for dfa matching which is
simply done very often).
you may use this "script" for checking matchers' timings on
several different boards at once (run from gnugo/):
find regression/games/nngs/[m-z]*.sgf | xargs -igame echo \
'time -p echo match 5000 | interface/gnugo --mode gtp --quiet' \
'-l game -L 20' | sh
replace `match' with `match_c' to use the new matcher. note that
gnugo initialization does take some time, so for the new matcher
5000 is too small to achieve a reliable speed estimation.
comments and evaluations are welcome.
Paul
Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.50
diff -u -p -r1.50 matchpat.c
--- engine/matchpat.c 3 Jan 2003 18:23:42 -0000 1.50
+++ engine/matchpat.c 6 Jan 2003 17:32:24 -0000
@@ -1261,16 +1261,32 @@ 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 const int corner_x[8] = {0, 0, 1, 1, 1, 1, 0, 0};
+static const int corner_y[8] = {0, 1, 1, 0, 1, 0, 0, 1};
+/* The number of stones in "corner area" for each board position. For example,
+ * corner area for position E3 when anchoring at A1 corner, looks like this:
+ *
+ * |........ In general, num_stones[pos] is the number of stones
+ * |........ which are closer to the corner (stone at pos, if any,
+ * 3 |#####... counts too) than pos. Note, that say G2 is not closer
+ * |#####... to the corner than E3, the reverse isn't true either.
+ * 1 |#####... Their distances are "incomparable" since E < G but
+ * +-------- 3 > 2.
+ * A E
+ */
static int num_stones[BOARDMAX];
+/* Recursively performs corner matching. This function checks whether
+ * `num_variation' variations pointed by `variation' parameter match.
+ * If any of them do, it calls itself recursively. If any pattern
+ * corresponding to those variations matches, it notifies callback
+ * function.
+ */
static void
do_corner_matchpat(int num_variations, struct corner_variation *variation,
int match_color, corner_matchpat_callback_fn_ptr callback,
@@ -1286,6 +1302,7 @@ do_corner_matchpat(int num_variations, s
= AFFINE_TRANSFORM(pattern->second_corner_offset, trans, anchor);
if (num_stones[second_corner] == stones) {
+ /* We have found a matching pattern. */
ASSERT1(board[move] == EMPTY, move);
callback(move, callback_color, pattern, trans);
@@ -1295,6 +1312,7 @@ do_corner_matchpat(int num_variations, s
if (variation->num_variations
&& num_stones[move] == variation->num_stones
&& board[move] == color_check) {
+ /* A matching variation. */
do_corner_matchpat(variation->num_variations, variation->variations,
match_color, callback, callback_color,
trans, anchor, stones + 1);
@@ -1303,6 +1321,10 @@ do_corner_matchpat(int num_variations, s
}
+/* Perform corner matching at all four corners and both possible
+ * transformations at each corner. `callback' is notified if any
+ * matching pattern is found.
+ */
void
corner_matchpat(corner_matchpat_callback_fn_ptr callback, int color,
struct corner_db *database)
@@ -1319,12 +1341,15 @@ corner_matchpat(corner_matchpat_callback
int pos;
struct corner_variation *variation = database->top_variations;
+ /* Fill in the num_stones[] array. We use `max_width' and `max_height'
+ * fields of database structure to stop working as early as possible.
+ */
num_stones[anchor] = IS_STONE(board[anchor]);
pos = anchor;
for (i = 1; i < database->max_height; i++) {
pos += dx;
- if (!ON_BOARD1(pos)) {
+ if (!ON_BOARD(pos)) {
do {
num_stones[pos] = BOARDMAX;
pos += dx;
@@ -1339,7 +1364,7 @@ corner_matchpat(corner_matchpat_callback
pos = anchor;
for (j = 1; j < database->max_width; j++) {
pos += dy;
- if (!ON_BOARD1(pos)) {
+ if (!ON_BOARD(pos)) {
do {
num_stones[pos] = BOARDMAX;
pos += dy;
@@ -1360,6 +1385,9 @@ corner_matchpat(corner_matchpat_callback
}
}
+ /* Try to match top variations. If any of them matches, we call
+ * do_corner_matchpat() to recurse that variation's tree.
+ */
for (i = 0; i < database->num_top_variations; i++) {
int move = AFFINE_TRANSFORM(variation->move_offset, k, anchor);
@@ -1371,7 +1399,6 @@ corner_matchpat(corner_matchpat_callback
}
}
}
-#endif
/*
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.109
diff -u -p -r1.109 mkpat.c
--- patterns/mkpat.c 4 Jan 2003 15:13:03 -0000 1.109
+++ patterns/mkpat.c 6 Jan 2003 17:32:41 -0000
@@ -2155,6 +2155,7 @@ struct corner_element {
};
+/* Initialize corner variation tree. */
static void
corner_init(void)
{
@@ -2163,7 +2164,31 @@ corner_init(void)
}
-static int corner_best_element(struct corner_element *el, int n, int x, int y,
+/* corner_best_element() chooses the best element from supplied. The best
+ * element is always selected from those which don't have other elements
+ * closer to the corner
+ *
+ * +------ E.g. elements A and B are candidates to become the best
+ * |...... element, while C and D are not (A is closer to the corner
+ * |..A... than both C and D). Note that A and B are at "incomparable"
+ * |..C.D. distances from the corner, since their coordinates are in
+ * |.B.... opposite relations.
+ * |......
+ *
+ * If there are existing variations among candidates, all other candidates
+ * are automatically rejected. Once we have a set of candidates, we select
+ * the best candidate as the one which has the best parameters (in order
+ * of decreasing importance):
+ * 1) maximal "corner area" (see function code);
+ * 2) minimal distance to the corner bisector;
+ * 3) those which x coordinate is smaller than y one
+ *
+ * The purpose of this function is to reduce size of variation tree (by
+ * selecting similar variations) and allow rejecting variations as
+ * quickly as possible (based on num_stones field value). The latter
+ * can still be improved if a need arises.
+ */
+static int corner_best_element(struct corner_element *el, int n,
struct corner_variation_b *variations,
int color)
{
@@ -2177,6 +2202,7 @@ static int corner_best_element(struct co
int existing_variation[MAX_BOARD * MAX_BOARD];
int have_existing_variation = 0;
+ /* Find candidates and mark those which correspond to existing variations. */
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
if (i == k)
@@ -2207,10 +2233,10 @@ static int corner_best_element(struct co
}
}
+ /* Select the best move. */
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))
+ int value = 2 * MAX_BOARD * (el[m].x + 1) * (el[m].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
@@ -2224,6 +2250,7 @@ static int corner_best_element(struct co
}
+/* Dynamically allocates a new variation structure. */
static struct corner_variation_b*
corner_variation_new(int move_offset, char xor_att, char num_stones)
{
@@ -2246,6 +2273,9 @@ corner_variation_new(int move_offset, ch
}
+/* Follow a variation. If such a variation already exists, returns
+ * a pointer to it. Otherwise, creates and initializes a new one.
+ */
static struct corner_variation_b*
corner_follow_variation(struct corner_variation_b *variation,
int offset, int color, char num_stones)
@@ -2272,6 +2302,7 @@ corner_follow_variation(struct corner_va
}
+/* Adds a pattern to corner database. */
static void
corner_add_pattern(void)
{
@@ -2288,6 +2319,7 @@ corner_add_pattern(void)
char num_stones;
struct corner_variation_b *variation = &corner_root;
+ /* Check if we have a corner pattern and select appropriate transformation.
*/
switch (where) {
case SOUTH_EDGE | WEST_EDGE: trans = 5; corner_x = maxi; break;
case WEST_EDGE | NORTH_EDGE: trans = 0; break;
@@ -2306,6 +2338,7 @@ corner_add_pattern(void)
move_x = I(move_pos);
move_y = J(move_pos);
+ /* Find all pattern elements. */
for (k = 0; k < el; k++) {
if (elements[k].att == ATT_X || elements[k].att == ATT_O) {
TRANSFORM2(elements[k].x, elements[k].y,
@@ -2322,45 +2355,56 @@ corner_add_pattern(void)
}
}
+ /* Follow variations. */
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);
+ best = k + corner_best_element(stone + k, stones - k, 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);
+ best = corner_best_element(stone, stones, 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) {
+ /* To reduce number of variations, swap coordinates of all elements
+ * unless there is one with mirrored coordinates already.
+ */
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;
+ for (i = 1; i < k; i++) {
+ if (stone[i].x == stone[0].y && stone[i].y == stone[0].x)
+ break;
+ }
+
+ if (i == k) {
+ 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;
+ num_stones = 1;
for (i = 0; i < k; i++) {
if (stone[i].x <= stone[k].x && stone[i].y <= stone[k].y)
num_stones++;
@@ -2371,7 +2415,8 @@ corner_add_pattern(void)
num_stones);
}
- num_stones = 0;
+ /* Finally, follow the pattern move as a variation. */
+ num_stones = 1;
for (k = 0; k < stones; k++) {
if (stone[k].x <= move_x && stone[k].y <= move_y)
num_stones++;
@@ -2396,6 +2441,9 @@ corner_add_pattern(void)
}
+/* Enumerates all variations so that we know addresses of subvariations
+ * when it is time to write them into a .c file.
+ */
static int
corner_pack_variations(struct corner_variation_b *variation, int counter)
{
@@ -2411,6 +2459,7 @@ corner_pack_variations(struct corner_var
}
+/* Write variations recursively into an array. */
static void
corner_write_variations(struct corner_variation_b *variation, FILE *outfile)
{
@@ -2578,8 +2627,8 @@ write_pattern_db(FILE *outfile)
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_max_width + 1);
+ fprintf(outfile, " %d,\n", corner_max_height + 1);
fprintf(outfile, " %d,\n", corner_root.num_variations);
fprintf(outfile, " %s_variations\n", prefix);
fprintf(outfile, "};\n");
--------------- second patch ---------------------------------------
Index: patterns/patterns.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.h,v
retrieving revision 1.48
diff -u -p -r1.48 patterns.h
--- patterns/patterns.h 3 Jan 2003 18:23:42 -0000 1.48
+++ patterns/patterns.h 6 Jan 2003 17:35:17 -0000
@@ -322,6 +322,7 @@ void init_tree_oracle(void);
/* pattern arrays themselves */
extern struct pattern_db pat_db;
extern struct pattern_db joseki_db;
+extern struct corner_db joseki_c_db;
extern struct pattern_db aa_attackpat_db;
extern struct pattern_db owl_attackpat_db;
extern struct pattern_db owl_vital_apat_db;
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.111
diff -u -p -r1.111 play_gtp.c
--- interface/play_gtp.c 3 Jan 2003 15:26:52 -0000 1.111
+++ interface/play_gtp.c 6 Jan 2003 17:35:27 -0000
@@ -31,6 +31,7 @@
#include "liberty.h"
#include "gtp.h"
#include "gg_utils.h"
+#include "../patterns/patterns.h"
/* Internal state that's not part of the engine. */
static int handicap = 0;
@@ -107,6 +108,8 @@ DECLARE(gtp_draw_search_area);
DECLARE(gtp_list_commands);
DECLARE(gtp_list_stones);
DECLARE(gtp_loadsgf);
+DECLARE(gtp_match);
+DECLARE(gtp_match_c);
DECLARE(gtp_name);
DECLARE(gtp_estimate_score);
DECLARE(gtp_experimental_score);
@@ -234,6 +237,8 @@ static struct gtp_command commands[] = {
{"list_commands", gtp_list_commands},
{"list_stones", gtp_list_stones},
{"loadsgf", gtp_loadsgf},
+ {"match", gtp_match},
+ {"match_c", gtp_match_c},
{"name", gtp_name},
{"new_score", gtp_estimate_score},
{"owl_analyze_semeai", gtp_owl_analyze_semeai},
@@ -378,6 +383,75 @@ gtp_program_version(char *s)
{
UNUSED(s);
return gtp_success(VERSION);
+}
+
+
+static void
+m_dummy_callback(int anchor, int color, struct pattern *patt, int rotation,
+ void *data)
+{
+ UNUSED(anchor); UNUSED(color); UNUSED(patt); UNUSED(rotation); UNUSED(data);
+}
+
+static void
+m_callback(int anchor, int color, struct pattern *patt, int rotation,
+ void *data)
+{
+ UNUSED(data);
+ gprintf("Pattern %s matched at %1m for %C\n", patt->name,
+ AFFINE_TRANSFORM(patt->move_offset, rotation, anchor), color);
+}
+
+static int
+gtp_match(char *s)
+{
+ int k;
+ int t;
+
+ if (sscanf(s, "%d", &t) == 1)
+ for(k = 0; k < t; k++){
+ matchpat(m_dummy_callback, BLACK, &joseki_db, NULL, NULL);
+ matchpat(m_dummy_callback, WHITE, &joseki_db, NULL, NULL);
+ }
+ else {
+ matchpat(m_callback, BLACK, &joseki_db, NULL, NULL);
+ matchpat(m_callback, WHITE, &joseki_db, NULL, NULL);
+ }
+
+ return gtp_success("");
+}
+
+
+static void
+mc_dummy_callback(int move, int color, struct corner_pattern *patt, int
rotation)
+{
+ UNUSED(move); UNUSED(color); UNUSED(patt); UNUSED(rotation);
+}
+
+static void
+mc_callback(int move, int color, struct corner_pattern *patt, int rotation)
+{
+ UNUSED(rotation);
+ gprintf("Pattern %s matched at %1m for %C\n", patt->name, move, color);
+}
+
+static int
+gtp_match_c(char *s)
+{
+ int k;
+ int t;
+
+ if (sscanf(s, "%d", &t) == 1)
+ for(k = 0; k < t; k++){
+ corner_matchpat(mc_dummy_callback, BLACK, &joseki_c_db);
+ corner_matchpat(mc_dummy_callback, WHITE, &joseki_c_db);
+ }
+ else {
+ corner_matchpat(mc_callback, BLACK, &joseki_c_db);
+ corner_matchpat(mc_callback, WHITE, &joseki_c_db);
+ }
+
+ return gtp_success("");
}
---------- and this to build corner database -------------------------
--- patterns/Makefile Mon Jan 6 19:44:17 2003
+++ patterns/Makefile Mon Jan 6 14:58:49 2003
@@ -503,6 +503,7 @@
josekidb.c : $(DBBUILT) mkpat$(EXEEXT)
cat $(DBBUILT) | ./mkpat -b joseki >josekidb.c
+ cat $(DBBUILT) | ./mkpat -C joseki_c >>josekidb.c
apatterns.c : $(srcdir)/attack.db mkpat$(EXEEXT)
cat $(srcdir)/attack.db | ./mkpat -X attpat >apatterns.c
- [gnugo-devel] corner matcher,
Paul Pogonyshev <=