[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] semeai patch
From: |
Gunnar Farneback |
Subject: |
[gnugo-devel] semeai patch |
Date: |
Sat, 10 May 2003 20:33:54 +0200 |
User-agent: |
EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.2 (Yagi-Nishiguchi) APEL/10.3 Emacs/20.7 (sparc-sun-solaris2.7) (with unibyte mode) |
This patch does a little cleaning and adds comments to the semeai code
in owl.c. Additionally some minor tuning and two new semeai tests.
- semeai code revisions
- owl tuning
- new test cases
I don't have current breakage but before the latest patches went into
CVS it was
nngs1:20 FAIL S13 [F17] - accidental
semeai:46 FAIL ALIVE DEAD T11 [...] - new test
nando:6 PASS 0 [0] - haven't checked
/Gunnar
Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.110
diff -u -r1.110 dragon.c
--- engine/dragon.c 27 Mar 2003 10:33:11 -0000 1.110
+++ engine/dragon.c 10 May 2003 18:22:38 -0000
@@ -1259,7 +1259,7 @@
* This function loops over the topologically false and half eye
* vertices and calls connected_to_eye() for each adjoining string to
* determine whether they all have external connection to an eye. The
- * result is stored in the array false_eye_territory[] array.
+ * result is stored in the false_eye_territory[] array.
*/
static void
analyze_false_eye_territory(void)
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.157
diff -u -r1.157 owl.c
--- engine/owl.c 9 May 2003 22:44:38 -0000 1.157
+++ engine/owl.c 10 May 2003 18:22:42 -0000
@@ -346,8 +346,13 @@
do_owl_analyze_semeai(apos, bpos, owla, owlb, EMPTY, NO_MOVE,
resulta, resultb, move, 0, owl);
- *semeai_result_certain = result_certain;
+ if (semeai_result_certain)
+ *semeai_result_certain = result_certain;
+ /* FIXME: We throw away information about ko results here. We need
+ * to do this until the callers are prepared to deal with ko
+ * results.
+ */
if (resulta) {
if (*resulta != 0)
*resulta = ALIVE;
@@ -427,12 +432,6 @@
if (!move)
move = &dummy_move;
- shape_offensive_patterns.initialized = 0;
- shape_defensive_patterns.initialized = 0;
-
- global_owl_node_counter++;
- local_owl_node_counter++;
-
ASSERT1(board[apos] == owla->color, apos);
ASSERT1(board[bpos] == owlb->color, bpos);
@@ -443,6 +442,7 @@
if (rr_get_result1(*read_result) != 0)
*move = rr_get_move(*read_result);
+
*resulta = rr_get_result1(*read_result);
*resultb = rr_get_result2(*read_result);
@@ -457,6 +457,12 @@
}
}
+ global_owl_node_counter++;
+ local_owl_node_counter++;
+
+ shape_offensive_patterns.initialized = 0;
+ shape_defensive_patterns.initialized = 0;
+
#if 0
wormsa = catalog_goal(owla, goal_wormsa);
wormsb = catalog_goal(owlb, goal_wormsb);
@@ -466,9 +472,6 @@
common_liberty.pos = NO_MOVE;
backfill_outside_liberty.pos = NO_MOVE;
backfill_common_liberty.pos = NO_MOVE;
- /* turn off the sgf file and variation counting */
- sgf_dumptree = NULL;
- count_variations = 0;
for (k = 0; k < MAX_SEMEAI_MOVES; k++) {
moves[k].pos = 0;
moves[k].value = -1;
@@ -478,8 +481,14 @@
ASSERT1(other == board[bpos], bpos);
memset(mw, 0, sizeof(mw));
- /* Look for a tactical attack. We seek a semeai worm of owlb
- * which can be attacked. If such exists, we declare victory.
+ /* Turn off the sgf file and variation counting. */
+ sgf_dumptree = NULL;
+ count_variations = 0;
+
+ /* Look for a tactical attack. We seek a semeai worm of owlb which
+ * can be attacked. If such exists and is considered critical, we
+ * declare victory. If it's not considered critical we add the
+ * attacking move as a high priority move to try.
*/
{
@@ -498,8 +507,6 @@
sgf_dumptree = save_sgf_dumptree;
count_variations = save_count_variations;
SGFTRACE_SEMEAI(upos, WIN, WIN, "tactical win found");
- close_pattern_list(color, &shape_defensive_patterns);
- close_pattern_list(color, &shape_offensive_patterns);
READ_RETURN_SEMEAI(read_result, move, upos, WIN, WIN);
}
else if (find_defense(semeai_worms[sworm], NULL)) {
@@ -630,10 +637,7 @@
break;
/* Now we review the moves already considered, while collecting
- * them into a single list. If no owl moves are found, we end the owl
- * phase. If no owl move of value > 30 is found, we want to be sure that we
- * have included a move that fills a liberty. If no such move is found, we
- * will have to add it later.
+ * them into a single list.
*/
if (!I_look_alive) {
@@ -665,25 +669,29 @@
}
if (level < 10) {
- /* If no owl moves were found on two consecutive moves,
- turn off the owl phase. */
- if (moves[0].pos == NO_MOVE) {
- if (owl_phase == 1)
- owl_phase = 2;
- else if (owl_phase == 2)
- owl_phase = 0;
- }
- else owl_phase = 1;
- }
+ /* If no owl moves were found on two consecutive moves,
+ * turn off the owl phase.
+ */
+ if (moves[0].pos == NO_MOVE) {
+ if (owl_phase == 1)
+ owl_phase = 2;
+ else if (owl_phase == 2)
+ owl_phase = 0;
+ }
+ else
+ owl_phase = 1;
+ }
}
- /* now we look for a move to fill a liberty.
- */
if (1 && verbose) {
showboard(0);
goaldump(owla->goal);
goaldump(owlb->goal);
}
+
+ /* Now we look for a move to fill a liberty. This is only
+ * interesting if the opponent doesn't already have two eyes.
+ */
if (!you_look_alive
&& !safe_outside_liberty_found && moves[0].value < 100) {
int pos;
@@ -719,6 +727,12 @@
}
}
+ /* Add the best liberty filling move available. We first want to
+ * play outer liberties, second backfilling moves required before
+ * filling an outer liberty. If no such moves are available we try
+ * to fill a mutual liberty or play a corresponding backfilling
+ * move.
+ */
if (!you_look_alive) {
if (safe_outside_liberty_found
&& outside_liberty.pos != NO_MOVE) {
@@ -766,20 +780,24 @@
tested_moves = 0;
for (k = 0; k < MAX_SEMEAI_MOVES; k++) {
int mpos = moves[k].pos;
+ if (mpos == NO_MOVE)
+ break;
+ /* Do not try too many moves. */
+ /* FIXME: Replace the hardcoded 6 below with a proper DEPTH constant. */
if (tested_moves > 2
|| (stackp > semeai_branch_depth2 && tested_moves > 1)
|| (stackp > semeai_branch_depth && tested_moves > 0)) {
/* If allpats, try and pop to get the move in the sgf record. */
- if (allpats && mpos!= NO_MOVE
- && trymove(mpos, color, moves[k].name, apos, komaster, kom_pos)) {
+ if (!allpats)
+ break;
+ else if (trymove(mpos, color, moves[k].name, apos, komaster, kom_pos)) {
semeai_add_sgf_comment(moves[k].value, owl_phase);
popgo();
}
continue;
}
- if (mpos != NO_MOVE
- && count_variations < semeai_node_limit
+ if (count_variations < semeai_node_limit
&& stackp < MAX_SEMEAI_DEPTH
&& komaster_trymove(mpos, color, moves[k].name, apos,
komaster, kom_pos,
@@ -800,7 +818,14 @@
owlb->lunches_are_current = 0;
owl_update_boundary_marks(mpos, owlb);
+ /* Do a recursive call to read the semeai after the move we just
+ * tried. If dragon b was captured by the move, call
+ * do_owl_attack() to see whether it sufficed for us to live.
+ */
if (board[bpos] == EMPTY) {
+ /* FIXME: Are all owl_data fields and relevant static
+ * variables properly set up for a call to do_owl_attack()?
+ */
this_resulta = REVERSE_RESULT(do_owl_attack(apos, NULL, NULL, owla,
new_komaster, new_kom_pos,
0));
@@ -820,6 +845,7 @@
popgo();
+ /* Does success require ko? */
if (ko_move) {
if (this_resulta != 0)
this_resulta = KO_B;
@@ -835,6 +861,7 @@
}
if (this_resultb == WIN && this_resulta == WIN) {
+ /* Ideal result, no need to try any more moves. */
*resulta = WIN;
*resultb = WIN;
*move = mpos;
@@ -844,6 +871,13 @@
close_pattern_list(color, &shape_offensive_patterns);
READ_RETURN_SEMEAI(read_result, move, mpos, WIN, WIN);
}
+ /* We consider our own safety most important and attacking the
+ * opponent as a secondary aim. This means that we prefer seki
+ * over a ko for life and death.
+ *
+ * FIXME: If our dragon is considerably smaller than the
+ * opponent dragon, we should probably prefer ko over seki.
+ */
else if (this_resulta > best_resulta
|| (this_resulta == best_resulta
&& this_resultb > best_resultb)) {
@@ -879,7 +913,7 @@
READ_RETURN_SEMEAI(read_result, move, PASS_MOVE, WIN, 0);
}
- /* If no move was found, then pass */
+ /* If no move was found, then pass. */
if (tested_moves == 0) {
do_owl_analyze_semeai(bpos, apos, owlb, owla, komaster, kom_pos,
resultb, resulta, NULL, 1, owl_phase);
@@ -948,8 +982,15 @@
return 0;
}
-
-
+
+
+/* Review the moves in owl_moves[] and add them into semeai_moves[].
+ * This is used to merge multiple sets of owl moves into one move
+ * list, while revising the values for use in semeai reading.
+ *
+ * We also record whether the moves include an outer or common liberty
+ * in the semeai.
+ */
static void
semeai_review_owl_moves(struct owl_move_data owl_moves[MAX_MOVES],
struct local_owl_data *owla,
@@ -961,27 +1002,31 @@
int guess_same_dragon, int value_bonus,
int *critical_semeai_worms)
{
- int upos;
+ int move;
int move_value;
int same_dragon;
int k;
for (k = 0; k < MAX_MOVES-1; k++) {
- upos = owl_moves[k].pos;
- if (upos == NO_MOVE)
+ move = owl_moves[k].pos;
+ if (move == NO_MOVE)
break;
-
- if (liberty_of_goal(upos, owlb)
- && safe_move(upos, color)) {
- if (!liberty_of_goal(upos, owla))
+
+ /* Does the move fill a liberty in the semeai? */
+ if (liberty_of_goal(move, owlb)
+ && safe_move(move, color)) {
+ if (!liberty_of_goal(move, owla))
*safe_outside_liberty_found = 1;
else
*safe_common_liberty_found = 1;
}
+ /* For some types of owl moves we don't have same_dragon
+ * information recorded and need to guess.
+ */
if (guess_same_dragon) {
- if (liberty_of_goal(upos, owla)
- || second_liberty_of_goal(upos, owla))
+ if (liberty_of_goal(move, owla)
+ || second_liberty_of_goal(move, owla))
same_dragon = 1;
else
same_dragon = 0;
@@ -989,20 +1034,21 @@
else
same_dragon = owl_moves[k].same_dragon;
- mw[upos] = 1;
- move_value = (semeai_move_value(upos, owla, owlb, owl_moves[k].value,
+ mw[move] = 1;
+ move_value = (semeai_move_value(move, owla, owlb, owl_moves[k].value,
critical_semeai_worms)
+ value_bonus);
- owl_add_move(semeai_moves, upos, move_value, owl_moves[k].name,
+ owl_add_move(semeai_moves, move, move_value, owl_moves[k].name,
same_dragon, owl_moves[k].escape,
NO_MOVE, MAX_SEMEAI_MOVES);
- TRACE("Added %1m %d\n", upos, move_value);
+ TRACE("Added %1m %d\n", move, move_value);
}
}
-/* Returns the number of liberties gained by the first goal minus the
- * number of liberties lost by the second goal when a move is played
- * at move (if positive, zero otherwise). Used for sorting the moves.
+/* Try to estimate the value of a semeai move. This has two
+ * components. The first is the change in the total number of
+ * liberties for strings involved in the semeai. The second is a bonus
+ * for attacks and defenses of critical semeai worms.
*/
static int
@@ -1073,10 +1119,7 @@
-/* If (pos) points to an empty intersection, returns true if
- * this spot is adjacent to an element of the owl goal.
- */
-
+/* Is the vertex at pos adjacent to an element of the owl goal? */
static int
liberty_of_goal(int pos, struct local_owl_data *owl)
{
@@ -1088,6 +1131,7 @@
return 0;
}
+/* Is the vertex at pos a second liberty of the owl goal? */
static int
second_liberty_of_goal(int pos, struct local_owl_data *owl)
{
Index: patterns/komoku.sgf
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/komoku.sgf,v
retrieving revision 1.13
diff -u -r1.13 komoku.sgf
--- patterns/komoku.sgf 16 Apr 2003 21:13:37 -0000 1.13
+++ patterns/komoku.sgf 10 May 2003 18:22:42 -0000
@@ -166,11 +166,15 @@
)
(;B[pf]MA[lh]
-(;W[qc]MA[lh]C[:-,shape(3)];B[rc]MA[lh];W[pc]MA[lh]C[U]
+(;W[qc]MA[lh]C[:-,shape(3)]
+(;B[rc]MA[lh];W[pc]MA[lh]C[U]
(;B[re]MA[lh]C[:-,shape(8)];W[kc]MA[jg]C[
])
(;B[rb]MA[kg];W[kc]MA[jg];B[qj]MA[jk])
+)
+
+(;B[pc]MA[lh]C[0])
)
(;W[lc]MA[lh]C[0])
Index: patterns/owl_attackpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_attackpats.db,v
retrieving revision 1.80
diff -u -r1.80 owl_attackpats.db
--- patterns/owl_attackpats.db 2 May 2003 15:04:59 -0000 1.80
+++ patterns/owl_attackpats.db 10 May 2003 18:22:45 -0000
@@ -3624,6 +3624,7 @@
Pattern A1105
+# gf Added n classification. (3.3.20)
O..
XO* connect against double threat
@@ -3631,7 +3632,7 @@
x..
---
-:8,-,value(85)
+:8,n,value(85)
Oa.
XO*
Index: patterns/owl_defendpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_defendpats.db,v
retrieving revision 1.94
diff -u -r1.94 owl_defendpats.db
--- patterns/owl_defendpats.db 9 May 2003 22:44:38 -0000 1.94
+++ patterns/owl_defendpats.db 10 May 2003 18:22:47 -0000
@@ -2499,6 +2499,23 @@
;!oplay_defend(*,A)
+Pattern D640
+# gf New pattern. (3.3.20)
+# Compare D720.
+
+?O*.o try to make eye on edge
+O....
+-----
+
+:8,-,value(56)
+
+?O*bo
+Oa...
+-----
+
+;!obvious_false_oeye(a) && !oplay_attack(b,*,*)
+
+
#########################################################
# #
# Make eyeshape in the center #
@@ -4649,12 +4666,13 @@
Pattern D1139
# tm New Pattern (3.1.20) (see nngs:110)
+# gf Added n classification. (3.3.20)
?*
XO
OX
-:8,bE,value(75)
+:8,bEn,value(75)
?*
aO
Index: regression/semeai.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/semeai.tst,v
retrieving revision 1.36
diff -u -r1.36 semeai.tst
--- regression/semeai.tst 29 Apr 2003 03:17:13 -0000 1.36
+++ regression/semeai.tst 10 May 2003 18:22:47 -0000
@@ -238,6 +238,10 @@
#? [ALIVE DEAD (A15|A11|B11|C14|C13|D12|D11|D10|D9|B9|A9)]
44 owl_analyze_semeai A12 A16
#? [ALIVE DEAD (A17|B17|C16|D16|E15|E14|F13|F12|F11|F10|F9|F8|B9|A9)]
+45 owl_analyze_semeai Q12 S11
+#? [ALIVE ALIVE (PASS|R8|R9|T11|T9|R11|R10)]
+46 owl_analyze_semeai S11 Q12
+#? [ALIVE ALIVE (PASS|T11|T9|R9|T10|R10|R11)]
loadsgf games/semeai/semeai12.sgf
45 owl_analyze_semeai B5 A9
Index: regression/games/semeai/semeai9.sgf
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/games/semeai/semeai9.sgf,v
retrieving revision 1.2
diff -u -r1.2 semeai9.sgf
--- regression/games/semeai/semeai9.sgf 4 Apr 2003 10:42:28 -0000 1.2
+++ regression/games/semeai/semeai9.sgf 10 May 2003 18:22:49 -0000
@@ -5,6 +5,6 @@
GN[White (W) vs. Black (B)]
DT[2000-06-10]
SY[Cgoban 1.9.2]TM[30:00(5x1:00)];
-AW[ja][na][pa][ab][bb][cb][jb][nb][ob][pb][qb][rb][cc][dc][ec][jc][mc][ed][fd][jd][md][fe][je][ke][me][bf][ff][gf][lf][mf][nf][of][pf][qf][rf][sf][bg][gg][ah][bh][ch][gh][ci][gi][hi][aj][bj][cj][gj][ij][ck][gk][hk][ik][jk][gl][jl][am][bm][cm][em][fm][gm][jm][cn][dn][gn][jn][kn][ln][mn][nn][on][pn][qn][rn][sn][do][eo][go][jo][ep][fp][gp][jp][aq][fq][gq][jq][ar][br][fr][gr][kr][lr][mr][nr][or][bs][fs][gs][ks][ms]
-AB[ma][ra][lb][mb][sb][lc][nc][oc][pc][qc][rc][ad][bd][ld][be][ce][de][le][af][df][kf][dg][eg][kg][lg][mg][ng][og][pg][qg][rg][sg][eh][ph][rh][ei][qi][ri][si][ej][ek][al][bl][cl][dl][el][il][dm][im][in][ao][bo][io][po][qo][ro][so][bp][cp][ip][kp][lp][mp][np][op][cq][dq][iq][kq][pq][dr][ir][jr][pr][ds][is][os]
+AW[ja][na][pa][ab][bb][cb][jb][nb][ob][pb][qb][rb][cc][dc][ec][jc][mc][ed][fd][jd][md][fe][je][ke][me][bf][ff][gf][lf][mf][nf][of][pf][qf][rf][sf][bg][gg][ah][bh][ch][gh][ph][qh][rh][sh][ci][gi][hi][pi][aj][bj][cj][gj][ij][pj][ck][gk][hk][ik][jk][pk][gl][jl][pl][rl][am][bm][cm][em][fm][gm][jm][qm][rm][cn][dn][gn][jn][rn][sn][do][eo][go][jo][ep][fp][gp][jp][aq][fq][gq][jq][ar][br][fr][gr][kr][lr][mr][nr][or][bs][fs][gs][ks][ms]
+AB[ma][ra][lb][mb][sb][lc][nc][oc][pc][qc][rc][ad][bd][ld][be][ce][de][le][af][df][kf][dg][eg][kg][lg][mg][ng][og][pg][qg][rg][sg][eh][oh][ei][oi][ri][ej][oj][rj][ek][ok][rk][al][bl][cl][dl][el][il][ol][sl][dm][im][om][pm][in][pn][qn][ao][bo][io][po][ro][so][bp][cp][ip][kp][lp][mp][np][op][pp][qp][cq][dq][iq][kq][pq][dr][ir][jr][pr][ds][is][os]
)
- [gnugo-devel] semeai patch,
Gunnar Farneback <=