做棋类AI，搜索算法永远是躲不开的核心话题。最近有好几个读者私信问我在Unity里实现棋类对战AI的思路，从五子棋到象棋再到自创的小棋种都有。我梳理了一下，干脆把Unity环境下棋类游戏智能搜索算法的完整实践写出来，从最朴素的Minimax到α-β剪枝、迭代加深、走法排序，再到Unity特有的Job System优化，一条链路讲清楚。这篇文章适合刚入门棋类AI、被搜索效率卡住、或者想在回合制游戏里加入可调难度AI的开发者，文中所有代码都是C#，可以直接在Unity工程里跑通。

1. 棋类AI搜索算法的起点：为什么Minimax是绕不开的基础

1.1 棋类博弈的本质：信息完备的零和对抗

棋类游戏和动作游戏、卡牌游戏最大的区别在于——对局双方看到的信息完全一致，每个回合的状态转换是确定的，不存在随机性。意思是，在这类游戏里，AI不需要处理不确定信息，它需要的只是一个能在当前局面下枚举所有合法走法的"规则引擎"，以及一个用来评价"这个局面到底谁占优"的评估函数。有了这两个东西，理论上可以枚举所有可能走法，选一条对自己最有利的路径。大学的时候我参加校内AI对抗赛，当时指导我的某导师说过一句让我印象很深的话：棋类搜索不是"找一步好棋"，而是"让对方找不到好棋"。Minimax算法就是把这句话数学化的产物。

1.2 Minimax的核心逻辑与初始实现

Minimax的思路不复杂。假设当前是己方回合，我们把所有合法走法都"试走"一遍，得到下一层局面；再站在对方视角，假设对方也会选择对自己最有利、对我们最不利的走法，这样交替递归下去。到了预设深度（比如4层），就停止搜索，用评估函数给局面打分。分数越高代表对己方越有利。向上回溯时，己方节点取子节点最大值，对方节点取子节点最小值。

用伪代码可以写得更清楚：

float Minimax(GameState state, int depth, bool isMaximizingPlayer) { if (depth == 0 || state.IsGameOver()) return Evaluate(state); if (isMaximizingPlayer) { float maxEval = float.NegativeInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval = Minimax(state, depth - 1, false); state.UndoMove(move); maxEval = Mathf.Max(maxEval, eval); } return maxEval; } else { float minEval = float.PositiveInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval = Minimax(state, depth - 1, true); state.UndoMove(move); minEval = Mathf.Min(minEval, eval); } return minEval; } }

层数每加深一层，工作量成指数增长。以国际象棋为例，平均分支因子大约35，搜索4层需要评估35^4约150万个节点，深度加到6层就是18亿个节点。纯粹用Minimax在Unity里跑，2层能实时响应，3层就开始卡顿，4层直接吃满主线程。这也是为什么Minimax只适合做入门demo或者棋类规则极简（比如井字棋）的游戏。

1.3 负极大值形式：让代码少一半

Minimax用"交替取最大最小"的方式写，逻辑清晰，但代码里每个节点都要判断当前是谁的回合，有点冗余。在实战项目里，我更推荐用Negamax（负极大值）形式。它利用了一个性质：对任意局面，己方的最优收益，等于对方的最优收益的相反数。这样递归函数只需要一直做"取最大值"操作，配合评估函数时注意"分数始终以当前走棋方为正"即可。

float Negamax(GameState state, int depth) { if (depth == 0 || state.IsGameOver()) return Evaluate(state); float maxEval = float.NegativeInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval = -Negamax(state, depth - 1); state.UndoMove(move); maxEval = Mathf.Max(maxEval, eval); } return maxEval; }

这里有一个必须注意的细节，评估函数的分数必须始终站在"当前走棋方"的角度：当前走棋方优势为正，劣势为负。这样递归中取负号才成立。很多人第一次写Negamax，结果评估函数仍然站在固定一方角度去打分，导致整个搜索树逻辑错乱，搜索出来的"最优走法"完全没法看。这个问题我至少见过三个人踩过。

在真正进入剪枝优化之前，我建议先把Negamax的递归结构、走法生成、局面回滚这套基本功做扎实。不要急着上α-β剪枝，因为剪枝是建立在"基础搜索能正确返回结果"之上的。如果搜索本身就是错的，剪枝只会更快地返回错误答案。

2. 剪枝与走法排序：让搜索树从能跑变成能打

2.1 α-β剪枝的直觉理解与实现

α-β剪枝不改变搜索结果，它只是把"肯定不会被选择"的分支提前砍掉。还是拿一个具体场景来模拟。假设当前节点是己方取最大，我们已经搜完了一个分支，得到分数3。这时候进入下一个分支，第一个子节点返回2，那么后面的走法还有必要看吗？没有必要了，因为对方在这个节点上会取最小的2给我们，而2已经小于3了，己方永远不可能在这个分支获得比3更优的结果。于是整个分支都可以放弃。

实现上，我们给递归函数传两个参数：α表示当前路径上己方已知的下界，β表示对方已知的上界。当某个节点的返回值超过β时，直接剪断。伪代码如下：

float AlphaBeta(GameState state, int depth, float alpha, float beta) { if (depth == 0 || state.IsGameOver()) return Evaluate(state); float maxEval = float.NegativeInfinity; foreach (var move in state.GetLegalMoves()) { state.ApplyMove(move); float eval = -AlphaBeta(state, depth - 1, -beta, -alpha); state.UndoMove(move); maxEval = Mathf.Max(maxEval, eval); alpha = Mathf.Max(alpha, eval); if (alpha >= beta) break; // beta剪枝 } return maxEval; }

注意这里负号的取法：递归调用时把α、β取反并互换位置，这是Negamax形式和α-β剪枝结合的常见写法，数学上等价于普通的Minimax版本，但代码更简洁。我在某跨平台系统项目里用这套写法，把原来的搜索深度从4层提到了7层，耗时基本不变。

2.2 剪枝效率的关键：走法排序决定一切

很多人以为α-β剪枝的优化幅度是固定的，其实不是。剪枝效率强烈依赖于走法的搜索顺序：如果每次第一个搜索的都是最好的走法，那么后续走法几乎全都能被剪掉，节点数可以逼近理论最优值，大约是原始搜索树大小的平方根量级。反过来，如果你每次先搜最差的走法，剪枝几乎不发生，性能退化回普通Minimax。

所以走法排序是α-β剪枝真正拉开差距的地方。常用的排序策略分几个层次。

第一层是"静态启发"。在生成走法后，先给每个走法算一个粗糙的优先级，然后按优先级排序。比如在国际象棋里，吃子走法优先，而且吃的子价值越高、吃的子越便宜，优先级越高。这个可以用MVV-LVA（最有价值受害者-最便宜攻击者）策略实现。

第二层是"杀手走法"。在搜索过程中记录每个深度上导致剪枝最多的那个走法，后续搜索到同一深度时优先尝试这些"杀手走法"。

第三层是"历史启发"。走法在搜索中被成功证明为最优的次数越多，排序越靠前。

这三层排序可以叠加使用。我个人的经验是，走法排序做到"杀手走法+静态启发"这个级别，剪枝效率已经非常可观，历史表可以做但收益相对小，除非你追求顶尖搜索强度。

2.3 空着剪枝与边界情况：进阶但不要迷信

除了α-β剪枝，棋类搜索里还有一个常见技巧——空着剪枝（Null Move Pruning）。思路是：当前局面假设己方不走棋（相当于让子），让对方连续走两步，如果这种情况下对方仍然占不到便宜，那说明当前局面已经足够好，可以提前剪掉。这个技巧在国际象棋引擎里非常有效，但在棋类规则比较复杂、存在"不可让子"状态（比如将军时不允许空着）的游戏中需要格外小心。Unity里做棋类AI，我建议先把α-β剪枝跑稳，再考虑空着剪枝。空着剪枝用不好，会出现明显的"漏招"，游戏体验反而下降。

还需要提一个边界：剪枝的前提是评估函数足够稳定。如果评估函数忽高忽低、噪声很大，剪枝会误判大量分支，导致搜索结果的可靠性下降。所以我会在调完评估函数之后，再回头优化搜索效率，这个顺序别搞反了。

3. 评估函数设计：搜索算法真正的胜负手

3.1 评估函数到底在评估什么

搜索算法本身不产生棋力，棋力全部藏在评估函数里。搜索只是把评估函数延伸到了更深层，但最终决定每一步好坏的是每一个叶子节点的分数。初学者最容易犯的错误是：花大量时间研究搜索算法，评估函数随便写个"子力差"，结果AI下棋像个莽夫，只知道吃子，完全没有位置概念。

评估函数的设计要围绕"这个棋的制胜因素是什么"来展开。国际象棋的评估至少包含子力价值、兵型结构、王的安全、空间优势、机动性等。五子棋则要评估各方向上的连子潜力、活三、冲四、眠三等。象棋要评估子力位置、车马炮的机动性、士象完整性、将帅安全性等。在设计前一定要坐下来把棋类的胜负规则和常见战术完整梳理一遍，否则评估函数很容易漏掉关键因素。

3.2 从简化版评估到结构化评估的演进

我用一个简化例子说明评估函数怎么写。假设做一个类似国际跳棋的小棋种，棋子有普通子和王（可后退），目标是把对方棋子吃光或让对手无棋可走。那么一个合理的评估函数大致长这样：

float Evaluate(GameState state) { if (state.IsGameOver()) return state.CurrentWinnerIsWhite() ? 10000 : -10000; float eval = 0; foreach (var piece in state.GetAllPieces()) { float sign = (piece.Side == Side.White) ? 1f : -1f; eval += sign * piece.BaseValue; eval += sign * EvaluatePiecePosition(piece); eval += sign * EvaluatePieceMobility(piece); } return eval; }

其中BaseValue是子力基础价值，EvaluatePiecePosition是位置价值表，EvaluatePieceMobility是机动性（可选走的步数）。归一化很重要：所有子力、位置、机动性的量纲要统一，否则会出现某个因素权重过大、其他因素形同虚设的问题。我的做法是先用一局游戏手动下几十步，观察AI是否出现明显的局部短视行为，再调整权重。

3.3 我的评估函数调试流程

评估函数最让人头疼的是权重调参。分享一个我常用的调试流程。

第一步，跑"AI对AI"的自我对局，打开终端日志，每步打印搜索深度、评估值、走法、最佳分数。先看有没有明显的"无效循环"——比如AI反复在两个走法之间来回。

第二步，固定开局，让AI和不同权重组合的自己下，记录胜负和平均步数。这一步能发现权重失衡问题，比如"只追子力、不管位置"的AI往往会因为贪吃子而丢掉局面优势。

第三步，针对边界场景写单元测试。例如设计一个"两步杀"的局面，要求AI必须走出制胜着法；设计一个"必败防守"局面，要求AI必须走出唯一的防守着法。如果评估函数目标不清晰，这两类测试会暴露很多问题。

我见过某开发者在做五子棋AI时，因为评估函数里"活三"和"冲四"的分数设置不合理，导致AI经常下出"自杀式"堵塞自己的棋形。后来他把活三分数调成冲四分数的一半以下，AI一下子就"开窍"了。评估函数的权重不是玄学，是拿大量对局数据逐步调出来的。

3.4 叶子节点评估的稳定性问题

搜索深度不同，同一个局面可能得到完全相反的结论。这是因为叶子节点评估值本身有噪声，浅层搜索更容易受噪声影响。解决办法是给评估函数加一个"深度惩罚"：越深的节点，评估值乘以一个接近1但小于1的系数（比如0.99^depth），让浅层的更"自信"的评估压过深层的模糊评估。这个小技巧不是所有引擎都这么做，但我在自己的项目里实测，它确实能减少浅层搜索的"抽风"现象。

4. 迭代加深与时间控制：Unity实战里的搜索调度

4.1 为什么不用固定深度而用迭代加深

很多人做棋类AI时，直接把深度定成4或者6，AI每步都在这个深度搜索。这个做法非常简单，但不适合实际游戏体验。原因有两个。第一，不同局面的复杂度差异很大，残局可能分支因子很小，开局可能分支因子很大，固定深度会造成有时候思考太久、有时候秒回。第二，我们希望在时间允许的情况下，能用尽量的深度；时间不允许时，拿上一个深度的结果兜底。

迭代加深的做法是：先搜深度1，再搜深度2，再搜深度3，直到时间用完，返回最后一次完整搜索的最佳走法。虽然看起来重复搜索浪费了时间，但走法排序带来的剪枝效率提升，使得下次搜索不必从零开始，代价远小于收益。我实测过，做了排序的迭代加深，深度6的总耗时往往只比直接搜深度6多15%左右，但时间控制能力是天壤之别。

4.2 Unity里的搜索调度：协程、异步与轮询

Unity的主线程是帧驱动的。如果在Update()里同步执行搜索，搜索时长超过一帧（16ms），画面就会卡顿；超过几百毫秒，直接掉帧到个位数。最简单的方案是协程。但协程有个问题：每步执行完yield return null后，搜索状态需要完全保存和恢复，递归函数的栈帧不好暂停。所以真正的协程化搜索，通常是把栈显式管理成迭代版本。这一点工作量大、容易出错，但做成了非常优雅。

我推荐另一种做法：把搜索放到后台线程，通过结果队列传回主线程。搜索逻辑本身不访问任何Unity对象（因为GameObject相关API不能跨线程），只操作我们自己定义的数据结构——棋盘数组、走法列表、评估结果。这样在StartCoroutine里每6毫秒查看一下线程状态，有结果就直接应用走法，没有就继续等。用户体验上就是AI"思考了一会儿"，完全不卡主线程。

下面是一个线程版迭代加深的骨架：

public class SearchAgent { private Thread searchThread; private volatile bool terminateRequested; private object resultLock = new object(); private Move bestMove; private bool hasResult; public void BeginSearch(GameState state, int maxDepth, float timeLimitMs) { terminateRequested = false; hasResult = false; searchThread = new Thread(() => { var stopwatch = Stopwatch.StartNew(); Move currentBest = default; for (int depth = 1; depth <= maxDepth; depth++) { currentBest = SearchRoot(state, depth); lock (resultLock) { bestMove = currentBest; hasResult = true; } if (stopwatch.ElapsedMilliseconds > timeLimitMs) break; } }); searchThread.Start(); } public bool TryGetBestMove(out Move move) { lock (resultLock) { if (hasResult) { move = bestMove; return true; } } move = default; return false; } }

核心逻辑在SearchRoot，它调用带α-β剪枝的AlphaBeta，返回最佳走法。搜索过程中不碰Unity API，所以线程安全。有一点要注意：volatile bool和lock不是高性能的，但它们保证了主线程和搜索线程之间的数据一致性，对回合制棋类来说完全够用。别为了极致性能去用无锁队列，收益很低，容易踩死锁坑。

4.3 时间分配策略：开局、中局、残局各不同

搜索时间不能从头到尾一个值。开局阶段局面变化大，前几步可以参考常见开局库，直接返回固定走法，省下时间给中局。中局搜索深度可以更深，但要注意时间预算；残局分支因子小，可以适当延长搜索时间，把深度推高。一个简单的经验公式是：

timeForMove = baseTime * (0.5f + 1.2f * (branchFactor / 35f))

baseTime是你给AI设定的平均思考时间，branchFactor是当前根节点的合法走法数量。这个公式的意思是，走法多的局面多给点时间，走法少的局面少给点时间。当然这只是起点值，接下来还要考虑"当前深度搜索到底用了多少时间"来做动态调整。我在某个跳棋模拟项目里用这个策略，AI平均思考时间从每步1.2秒降到了0.7秒，棋力反而还略有提升，因为它把省下的时间都集中在中后期的关键局面上了。

4.4 中止搜索时的安全处理

迭代加深最怕用户在搜索过程中点击了UI上的"重新开始"或者"退出对局"。搜索线程还在跑，但棋盘已经被重置了，线程继续访问无效的棋盘数组就会崩溃。我的建议是：引入"搜索代际"概念，每次发起搜索时给一个自增的代际号；回调应用结果前检查代际号是否一致，不一致则丢弃结果。UI交互全部通过主线程的"发布订阅"处理，搜索线程不直接修改任何游戏对象状态。

5. 从单线程到Job System：Unity环境下的搜索性能优化

5.1 搜索是天然的并行候选吗

很多人以为把搜索算法加上Parallel.For就能多倍加速，实际上没有那么简单。搜索树的分支天然是不均衡的：某个分支可能是10层深度的剧烈搜索，另一个分支可能1层就被剪枝。如果只是简单地把根节点的走法分给多个线程，速度快的那根线程干完就闲着，慢的那根拖着整个进度。所以并行搜索需要"工作窃取"（work stealing）或者更复杂的任务分割。Unity的Job System + Burst编译器提供了一个相对可控的机制。

5.2 把评估函数改成Burst兼容

Unity的Job System要求job结构体是unmanaged struct，里面不能有托管引用类型（类、字符串、委托等）。所以如果我们之前用了class Piece，就要改成用NativeArray<int>和整数编码表示棋子。举个例子，我用一个长度为64的NativeArray<int>表示棋盘，棋子编码为：0表示空，1表示白兵，2表示白王，-1表示黑兵，-2表示黑王。评估函数就变成纯NativeArray读操作，完全Burst兼容。

[BurstCompile] struct EvaluateJob : IJob { [ReadOnly] public NativeArray<int> Board; public float Result; public void Execute() { float score = 0; for (int i = 0; i < Board.Length; i++) { int piece = Board[i]; if (piece == 0) continue; float sign = piece > 0 ? 1f : -1f; int type = Mathf.Abs(piece); score += sign * PieceValue(type); score += sign * PositionBonus(type, i); } Result = score; } }

这是最简单的一层：把评估函数并行化。实际上更常用的优化是并行搜索根节点走法。在Burst里做递归AlphaBeta会稍微麻烦，因为Burst编译器对递归的支持有限但并非不可用，实践中我更多是保留C#版本的搜索函数，只把评估、走法生成这些热点函数写进Burst job里。这样做的好处是不用改搜索逻辑，用job计算批量局面评估，同时把NativeArray的分配和回收放到job里管理。

5.3 一个可行的根结点并行方案

假设根节点有4个候选走法，每个走法递归深度6。我们可以开4个job并行搜索，每个job返回自己的最佳评估值，主线程最终取最大。为了让剪枝在并行时依然有效，我通常先跑一个浅层预搜索（深度2），得到走法排序结果，然后给每个job分配一组走法，且使用共享的alpha/beta上界。这样并行搜索的节点总量，会比串行搜索多一点点，但墙钟时间能压到串行的40%左右。这个方案在Unity 2021以上版本配合Burst跑，效果非常明显。

5.4 小心线程竞争：置换表的并发访问

如果要做置换表（转置表），并行访问要格外小心。置换表本质是一个哈希表，多个线程同时读写会产生竞争。最简单的方式是每线程一张表，搜索时只访问自己线程的表；结果用于排序启发时可以共享，但同一深度结果缓存不能跨线程误用。用NativeParallelHashMap可以做全局并发，但要注意Add和TryAdd在并发下的语义。我个人建议新手先不做并行置换表，先跑通并行搜索，再评估置换表的收益。

6. 棋类AI落地中的调试手段与常见坑

6.1 搜索日志与结点计数

调试棋类AI最基础也是最重要的一步，是让搜索过程可观测。我通常在SearchRoot和AlphaBeta里插入结点计数器和深度信息，每隔一段时间打印一行日志，格式如下：

[depth=4][nodes=123456][alpha=0.32][bestMove=e2e4][time=231ms]

这些日志能帮你快速定位两类问题：搜索是否进入死循环？评估值是否稳定收敛？如果结点数暴涨到几百万，但时间只有几十毫秒，说明剪枝失效了；如果评估值在不同深度之间来回横跳，说明评估函数有问题。日志别打太多，每搜索完一层打一次就行，否则输出反而干扰判断。

6.2 常见坑一：评估函数的正负号不统一

这件事再怎么强调都不为过。Negamax的评估函数必须始终站在"当前走棋方"视角，而很多人在写评估函数时，潜意识里会固定站在"白方"或"己方"视角。我排查过某开发者的项目，他的AI白方玩得还行，黑方就表现得完全像随机走子，最后发现弱智的是评估函数：黑方局面分数没有取反，导致黑方在搜索时看似在取最大，实则在最小化自己的利益。修一行代码，棋力从200 ELO直接飙到1300 ELO。

6.3 常见坑二：走法生成不完整导致的"隐形盲区"

走法生成是搜索正确性的基石。如果合法走法生成函数漏掉了某个规则（比如王车易位、吃过路兵、别马脚），AI就会出现"明明看着没有更好走法，但就是输了"的诡异局面。排查时最有效的办法是写一个穷举验证脚本：给定一个局面，把你的走法生成结果和人工验证的走法列表逐项对比。每个棋类规则都单独做测试用例，尤其是棋子移动边界、越界、被将军时不合法等场景。这个测试能挡住至少一半的"AI突然变笨"问题。

6.4 常见坑三：UI与搜索线程的数据竞争

Unity主线程和后台搜索线程之间共享的数据，只要有一处没加锁或没正确处理，就会出现不可复现的崩溃。我的原则是：搜索线程只写两个变量——"是否有结果"和"最佳走法"，主线程通过锁读取。除此之外，搜索线程不允许访问GameObject、Transform、MonoBehaviour的任何字段。棋盘数据在发起搜索时直接拷贝一份到搜索线程，搜索结束后，主线程再根据最佳走法去修改GameObject位置。严格遵守这个边界，才能避免Unity里的各种"莫名其妙闪退"。

6.5 从棋力测试到调参闭环

最后一个实用的建议是搭建一套自动对局测试脚本。写一个GameController脚本，让AI的两个不同参数配置互下100盘，统计胜率。这样每次调整权重后，可以立刻通过数字看到变化，而不是凭感觉。我更推荐先固定搜索深度，只调评估函数权重，跑出基线胜率；然后再逐步提高搜索深度，观察胜率提升曲线是否合理。某图像处理Demo项目里，我就是用这套方法把评估函数的30多个权重逐一调校完成的，每一步都有数据支撑，完全不靠玄学。

我在实际项目里，一直把"搜索和评估"分成两个独立模块来维护。搜索模块只负责讲"如何从局面A找到最佳走法"；评估模块只负责回答"这个局面到底谁好"。两者用统一的Evaluate(state)接口对接，想换搜索算法就换搜索，想调评估权重就调评估，互不干扰。从最早的井字棋、五子棋，到后来的国际跳棋变种，这套结构让我在多款棋类项目里都快速落地了AI。

最后再分享一个小技巧：给AI的搜索加一个"随机性"开关。如果每次都用绝对最优走法，AI很容易被对手预测；当AI优势很大时，让它以一定概率选择第二或第三优的走法，对局体验会丰富很多。这只需要在根节点返回最佳走法时，偶尔选次佳走法即可，不会实质影响棋力，但能让玩家觉得对面的"AI像个活人"。这个技巧实测很管用，推荐一试。