搜索树画得再漂亮规则写错分数也没有意义。黑白棋里一个很容易遗漏的分支是轮到自己时没有合法落子是否立即结束按 Othello 规则应交给对方继续双方都不能落子才结束。不能自愿放弃一手也不能把单方无合法动作直接判成终局。本文把棋盘缩成 4×4 做教学练习不声称复现标准 8×8 对局强度。先固定“深度”的单位这里的深度指还能放下多少枚棋子。pass 没有落子因此不扣减深度。换成“经过多少个回合”的定义也可以但所有实现、测试和说明必须使用同一口径。分数始终从黑方看黑子数减白子数。黑方取最大白方取最小。到终局时它是明确的棋子差搜索提前截断时它只是简陋估值不能据此保证整局最优。Berkeley 的教材把 Minimax、Alpha-Beta 与截断估值分别解释。剪枝能省去不影响当前结果的分支并不会让一个粗糙估值突然变准。CS188 教材一个能运行的缩小版规则与搜索棋盘用不可变字符串元组表示每次落子返回新棋盘避免“搜索回来忘记翻回一颗棋子”。下面同时包含八方向翻子、pass、终局和可开关的剪枝。DIRECTIONS [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if dr or dc] def moves(board, player): n, opponent len(board), W if player B else B result {} for r in range(n): for c in range(n): if board[r][c] ! .: continue flips [] for dr, dc in DIRECTIONS: line, x, y [], r dr, c dc while 0 x n and 0 y n and board[x][y] opponent: line.append((x, y)) x, y x dr, y dc if line and 0 x n and 0 y n and board[x][y] player: flips.extend(line) if flips: result[(r, c)] flips return result def play(board, position, flips, player): rows [list(row) for row in board] for r, c in [position] flips: rows[r][c] player return tuple(.join(row) for row in rows) def score(board): return sum(row.count(B) - row.count(W) for row in board) def search(board, player, depth, pruneTrue, alpha-1000, beta1000): legal moves(board, player) other W if player B else B if not legal: if not moves(board, other): return score(board) return search(board, other, depth, prune, alpha, beta) if depth 0: return score(board) best -1000 if player B else 1000 for position, flips in legal.items(): value search(play(board, position, flips, player), other, depth - 1, prune, alpha, beta) if player B: best, alpha max(best, value), max(alpha, value) else: best, beta min(best, value), min(beta, value) if prune and alpha beta: break return best initial (...., .WB., .BW., ....) assert len(moves(initial, B)) 4 roots [initial] [play(initial, pos, flips, B) for pos, flips in moves(initial, B).items()] for board in roots: before board assert search(board, B, 3, True) search(board, B, 3, False) assert board before pass_case (.WBB, BBBB, BBBB, BBBB) assert not moves(pass_case, W) and moves(pass_case, B) assert search(pass_case, W, 1) 16 assert search((BBBB,) * 4, W, 3) 16 print(5 roots agree; pass and terminal checked)本地 Python 3.9.6 运行通过。测试比较了初始局面及四个一步后局面的两种搜索结果另检查一个构造的 pass 局面和满盘终局。它不是所有可达局面的穷举不能把这些断言数量当成引擎正确率。pass 测试尤其重要白方不能下但黑方还能填左上角并翻白子如果程序提前返回当前子数差就会与真正走完后的 16 不同。这个反例不需要模型参与也能抓住规则层的错误。最后再讨论节点数比较节点访问量时要固定落子顺序、深度和计数定义。是否把 pass 算一个访问是否复用置换表都可能改变数字。不同顺序即使返回相同结果剪枝数量也可能不同。本例没有公布耗时或节点胜负。它先回答三个更基础的问题规则有没有表达完整剪枝开关是否保持结果搜索会不会破坏输入棋盘。后面若接模型生成代码应使用这类测试验收输出而不是从一段自然语言推演推断它的内部搜索机制。规则参考World Othello Federation 对 pass 与终局的说明2020-08-02历史规则材料。