float GetTrompTaylorScore()

in go/board.cc [1584:1688]
65 lines of code
24 McCabe index (conditional complexity)

float GetTrompTaylorScore(const Board *board, const Stone *group_stats, Stone *territory) {
  Stone * internal_territory = NULL;
  if (territory == NULL) {
    internal_territory = new Stone[BOARD_SIZE * BOARD_SIZE];
    territory = internal_territory;
  }
  ::memset(territory, S_EMPTY, BOARD_SIZE * BOARD_SIZE * sizeof(Stone));

  //
  Coord queue[BOARD_SIZE * BOARD_SIZE];
  int territories[4] = { 0, 0, 0, 0 };

  // Flood fill, starts with an empty location and expand.
  // The output territory is 1 = BLACK, 2 = WHITE, and 3 = DAME
  for (int i = 0; i < BOARD_SIZE; ++i) {
    for (int j = 0; j < BOARD_SIZE; ++j) {
      Coord c = OFFSETXY(i, j);
      Stone s = board->_infos[c].color;

      // printf("Check %s ... \n", get_move_str(c, s));
      // Skip any stone.
      if (s != S_EMPTY) {
        Stone *t = &territory[EXPORT_OFFSET(c)];
        if (*t == S_EMPTY) {
          // Get the true color of the stone
          unsigned char id = board->_infos[c].id;
          if (group_stats != NULL && (group_stats[id] & S_DEAD)) s = OPPONENT(s);
          *t = s;
          territories[s] ++;
        }
        continue;
      }

      // It is visited.
      if (territory[EXPORT_OFFSET_XY(i, j)] != S_EMPTY) continue;

      // Empty space and it is not visited.
      // Do DFS
      Stone owner = S_EMPTY;
      int q_start = 0, q_end = 0;
      queue[q_end ++] = c;
      territory[EXPORT_OFFSET(c)] = S_DAME;

      // printf("Start DFS ...\n");
      // fflush(stdout);
      while (q_end - q_start > 0) {
        Coord cc = queue[q_start ++];

        // printf("Visited %s..owner = %d\n", get_move_str(cc, board->_infos[cc].color), owner);
        // fflush(stdout);

        // Put its neighbor into the queue
        FOR4(cc, _, ccc) {
          Stone sss = board->_infos[ccc].color;
          if (sss != S_EMPTY) {
            if (sss != S_OFF_BOARD && owner != S_DAME) {
              Stone *t = &territory[EXPORT_OFFSET(ccc)];
              if (*t == S_EMPTY) {
                // Get the true color of the stone
                unsigned char id = board->_infos[ccc].id;
                if (group_stats != NULL && (group_stats[id] & S_DEAD)) sss = OPPONENT(sss);
                *t = sss;
                territories[sss] ++;
              }

              if (owner == S_EMPTY) owner = *t;
              else if (owner != *t) owner = S_DAME;
              // printf("sss = %d, owner = %d\n", *t, owner);
              // fflush(stdout);
            }
          } else if (territory[EXPORT_OFFSET(ccc)] == S_EMPTY) {
            // Make it visited with S_DAME
            territory[EXPORT_OFFSET(ccc)] = S_DAME;
            // Empty slot and empty territory, put them in.
            queue[q_end ++] = ccc;
          }
        } ENDFOR4
      }
      // Finish BFS, then we go through the visited again and set them to owner (if owner is not S_DAME).
      if (owner == S_EMPTY) {
        // Empty board.
        return 0.0;
      }
      if (owner != S_DAME) {
        for (int i = 0; i < q_end; ++i) {
          // printf("Deal with %s\n", get_move_str(queue[i], owner));
          // fflush(stdout);
          territory[EXPORT_OFFSET(queue[i])] = owner;
          // Each empty spot only visited once.
          territories[owner] ++;
        }
      }
      // Check whether we have visited all board locations, if so, just break.
      if (territories[S_BLACK] + territories[S_WHITE] == BOARD_SIZE * BOARD_SIZE) break;
      // fflush(stdout);
    }
  }

  if (internal_territory) delete [] internal_territory;

  // Finally count the score.
  // printf("black = %d\n", territories[S_BLACK]);
  // printf("white = %d\n", territories[S_WHITE]);
  return territories[S_BLACK] - territories[S_WHITE];
}