int CheckLadderUseSearch()

in go/board.cc [203:317]
86 lines of code
27 McCabe index (conditional complexity)

int CheckLadderUseSearch(Board *board, Stone victim, int *num_call, int depth) {
  (*num_call) ++;
  Coord c = board->_last_move;
  Coord c2 = board->_last_move2;
  unsigned short id = board->_infos[c].id;
  unsigned short lib = board->_groups[id].liberties;
  // char buf[30];
  GroupId4 ids;

  if (victim == OPPONENT(board->_next_player)) {
    // Capturer to play. He can choose two ways to capture.

    // Captured.
    if (lib == 1) return depth;
    // Not able to capture.
    if (lib >= 3) return 0;
    // Check if c's vicinity's two empty locations.
    Coord escape[2];
    int num_escape = 0;
    FOR4(c, _, cc) {
      if (board->_infos[cc].color == S_EMPTY) {
        escape[num_escape ++] = cc;
      }
    } ENDFOR4
    // Not a ladder.
    if (num_escape <= 1) return 0;

    // Play each possibility and recurse.
    // We can avoid copying if we are sure one branch cannot be right and only trace down the other.
    int freedom[2];
    Coord must_block = M_PASS;
    for (int i = 0; i < 2; ++i) {
      freedom[i] = 0;
      FOR4(escape[i], _, cc) {
        if (board->_infos[cc].color == S_EMPTY) {
          freedom[i] ++;
        }
      } ENDFOR4
      if (freedom[i] == 3) {
        // Then we have to block this.
        must_block = escape[i];
        break;
      }
    }

    // Check if we have too many branches. If so, stopping the branching.
    if (must_block == M_PASS && *num_call >= MAX_LADDER_SEARCH) {
      must_block = escape[0];
    }

    if (must_block != M_PASS) {
      // It suffices to only play must_block.
      if (TryPlay2(board, must_block, &ids)) {
        Play(board, &ids);
        int final_depth = CheckLadderUseSearch(board, victim, num_call, depth + 1);
        if (final_depth > 0) return final_depth;
      }
    } else {
      // printf("IsLadderUseSearch: Branching:\n");
      // printf("Choice 1: %s\n", get_move_str(escape[0], board->_next_player, buf));
      // printf("Choice 2: %s\n", get_move_str(escape[1], board->_next_player, buf));
      // ShowBoard(board, SHOW_ALL);

      // We need to play both. This should seldomly happen.
      Board b_next;
      CopyBoard(&b_next, board);
      if (TryPlay2(&b_next, escape[0], &ids)) {
        Play(&b_next, &ids);
        int final_depth = CheckLadderUseSearch(&b_next, victim, num_call, depth + 1);
        if (final_depth > 0) return final_depth;
      }

      if (TryPlay2(board, escape[1], &ids)) {
        Play(board, &ids);
        int final_depth = CheckLadderUseSearch(board, victim, num_call, depth + 1);
        if (final_depth > 0) return final_depth;
      }
    }
  } else {
    // Victim to play. In general he only has one choice because he is always in atari.
    // If the capturer place a stone in atari, then the capture fails.
    if (lib == 1) return 0;
    // Otherwise the victim need to continue fleeing.
    Coord flee_loc = M_PASS;
    FOR4(c2, _, cc) {
      if (board->_infos[cc].color == S_EMPTY) {
        flee_loc = cc;
        break;
      }
    } ENDFOR4
    // Make sure flee point is not empty
    if (flee_loc == M_PASS) {
      ShowBoard(board, SHOW_ALL);
      error("Error!! IsLadderUseSearch is wrong!\n");
      return 0;
    }
    if (TryPlay2(board, flee_loc, &ids)) {
      Play(board, &ids);
      unsigned char id = board->_infos[flee_loc].id;
      if (board->_groups[id].liberties >= 3) return 0;
      if (board->_groups[id].liberties == 2) {
        // Check if the neighboring enemy stone has only one liberty, if so, then it is not a ladder.
        FOR4(flee_loc, _, cc) {
          if (board->_infos[cc].color != OPPONENT(victim)) continue;
          unsigned char id2 = board->_infos[cc].id;
          // If the enemy group is in atari but our group has 2 liberties, then it is not a ladder.
          if (board->_groups[id2].liberties == 1) return 0;
        } ENDFOR4
      }
      int final_depth = CheckLadderUseSearch(board, victim, num_call, depth + 1);
      if (final_depth > 0) return final_depth;
    }
  }
  return 0;
}