[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] optics: minor bugfix and minor improvements
|
From: |
Paul Pogonyshev |
|
Subject: |
[gnugo-devel] optics: minor bugfix and minor improvements |
|
Date: |
Fri, 29 Nov 2002 01:12:13 +0200 |
here is a nasty bug (optics.c):
/* This macro is not fully generalized. It works because it is used only where
* c, d match the first vital attack/defend point of the the half eye or none
* at all.
*/
#define hadj(heye, apos, bpos) \
(heye[apos].type == HALF_EYE \
>>> && (heye[apos].attack_point[0] == (bpos) \
>>> || (heye[apos].defense_point[0] == (bpos))))
this can eventually match a wrong half eye (if i.e. two neighboring half eyes
have a common attack point). i had very hard time trying to figure out why
the number of calls to most functions changed between patched and non-patched
version. finally, when i had tried almost everything else (and found a typo
in the patch ;) i discovered the thing shown above. i did check that it was
really the cause: placed the very same logic in my patch and it started
giving exactly the same results as non-patched version (in terms of function
calls). who said gprof couldn't be used as a debugger ;) ?
actually, the bugfix hasn't caused any regression changes, but it has some
influence on the engine (some variations must go another way since number of
calls to functions has changed).
- eye_vertex and eye_graph structures reorganized
- mkeyes.c rewritten to conform the changes in eyes.h
- adjacent() and buggy hadj() macros in optics.c retired
- recognize_eye(), first_map() and next_map() simplified and sped up
- new static reset_map() in optics.c
all the stuff above brings the following:
* one bug tracked down in optics.c, the code looks somewhat cleaner to me now
* around 60k decrease in executable size
* slight performance improvement (i just couldn't stop ^^ and made changes to
first_map() and next_map() though they take _very_ little of total runtime):
BEFORE
...
0.49 588.64 3.28 185678 0.02 0.03 recognize_eye
...
0.08 655.90 0.57 8115520 0.00 0.00 next_map
...
0.03 664.34 0.17 2495304 0.00 0.00 first_map
...
-----------------------------------------------
3.28 2.89 185678/185678 read_eye [146]
[149] 0.9 3.28 2.89 185678 recognize_eye [149]
0.00 2.10 34338/667409 safe_move [64]
0.57 0.00 8115520/8115520 next_map [272]
0.17 0.00 2495304/2495304 first_map [336]
0.04 0.00 581137/1560651 is_halfeye [378]
0.01 0.00 151729/332905 eye_move_urgency [478]
...
AFTER
...
0.38 600.17 2.52 185760 0.01 0.03 recognize_eye
...
0.07 652.44 0.48 8136365 0.00 0.00 next_map
...
0.01 663.61 0.06 2342556 0.00 0.00 first_map
...
0.00 665.18 0.03 732837 0.00 0.00 reset_map
...
-----------------------------------------------
2.52 2.67 185760/185760 read_eye [149]
[152] 0.8 2.52 2.67 185760 recognize_eye [152]
0.00 2.06 34362/667663 safe_move [64]
0.48 0.00 8136365/8136365 next_map [283]
0.06 0.00 2342556/2342556 first_map [411]
0.03 0.00 732837/732837 reset_map [477]
0.02 0.00 581604/1562113 is_halfeye [412]
0.02 0.00 151763/333022 eye_move_urgency [446]
Paul
Index: patterns/eyes.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/eyes.h,v
retrieving revision 1.7
diff -u -p -r1.7 eyes.h
--- patterns/eyes.h 16 Sep 2002 07:27:49 -0000 1.7
+++ patterns/eyes.h 28 Nov 2002 22:06:21 -0000
@@ -21,25 +21,27 @@
#include "liberty.h"
+
+#define CAN_BE_EMPTY 1
+#define CAN_CONTAIN_STONE 2
+#define EYE_DEFENSE_POINT 4
+#define EYE_ATTACK_POINT 8
+
/*
- * The vertices of each eye is defined by an array of struct eye_vertex.
+ * The vertices of each eye are defined by an array of struct eye_vertex.
*/
struct eye_vertex {
- int i; /* coordinates of the vertex */
- int j;
- char type; /* . x or X */
-
- int neighbors; /* number of neighbors */
- int n1; /* first neighbor (position in array) */
- int n2; /* second neighbor */
- int n3; /* third neighbor */
- int n4; /* fourth neighbor */
- int edge; /* 0=center, 1=edge, 2=corner */
+ char marginal; /* 1 if marginal vertex, 0 otherwise */
+ char edge; /* 0 = center, 1 = edge, 2 = corner */
/* A corner vertex may only be matched at the corner.
* An edge vertex may be matched at the corner or on the edge.
* A center vertex may be matched anywhere.
*/
+ char flags; /* see the #defines above */
+
+ char neighbors; /* number of neighbors */
+ int n[4]; /* position in array of vertex neighors */
};
@@ -50,7 +52,7 @@ struct eye_vertex {
struct eye_graph {
struct eye_vertex *vertex;
- const char *patname; /* Name of pattern */
+ int patnum; /* Number of pattern */
int esize; /* number of vertices */
int msize; /* number of marginal vertices */
int ends; /* number of vertices with one neighbor */
Index: patterns/mkeyes.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkeyes.c,v
retrieving revision 1.10
diff -u -p -r1.10 mkeyes.c
--- patterns/mkeyes.c 16 Sep 2002 07:27:49 -0000 1.10
+++ patterns/mkeyes.c 28 Nov 2002 22:06:25 -0000
@@ -36,6 +36,8 @@
#include <ctype.h>
#include <assert.h>
+#include "eyes.h"
+
#define DEBUG(x) /* printf x */
@@ -49,10 +51,11 @@ main(void)
int patno = 0;
int p;
char vertex[MAXDIMEN][MAXDIMEN];
- int marginal[MAXDIMEN][MAXDIMEN];
- int edge[MAXDIMEN][MAXDIMEN];
+ char marginal[MAXDIMEN][MAXDIMEN];
+ char edge[MAXDIMEN][MAXDIMEN];
+ char flags[MAXDIMEN][MAXDIMEN];
int neighbors[MAXSIZE];
- int i, k, l, h;
+ int k, l, h;
int m = 0, n = 0;
int vi[MAXSIZE];
int vj[MAXSIZE];
@@ -70,13 +73,11 @@ main(void)
int num_defenses = 0;
int debug = 0;
- printf("\
-/* This file is automatically generated by mkeyes. Do not\n\
- * edit it directly. Instead, edit the eye shape database.\n\
- */\n\n\
-\
-#include <stdio.h> /* for NULL */\n\
-#include \"eyes.h\"\n\n");
+ printf("/* This file is automatically generated by mkeyes. Do not\n");
+ printf(" * edit it directly. Instead, edit the eye shape database.\n");
+ printf(" */\n\n");
+ printf("#include <stdio.h> /* for NULL */\n");
+ printf("#include \"eyes.h\"\n\n");
memset(ends, 0, sizeof(ends));
memset(two_neighbors, 0, sizeof(two_neighbors));
@@ -84,18 +85,17 @@ main(void)
memset(esize, 0, sizeof(esize));
while (fgets(line, MAXLINE, stdin) && !fatal_errors) {
+ int last = strlen(line) - 1;
- if (line[strlen(line)-1] != '\n') {
+ if (line[last] != '\n') {
fprintf(stderr, "mkeyes: line truncated: %s\n", line);
return 1;
}
/* remove trailing whitespace */
- i = strlen(line)-2; /* start removing backwards just before newline
*/
- while (i >= 0 && (line[i] == ' ' || line[i] == '\t' || line[i] == '\r'))
{
- line[i] = '\n';
- line[i+1] = '\0';
- i--;
+ for (last--; last >= 0 && isspace(line[last]); last--) {
+ line[last] = '\n';
+ line[last+1] = '\0';
}
/* New pattern. */
@@ -108,9 +108,12 @@ main(void)
}
if (debug)
fprintf(stderr, "parsing pattern %d\n", eye_number[patno]);
+
memset(vertex, 0, sizeof(vertex));
memset(marginal, 0, sizeof(marginal));
memset(edge, 0, sizeof(edge));
+ memset(flags, 0, sizeof(flags));
+
m = 0;
esize[patno] = 0;
msize[patno] = 0;
@@ -158,16 +161,19 @@ main(void)
{
case '.':
marginal[m][n] = 0;
+ flags[m][n] = CAN_BE_EMPTY;
break;
case '!':
msize[patno]++;
marginal[m][n] = 1;
+ flags[m][n] = CAN_BE_EMPTY;
break;
case '@':
msize[patno]++;
marginal[m][n] = 1;
+ flags[m][n] = CAN_BE_EMPTY | EYE_DEFENSE_POINT | EYE_ATTACK_POINT;
num_attacks++;
num_defenses++;
break;
@@ -175,42 +181,50 @@ main(void)
case '$':
msize[patno]++;
marginal[m][n] = 1;
+ flags[m][n] = CAN_CONTAIN_STONE;
break;
case '(':
msize[patno]++;
marginal[m][n] = 1;
+ flags[m][n] = CAN_BE_EMPTY | EYE_ATTACK_POINT;
num_attacks++;
break;
case ')':
msize[patno]++;
marginal[m][n] = 1;
+ flags[m][n] = CAN_BE_EMPTY | EYE_DEFENSE_POINT;
num_defenses++;
break;
case 'x':
marginal[m][n] = 0;
+ flags[m][n] = CAN_BE_EMPTY | CAN_CONTAIN_STONE;
break;
case '*':
marginal[m][n] = 0;
+ flags[m][n] = CAN_BE_EMPTY | EYE_ATTACK_POINT | EYE_DEFENSE_POINT;
num_attacks++;
num_defenses++;
break;
case '<':
marginal[m][n] = 0;
+ flags[m][n] = CAN_BE_EMPTY | EYE_ATTACK_POINT;
num_attacks++;
break;
case '>':
marginal[m][n] = 0;
+ flags[m][n] = CAN_BE_EMPTY | EYE_DEFENSE_POINT;
num_defenses++;
break;
case 'X':
marginal[m][n] = 0;
+ flags[m][n] = CAN_CONTAIN_STONE;
break;
default:
@@ -253,13 +267,15 @@ main(void)
}
printf("static struct eye_vertex eye%d[] = {\n", eye_number[patno]);
+
for (l = 0; l < esize[patno]; l++) {
-
int ni[4];
int nj[4];
int nb[4];
int mx[MAXDIMEN][MAXDIMEN];
int count = 0;
+ int i = vi[l];
+ int j = vj[l];
memset(mx, -1, sizeof(mx));
@@ -271,36 +287,36 @@ main(void)
nb[h] = -1;
}
- mx[vi[l]][vj[l]] = 0;
+ mx[i][j] = 0;
- if (vi[l] > 0 && vertex[vi[l]-1][vj[l]]) {
- ni[neighbors[l]] = vi[l]-1;
- nj[neighbors[l]] = vj[l];
+ if (i > 0 && vertex[i-1][j]) {
+ ni[neighbors[l]] = i-1;
+ nj[neighbors[l]] = j;
neighbors[l]++;
count++;
- mx[vi[l]-1][vj[l]] = l;
+ mx[i-1][j] = l;
}
- if (vi[l] < MAXDIMEN-1 && vertex[vi[l]+1][vj[l]]) {
- ni[neighbors[l]] = vi[l]+1;
- nj[neighbors[l]] = vj[l];
+ if (i < MAXDIMEN-1 && vertex[i+1][j]) {
+ ni[neighbors[l]] = i+1;
+ nj[neighbors[l]] = j;
neighbors[l]++;
count++;
- mx[vi[l]+1][vj[l]] = l;
+ mx[i+1][j] = l;
}
- if (vj[l] > 0 && vertex[vi[l]][vj[l]-1]) {
- ni[neighbors[l]] = vi[l];
- nj[neighbors[l]] = vj[l]-1;
+ if (j > 0 && vertex[i][j-1]) {
+ ni[neighbors[l]] = i;
+ nj[neighbors[l]] = j-1;
neighbors[l]++;
- mx[vi[l]][vj[l]-1] = l;
+ mx[i][j-1] = l;
}
- if (vi[l] < MAXDIMEN-1 && vertex[vi[l]][vj[l]+1]) {
- ni[neighbors[l]] = vi[l];
- nj[neighbors[l]] = vj[l]+1;
+ if (j < MAXDIMEN-1 && vertex[i][j+1]) {
+ ni[neighbors[l]] = i;
+ nj[neighbors[l]] = j+1;
neighbors[l]++;
- mx[vi[l]][vj[l]+1] = l;
+ mx[i][j+1] = l;
}
@@ -319,10 +335,9 @@ main(void)
}
- printf(" {%d, %d, \'%c\', %d, %d, %d, %d, %d, %d}",
- vi[l], vj[l], vertex[vi[l]][vj[l]],
- neighbors[l], nb[0], nb[1], nb[2], nb[3],
- edge[vi[l]][vj[l]]);
+ printf(" {%d, %d, %2d, %d, {%2d, %2d, %2d, %2d}}",
+ marginal[i][j], edge[i][j], flags[i][j],
+ neighbors[l], nb[0], nb[1], nb[2], nb[3]);
if (l < esize[patno]-1)
printf(",\n");
@@ -343,14 +358,14 @@ main(void)
printf("\nstruct eye_graph graphs[] = {\n");
for (l = 0; l < patno; l++) {
- printf(" {eye%d, \"%d\", %d, %d, %d, %d, %d, {%d, %d, %d, %d}}",
+ printf(" {eye%d, %d, %d, %d, %d, %d, %d, {%d, %d, %d, %d}}",
eye_number[l], eye_number[l], esize[l], msize[l], ends[l],
two_neighbors[l], three_neighbors[l],
value_a[l], value_b[l], value_c[l], value_d[l]);
if (l < patno-1)
printf(",\n");
else
- printf(",\n{NULL, 0, 0, 0, 0, 0, 0, {0, 0, 0, 0}}\n};\n");
+ printf(",\n {NULL, 0, 0, 0, 0, 0, 0, {0, 0, 0, 0}}\n};\n");
}
if (fatal_errors) {
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.60
diff -u -p -r1.60 optics.c
--- engine/optics.c 15 Nov 2002 15:12:45 -0000 1.60
+++ engine/optics.c 28 Nov 2002 22:06:54 -0000
@@ -29,28 +29,6 @@
#include "gg_utils.h"
-/* This macro is not fully generalized. It works because it is used only
where
- * c, d match the first vital attack/defend point of the the half eye or none
- * at all.
- */
-#define hadj(heye, apos, bpos) \
- (heye[apos].type == HALF_EYE \
- && (heye[apos].attack_point[0] == (bpos) \
- || (heye[apos].defense_point[0] == (bpos))))
-
-/*
- * Two eye points are defined to be adjacent if they are either
- * next to each other or if one vertex is a half eye and the
- * other one is the point making it a real eye.
- */
-
-#define adjacent(heye, apos, bpos) ( (apos) == SOUTH(bpos) \
- || (apos) == WEST(bpos) \
- || (apos) == NORTH(bpos) \
- || (apos) == EAST(bpos) \
- || hadj(heye, apos, bpos) \
- || hadj(heye, bpos, apos))
-
#define MAXEYE 20
@@ -64,6 +42,7 @@ struct vital_points {
int num_defenses;
};
+
static void
compute_primary_domains(int color, int domain[BOARDMAX],
int lively[BOARDMAX],
@@ -84,12 +63,13 @@ static int recognize_eye(int pos, int *a
struct eyevalue *value,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
- int color, struct vital_points *vp);
+ struct vital_points *vp);
static void guess_eye_space(int pos, int effective_eyesize, int margins,
struct eye_data eye[BOARDMAX],
struct eyevalue *value, char *pessimistic_min);
-static void first_map(int q, int map[MAXEYE]);
-static int next_map(int *q, int map[MAXEYE], int esize);
+static void reset_map(int size);
+static void first_map(int* map_value);
+static int next_map(int *q, int map[MAXEYE]);
static void print_eye(struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX], int pos);
static float
@@ -102,6 +82,10 @@ evaluate_diagonal_intersection(int m, in
static int black_domain[BOARDMAX];
static int white_domain[BOARDMAX];
+/* Used internally by mapping functions. */
+static int map_size;
+static char used_index[MAXEYE];
+
/*
* Clear a struct eye_data.
@@ -1045,7 +1029,7 @@ read_eye(int pos, int *attack_point, int
struct vital_points *best_vp = &vp;
eye_color = recognize_eye(pos, attack_point, defense_point, value,
- eye, heye, color, &vp);
+ eye, heye, &vp);
if (!eye_color)
return 0;
@@ -1065,7 +1049,7 @@ read_eye(int pos, int *attack_point, int
heye[ko_halfeye].type = 0;
result = recognize_eye(pos, &apos, &dpos, &ko_value, eye,
- heye, color, &ko_vp);
+ heye, &ko_vp);
heye[ko_halfeye].type = HALF_EYE;
if (result && max_eyes(value) < max_eyes(&ko_value)) {
@@ -1107,20 +1091,16 @@ recognize_eye(int pos, int *attack_point
struct eyevalue *value,
struct eye_data eye[BOARDMAX],
struct half_eye_data heye[BOARDMAX],
- int color, struct vital_points *vp)
+ struct vital_points *vp)
{
int m, n;
- int k;
+ int eye_color;
int eye_size = 0;
- int vpos[MAXEYE], marginal[MAXEYE], neighbors[MAXEYE];
- int edge[MAXEYE];
+ int num_marginals = 0;
+ int vpos[MAXEYE];
+ char marginal[MAXEYE], edge[MAXEYE], neighbors[MAXEYE];
int graph;
- int q;
int map[MAXEYE];
- int ok, contin;
- int eye_color;
- int kpos;
- int num_marginals = 0;
gg_assert(attack_point != NULL);
gg_assert(defense_point != NULL);
@@ -1132,7 +1112,6 @@ recognize_eye(int pos, int *attack_point
if (eye_color == WHITE_BORDER)
eye_color = WHITE;
-
if (eye[pos].esize-eye[pos].msize > 7)
return 0;
@@ -1163,26 +1142,22 @@ recognize_eye(int pos, int *attack_point
if (n == 0 || n == board_size-1)
edge[eye_size]++;
- eye_size++;
if (is_halfeye(heye, pos2)) {
-
- /* Use one of the diagonals as a marginal for mapping purposes.
- * The whole set of diagonals is isomorphic to a marginal.
- * Note that the half eye preceedes the diagonal in the list.
+ neighbors[eye_size]++; /* Increase neighbors of half eye. */
+ eye_size++;
+ /* Use a virtual marginal vertex for mapping purposes. We set it
+ * to be at NO_MOVE so it won't be accidentially count as a
+ * neighbor for another vertex. Note that the half eye preceedes
+ * the virtual marginal vertex in the list.
*/
- neighbors[eye_size-1]++; /* increase neighbors of half eye */
- if (eye_color == color)
- kpos = heye[pos2].defense_point[0];
- else
- kpos = heye[pos2].attack_point[0];
- ASSERT_ON_BOARD1(kpos);
- vpos[eye_size] = kpos;
+ vpos[eye_size] = NO_MOVE;
marginal[eye_size] = 1;
- edge[eye_size] = 0;
num_marginals++;
+ edge[eye_size] = 0;
neighbors[eye_size] = 1;
- eye_size++;
}
+
+ eye_size++;
}
}
@@ -1192,86 +1167,70 @@ recognize_eye(int pos, int *attack_point
*/
for (graph = 0; graphs[graph].vertex != NULL; graph++) {
+ int q;
+
if (graphs[graph].esize != eye_size
|| graphs[graph].msize != num_marginals)
continue;
-
+ reset_map(eye_size);
q = 0;
- first_map(q, map);
+ first_map(&map[0]);
- contin = 1;
- while (contin && q >= 0 && q < eye_size) {
- ok = 1;
+ while (1) {
+ struct eye_vertex *gv = &graphs[graph].vertex[q];
+ int mv = map[q];
+ int ok = 1;
if (0)
TRACE("q=%d: %d %d %d %d %d %d\n",
q, map[0], map[1], map[2], map[3], map[4], map[5]);
- if (neighbors[map[q]] != graphs[graph].vertex[q].neighbors)
+ if (neighbors[mv] != gv->neighbors
+ || marginal[mv] != gv->marginal
+ || edge[mv] < gv->edge)
ok = 0;
- if (ok && marginal[map[q]]
- && graphs[graph].vertex[q].type != '!'
- && graphs[graph].vertex[q].type != '@'
- && graphs[graph].vertex[q].type != '$'
- && graphs[graph].vertex[q].type != ')'
- && graphs[graph].vertex[q].type != '(')
- ok = 0;
-
- if (ok && !marginal[map[q]]
- && (graphs[graph].vertex[q].type == '!'
- || graphs[graph].vertex[q].type == '('
- || graphs[graph].vertex[q].type == ')'
- || graphs[graph].vertex[q].type == '@'
- || graphs[graph].vertex[q].type == '$'))
- ok = 0;
-
- if (ok && IS_STONE(board[vpos[map[q]]])
- && graphs[graph].vertex[q].type != 'X'
- && graphs[graph].vertex[q].type != 'x'
- && graphs[graph].vertex[q].type != '$')
- ok = 0;
-
- if (ok && board[vpos[map[q]]] == EMPTY
- && (graphs[graph].vertex[q].type == 'X'
- || graphs[graph].vertex[q].type == '$'))
- ok = 0;
-
- if (ok && edge[map[q]] < graphs[graph].vertex[q].edge)
- ok = 0;
-
- if (ok && graphs[graph].vertex[q].n1 < q
- && graphs[graph].vertex[q].n1 != -1)
- {
- if (!adjacent(heye, vpos[map[q]],
- vpos[map[graphs[graph].vertex[q].n1]]))
- ok = 0;
- }
- if (ok && graphs[graph].vertex[q].n2 < q
- && graphs[graph].vertex[q].n2 != -1)
- {
- if (!adjacent(heye, vpos[map[q]],
- vpos[map[graphs[graph].vertex[q].n2]]))
- ok = 0;
- }
- if (ok && graphs[graph].vertex[q].n3 < q
- && graphs[graph].vertex[q].n3 != -1)
- {
- if (!adjacent(heye, vpos[map[q]],
- vpos[map[graphs[graph].vertex[q].n3]]))
+ if (ok) {
+ if (IS_STONE(board[vpos[mv]])) {
+ if (!(gv->flags & CAN_CONTAIN_STONE))
ok = 0;
}
- if (ok && graphs[graph].vertex[q].n4 < q
- && graphs[graph].vertex[q].n4 != -1)
- {
- if (!adjacent(heye, vpos[map[q]],
- vpos[map[graphs[graph].vertex[q].n4]]))
- ok = 0;
+ /* Virtual half eye marginals also fall here since they are off
+ * board.
+ */
+ else if (!(gv->flags & CAN_BE_EMPTY))
+ ok = 0;
+ }
+
+ if (ok) {
+ int k;
+
+ for (k = 0; k < gv->neighbors; k++) {
+ if (gv->n[k] < q) {
+ int mn = map[gv->n[k]];
+
+ /* Two eye vertices are neighbours if they are adjacent on the
+ * board or one of them is a half eye and the other is its
+ * virtual marginal vertex (and follows it in vpos[] array).
+ */
+ if (vpos[mv] != SOUTH(vpos[mn])
+ && vpos[mv] != WEST(vpos[mn])
+ && vpos[mv] != NORTH(vpos[mn])
+ && vpos[mv] != EAST(vpos[mn])
+ && (mv != mn - 1 || heye[vpos[mv]].type != HALF_EYE)
+ && (mn != mv - 1 || heye[vpos[mn]].type != HALF_EYE)) {
+ ok = 0;
+ break;
+ }
+ }
}
+ }
if (!ok) {
- contin = next_map(&q, map, eye_size);
+ if (!next_map(&q, map))
+ break;
+
if (0)
gprintf(" q=%d, esize=%d: %d %d %d %d %d\n",
q, eye_size,
@@ -1279,55 +1238,54 @@ recognize_eye(int pos, int *attack_point
}
else {
q++;
- first_map(q, map);
+ if (q == eye_size)
+ break; /* A match! */
+
+ first_map(&map[q]);
}
}
- /* We have found a match! Now sort out the vital moves. */
if (q == eye_size) {
+ /* We have found a match! Now sort out the vital moves. */
*value = graphs[graph].value;
vp->num_attacks = 0;
vp->num_defenses = 0;
if (eye_move_urgency(value) > 0) {
/* Collect all attack and defense points in the pattern. */
- for (k = 0; k < graphs[graph].esize; k++) {
- if (graphs[graph].vertex[k].type == '*'
- || graphs[graph].vertex[k].type == '<')
- vp->attacks[vp->num_attacks++] = vpos[map[k]];
- else if (graphs[graph].vertex[k].type == '@'
- || graphs[graph].vertex[k].type == '(') {
- /* check for marginal matching half eye diagonal
- * If it is a half eye diagonal, the half eye preceeds
- * the diagonal in the list of vertices
+ int k;
+
+ for (k = 0; k < eye_size; k++) {
+ struct eye_vertex *ev = &graphs[graph].vertex[k];
+
+ if (ev->flags & EYE_ATTACK_POINT) {
+ /* Check for a marginal vertex matching a half eye virtual
+ * marginal. This is the case if a half eye preceeds the
+ * current vertex in the list.
*/
- if (map[k] > 0 && is_halfeye(heye, vpos[map[k]-1])) {
+ if (ev->marginal && map[k] > 0
+ && is_halfeye(heye, vpos[map[k] - 1])) {
/* Add all diagonals as vital. */
int ix;
- struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
+ struct half_eye_data *he = &heye[vpos[map[k] - 1]];
- for (ix = 0; ix < this_half_eye->num_attacks; ix++)
- vp->attacks[vp->num_attacks++] =
- this_half_eye->attack_point[ix];
+ for (ix = 0; ix < he->num_attacks; ix++)
+ vp->attacks[vp->num_attacks++] = he->attack_point[ix];
}
else
vp->attacks[vp->num_attacks++] = vpos[map[k]];
}
- if (graphs[graph].vertex[k].type == '*'
- || graphs[graph].vertex[k].type == '>')
- vp->defenses[vp->num_defenses++] = vpos[map[k]];
- else if (graphs[graph].vertex[k].type == '@'
- || graphs[graph].vertex[k].type == ')') {
- /* Check for marginal matching half eye diagonal. */
- if (map[k] > 0 && is_halfeye(heye, vpos[map[k]-1])) {
+ if (ev->flags & EYE_DEFENSE_POINT) {
+ /* Check for a half eye virtual marginal vertex. */
+ if (ev->marginal && map[k] > 0
+ && is_halfeye(heye, vpos[map[k] - 1])) {
/* Add all diagonals as vital. */
int ix;
- struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
-
- for (ix = 0; ix < this_half_eye->num_defends; ix++)
- vp->defenses[vp->num_defenses++]
- = this_half_eye->defense_point[ix];
+ struct half_eye_data *he = &heye[vpos[map[k] - 1]];
+
+ for (ix = 0; ix < he->num_defends; ix++)
+ vp->defenses[vp->num_defenses++] = he->defense_point[ix];
}
else
vp->defenses[vp->num_defenses++] = vpos[map[k]];
@@ -1350,10 +1308,10 @@ recognize_eye(int pos, int *attack_point
DEBUG(DEBUG_EYES, " vital points: %1m (attack) %1m (defense)\n",
*attack_point, *defense_point);
- DEBUG(DEBUG_EYES, " pattern matched: %s\n", graphs[graph].patname);
+ DEBUG(DEBUG_EYES, " pattern matched: %d\n", graphs[graph].patnum);
}
- TRACE("eye space at %1m of type %s\n", pos, graphs[graph].patname);
+ TRACE("eye space at %1m of type %d\n", pos, graphs[graph].patnum);
return eye_color;
}
@@ -1366,69 +1324,60 @@ recognize_eye(int pos, int *attack_point
/* a MAP is a map of the integers 0,1,2, ... ,q into
* 0,1, ... , esize-1 where q < esize. This determines a
* bijection of the first q+1 elements of the graph into the
- * eyespace. The function first_map finds the smallest valid
- * value of element q, assuming the previous elements are ok.
+ * eyespace. The following three functions work with maps.
*/
+/* Reset internal data structure used by first_map() and
+ * next_map() functions.
+ */
static void
-first_map(int q, int map[MAXEYE])
+reset_map(int size)
{
- int k;
- int r;
-
- for (k = 0; k <= q; k++) {
- for (r = 0; r < q; r++)
- if (map[r] == k)
- break;
-
- if (r == q) {
- map[q] = k;
- break;
- }
- }
-}
+ map_size = size;
+ memset(used_index, 0, size * sizeof(char));
+}
-/* a MAP is a map of the integers 0,1,2, ... ,q into
- * 0,1, ... , esize-1 where q < esize. This determines a
- * bijection of the first q+1 elements of the graph into the
- * eyespace. The function next_map produces the next map when
- * these are ordered lexicographically. If no next map can
- * be found, q is decremented, then we try again. If q==0
- * and no next map can be found, the function returns false.
+/* The function first_map finds the smallest valid
+ * value of a map element.
*/
-
-static int
-next_map(int *q, int map[MAXEYE], int esize)
+static void
+first_map(int* map_value)
{
- int mapok = 0;
- int r;
+ int k = 0;
- if (0)
- gprintf(" q=%d, esize=%d: %d %d %d %d %d\n",
- *q, esize, map[0], map[1], map[2], map[3], map[4]);
+ while (used_index[k])
+ k++;
- if (*q == 0 && map[*q] == esize - 1)
- return 0;
+ used_index[k] = 1;
+ *map_value = k;
+}
- map[*q]++;
- while (!mapok) {
- mapok = 1;
- for (r = 0; r < *q; r++) {
- if (map[r] == map[*q]) {
- map[*q]++;
- mapok = 0;
+
+/* The function next_map produces the next map in lexicographical
+ * order. If no next map can be found, q is decremented, then we
+ * try again. If the entire map is lexicographically last, the
+ * function returns false.
+ */
+static int
+next_map(int *q, int map[MAXEYE])
+{
+ int k;
+
+ do {
+ used_index[map[*q]] = 0;
+ for (k = map[*q]; ++k < map_size;) {
+ if (!used_index[k]) {
+ used_index[k] = 1;
+ map[*q] = k;
+ return 1;
}
}
- }
- if (map[*q] >= esize) {
- map[*q] = 0;
(*q)--;
- return next_map(q, map, esize);
- }
- else
- return 1;
+ } while (*q >= 0);
+
+ return 0;
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnugo-devel] optics: minor bugfix and minor improvements,
Paul Pogonyshev <=