AI不需要搜索所有空位——候选位置生成是AI性能的关键

设计截图如下：

为什么需要候选位置

15x15棋盘有225个位置。如果AI每步都搜索所有空位：

• 225个候选 × 225个候选 × … = 指数爆炸
• 即使搜索深度2，也需要评估50625个局面

实际策略：只搜索已有棋子周围的位置。因为远离现有棋子的落子几乎没有战术价值。

getCandidateMoves方法

getCandidateMoves(range: number = 2): Move[] {
  const candidates: Move[] = [];
  const seen: Set<string> = new Set();

  for (let i = 0; i < BOARD_SIZE; i++) {
    for (let j = 0; j < BOARD_SIZE; j++) {
      if (this.board[i][j] !== EMPTY) {
        // 以这个棋子为中心，扫描range范围内的空位
        for (let dr = -range; dr <= range; dr++) {
          for (let dc = -range; dc <= range; dc++) {
            const r = i + dr;
            const c = j + dc;
            if (r >= 0 && r < BOARD_SIZE && c >= 0 && c < BOARD_SIZE) {
              if (this.board[r][c] === EMPTY) {
                const key = `${r},${c}`;
                if (!seen.has(key)) {
                  seen.add(key);
                  candidates.push(new Move(r, c));
                }
              }
            }
          }
        }
      }
    }
  }
  return candidates;
}

算法图解

假设棋盘上有两个棋子（●），range=2：

    0  1  2  3  4  5  6
  ┌──┬──┬──┬──┬──┬──┬──┐
0 │  │  │ ✓│ ✓│ ✓│  │  │
  ├──┼──┼──┼──┼──┼──┼──┤
1 │  │  │ ✓│ ●│ ✓│  │  │
  ├──┼──┼──┼──┼──┼──┼──┤
2 │ ✓│ ✓│ ✓│ ✓│ ✓│ ✓│ ✓│
  ├──┼──┼──┼──┼──┼──┼──┤
3 │ ✓│ ●│ ✓│ ✓│ ✓│ ✓│ ✓│
  ├──┼──┼──┼──┼──┼──┼──┤
4 │ ✓│ ✓│ ✓│ ✓│ ✓│ ✓│ ✓│
  └──┴──┴──┴──┴──┴──┴──┘

✓ = 候选位置（空位且在某个棋子的range范围内）

Set去重机制

const seen: Set<string> = new Set();
const key = `${r},${c}`;
if (!seen.has(key)) {
  seen.add(key);
  candidates.push(new Move(r, c));
}

两个相邻棋子的range范围会重叠，同一个空位可能被多次发现。用Set的has操作去重，保证每个位置只出现一次。

为什么用字符串key而非对象？ 因为JavaScript/ArkTS的对象引用比较不适合Set去重，字符串"r,c"是唯一且可比较的。

range参数的意义

getCandidateMoves(range: number = 2): Move[]

• range=1：只搜索紧邻位置，候选少但速度快
• range=2（默认）：搜索2格范围，平衡速度和质量
• range=3：搜索3格范围，候选多但可能包含低价值位置

AIPlayer中默认使用range=2：

const candidates = this.getCandidates(board, 2);

AIPlayer中的getCandidates

AIPlayer有自己的候选生成方法（因为不持有引擎实例）：

private getCandidates(board: number[][], range: number = 2): Move[] {
  // 逻辑与GomokuEngine.getCandidateMoves完全一致
  // ...
  if (candidates.length === 0) {
    candidates.push(new Move(7, 7));  // 空棋盘下天元
  }
  return candidates;
}

多了一个兜底逻辑：如果没有候选（空棋盘），返回天元(7,7)。

候选数量分析

棋子数	range=1候选	range=2候选
1	~8	~24
5	~25	~60
10	~35	~80
20	~50	~100

相比225个全量位置，候选生成将搜索空间缩小到1/3到1/4。

getSortedCandidates：进一步优化

困难模式下，AI不仅生成候选，还按评分排序：

private getSortedCandidates(board: number[][]): Move[] {
  const candidates = this.getCandidates(board, 2);
  const scored: ScoredMove[] = [];

  for (const move of candidates) {
    board[move.row][move.col] = this.aiColor;
    const attack = this.evaluatePosition(board, move.row, move.col, this.aiColor);
    board[move.row][move.col] = EMPTY;

    board[move.row][move.col] = this.humanColor;
    const defend = this.evaluatePosition(board, move.row, move.col, this.humanColor);
    board[move.row][move.col] = EMPTY;

    scored.push(new ScoredMove(move, attack + defend));
  }

  scored.sort((a: ScoredMove, b: ScoredMove) => b.score - a.score);
  return scored.map((s: ScoredMove) => s.move);
}

排序后只取前12个候选进行Minimax搜索：

const candidates = this.getSortedCandidates(board);
const maxCandidates = Math.min(12, candidates.length);

两层过滤策略：

1. 空间过滤：只搜索棋子周围2格 → ~50个候选
2. 评分过滤：只搜索评分最高的12个 → 12个候选

总结

候选位置生成是AI性能的关键优化：

1. 空间剪枝：只搜索棋子周围的位置
2. Set去重：避免重复位置
3. 评分排序：优先搜索高价值位置
4. 数量限制：控制搜索宽度

这些优化使得困难模式的Minimax搜索（深度2，宽度12）在移动端也能流畅运行。