企业官网建设流程全解析

做棋类搜索的人大概都经历过这样一个下午：程序跑起来了，机器也老老实实落子，可每一步都透着古怪——明明能吃掉对方一个子，它偏要往角落里钻；把搜索深度从 3 调到 5，走法不但没变好，反而更离谱。你翻回代码，极小化极大算法写得工工整整，递归、终止条件、评估函数一样不缺；咬咬牙换成负极大值算法，把两段分支合并成一次取负，结果还是那样。折腾到半夜才反应过来：问题根本不在搜索框架上，而在价值函数的符号约定——评估函数返回的是"谁的分数"，搜索里又默认它是"谁的分数"，两个"谁"不是同一个人。

这篇东西就是围绕这条线展开的。极小化极大算法（Minimax）和负极大值算法（Negamax）在教科书里通常只占两页，公式干净得像艺术品，但真正落到代码里，麻烦全在符号、边界、剪枝窗口和返回语义这些"脏活"上。我会从最朴素的递归骨架讲起，把 Negamax 的等价性推一遍，然后重点拆 Alpha-Beta 剪枝打开之后那些必须同步修改的地方——取着方式、置换表条目类型、根节点处理，一个都不能漏。适合已经能写出能跑的搜索、但卡在"结果不对"或者"跑得太慢"这两道坎上的朋友；完全没接触过博弈树搜索的读者也能看懂，因为所有概念我都会用日常场景先铺垫一遍。

1. 搜错着法的那个夜晚：症状清单比答案更有用

先把症状摆出来，因为排查这类问题，能不能快速定位取决于你会不会"看症状"。我见过的情况基本可以归成四类，每类对应的根因范围都很窄。

第一类是深度变化导致结果反转。深度 2 时机器走得挺聪明，深度 4 时开始犯傻。这种最容易被误判成"搜索太深反而过拟合"，实际上多半是评估函数在奇偶层的视角反了——偶数层用对了符号，奇数层用反了，所以深度一变，最后落子的那一层视角就跟着变。井字棋这种小棋盘上一眼能看出来，换成棋盘大一点的游戏就极其隐蔽。

第二类是先后手互换后行为诡异。让机器执黑正常，执白就开始送子。这几乎是符号约定错误的铁证：评估函数里写了类似self.material[BLACK] - self.material[WHITE]这种固定视角的表达式，而搜索本身假设的是"当前行动方视角"。前半句是绝对的，后半句是相对的，两者一撞就出事。

第三类是剪枝和不剪枝结果不一致。关掉 Alpha-Beta 一切正常，打开就开始选烂棋。这通常不是剪枝算法本身错了，而是剪枝之后返回值不再是"真实值"而是"边界值"（fail-soft），而你的取着逻辑还在用"谁的分高选谁"的老思路去比较这些边界值。

第四类是同一局面反复搜索得到不同着法。分数一样但选择飘忽，多半是着法生成顺序不稳定（比如用了集合、字典的遍历顺序），导致同分着法的胜负判定随机。这在自对弈训练里会放大成大问题。

提示：这四类症状的排查顺序建议是「先查视角，再查剪枝，最后查排序」。视角错了，后面两项怎么调都是白费。

我个人的习惯是：写搜索之前先写一个只有一层的暴力版本，把每个候选着法走一步之后的评估值打印出来，人工核对这些数字符不符合直觉。井字棋的中心格应该比角格分高，角格应该比边格分高；黑白棋的角格应该远高于其他位置。如果这一步的数字就是反的，别往下写了，回头改评估函数。

2. 极小化极大算法的递归骨架：极大层与极小层到底在比什么

Minimax 的核心假设只有三条：双方都能看到完整局面（完全信息）、没有随机因素（确定性）、一方的收益等于另一方的损失（零和）。这三条成立，就可以把"我会怎么走"和"对手会怎么走"折叠成一个递归定义。

定义V(s)为局面s对根玩家的价值。如果s是终局，V(s)直接由胜负给出，比如赢+1000、输-1000、平0。如果轮到根玩家行动，那么V(s) = max(V(s'))，s'遍历所有走一步之后的局面；如果轮到对手行动，那么V(s) = min(V(s'))。就这么两条规则，交替递归到叶子。

这个定义的妙处在于它把"对手很强"这件事编码进了min里。你不需要知道对手会犯什么错，只需要假设他每一步都挑对你最不利的那个。这是一种悲观假设，但在零和完全信息博弈里，它是唯一站得住的假设——任何比这更乐观的假设都意味着你在赌对手失误，而赌对手失误在长对局里迟早要还。

代价是指数级的。设平均分支因子为b，搜索深度为d，节点数大约是b^d。井字棋的分支因子从 9 递减到 1，全空间也就 50 多万个节点，暴力搜完毫无压力。但换成 8×8 的黑白棋，开局分支因子约 10，中局大约 8~12，深度 8 就是上亿节点；换成 15×15 的五子棋，分支因子 200 以上，深度 4 就已经是天文数字。

看这张表就明白为什么光有 Minimax 不够。搜索本身是对的，但它跑不动。后面所有的工程手段——Negamax 简化、Alpha-Beta 剪枝、着法排序、置换表——本质上都是在不改变结果的前提下砍掉这张表里的节点。

最朴素的实现大概长这样，注意这里evaluate是根玩家视角，全局固定：

INF = float('inf') def minimax(state, depth, root_player): if state.is_terminal() or depth == 0: return state.evaluate_for(root_player) if state.player == root_player: # 极大层 best = -INF for move in state.legal_moves(): best = max(best, minimax(state.play(move), depth - 1, root_player)) return best else: # 极小层 best = INF for move in state.legal_moves(): best = min(best, minimax(state.play(move), depth - 1, root_player)) return best

这段代码能跑，而且对绝大多数初学者来说，第一版就应该这么写——它把"视角"这件事固定死了，不容易出错。但它的两个毛病也很明显：一是每一层都要判断"现在是谁的回合"，白写了一半代码；二是这个if/else结构一旦要加剪枝，就得维护两套窗口逻辑，出错概率翻倍。Negamax 就是来解决这两个问题的。

3. 负极大值算法做的那件事：把"对手最强"折叠成一次取负

Negamax 的全部依据是一条初中的恒等式：

max(a, b) = -min(-a, -b)

推广到整个列表就是max(x for x in X) = -min(-x for x in X)。这意味着，只要把子节点的分数取负再取最大，就等价于对子节点取最小。于是极小的那一层可以彻底删掉，所有节点统一写成"取最大值"的形式。

但这里有个前提，也是 Negamax 唯一需要小心的地方：价值函数的视角必须跟着行动方走。也就是说，evaluate(state)必须返回"轮到走棋的这一方比对手领先多少"，而不是"黑方比白方领先多少"。视角一换，取负才有意义——父节点说"这个局面我领先 3 分"，子节点（对手行动）就应该说"这个局面我落后 3 分"，也就是-3。

写成代码是这样：

def negamax(state, depth, alpha, beta): if state.is_terminal(): return state.terminal_value() # 当前行动方视角，输为负 if depth == 0: return state.evaluate() # 当前行动方视角 best = -INF for move in state.legal_moves(): child = state.play(move) score = -negamax(child, depth - 1, -beta, -alpha) if score > best: best = score if best > alpha: alpha = best if alpha >= beta: break return best

对比一下第 2 节那段：少了一个if/else，少了一个root_player参数，max和min合并成了-号加max。行数直接砍掉四成，剪枝逻辑也只需要维护一套。

很多人第一次看到-negamax(child, depth-1, -beta, -alpha)里的窗口翻转会懵。这里的直觉其实很简单：父节点传给子节点的窗口[alpha, beta]是父方视角的，意思是"父方至少能拿到 alpha，至多能拿到 beta"。换算到子方视角，父方拿到 alpha 就等于子方丢了 alpha，所以子方的上界是-alpha；父方的上界 beta 换算过来就是子方的下界-beta。窗口端点的顺序要保持"左小右大"，所以就写成了(-beta, -alpha)。记不住也没关系，把这条当成模板背下来，只需记住"两个都取负，顺序颠倒"。

关于等价性，可以直接用归纳法证明：假设深度为d-1时 Negamax 返回的确实是子节点行动方视角的极小化极大值，那么深度为d时，父方对每个子局面的真实价值是-V(child)（因为子局面里对手领先的，就是父方落后的），父方要选使这个值最大的着法，也就是max(-V(child)) = -min(V(child))，正是对手取最优的语义。基例是叶子和终局，由评估函数定义保证。

这里有个容易被忽略的边界：终局值的方向。如果一个局面已经是终局，那么"当前行动方"其实是上一手落子之后的输家（对手刚赢了），所以终局值应该返回负数。这是一个高频错误点，代码往往写成：

def terminal_value(self): w = self.winner() if w == 0: return 0 # 平局 return 1 if w == self.player else -1

逻辑是对的，但如果你的胜负判定返回的是"赢家是谁（1 或 -1）"，而self.player是"轮到谁"，那么w == self.player在终局里几乎永远为假——因为赢家刚走完，轮到的已经不是他了。所以更稳妥的写法是直接返回负分，再乘上一个随深度衰减的系数（越早输越糟糕）：

def terminal_value(self, ply): if self.winner() == 0: return 0 return -(1000 - ply) # 当前行动方已输

顺带一提，如果你要做带随机事件的游戏（比如掷骰子走子），模型会变成"期望极小极大"，多出一类机会节点。机会节点取的是期望而不是最大最小，但期望是线性的，E[-X] = -E[X]依然成立，所以 Negamax 的取负写法照样能用。唯一要小心的是：机会节点不属于任何一方，别在里面多做一次取负。

4. 评估函数的视角约定：符号翻转类 bug 最集中的地方

前面反复提到"当前行动方视角"，这一节把它彻底讲清楚，因为实际项目里八成以上的"结果不对"都源于此。

先看一个错误的写法，这段代码在只有黑方搜索、且只搜奇数深度的时候完全正常，所以能骗过很多测试：

def evaluate(self): # 错误：固定成黑方视角 return self.material[BLACK] - self.material[WHITE]

塞进 Negamax 之后：根节点（假设黑方行动）返回值是"黑减白"，没问题。子节点（白方行动）返回值也是"黑减白"，父节点取负之后变成"白减黑"，语义就乱了——父节点本来期待的是"黑方领先多少"，结果拿到的是"白方领先多少"的负值，恰好等于黑方领先的相反数。于是根节点在选择时会把好的着法当成坏的。

正确的写法只有一句话：分数永远站在"将要落子的那一方"这边。

def evaluate(self): me = self.player opp = -me return self.material[me] - self.material[opp]

如果嫌每次查字典麻烦，可以用self.player乘以一个"绝对分差"，因为player是 +1 或 -1：

def evaluate(self): diff = self.pieces_count(1) - self.pieces_count(-1) # 绝对的 黑减白 return diff * self.player # 轮到黑时 +diff，轮到白时 -diff

第二种写法更简洁，也更容易验证：轮到黑方时player=1，返回黑减白；轮到白方时player=-1，返回白减黑。一眼就能看出是对的。

除了主评估值，还有一些"局部特征"同样需要检查视角。比如"某个位置被对手控制"的惩罚项、"下一步能吃子"的奖励项。这些项如果内部使用了固定的颜色常量，就会在整个评估里混入两个视角的分量，结果既不是黑方视角也不是白方视角，而是一个毫无意义的混合体。它的症状是：搜索能跑、也能出着法，但明显不如下棋，分数差距很小（因为正负项互相抵消）。

注意：排查这类混合视角问题，光看总分没用。把评估函数拆成若干项，每项单独打印，然后在同一个局面下交换self.player再打印一次，两次结果应该严格互为相反数。只要有一项不满足，那一项就是错的。

还有一个更隐蔽的坑：评估函数里偷偷读取了外部状态。比如用一个全局变量记录"根玩家是谁"，然后所有层都拿它做参照。这在单线程单次搜索里没问题，一旦上了迭代加深、多线程并行搜索、或者自对弈训练，全局状态一变，整棵树的价值就全乱了。评估函数应该是纯函数，只依赖传入的局面。

最后提醒一点关于数值范围的事。很多实现用±INF作为初始的best和窗口边界，如果评估值本身可能取到很大的数（比如用"棋子数 × 1000"这种量级），INF设得太小（比如9999）就会导致"值被窗口截断"，表现为搜索在某些局面下突然给出最差着法。稳妥做法是把INF设成评估函数理论最大值的十倍以上，同时确保终局分数的绝对值不会和普通评估值混淆。

5. Alpha-Beta 剪枝的合法性：凭什么丢掉的分支不影响结论

剪枝这件事，最容易被误解成"近似算法"。它其实是精确的：只要实现正确，剪枝后的结果和不剪枝的结果一模一样，一个比特都不差。

用一个讨价还价的场景来理解。假设你去买一件二手家具，卖家开价一千。你心里有个底线：超过六百就不买。你开始一路砍价，砍到五百八的时候卖家说"最低七百"。这时候你根本不需要还价到六百五、七百，也不需要确认卖家还能不能降到六百——因为只要最后成交价不低于六百，你都不会要。剩下那些还价方案，谈下去纯属浪费时间。Alpha-Beta 做的就是这件事：当某个分支已经能证明"不比已有的选择更好"时，直接放弃整个分支。

形式化一点：alpha是当前节点已经确保能拿到的下界（从当前行动方视角），beta是上界——超过这个上界，祖先那一层根本不会选这条路。当alpha >= beta，说明这个节点的真实值已经不重要了：父方要么不会选它（因为已经有更好的），要么不会进入它（因为超出容忍范围）。两种情况都可以提前返回。

对应到代码里，alpha的更新逻辑和普通搜索完全一样：

best = -INF for move in state.legal_moves(): score = -negamax(child, depth - 1, -beta, -alpha) if score > best: best = score if best > alpha: alpha = best # 提升下界 if alpha >= beta: break # 上界被击穿，本分支作废

关键的实现细节在于传参顺序和剪枝条件的方向，这两处出错的表现是"剪枝后搜出来的着法明显是烂棋，但不剪枝就正常"。

negamax(child, depth-1, -beta, -alpha)这里，-beta对应子节点的alpha，-alpha对应子节点的beta。为什么？成长路径是这样的：父节点在为一个"至少 alpha"的结果努力，那么子节点（对手）的目标就是把这个结果压到"最多 -alpha"；父节点能接受的极限是 beta，那么子节点必须保证自己至少能拿到-beta才有意义。窗口一旦翻转，端点的角色也翻转了，但"左小右大"的排列不能变——所以得先放-beta再放-alpha。写成(-alpha, -beta)就变成了无效窗口（左大于右），剪枝会乱剪。

alpha >= beta这个条件里，>=和>都对，但语义不同。用>=配break是标准写法，简洁有效。用>也能工作，只是剪枝效率略低。真正需要留意的是返回值的语义，这就引出了下一节的核心冲突。

再讲一个剪枝效率的直觉：Alpha-Beta 的效果极度依赖着法顺序。如果每次都恰好先搜到最好的着法，节点数会从b^d降到b^(d/2)——也就是同样时间内能搜两倍的深度，这是数量级的提升。如果顺序恰好最差（先搜最烂的），剪枝几乎不起作用，退化回完整搜索。这就是为什么工程上要花大力气做着法排序：吃子优先、杀手着法、历史启发，全都是为了把"好着法"往前挪。

6. 剪枝打开以后，取着方式和返回值语义都得跟着改

这是实际开发中最容易吃亏的一节。很多人把 Alpha-Beta 加进去之后，分数看起来是对的，但选出来的着法错了，而且是那种"分数一样、着法莫名其妙"的错。根因在于：剪枝之后的返回值不再是"这个局面的真实价值"，而是一个边界值。

具体来说，在 fail-soft 实现里：

• 如果某个节点没有发生剪枝，返回的是真实的极大值，这个值叫精确值。
• 如果节点是因为alpha >= beta提前返回的，返回的值可能低于真实值（因为后面的兄弟着法没搜），也可能高于真实值——取决于你返回的是best还是beta。

这直接影响到置换表的设计。置换表用哈希键存储"这个局面在某个深度下的搜索结论"，但如果结论是个边界值，下次复用时就可能用错。所以表项必须带上类型标记：

实现时要注意保存alpha的原始值再更新，否则判断 UPPER 的条件会被污染：

alpha_orig = alpha best = -INF for move in ordered_moves(state): score = -negamax(state.play(move), depth - 1, -beta, -alpha) if score > best: best = score if best > alpha: alpha = best if alpha >= beta: break if best <= alpha_orig: tt_store(key, depth, best, UPPER) elif best >= beta: tt_store(key, depth, best, LOWER) else: tt_store(key, depth, best, EXACT)

如果嫌复杂，第一版可以先不上置换表，等搜索深度到 6 以上、重复局面明显增多的时候再加。

回到取着。根节点的处理必须单独写，不要指望在递归函数里挂个全局变量记录 best_move。原因有两个：一是根节点一般不做剪枝（窗口是±INF），但一旦引入空窗口搜索（PVS/NegaScout）它就会剪；二是记录 best_move 的时机必须和alpha的更新严格同步，否则会把"分数更高但在窗口外被截断"的着法误记成最优。

标准写法：

def search_root(state, depth): best_move, best_score = None, -INF alpha, beta = -INF, INF for move in ordered_moves(state): child = state.play(move) score = -negamax(child, depth - 1, -beta, -alpha) if score > best_score: best_score = score best_move = move if score > alpha: alpha = score return best_move, best_score

注意best_score和alpha是两个变量。很多人图省事只用一个alpha，然后在if best_score > alpha里记录着法，结果因为更新顺序的问题，第一个着法永远被记录（初始alpha是-INF，第一个着法必然大于它），后面同分的着法再也不更新。这在"第一个着法恰好是最差的"时候会表现得很明显。

还有同分着法的确定性问题。if score > best_score保留的是第一个遇到的最高分着法，所以最终选谁取决于ordered_moves的顺序。如果这个顺序来自集合遍历，每次运行都可能不同，自对弈时会出现"同一局面重开两次走了不同的棋"。解决办法很简单：着法用列表存储，排序时用稳定的排序键（比如先按位置索引，再按启发值），保证同一局面永远生成同样的顺序。这不影响正确性，但影响可复现性——做实验的时候，可复现比什么都重要。

7. 深度、地平线与着法排序：让搜索结果真正可用的三件事

搜索写对了是一回事，搜出来能下棋是另一回事。这一节讲三个从"能跑"到"能用"必须跨过的坎。

第一坎：固定深度的地平线效应。搜索到第d层就停下来做静态评估，问题是这第d层里可能正藏着一场灾难。举个典型场景：你的搜索在深度 4 时看到"再走一步就能吃掉对方一个大子"，评价极高；但真实对局里，对方在第 5 步有一手反吃，直接让你亏更多。搜索没看到第 5 步，是因为它被地平线挡住了。这个现象叫地平线效应，是所有固定深度搜索的通病。

缓解办法是静态搜索（quiescence search）：主搜索到达深度 0 之后，不立刻返回评估值，而是继续只搜索"吃子"这类强制性的着法，直到局面"安静"为止。因为只有这类着法才会让评估值剧烈波动，而安静局面下的评估相对可靠。

def quiescence(state, alpha, beta): stand_pat = state.evaluate() if stand_pat >= beta: return beta if stand_pat > alpha: alpha = stand_pat for move in state.capture_moves(): score = -quiescence(state.play(move), -beta, -alpha) if score >= beta: return beta if score > alpha: alpha = score return alpha

注意这里返回的是beta或alpha（fail-hard），不是best。静态搜索里混用两种语义很容易把分数量级搞乱，建议整个项目统一一种。

第二坎：着法排序。前面说过，剪枝效率取决于顺序。实测下来，性价比最高的排序策略是这几条叠加：

MVV-LVA 是"最有价值受害者—最无价值攻击者"的缩写，打分方式是被吃子价值 × 10 - 吃子方价值。这条规则背后的逻辑是：用兵吃车几乎必定是好事，用车吃兵几乎必定是坏事，按这个顺序搜，好着法更早出现。杀手着法指的是"在某一层曾经导致剪枝、但当前局面并不存在的着法"，它们往往在同一层反复有效。

排序的开销不能忽视。全排序（sort）是O(n log n)，深搜里调用次数巨大。常见的折中做法是只做部分排序：先把置换表着法和吃子着法挑到前面，剩下的保持原序，用max边搜边选。省下的排序时间往往比多搜几个节点更划算。

第三坎：迭代加深与时间控制。与其一次搜到深度 8，不如从深度 1 开始，逐层加深到 8。听起来浪费，实际更快——因为浅层搜索的结果给深层提供了极好的着法排序，剪枝效率大幅提升。而且它天然解决了"不知道搜多深合适"的问题：给定一个时间预算，搜到哪层算哪层，随时能停下来。

def iterative_deepening(state, time_budget): best_move, best_score = None, -INF deadline = time.time() + time_budget for depth in range(1, MAX_DEPTH + 1): move, score = search_root(state, depth) base[state.hash()] = move # 供下一层排序用 best_move, best_score = move, score if time.time() > deadline: break return best_move, best_score

有个细节要注意：逐层加深时，未搜完的那一层结果必须丢弃，只能用上一层完整搜完的结果。因为半层搜索的着法排序是不完整的，给出的最优着法可能只是"这一层第一个搜到的"。判断"是否搜完"的办法是自己维护一个计数器，而不是靠时间戳——时间戳在各层之间的粒度太粗。

8. 用参考实现对拍：小棋盘上的穷举验证与调试手法

所有前面讲的坑，最终都要靠验证兜底。我的习惯是：每写一个优化版本，就留一个"笨但正确"的参考实现，两者对拍。参考实现不用剪枝、不用置换表、不用排序，慢得离谱但绝对可信。

def negamax_reference(state, depth): """无剪枝参考实现，返回值恒为当前行动方视角的真实值""" if state.is_terminal(): return state.terminal_value() if depth == 0: return state.evaluate() best = -INF for move in state.legal_moves(): score = -negamax_reference(state.play(move), depth - 1) best = max(best, score) return best

对拍的时候要注意，negamax_reference返回的是根节点（根节点行动方）视角的值，而带剪枝的版本返回的是同一个东西——因为根节点的行动方就是"当前行动方"，视角一致。所以两者的返回值应该严格相等，不是近似相等。如果出现不等，那一定是剪枝逻辑有问题。

对拍不能只测一个局面。写个随机局面生成器，批量跑几百个：

def self_check(rounds=300, max_depth=4): for _ in range(rounds): state = random_state() for depth in range(1, max_depth + 1): ref = negamax_reference(state, depth) got = negamax_ab(state, depth) # 带 Alpha-Beta if ref != got: print(f"不一致: depth={depth}, ref={ref}, got={got}") print(state.render()) return False return True

跑出不一致的时候，别急着改代码，先把最小复现局面揪出来。方法是二分：如果在深度 4 不一致，先测深度 1、2、3，找出最早出问题的深度；然后把该局面下的所有着法逐个走一遍，对每个子局面再跑一次对拍，递归下去，通常三步之内就能定位到具体是哪个分支开始出现偏差。

调试视角类 bug 有个很好用的小技巧：在叶子节点打印两行，一行是state.player，一行是state.evaluate()，然后对照棋盘看一眼——如果轮到黑方，评估值却是"白方领先"的正数，心里就有数了。这个方法比在递归里打一堆断点快得多。

还有一个检查我每次必做：检查分数分布的对称性。把棋盘的双方颜色对调（同时把行动方也调换），搜索得到的值应该严格变为相反数。如果对调之后值不变，或者变成别的数，说明评估函数里存在不对称的特征项——比如某个方向的位置加权只给了一方、某个棋子类型的价值表只在一边生效。这类问题在手工调参的时候特别容易引入，而且不会报错，只会让棋力莫名其妙地下降。

提示：颜色对调测试最好写成一个固定的单元测试，每次改评估函数都跑一遍。三行代码，能挡掉后面无数次"怎么感觉不如昨天"的困惑。

最后说一个工程上的习惯：把搜索的**主变例（PV）**打印出来。PV 就是从根节点一路沿着最优着法走下去的那条路径。如果 PV 显示出"我的最优走法是自娱自乐，对手全程没有回应"，那基本可以确定是对手层的价值没被正确取负——因为搜索根本没把对手当回事，自然不会考虑对手的回应。PV 是排查这类"看起来对其实不对"问题最快的一把刀。

这套组合拳——参考实现对拍、颜色对调检查、主变例打印——是我在写任何博弈搜索时都会先搭起来的三件套。搭一次不到一小时，后面能省下的时间不止几十个小时。