[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] Optics improvement
From: |
Gunnar Farnebäck |
Subject: |
Re: [gnugo-devel] Optics improvement |
Date: |
Fri, 04 Feb 2005 07:21:20 +0100 |
User-agent: |
EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.2 (Yagi-Nishiguchi) APEL/10.3 Emacs/21.3 (sparc-sun-solaris2.9) MULE/5.0 (SAKAKI) |
I wrote:
> Appended is a revised patch which adds the revisions above,
> documentation, some major FIXMEs, and a relevant test.
Arend had already added Martin's patch, so here's a rediffed
incremental patch instead.
/Gunnar
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.97
diff -u -r1.97 optics.c
--- engine/optics.c 1 Feb 2005 09:59:30 -0000 1.97
+++ engine/optics.c 4 Feb 2005 06:16:18 -0000
@@ -1777,8 +1777,96 @@
J(pos) + deltaj[k], color,
&attack_point, &defense_point,
my_eye);
- if (val < 2.0 && board[diag] == OTHER_COLOR(color) && !is_edge_vertex(pos)
- && neighbor_of_string(pos, diag) && countstones(diag) >= 3) {
+
+ /*
+ * Eyespaces with cutting points are problematic. In this position
+ *
+ * .....XXXXX
+ * XXXXX.OO.X
+ * X.OOOO.O.X
+ * X.O.XXXO.X
+ * ----------
+ *
+ * the eyespace will be .XXX. which evaluates to two eyes (seki)
+ * unless countermeasures are taken.
+ *
+ * This can be worked around in the topological analysis by
+ * sometimes setting the diagonal value to 2.0 for vertices inside
+ * the eyespace which are occupied by opponent stones. More
+ * precisely all of the following conditions must hold:
+ *
+ * a) The value is not already 2.0.
+ * a) The (potential) eyepoint is empty.
+ * b) The diagonal is occupied by an opponent string,
+ * c) which is also adjacent to the (potential) eye and
+ * d) at least three stones long.
+ * e) The (potential) eye is not on the edge (to steer clear of all the
+ * hairy cases that are handled by eyes.db anyway).
+ * f) At least two own strings are adjacent to the (potential) eye.
+ * g) At least one of the own strings adjacent to the (potential) eye has
+ * only one liberty which is an eye space and not decided false, yet.
+ *
+ * With this revision the eyespace above becomes .XXXh or
+ * equivalently .XXX.! which is almost evaluated correctly, eye
+ * value 0122 instead of the correct 1122. Compared to the
+ * previous value 2222 it's a major improvement.
+ *
+ * FIXME: This approach has a number of shortcomings.
+ *
+ * 1. d) is kind of arbitrary and there may be exceptional
+ * cases.
+ *
+ * 2. This diagonal value modification should not apply to
+ * two diagonals of the same strings inside the eyespace.
+ * E.g. if we have a partial eyespace looking like
+ *
+ * .OOO.
+ * OO.OO
+ * OXXXO
+ *
+ * it doesn't make sense to mark the middle vertex as a
+ * false eye. Possibly this doesn't make any difference
+ * in practice but it's at the very least confusing.
+ *
+ * 3. Actually it doesn't make sense to mark vertices as
+ * false otherwise either due to these revisions (half
+ * eyes make good sense though) as can be seen if a
+ * stone is added to the initial diagram,
+ *
+ * .....XXXXX
+ * XXXXXXOO.X
+ * X.OOOO.O.X
+ * X.O.XXXO.X
+ * ----------
+ *
+ * Now the eyespace instead becomes .XXX! which has the
+ * eye value 0011 but if X tries to attack the eye O
+ * suddenly gets two solid eyes!
+ *
+ * The correct analysis would be to remove the vertex
+ * from the eyespace rather than turning it into a false
+ * eye. Then we would have the eyespace .XXX which is
+ * correctly evaluated to one eye (eye value 1112).
+ *
+ * The problem with this is that removing eye points is
+ * messy. It can surely be done but currently there is
+ * no support in the code for doing that. It has existed
+ * at an earlier time but was removed because the
+ * implementation was not robust enough and there was no
+ * longer any apparent need for it. To correct this
+ * problem is sufficient reason to reimplement that
+ * functionality.
+ *
+ * 4. The test of condition g) has a result which
+ * potentially depends on the ordering of the eyespaces
+ * and thus presumably on the orientation of the board.
+ * It might make more sense to examine whether the
+ * string neighbors more than one empty vertex in the
+ * same eyespace.
+ */
+ if (val < 2.0 && board[pos] == EMPTY && board[diag] == OTHER_COLOR(color)
+ && !is_edge_vertex(pos) && neighbor_of_string(pos, diag)
+ && countstones(diag) >= 3) {
int strings[3];
int string_count;
int s;
@@ -1810,7 +1898,8 @@
continue;
for (r = 0; r < lib_count && adj_eye_count < 2; r++)
- if (is_proper_eye_space(libs[r]))
+ if (my_eye[libs[r]].color == OTHER_COLOR(color)
+ && !my_eye[libs[r]].marginal)
adj_eye_count++;
if (adj_eye_count < 2) {
val = 2.0;
Index: regression/owl1.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/owl1.tst,v
retrieving revision 1.104
diff -u -r1.104 owl1.tst
--- regression/owl1.tst 20 Jan 2005 19:04:34 -0000 1.104
+++ regression/owl1.tst 4 Feb 2005 06:16:19 -0000
@@ -422,6 +422,12 @@
363 owl_defend F9
#? [1 (F5|G5|G6|H6)]*
+loadsgf games/owl54.sgf
+364 owl_attack E9
+#? [1 (PASS|A7|D6|F8|F9)]
+365 owl_defend E9
+#? [0]
+
########### end of tests #####################
# Report number of nodes visited by the tactical reading
Index: regression/games/owl54.sgf
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/games/owl54.sgf,v
retrieving revision 1.1
diff -u -r1.1 owl54.sgf
--- regression/games/owl54.sgf 1 Jan 2005 19:40:15 -0000 1.1
+++ regression/games/owl54.sgf 4 Feb 2005 06:16:19 -0000
@@ -1,5 +1,5 @@
(;GM[1]FF[3]
SZ[9]
-AW[ib][hc][ic][id][ae][be][ce][he][cf][df][ef][ff][gf][hf][ag][bg][cg][bh][dh][gh][hh][bi][ci][hi]
-AB[fa][ha][fb][gb][hb][ec][gc][ad][bd][cd][dd][ed][fd][gd][hd][if][dg][eg][fg][gg][hg][eh][ih][di][ei]
+AW[ea][ab][bb][cb][eb][ib][dc][ec][hc][ic][id][he][af][bf][cf][df][ef][ff][gf][hf][bg][cg][ah][bh][dh][gh][hh][bi][ci][hi]
+AB[ba][ca][da][ha][gb][hb][bc][cc][fc][gc][ad][cd][ed][gd][hd][ae][be][ce][de][ee][fe][ge][if][dg][eg][fg][gg][hg][eh][ih][di][ei]
)