/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * * http://www.gnu.org/software/gnugo/ for more information. * * * * Copyright 1999, 2000, 2001, 2002, 2003 and 2004 * * by the Free Software Foundation. * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation - version 2 * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License in file COPYING for more details. * * * * You should have received a copy of the GNU General Public * * License along with this program; if not, write to the Free * * Software Foundation, Inc., 59 Temple Place - Suite 330, * * Boston, MA 02111, USA. * \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #include "gnugo.h" #include #include "liberty.h" #include "gg_utils.h" static int dilate_erode(int dilations, int erosions, int gb[BOARDMAX], int color); static void print_new_moyo(int dilations, int erosions); static void close_bubbles(int gb[BOARDMAX]); static int captured_territory(int pos, int color); #define ARRAYSIZE MAX_BOARD*MAX_BOARD /* The code in this file is not much used in the engine, * being largely superceded by the algorithms in influence.c. * The exception is the function estimate_score(), and * that too could be replaced with influence_score() * in influence.c. */ /* As explained in the Texinfo documentation, this function * takes the characteristic function of the live groups, * dilates and erodes the required number of times. If * erosions = dilations*(dilations-1)+1, an isolated stone * does not get any area, suitable for computing territory. * * If dragons are CRITICAL, these are awarded to the player * 'color' for the purpose of determining an upper and lower * bound. The function returns 1 if critical dragons are found, * otherwise 0. */ static int dilate_erode(int dilations, int erosions, int gb[BOARDMAX], int color) { int ii; int work[BOARDMAX]; int n; int critical_found = 0; for (ii = BOARDMIN; ii < BOARDMAX; ii++) { if (!ON_BOARD(ii)) continue; if (board[ii] && dragon[ii].status == CRITICAL && DRAGON2(ii).safety != INESSENTIAL) { critical_found = 1; DEBUG(DEBUG_SCORING, "critical dragon found at %1m\n", ii); } if (board[ii] == WHITE && !captured_territory(ii, color)) gb[ii] = 128; else if (board[ii] == BLACK && !captured_territory(ii, color)) gb[ii] = -128; else gb[ii] = 0; } /* dilate */ memcpy(work, gb, sizeof(work)); for (n = 0; n < dilations; n++) { for (ii = BOARDMIN; ii < BOARDMAX; ii++) { if (!ON_BOARD(ii)) continue; if (gb[ii] >= 0 && (!ON_BOARD(SOUTH(ii)) || gb[SOUTH(ii)] >= 0) && (!ON_BOARD(WEST(ii)) || gb[WEST(ii)] >= 0) && (!ON_BOARD(NORTH(ii)) || gb[NORTH(ii)] >= 0) && (!ON_BOARD(EAST(ii)) || gb[EAST(ii)] >= 0)) { if (ON_BOARD(SOUTH(ii)) && gb[SOUTH(ii)] > 0) work[ii]++; if (ON_BOARD(WEST(ii)) && gb[WEST(ii)] > 0) work[ii]++; if (ON_BOARD(NORTH(ii)) && gb[NORTH(ii)] > 0) work[ii]++; if (ON_BOARD(EAST(ii)) && gb[EAST(ii)] > 0) work[ii]++; } if (gb[ii] <= 0 && (!ON_BOARD(SOUTH(ii)) || gb[SOUTH(ii)] <= 0) && (!ON_BOARD(WEST(ii)) || gb[WEST(ii)] <= 0) && (!ON_BOARD(NORTH(ii)) || gb[NORTH(ii)] <= 0) && (!ON_BOARD(EAST(ii)) || gb[EAST(ii)] <= 0)) { if (ON_BOARD(SOUTH(ii)) && gb[SOUTH(ii)] < 0) work[ii]--; if (ON_BOARD(WEST(ii)) && gb[WEST(ii)] < 0) work[ii]--; if (ON_BOARD(NORTH(ii)) && gb[NORTH(ii)] < 0) work[ii]--; if (ON_BOARD(EAST(ii)) && gb[EAST(ii)] < 0) work[ii]--; } } memcpy(gb, work, sizeof(work)); } /* erode */ for (n = 0; n < erosions; n++) { for (ii = BOARDMIN; ii < BOARDMAX; ii++) { if (!ON_BOARD(ii)) continue; if (work[ii] > 0) { if (ON_BOARD(SOUTH(ii)) && gb[SOUTH(ii)] <= 0) work[ii]--; if (ON_BOARD(WEST(ii)) && gb[WEST(ii)] <= 0 && work[ii] > 0) work[ii]--; if (ON_BOARD(NORTH(ii)) && gb[NORTH(ii)] <= 0 && work[ii] > 0) work[ii]--; if (ON_BOARD(EAST(ii)) && gb[EAST(ii)] <= 0 && work[ii] > 0) work[ii]--; } if (work[ii] < 0) { if (ON_BOARD(SOUTH(ii)) && gb[SOUTH(ii)] >= 0) work[ii]++; if (ON_BOARD(WEST(ii)) && gb[WEST(ii)] >= 0 && work[ii] < 0) work[ii]++; if (ON_BOARD(NORTH(ii)) && gb[NORTH(ii)] >= 0 && work[ii] < 0) work[ii]++; if (ON_BOARD(EAST(ii)) && gb[EAST(ii)] >= 0 && work[ii] < 0) work[ii]++; } } memcpy(gb, work, sizeof(work)); } return critical_found; } /* For scoring, it is assumed that any region completely * surrounded by territory is territory. This assumption * is particularly valid at the end of the game when * genmove produces a PASS. This function identifies * regions completely surrounded by territory and sets * them equal to 1 or -1 for WHITE or BLACK. * * We define an *bubble* to be a region of the complement * of the region marked in gb. The border color of the * bubble may be BLACK, WHITE or GRAY depending on whether * it is only adjacent to BLACK or WHITE marked regions, * or to both. */ static void close_bubbles(int gb[BOARDMAX]) { int bubbles[BOARDMAX]; int ii; int found_one = 1; memset(bubbles, 0, sizeof(bubbles)); while (found_one) { found_one = 0; for (ii = BOARDMIN; ii < BOARDMAX; ii++) { int white_neighbor = 0; int black_neighbor = 0; int new_color = 0; if (!ON_BOARD(ii) || gb[ii] || bubbles[ii] == GRAY) continue; /* If any neighbor is gray, mark the spot gray */ if ((ON_BOARD(SOUTH(ii)) && bubbles[SOUTH(ii)] == GRAY) || (ON_BOARD(WEST(ii)) && bubbles[WEST(ii)] == GRAY) || (ON_BOARD(NORTH(ii)) && bubbles[NORTH(ii)] == GRAY) || (ON_BOARD(EAST(ii)) && bubbles[EAST(ii)] == GRAY)) { found_one = 1; bubbles[ii] = GRAY; } else { /* Look for white neighbors, including the spot itself */ if (bubbles[ii] == WHITE || (ON_BOARD(SOUTH(ii)) && (gb[SOUTH(ii)] > 0 || bubbles[SOUTH(ii)] == WHITE)) || (ON_BOARD(WEST(ii)) && (gb[WEST(ii)] > 0 || bubbles[WEST(ii)] == WHITE)) || (ON_BOARD(NORTH(ii)) && (gb[NORTH(ii)] > 0 || bubbles[NORTH(ii)] == WHITE)) || (ON_BOARD(EAST(ii)) && (gb[EAST(ii)] > 0 || bubbles[EAST(ii)] == WHITE))) white_neighbor = 1; if (bubbles[ii] == BLACK || (ON_BOARD(SOUTH(ii)) && (gb[SOUTH(ii)] < 0 || bubbles[SOUTH(ii)] == BLACK)) || (ON_BOARD(WEST(ii)) && (gb[WEST(ii)] < 0 || bubbles[WEST(ii)] == BLACK)) || (ON_BOARD(NORTH(ii)) && (gb[NORTH(ii)] < 0 || bubbles[NORTH(ii)] == BLACK)) || (ON_BOARD(EAST(ii)) && (gb[EAST(ii)] < 0 || bubbles[EAST(ii)] == BLACK))) black_neighbor = 1; if (white_neighbor) { if (black_neighbor) new_color = GRAY; else new_color = WHITE; } else if (black_neighbor) new_color = BLACK; if (new_color && new_color != bubbles[ii]) { found_one = 1; bubbles[ii] = new_color; } } } } /* The bubbles are found and classified. Now adjoin them. */ for (ii = BOARDMIN; ii < BOARDMAX; ii++) { if (!ON_BOARD(ii) || gb[ii]) continue; if (bubbles[ii] == WHITE) gb[ii] = 1; if (bubbles[ii] == BLACK) gb[ii] = -1; } } /* Generic function to print the regions in gb, rendering * positive as white territory, negative as black. Stones * with status == DEAD are invisible and appear as * territory. */ static void print_regions(int gb[BOARDMAX]) { int i, j, k; int ii; start_draw_board(); for (i = 0; i < board_size; i++) { for (j = 0; j < board_size; j++) { ii = POS(i, j); if (board[ii] && dragon[ii].status != DEAD) k = board[ii]; else k = EMPTY; switch (k) { case EMPTY: if (gb[ii] > 0) draw_color_char(i, j, 'w', GG_COLOR_GREEN); else if (gb[ii] < 0) draw_color_char(i, j, 'b', GG_COLOR_MAGENTA); else draw_color_char(i, j, '.', GG_COLOR_BLACK); break; case BLACK: if (dragon[ii].status == CRITICAL) draw_color_char(i, j, 'X', GG_COLOR_RED); else draw_color_char(i, j, 'X', GG_COLOR_BLACK); break; case WHITE: if (dragon[ii].status == CRITICAL) draw_color_char(i, j, 'O', GG_COLOR_RED); else draw_color_char(i, j, 'O', GG_COLOR_BLACK); break; } } } end_draw_board(); } /* Print the moyo regions after a specified number * of dilations and erosions. NOTE: This partitioning * of the board into moyo, territory and area is obsolete, * and except for estimate_score() it is is not used by the * engine. Use instead print_influence_areas(). */ void print_moyo(void) { if (printmoyo & PRINTMOYO_TERRITORY) print_new_moyo(5, 21); if (printmoyo & PRINTMOYO_MOYO) print_new_moyo(5, 10); if (printmoyo & PRINTMOYO_AREA) { print_new_moyo(4, 0); } } static void print_new_moyo(int dilations, int erosions) { int gb[BOARDMAX]; dilate_erode(dilations, erosions, gb, WHITE); close_bubbles(gb); print_regions(gb); } /* Put upper and lower score estimates into *upper, *lower and * return the average. A positive score favors white. In computing * the upper bound, CRITICAL dragons are awarded to white; in * computing the lower bound, they are awarded to black. */ float estimate_score(float *upper, float *lower) { int gb[BOARDMAX]; float white_territory = 0.0; float black_territory = 0.0; float white_area = 0.0; float black_area = 0.0; int i, j; int ii; float u, l; int critical; critical = dilate_erode(5, 21, gb, WHITE); close_bubbles(gb); if (debug & DEBUG_SCORING) print_regions(gb); for (i = 0; i < board_size; i++) { int black_territory_in_row = 0; int white_territory_in_row = 0; int white_area_in_row = 0; int black_area_in_row = 0; for (j = 0; j < board_size; j++) { ii = POS(i, j); if (board[ii] == BLACK) { if (captured_territory(ii, WHITE)) { white_territory += 2; white_area++; white_territory_in_row += 2; white_area_in_row++; } else { black_area++; black_area_in_row++; } } else if (board[ii] == WHITE) { if (captured_territory(ii, WHITE)) { black_territory += 2; black_area++; black_territory_in_row += 2; black_area_in_row++; } else { white_area++; white_area_in_row++; } } else { if (gb[ii] > 0.0) { white_territory++; white_area++; white_territory_in_row++; white_area_in_row++; } else if (gb[ii] < 0.0) { black_territory++; black_area++; black_territory_in_row++; black_area_in_row++; } } } if (chinese_rules) { DEBUG(DEBUG_SCORING, "in row %d, white area=%d, black=%d\n", board_size - i, white_area_in_row, black_area_in_row); } else { DEBUG(DEBUG_SCORING, "in row %d, white territory=%d, black=%d\n", board_size - i, white_territory_in_row, black_territory_in_row); } } if (chinese_rules) u = white_area - black_area + komi; else { DEBUG(DEBUG_SCORING, "black captured: %d\nwhite captured: %d\nkomi: %f\n", black_captured, white_captured, komi); u = white_territory + black_captured - black_territory - white_captured + komi; } if (critical) { white_territory = 0.0; black_territory = 0.0; white_area = 0.0; black_area = 0.0; dilate_erode(5, 21, gb, BLACK); close_bubbles(gb); for (i = 0; i < board_size; i++) { int black_territory_in_row = 0; int white_territory_in_row = 0; int white_area_in_row = 0; int black_area_in_row = 0; for (j = 0; j < board_size; j++) { ii = POS(i, j); if (board[ii] == BLACK) { if (captured_territory(ii, BLACK)) { white_territory += 2; white_territory_in_row += 2; white_area++; white_area_in_row++; } else { black_area++; black_area_in_row++; } } else if (board[ii] == WHITE) { if (captured_territory(ii, BLACK)) { black_territory += 2; black_area++; black_territory_in_row += 2; black_area++; } else { white_area++; white_area_in_row++; } } else { if (gb[ii] > 0.0) { white_territory++; white_area++; white_territory_in_row++; white_area++; } else if (gb[ii] < 0.0) { black_territory++; black_area++; black_territory_in_row++; black_area_in_row++; } } } if (chinese_rules) { DEBUG(DEBUG_SCORING, "in row %d, white area=%d, black=%d\n", board_size-i, white_area_in_row, black_area_in_row); } else { DEBUG(DEBUG_SCORING, "in row %d, white territory=%d, black=%d\n", board_size-i, white_territory_in_row, black_territory_in_row); } } if (chinese_rules) l = white_area - black_area + komi; else { DEBUG(DEBUG_SCORING, "black captured: %d\nwhite captured: %d\nkomi: %f\n", black_captured, white_captured, komi); l = white_territory + black_captured - black_territory - white_captured + komi; } } else l = u; if (upper) *upper = u; if (lower) *lower = l; return (u + l) / 2; } /* We do not count dead stones inside the eyespace as territory. Such a * stone is characterized as having status DEAD yet having only * DEAD dragons as neighbors. * * Thus in this situation: * * XXXXXXX We do not count the X stone in the center as * XOOOOOX territory for O since the surrounding O dragon is * XO.X.OX dead. * XOOOOOX * XXXXXXX * * If (pos) is the location of a stone which is DEAD and which is * not an exception of this type then it is safe to count it as * two points territory for the opponent. This function tests for * this condition. * * CRITICAL dragons are awarded to 'color'. */ static int captured_territory(int pos, int color) { int d; if (board[pos] == EMPTY || dragon[pos].status == ALIVE || dragon[pos].status == UNKNOWN || (board[pos] == color && dragon[pos].status == CRITICAL)) return 0; if (DRAGON2(pos).neighbors == 0 && dragon[pos].status == DEAD) return 1; for (d = 0; d < DRAGON2(pos).neighbors; d++) if (DRAGON(DRAGON2(pos).adjacent[d]).color == OTHER_COLOR(board[pos]) && (DRAGON(DRAGON2(pos).adjacent[d]).status == ALIVE || (DRAGON(DRAGON2(pos).adjacent[d]).status == UNKNOWN && dragon2[DRAGON2(pos).adjacent[d]].weakness < .1) || (board[pos] != color && DRAGON(DRAGON2(pos).adjacent[d]).status == CRITICAL))) return 1; return 0; } /* * Local Variables: * tab-width: 8 * c-basic-offset: 2 * End: */