砍掉无用的搜索分支——Alpha-Beta剪枝让Minimax快一倍设计截图如下为什么需要剪枝Minimax搜索深度2、宽度12时需要评估 12 × 8 96 个叶节点。如果深度增加到3就是 12 × 8 × 8 768 个。指数增长很快就会让AI思考时间过长。Alpha-Beta剪枝的核心思想如果已经知道一个分支的结果不可能比另一个分支更好就没必要继续搜索了。Alpha和Beta的含义AlphaMAX层当前能保证的最大值AI至少能拿到这么高的分BetaMIN层当前能保证的最小值对手最多让AI拿到这么低的分剪枝条件beta alpha时剪枝——当前分支不可能影响最终决策。剪枝过程图解MAX / | \ A B C / \ / \ / \ 3 5 2 ? ? ? 1. 评估A的子节点min(3,5)3 → A3, alpha3 2. 评估B的第一个子节点2 此时 beta2, alpha3 beta(2) alpha(3) → 剪枝B的第二个子节点不需要评估 B2 3. 评估C...直觉理解AI已经知道A分支能拿3分。搜索B分支时发现对手能限制到2分。2 3所以AI不会选BB的剩余子节点不需要搜索。代码中的剪枝MAX层AI回合if(isMaximizing){letmaxEval:number-Infinity;for(leti0;imaxCandidates;i){// ... 落子、递归 ...maxEvalMath.max(maxEval,evalScore);alphaMath.max(alpha,evalScore);// 更新alphaif(betaalpha)break;// 剪枝}returnmaxEval;}MIN层对手回合else{letminEval:numberInfinity;for(leti0;imaxCandidates;i){// ... 落子、递归 ...minEvalMath.min(minEval,evalScore);betaMath.min(beta,evalScore);// 更新betaif(betaalpha)break;// 剪枝}returnminEval;}顶层调用的Alpha-BetaprivategetHardMove(board:number[][]):Move{letalpha:number-Infinity;constbeta:numberInfinity;for(leti0;imaxCandidates;i){// ...constscorethis.minimax(board,2,alpha,beta,false);// ...alphaMath.max(alpha,score);// 更新alpha}}顶层beta保持Infinity因为还没搜索完所有候选无法确定上限alpha随着搜索逐渐增大。剪枝效果分析场景无剪枝有剪枝加速比深度2宽度12×896次评估~48次评估2x深度3宽度12×8×8768次评估~256次评估3x深度4宽度12×8×8×86144次评估~1024次评估6x最佳情况剪枝后搜索量减少到原来的平方根。最差情况候选排序最差时没有剪枝效果但也不会更慢。候选排序对剪枝的影响privategetSortedCandidates(board:number[][]):Move[]{// 按攻防评分从高到低排序scored.sort((a:ScoredMove,b:ScoredMove)b.score-a.score);returnscored.map((s:ScoredMove)s.move);}排序越好剪枝越多。因为高价值候选先搜索alpha快速增大后续低价值候选更容易被剪掉。这就是为什么困难模式要用getSortedCandidates而非getCandidates——排序是为了让Alpha-Beta剪枝更有效。实际调试中的思考时间在本项目中困难模式的AI在移动端模拟器上的响应时间约200-500ms搜索 12 × 8 96 个局面理论值剪枝后约 40-60 个实际评估每个评估约5ms全盘扫描4个方向这个延迟在用户体验上是可以接受的配合400ms的setTimeout延迟看起来像AI在思考。总结Alpha-Beta剪枝是Minimax的标准优化原理简单alpha和beta两个变量维护搜索边界效果显著最佳情况下搜索量减少到平方根依赖排序候选排序越好剪枝效果越好零风险剪枝不影响最终结果只减少搜索量没有Alpha-Beta的Minimax在移动端几乎不可用而加上剪枝后深度2-3的搜索可以流畅运行。