- support for !experimental_semeai removed - old semeai() removed and new_semeai() renamed to semeai() - analyze_semeai(), add_appropriate_semeai_moves(), and liberty_of_dragon() removed Index: engine/dragon.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v retrieving revision 1.118 diff -u -r1.118 dragon.c --- engine/dragon.c 18 Jul 2003 18:59:21 -0000 1.118 +++ engine/dragon.c 1 Aug 2003 13:56:05 -0000 @@ -560,10 +560,7 @@ time_report(2, " post owl dragon data", NO_MOVE, 1.0); /* Resolve semeais. This may revise the safety and status fields. */ - if (experimental_semeai && level >= 8) - new_semeai(); - else - semeai(color); + semeai(); time_report(2, " semeai module", NO_MOVE, 1.0); Index: engine/liberty.h =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v retrieving revision 1.188 diff -u -r1.188 liberty.h --- engine/liberty.h 18 Jul 2003 18:59:21 -0000 1.188 +++ engine/liberty.h 1 Aug 2003 13:56:06 -0000 @@ -555,8 +555,7 @@ /* Various different strategies for finding a move */ void fuseki(int color); -void semeai(int color); -void new_semeai(void); +void semeai(void); void small_semeai(int save_verbose); void semeai_move_reasons(int color); void shapes(int color); Index: engine/owl.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v retrieving revision 1.176 diff -u -r1.176 owl.c --- engine/owl.c 18 Jul 2003 18:59:21 -0000 1.176 +++ engine/owl.c 1 Aug 2003 13:56:11 -0000 @@ -5362,11 +5362,8 @@ reduced_init_owl(struct local_owl_data **owl, int at_bottom_of_stack) { if (owl_stack_size == 0) { - if (experimental_semeai) - owl_stack_size = gg_max(owl_reading_depth + 2, - 2 * semeai_branch_depth + 4); - else - owl_stack_size = owl_reading_depth + 2; + owl_stack_size = gg_max(owl_reading_depth + 2, + 2 * semeai_branch_depth + 4); owl_stack = malloc(owl_stack_size * sizeof(*owl_stack)); gg_assert(owl_stack != NULL); } Index: engine/semeai.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/semeai.c,v retrieving revision 1.57 diff -u -r1.57 semeai.c --- engine/semeai.c 18 Jul 2003 18:59:21 -0000 1.57 +++ engine/semeai.c 1 Aug 2003 13:56:12 -0000 @@ -29,75 +29,24 @@ #define INFINITY 1000 -static void analyze_semeai(int my_dragon, int your_dragon); -static void add_appropriate_semeai_moves(int move, - int my_dragon, int your_dragon, - int my_status, int your_status, - int margin_of_safety); static void small_semeai_analyzer(int str1, int str2, int save_verbose); static void update_status(int dr, int new_status, int new_safety); -/* semeai() searches for pairs of dragons of opposite color which - * have safety DEAD. If such a pair is found, analyze_semeai is - * called to determine which dragon will prevail in a semeai, and +/* new_semeai() searches for pairs of dragons of opposite color which + * have safety DEAD. If such a pair is found, owl_analyze_semeai is + * called to read out which dragon will prevail in a semeai, and * whether a move now will make a difference in the outcome. The * dragon statuses are revised, and if a move now will make a - * difference in the outcome, an owl reason is generated. - */ - -void -semeai(int color) -{ - int d1, d2; - int k; - int apos = NO_MOVE; - int bpos = NO_MOVE; - int other = OTHER_COLOR(color); - - TRACE("Semeai Player is THINKING for %s!\n", - color_to_string(color)); - - for (d1 = 0; d1 < number_of_dragons; d1++) { - if (DRAGON(d1).color != color - || (DRAGON(d1).status != DEAD - && DRAGON(d1).status != CRITICAL)) - continue; - - for (k = 0; k < dragon2[d1].neighbors; k++) { - d2 = dragon2[d1].adjacent[k]; - if (DRAGON(d2).color != other - || (DRAGON(d2).status != DEAD - && DRAGON(d2).status != CRITICAL)) - continue; - - /* Dragons d1 (our) and d2 (opponent) are adjacent and both DEAD - * or CRITICAL. - */ - apos = DRAGON(d1).origin; - bpos = DRAGON(d2).origin; - - /* Ignore inessential worms or dragons */ - if (worm[apos].inessential - || DRAGON2(apos).safety == INESSENTIAL - || worm[bpos].inessential - || DRAGON2(bpos).safety == INESSENTIAL) - continue; - - analyze_semeai(apos, bpos); - } - } -} - - -/* revision of semeai(). Differs from the old program in calling - * owl_analyze_semeai() instead of relying on static analysis. + * difference in the outcome this information is stored in + * dragon_data2 and an owl reason is later generated by + * semeai_move_reasons(). */ #define MAX_DRAGONS 50 void -new_semeai() +semeai() { int semeai_results_first[MAX_DRAGONS][MAX_DRAGONS]; int semeai_results_second[MAX_DRAGONS][MAX_DRAGONS]; @@ -232,6 +181,7 @@ } } + /* This function adds the semeai related move reasons, using the information * stored in the dragon2 array. * @@ -267,27 +217,6 @@ } } -/* liberty_of_dragon(pos, origin) returns true if the vertex at (pos) is a - * liberty of the dragon with origin at (origin). - */ - -static int -liberty_of_dragon(int pos, int origin) -{ - if (pos == NO_MOVE) - return 0; - - if (board[pos] != EMPTY) - return 0; - - if ((ON_BOARD(SOUTH(pos)) && dragon[SOUTH(pos)].origin == origin) - || (ON_BOARD(WEST(pos)) && dragon[WEST(pos)].origin == origin) - || (ON_BOARD(NORTH(pos)) && dragon[NORTH(pos)].origin == origin) - || (ON_BOARD(EAST(pos)) && dragon[EAST(pos)].origin == origin)) - return 1; - - return 0; -} /* Change the status and safety of a dragon */ @@ -312,497 +241,6 @@ safety_to_string(DRAGON2(dr).safety), safety_to_string(new_safety)); DRAGON2(dr).safety = new_safety; } -} - - - -/* analyzes a pair of adjacent dragons which are - * DEAD or CRITICAL. - */ -static void -analyze_semeai(int my_dragon, int your_dragon) -{ - /* We start liberty counts at 1 since we will be subtracting - * the number of worms. */ - int mylibs = 1, yourlibs = 1, commonlibs = 0; - int yourlib = NO_MOVE; - int commonlib = NO_MOVE; - int color = board[my_dragon]; - int my_status = UNKNOWN; - int your_status = UNKNOWN; - int margin_of_safety = 0; - int owl_code_sufficient = 0; - int pos; - - DEBUG(DEBUG_SEMEAI, "semeai_analyzer: %1m (me) vs %1m (them)\n", - my_dragon, your_dragon); - - /* If both dragons are owl-critical, and the defense point for my - * dragon owl_does_attack your dragon, add another owl attack move - * reason. - */ - if (DRAGON2(my_dragon).owl_status == CRITICAL - && DRAGON2(your_dragon).owl_status == CRITICAL) { - if (DRAGON2(your_dragon).owl_attack_point - == DRAGON2(my_dragon).owl_defense_point) - return; - if (DRAGON2(my_dragon).owl_defense_point != NO_MOVE) { - int acode = owl_does_attack(DRAGON2(my_dragon).owl_defense_point, - your_dragon, NULL); - if (acode != 0) { - add_owl_attack_move(DRAGON2(my_dragon).owl_defense_point, your_dragon, - acode); - DEBUG(DEBUG_SEMEAI, "added owl attack of %1m at %1m with code %d\n", - your_dragon, DRAGON2(my_dragon).owl_defense_point, acode); - owl_code_sufficient = 1; - } - } - } - - /* If both dragons are owl-critical, or your dragon is owl-critical - * and my dragon is owl-dead, and the attack point for your dragon - * owl_does_defend my dragon, add another owl defense move reason - * and possibly change the owl status of my dragon to critical. - */ - if ((DRAGON2(my_dragon).owl_status == CRITICAL - || DRAGON2(my_dragon).owl_status == DEAD) - && DRAGON2(your_dragon).owl_status == CRITICAL) { - if (DRAGON2(your_dragon).owl_attack_point - == DRAGON2(my_dragon).owl_defense_point) - return; - if (DRAGON2(your_dragon).owl_attack_point != NO_MOVE) { - int dcode = owl_does_defend(DRAGON2(your_dragon).owl_attack_point, - my_dragon, NULL); - if (dcode != 0) { - add_owl_defense_move(DRAGON2(your_dragon).owl_attack_point, my_dragon, - dcode); - DEBUG(DEBUG_SEMEAI, "added owl defense of %1m at %1m with code %d\n", - my_dragon, DRAGON2(your_dragon).owl_attack_point, dcode); - if (DRAGON2(my_dragon).owl_status == DEAD) { - int pos; - - for (pos = BOARDMIN; pos < BOARDMAX; pos++) { - if (!ON_BOARD(pos)) - continue; - if (board[pos] == board[my_dragon] - && is_same_dragon(pos, my_dragon)) { - DRAGON2(pos).owl_status = CRITICAL; - dragon[pos].status = CRITICAL; - } - } - DEBUG(DEBUG_SEMEAI, - "changed owl_status and status of %1m to CRITICAL\n", - my_dragon); - } - owl_code_sufficient = 1; - } - } - } - - /* If the owl code was able to resolve the semeai, exit. */ - if (owl_code_sufficient) { - DEBUG(DEBUG_SEMEAI, "...owl code sufficient to resolve semeai, exiting\n"); - return; - } - - - /* The semeai module is prone to errors since semeai cannot - * really be handled by static analysis. It is really only needed - * when the dragons have many liberties since tight situations - * can be handled by the tactical reading code. Thus we exclude - * dragon pairs where either has a tactically DEAD or CRITICAL - * string which is adjacent to the other dragon which is owl - * substantial. - */ - for (pos = BOARDMIN; pos < BOARDMAX; pos++) { - if (!ON_BOARD(pos)) - continue; - - if (worm[pos].origin == pos - && worm[pos].attack_codes[0] == WIN) { - if (dragon[pos].origin == my_dragon - || dragon[pos].origin == your_dragon) { - int adj; - int adjs[MAXCHAIN]; - int r; - - adj = chainlinks(pos, adjs); - for (r = 0; r < adj; r++) { - int cpos = adjs[r]; - if (dragon[cpos].origin == my_dragon - || dragon[cpos].origin == your_dragon) { - if (owl_substantial(pos)) { - DEBUG(DEBUG_SEMEAI, - "...tactical situation detected, exiting\n"); - return; - } - } - } - } - } - } - - - /* Mark the dragons as involved in semeai */ - for (pos = BOARDMIN; pos < BOARDMAX; pos++) { - if (ON_BOARD(pos) - && (is_same_dragon(pos, my_dragon) - || is_same_dragon(pos, your_dragon))) - DRAGON2(pos).semeai = 1; - } - - /* First we try to determine the number of liberties of each - * dragon, and the number of common liberties. We subtract - * 1 minus the number of worms of the dragon from the liberty - * count, since if a dragon has several worms, a move may - * have to be invested in connecting them. At the same time - * we try to find a liberty of the opponent's dragon, and a - * common liberty, for future reference. - */ - for (pos = BOARDMIN; pos < BOARDMAX; pos++) { - if (!ON_BOARD(pos)) - continue; - if (IS_STONE(board[pos]) - && worm[pos].origin == pos) { - if (is_same_dragon(pos, my_dragon)) - mylibs--; - if (is_same_dragon(pos, your_dragon)) - yourlibs--; - } - else if (board[pos] == EMPTY) { - if (liberty_of_dragon(pos, your_dragon)) { - yourlibs ++; - if (liberty_of_dragon(pos, my_dragon)) { - commonlibs++; - mylibs++; - commonlib = pos; - } - else - yourlib = pos; - } - else if (liberty_of_dragon(pos, my_dragon)) - mylibs++; - } - } - - /* We add 1 to the - * number of liberties of an owl critical dragon if the point - * of attack is not a liberty of the dragon, since a move - * may have to be invested in attacking it. - */ - - if (DRAGON2(my_dragon).owl_status == CRITICAL - && DRAGON2(my_dragon).owl_attack_point != NO_MOVE - && !liberty_of_string(DRAGON2(my_dragon).owl_attack_point, my_dragon)) - mylibs++; - - if (DRAGON2(your_dragon).owl_status == CRITICAL - && DRAGON2(your_dragon).owl_attack_point != NO_MOVE - && !liberty_of_string(DRAGON2(your_dragon).owl_attack_point, your_dragon)) - yourlibs++; - - /* Now we compute the statuses which result from a - * naive comparison of the number of liberties. There - * is some uncertainty in these calculations, so we - * must exercise caution in applying the results. - * - * RULES FOR PLAYING SEMEAI. Let M be the number of liberties - * of my group, excluding common liberties; let Y be the - * number of liberties of your group, excluding common - * liberties; and let C be the number of common liberties. - * - * If both groups have zero eyes: - * - * (1) If C=0 and M=Y, whoever moves first wins. CRITICAL. - * (2) If C=0 and M>Y, I win. - * (3) If C=0 and M0 and M >= Y+C then your group is dead and mine is alive. - * (5) If C>0 and M = Y+C-1 then the situation is CRITICAL. - * (5a) If M=0, then Y=0 and C=1. Whoever moves first kills. - * (5b) If M>0, then I can kill or you can make seki. - * (6) If M < Y+C-1 and Y < M+C-1 then the situation is seki. - * (7) If C>0 and Y=M+C-1 the situation is CRITICAL. - * (7a) If Y=0, then M=0 and C=1 as in (5). - * (7b) If Y>0, you can kill or I can make seki. - * (8) If C>0 and Y > M+C then your group is alive and mine is dead. - * - * If both groups have one eye: - * - * In this case M > 0 and Y > 0. - * - * (1) If M>C+Y then I win. - * (2) If Y>C+M then you win. - * (3) If C=0 and M=Y then whoever moves first kills. CRITICAL. - * (4) If C>0 and M=C+Y then I can kill, you can make seki. CRITICAL. - * (5) If C>0 and M0 and Y=C+M, then you can kill, I can make seki. CRITICAL. - * - * If I have an eye and you dont: - * - * In this case, M > 0. This situation (me ari me nashi) can - * never be seki. The common liberties must be filled by you, - * making it difficult to win. - * - * (1) If M+C>Y then I win. - * (2) If M+C=Y then whoever moves first wins. CRITICAL. - * (3) If M+C 0. - * - * (1) If Y+C>M you win. - * (2) If Y+C=M whoever moves first wins. CRITICAL. - * (3) If Y+C yourlibs) { - my_status = ALIVE; - your_status = DEAD; - margin_of_safety = mylibs - yourlibs; - } - else if (mylibs < yourlibs) { - my_status = DEAD; - your_status = ALIVE; - margin_of_safety = yourlibs - mylibs; - } - else { - my_status = CRITICAL; - your_status = CRITICAL; - margin_of_safety = 0; - } - } - else if (mylibs == yourlibs + commonlibs - 1) { - if (mylibs == 0) { - my_status = CRITICAL; - your_status = CRITICAL; - margin_of_safety = 0; - } - else { - /* I can kill, you can make seki */ - my_status = ALIVE; - your_status = CRITICAL; - margin_of_safety = 0; - } - } - else if (mylibs < yourlibs + commonlibs - 1 - && yourlibs < mylibs+commonlibs - 1) { - /* Seki */ - my_status = ALIVE; - your_status = ALIVE; - margin_of_safety = INFINITY; - } - else if (commonlibs > 0 - && yourlibs == mylibs + commonlibs - 1) { - if (yourlibs == 0) { - my_status = CRITICAL; - your_status = CRITICAL; - margin_of_safety = 0; - } - else { - /* you can kill, I can make seki */ - my_status = CRITICAL; - your_status = ALIVE; - margin_of_safety = 0; - } - } - else if (commonlibs > 0 - && yourlibs > mylibs + commonlibs) { - my_status = DEAD; - your_status = ALIVE; - margin_of_safety = yourlibs - mylibs - commonlibs; - } - } - if (min_eyes(&DRAGON2(my_dragon).genus) > 0 - && min_eyes(&DRAGON2(your_dragon).genus) > 0) { - if (mylibs > yourlibs + commonlibs) { - my_status = ALIVE; - your_status = DEAD; - margin_of_safety = mylibs - yourlibs - commonlibs; - } - else if (yourlibs > mylibs + commonlibs) { - my_status = DEAD; - your_status = ALIVE; - margin_of_safety = yourlibs - mylibs - commonlibs; - } - else if (commonlibs == 0 - && mylibs == yourlibs) { - my_status = CRITICAL; - your_status = CRITICAL; - margin_of_safety = 0; - } - else if (commonlibs > 0 - && mylibs == commonlibs + yourlibs) { - my_status = ALIVE; - your_status = CRITICAL; - margin_of_safety = 0; - } - else if (commonlibs > 0 - && mylibs < commonlibs + yourlibs - && yourlibs < commonlibs + mylibs) { - /* seki */ - my_status = ALIVE; - your_status = ALIVE; - margin_of_safety = INFINITY; - } - else if (commonlibs > 0 - && yourlibs == commonlibs + mylibs) { - my_status = CRITICAL; - your_status = ALIVE; - margin_of_safety = 0; - } - } - if (min_eyes(&DRAGON2(my_dragon).genus) > 0 - && min_eyes(&DRAGON2(your_dragon).genus) == 0) { - if (mylibs > commonlibs + yourlibs) { - my_status = ALIVE; - your_status = DEAD; - margin_of_safety = mylibs - commonlibs - yourlibs; - } - else if (mylibs + commonlibs == yourlibs) { - my_status = CRITICAL; - your_status = CRITICAL; - } - else if (mylibs + commonlibs < yourlibs) { - my_status = DEAD; - your_status = ALIVE; - margin_of_safety = mylibs + commonlibs - yourlibs; - } - } - if (min_eyes(&DRAGON2(my_dragon).genus) == 0 - && min_eyes(&DRAGON2(your_dragon).genus) > 0) { - if (yourlibs + commonlibs > mylibs) { - my_status = DEAD; - your_status = ALIVE; - margin_of_safety = yourlibs + commonlibs - mylibs; - } - else if (yourlibs + commonlibs == mylibs) { - my_status = CRITICAL; - your_status = CRITICAL; - margin_of_safety = 0; - } - else if (yourlibs + commonlibs > mylibs) { - my_status = DEAD; - your_status = ALIVE; - margin_of_safety = yourlibs - mylibs - commonlibs; - } - } - - /* Update matcher statuses */ - - /* We do not want to change the matcher status of the friendly - * dragon if the owl status is critical. If my_status==DEAD by - * the preceeding heuristics but the owl code finds a way to - * live, then we should by all means take it. On the other hand - * if my_status==ALIVE we are alive by semeai, but as a matter - * of "safety first" if the owl code finds a way to live we may - * want to take it. So the matcher status is not changed. - */ - - if (DRAGON2(my_dragon).owl_status != CRITICAL) { - if (my_status == ALIVE) - update_status(my_dragon, ALIVE, ALIVE_IN_SEKI); - else if (my_status == CRITICAL) - update_status(my_dragon, CRITICAL, CRITICAL); - else if (my_status == DEAD) - update_status(my_dragon, DEAD, DEAD); - } - - if (your_status == ALIVE) - update_status(your_dragon, ALIVE, ALIVE_IN_SEKI); - else if (your_status == CRITICAL) - update_status(your_dragon, CRITICAL, CRITICAL); - else if (your_status == DEAD) - update_status(your_dragon, DEAD, DEAD); - - /* Find the recommended semeai moves. In order of priority, - * (1) We defend our dragon; - * (2) We attack your dragon; - * (3) If common liberties > 1, make an eye; - * (4) If common liberties > 1, kill an eye; - * (5) Fill a liberty of yours; - * (6) Fill a common liberty. */ - - if (my_status == CRITICAL || your_status == CRITICAL) { - int found_one = 0; - if (DRAGON2(my_dragon).owl_status == CRITICAL - && DRAGON2(my_dragon).owl_defense_point != NO_MOVE) - add_appropriate_semeai_moves(DRAGON2(my_dragon).owl_defense_point, - my_dragon, your_dragon, - my_status, your_status, margin_of_safety); - else if (DRAGON2(your_dragon).owl_status == CRITICAL - && DRAGON2(your_dragon).owl_attack_point != NO_MOVE) - add_appropriate_semeai_moves(DRAGON2(your_dragon).owl_attack_point, - my_dragon, your_dragon, - my_status, your_status, margin_of_safety); - else if (commonlibs > 1) { - if (eye_move_urgency(&DRAGON2(my_dragon).genus) > 0) - add_appropriate_semeai_moves(DRAGON2(my_dragon).heye, - my_dragon, your_dragon, - my_status, your_status, margin_of_safety); - if (eye_move_urgency(&DRAGON2(your_dragon).genus)) - add_appropriate_semeai_moves(DRAGON2(your_dragon).heye, - my_dragon, your_dragon, - my_status, your_status, margin_of_safety); - } - else { - for (pos = BOARDMIN; pos < BOARDMAX; pos++) { - if (!ON_BOARD(pos)) - continue; - - if (liberty_of_dragon(pos, your_dragon) - && !liberty_of_dragon(pos, my_dragon) - && safe_move(pos, color)) { - /* add move reasons for EVERY outside liberty where we can - * play safely. A move to win a semeai might not be a - * safe move if it is inside the opponent's eyespace. - * However we hope that the reading code can analyze the - * semeai in cases where every safe liberty has been filled. - */ - add_appropriate_semeai_moves(pos, my_dragon, your_dragon, - my_status, your_status, - margin_of_safety); - found_one = 1; - } - } - if (!found_one) { - /* No outside liberties --- look for common liberties. - * Filling a common liberty is usually bad but if our - * heuristics are accurate, we should only reach this point - * if we definitely have enough liberties to win. As a - * sanity check, we require filling a common liberty to - * be a safe move. - */ - for (pos = BOARDMIN; pos < BOARDMAX; pos++) { - if (ON_BOARD(pos) - && liberty_of_dragon(pos, your_dragon) - && safe_move(pos, color)) - add_appropriate_semeai_moves(pos, my_dragon, your_dragon, - my_status, your_status, - margin_of_safety); - } - } - } - } -} - -/* Add those move reasons which are appropriate. */ - -static void -add_appropriate_semeai_moves(int move, int my_dragon, int your_dragon, - int my_status, int your_status, - int margin_of_safety) -{ - if (my_status == CRITICAL) - add_semeai_move(move, my_dragon); - else if (margin_of_safety == 1) - add_semeai_threat(move, my_dragon); - if (your_status == CRITICAL) - add_semeai_move(move, your_dragon); - else if (margin_of_safety == 1) - add_semeai_threat(move, your_dragon); } Index: engine/utils.c =================================================================== RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v retrieving revision 1.81 diff -u -r1.81 utils.c --- engine/utils.c 18 Jul 2003 18:59:21 -0000 1.81 +++ engine/utils.c 1 Aug 2003 13:56:13 -0000 @@ -656,7 +656,6 @@ * Other policies depending on level: * aftermath.c: >= 8: call estimate_score(). * dragon.c: >= 8: compute owl threats (currently disabled) - * >= 8: call owl analysis of semeai (currently disabled) * genmove.c: >= 8: call estimate_score(). * owl.c: >= 9: use vital attack pattern database * >= 8: increase depth values in owl_substantial