Pikafish Wiki

简体中文

繁體中文
English
Tiếng Việt

简体中文

繁體中文
English
Tiếng Việt

外观

官网
简体中文繁體中文EnglishTiếng Việt

搜索算法 ​

皮卡鱼不会把所有变化都算到同样深。它会先试更有希望的走法，把关键变化算得更深；对希望较小的分支少算，或提前停下。NNUE 负责给局面打分，搜索负责比较“走下去会怎样”。

本文以 official Pikafish 的提交 1c66b9b 为核对基准。下文列出的方法均能在这份代码中找到；具体阈值会随版本调整，因此重点解释用途，不把调参常数当成固定规则。文末附源码入口及 Chessprogramming Wiki 等延伸资料。

相关内容：源码导读、局面评估与 NNUE、局面表示与规则、引擎运行与通信。

先看整体：一次搜索在做什么 ​

可以把搜索理解为不断重复下面几件事：

  1. 看当前局面是否已经触发胜负、和棋或重复局面等规则。
  2. 查缓存，看看以前是否算过，能否复用结果或好走法。
  3. 生成候选走法，优先试更有希望的，排除走后露将等非法着法。
  4. 走一步，换对方思考，再把结果传回来；算完后撤销这一步。
  5. 根据结果继续深算、补搜，或停止某些分支。

这是一次搜索的概览。实际实现会交错进行评估、剪枝和深度调整，下文按各方法解决的问题展开。

需要解决的问题Pikafish 使用的方法
双方都选对自己有利的棋，怎么比较？Negamax 形式的 Alpha-Beta、主要变例搜索（PVS）
时间有限，先算多深？迭代加深、期望窗口（Aspiration Windows）、时间管理
先看哪步，算过的能否复用？走法排序、历史启发、静态交换评估（SEE）、置换表（TT）
深度到了，但吃子还没算完怎么办？静态搜索（Quiescence Search）
哪些地方少算，哪些地方多算？空步剪枝、ProbCut、无望剪枝、LMR、IIR、奇异延伸等
象棋走法与棋规怎么处理？位棋盘与攻击表、合法性检查、将军／长捉／重复与限招判定

Minimax 与 Negamax：换个角度看分数 ​

先假设所有分数都从红方看：越大越利红，越小越利黑。红方走时选最大值，黑方走时选最小值，这就是 Minimax（极小化极大）。引擎不能只看“我能吃到什么”，还要考虑对手会选最让自己难受的回应。

Negamax 把两套处理统一起来：分数始终从当前行棋方看，换一方就取负号。 如果走完一步后，对手看到的分数是 -80，对自己就是 +80。于是双方都只需“取最大值”，递归时写成 score = -search(...)。

这里的一层（ply）指一方走一步，红黑各走一步是两层。示例分数只用于说明比较关系，不代表某个棋子的固定价值。

Alpha-Beta：已经不会改变选择，就不必算完 ​

假设红方已有一条路线，面对黑方的最佳回应也能得到 +50。再检查另一条路线时，只要发现黑方有一个回应能把分数压到 +30，这条路线就不可能比前者更好。黑方是否还能把它压到 +10，已不影响红方的选择，可以省下后续计算。

Alpha-Beta 用 alpha 和 beta 表示本次搜索关心的分数窗口：

  • alpha：需要超过的门槛；不超过它，就不能改善当前选择。
  • beta：达到它便已足以让上层排除这条路线，无须继续求精确分数。

窗口规定本次搜索关心的分数门槛。 结果不高于原来的 alpha 叫 fail-low，给出上界；达到或超过 beta 叫 fail-high，给出下界；落在窗口内，得到该深度、该评估方式下的确切值。fail-soft 允许返回窗口外的分数，解释结果时仍要保留相应界限类型。

只使用基本 Alpha-Beta，在相同搜索树和叶子评估下，可以得到与完整 Minimax 相同的结果。后面介绍的空步、无望剪枝和减深加入了经验判断，不能一概套用这个保证。

展开：一个只展示基本原理的 Negamax / Alpha-Beta 例子

下面用教学伪代码展示 Negamax 和 Alpha-Beta 的骨架。terminal_score() 先处理终局与规则，包含象棋中无合法着法判负；分数从当前行棋方看。示例在深度用完时直接评估，Pikafish 的对应路径会进入后文的静态搜索。

cpp
int search(int depth, int alpha, int beta) {
    if (auto result = terminal_score(); result.has_value())
        return *result;
    if (depth <= 0)
        return evaluate_side_to_move();

    int best = -INF;
    for (Move move : ordered_legal_moves()) {
        make_move(move);
        int score = -search(depth - 1, -beta, -alpha);
        undo_move(move);

        best = std::max(best, score);
        alpha = std::max(alpha, score);
        if (alpha >= beta)
            break;
    }
    return best;
}

负号不仅作用于返回分数，也会把子节点窗口变成 (-beta, -alpha)。INF 应选用足够大的安全常量，不能直接对最小整数取负，以免溢出。

PVS：其他走法先问“能不能更好” ​

PVS（Principal Variation Search，主要变例搜索）建立在好走法往往排在前面的基础上：在主变化节点，先用完整窗口搜索第一步，建立一个较可靠的候选；后面的走法先用很窄的窗口试探，问“它能不能超过当前最佳？”有希望时，再按需要用完整窗口补搜。

对于整数分数，(alpha, alpha + 1) 这样的窗口通常叫零窗口。它主要回答是否超过门槛，不能在这个窗口里求出一个严格介于两端的整数分数。

Pikafish 将 PVS 与 LMR 组合：后面的候选先浅搜，结果有希望再补深。窗口宽窄决定要问多精确，深度多少决定往后看多远。 零窗口搜索仍执行真实走法；空步搜索则临时交换行棋方，检验让一手后的结果。

源码：PVS 与 LMR 的递归搜索。

用具体窗口看一次 PVS 试探 ​

假设第一着已经得到 +50，后面的着法先用 (50, 51) 试探：

返回情况得到的信息下一步
不高于 50这次搜索给出上界，候选没有超过门槛。继续取下一候选。
达到或超过 51得到超过门槛的下界。在满足补搜条件时扩大窗口、恢复相应深度。

比如 fail-soft 返回 65，仍要结合下界类型阅读，再通过补搜判断它究竟多好。PVS 与 LMR 的实际组合见递归搜索。

迭代加深与期望窗口：先有答案，再逐步改进 ​

皮卡鱼从较浅的深度开始，一轮轮提高目标深度。这叫迭代加深。浅层搜索得到的最佳走法、主变化、分数和缓存，会帮助下一轮更快找到重点；时间用完时，也有已经得到的结果可用。

根节点的期望窗口围绕候选近期平均评分设置较小范围，并参考分数波动。结果明显超出范围时，代码扩大相应一侧的窗口再搜，使搜索在稳定候选上节省工作、在异常变化上补充计算。

界面的 depth 20 是迭代的目标深度。减深、延伸和静态搜索使各条分支的实际深度不同。主变化（PV）展示当前搜索认为双方会选择的主要路线，可随后续计算改变。

源码：迭代循环与窗口调整。

走法生成：列出候选，再检查能不能真走 ​

生成、合法性检查和排序各管一件事：有哪些候选、能不能走、先算哪步。

生成器可按需要列出吃子（CAPTURES）、非吃子（QUIETS）、应将（EVASIONS）或全部伪合法走法（PSEUDO_LEGAL）。伪合法的意思是基本走法符合要求，但还可能走后露将；主搜索取出候选后，会调用 pos.legal() 检查。需要直接拿到完整合法列表时，LEGAL 生成也会进行过滤。

这里的 quiet 常译作“静着”，但它只是不吃子的走法，仍然可能将军。

象棋中特别需要处理的情况 ​

  • 炮：不吃子时沿无阻挡的直线走，吃子时必须隔一个炮架。被炮将军时，移走己方炮架也可能解将。
  • 马与象：要处理马腿、象眼和象不过河；兵卒过河后的横走、将帅和士的九宫范围也由对应攻击规则限制。
  • 将帅安全：走后不能让己方将帅受攻击，包括将帅照面。
  • 多子将军：不能照抄国际象棋的“双将只能动王”。当前实现遇到多个将军棋子，会生成全部伪合法走法，再筛出合法应对。

在候选已符合基本走法的前提下，legal() 主要检查走后将帅是否安全；长将、长捉等依赖历史的判定由后面的规则逻辑处理。

源码：走法分类与应将生成、将帅安全检查。

位棋盘与攻击表：一次处理一组格点 ​

位棋盘把一组格点表示成二进制位，例如“所有红子的位置”或“这枚马能攻击的位置”。交、并等位运算就能同时处理一批格点。Pikafish 使用 128 位位棋盘容纳象棋的 90 个格点，同时保留按格点查询棋子的数组。

车、炮、马、象等攻击范围利用预先建立的表来查询。普通编译路径用 magic 乘法和移位计算索引；启用 USE_PEXT 的路径使用 PEXT / PDEP 指令。具体采用哪条路径取决于编译版本，不能据此认定某种指令在所有 CPU 上都更快。

搜索走入一个分支时落子，返回时撤销。局面状态和哈希键随走法增量更新，省去每一步重新扫描整盘的工作。

源码：位棋盘类型、攻击表与索引、落子与撤销。

走法排序与历史启发：先试最有希望的棋 ​

好的排序能更早找到强着，让 Alpha-Beta 更快停止其他分支。常规主搜索中的取着顺序大致为：

  1. 置换表里留下的候选走法（TT move）。
  2. 经 SEE 等快速判断较好的吃子。
  3. 历史评分较好的非吃子走法。
  4. 较差的吃子。
  5. 较差的非吃子走法。

MovePicker 按阶段生成、评分并取出候选，应将、静态搜索和 ProbCut 各有对应流程。阶段中的“较好”“较差”表示优先级，较差吃子仍可进入搜索。当前顺序允许高历史分非吃子先于较差吃子，主要依靠 TT、吃子历史和各类非吃子历史来排序。

历史启发（History Heuristic）记录走法在搜索中的效果。 经常产生有效截断或其他有用结果的走法会提高后续优先级，反复表现差则降低优先级。统计记录在引擎的历史表中。

代码同时使用主历史、吃子历史、连续着历史（结合前面走过什么）、兵卒结构历史，以及靠近根节点的历史。吃子评分会结合被吃子的价值与吃子历史；非吃子还会参考将军、躲避或进入低价值棋子的攻击范围等信息。

源码：MovePicker 阶段与评分、历史表定义。

SEE：先粗算一下换子是否吃亏 ​

SEE（Static Exchange Evaluation，静态交换评估）快速估计一个落点上的连续换子能否达到收益门槛：我吃过去，对方吃回来，我还能不能再吃，大致是赚是亏？Pikafish 的 see_ge() 回答的是“是否至少达到给定门槛”。

SEE 用于吃子排序和部分剪枝，也可筛查非吃子后是否容易丢子。它集中计算落点附近的交换收益；弃子引出的远处威胁与后续配合，需要搜索继续验证。

源码：静态交换评估。

置换表：算过的局面尽量复用 ​

不同的走棋顺序可能到达同一局面。置换表（Transposition Table，TT）用哈希键查找先前的搜索记录，保存候选走法、深度、分数、分数的界限类型及静态评估等信息。

记录的界限对应产生它的搜索深度、评估和选择性策略，复用时需要检查这些条件。

记录类型表示什么
EXACT在那次搜索条件下得到的确切返回值
LOWER下界：已知至少有这么好，常见于 fail-high
UPPER上界：已知不超过这个值，常见于 fail-low

只有深度、节点类型、界限等条件合适时，才可直接复用分数并停止搜索；否则，缓存中的走法仍可拿来优先尝试。EXACT 也不代表已经从数学上解出了这盘棋的最终胜负。

象棋的局面价值还会受走棋历史与限招影响。当前实现有相应的规则检查和部分缓存保护，不能简单认为“棋子摆放相同，任何历史下都可无条件使用同一结果”。

源码：TT 数据结构、主搜索读取与截断。设置内存大小可参见 Hash 说明。

静态搜索：不要在换子只算一半时停下 ​

假设搜索刚好在“我吃了对方一个子”后到达目标深度。如果立刻打分，却没看到对方下一步能吃回来，就会误以为赚了子。静态搜索（Quiescence Search，qsearch）在常规深度用完后继续处理部分战术变化，减少这种“停在半截”的误判。

当前 Pikafish 通常继续搜索吃子；被将军时改用应将候选，不能只生成吃子。

  • 未被将军时，可把当前静态评估作为 stand pat 的基准，再看值得搜索的吃子能否改善它。stand pat 是搜索中的近似基准，实战仍须走出合法着法。
  • 被将军时，不能使用 stand pat，必须考虑应将；若无合法应对，就是败局。
  • qsearch 自己也使用置换表、无望剪枝和 SEE 等筛选，并不会穷尽所有吃子或所有将军。
  • 象棋中无合法走法，即使没被将军也是困毙判负；当前代码对这种情况也有检查，不能照搬国际象棋的困毙和棋。

“静态搜索”仍然在走棋递归；“静态评估”才是给当前局面打分，两者要区分。

源码：qsearch。

剪枝：把算力留给更可能影响结果的分支 ​

下面这些选择性方法都能在当前 Pikafish 中找到。它们结合静态评估、深度、历史和分数窗口决定哪里可以少算。它们带有经验假设，可能误判；适用条件、余量和补搜用来控制风险。 表中只解释用途，不省略成“满足一句话就总会触发”。

方法用直白的话解释
Razoring静态分已经远低于 alpha 等条件满足时，转交静态搜索，检查眼前战术，而不继续原来的深层搜索。
反向无望剪枝（Reverse Futility）静态分减去余量仍足够高时，某些节点可提前返回，省去后续搜索。
空步剪枝（Null-move Pruning）内部假设自己让一手，浅搜后若仍够好，就可能无需把真实走法逐个算完。详见下文。
ProbCut对有希望的吃子先做静态搜索，再按需做较浅搜索；若越过一个比 beta 更高的门槛，就可能提前停止当前子树。
Small ProbCut利用置换表中足够深、明显超过额外门槛的下界，提前返回；不再重复完整的试吃子流程。
着法数量剪枝（Move-count Pruning / LMP）已经试了足够多候选且条件合适时，跳过后续非吃子走法；数量门槛会变化。
候选走法的无望剪枝（Futility）结合静态分、可能吃到的子力、历史和预计深度，跳过看起来难以追上 alpha 的候选。
历史剪枝（History Pruning）某些非吃子走法的连续着／兵卒结构历史太差时，不再投入搜索。
SEE 剪枝快速换子估计损失过大时，跳过某些候选；门槛随深度等因素改变。

这些判断会受节点类型、是否被将军、将杀分、子力和历史等条件限制，不能把每一项理解成适用于所有局面。

另外，**杀棋距离剪枝（Mate-distance Pruning）**利用当前距根节点的层数，收紧可能的杀棋分上下界，排除不可能改善杀棋距离的搜索。它属于分数界限推导，应与上面的经验判断区分。

源码：节点级剪枝、逐着筛选、杀棋距离剪枝。

空步为何有用，又会在哪里出错？ ​

空步剪枝采用“让对手先走，局面仍足够好”的经验判断：临时交换行棋方，以减小的深度检验这一假设。空步仅用于搜索内部。

轮到自己走反而变坏的局面称为 zugzwang（楚茨文克），会破坏上述假设。因此代码要求未被将军、己方仍有车马炮等条件，较深搜索还可能回到原局面验证。减深量随条件变化，验证搜索用来降低误判风险。

减深与延伸：关键分支值得算得更深 ​

剪枝是省掉某些搜索；减深是先少算；延伸是多算。 Pikafish 会根据搜索过程动态调整深度。

方法当前实现的作用
LMR（Late Move Reductions，后着减深）排在后面、希望较小的着法先浅搜；若结果超过 alpha，再视结果补深。减深量参考历史、节点类型等，也可能用于吃子。
IIR（Internal Iterative Reductions，内部迭代减深）缺少 TT 候选等条件成立时，降低当前节点的搜索深度。IID 则通过一轮浅搜寻找好候选，两者采用不同处理。
奇异延伸（Singular Extension）暂时排除一个合格的 TT 候选，浅搜其余走法；如果其他走法都明显差一截，就给这个候选更多深度。
Multi-cut 与负延伸在上述排除候选的检查中，其他走法仍足够好时，可能直接截断；另一些条件下则减少 TT 候选的深度。

奇异延伸判断的是 TT 候选与其他走法在一次受限搜索中的差距。即使有多个合法着法，一个明显突出的候选也可能获得延伸。其余深度调整还结合节点类型、历史和搜索结果共同决定。

源码：IIR、奇异延伸及相关处理、LMR 与补搜。

NNUE 与评估修正：打分也会影响搜索方向 ​

搜索经常需要一个不继续走棋的局面估分。Pikafish 调用 NNUE 评估，再结合搜索中的修正信息使用这个分数；它既帮助叶子评分，也会影响某些剪枝和深度分配。

评估修正历史（Correction History）记录静态估分与后续搜索结果的偏差。 代码按兵卒、其他子力布局和前序着法等信息组织统计，用于修正相关局面的静态分。统计保存在搜索历史表中，NNUE 权重由加载的网络文件提供。

因此，要把三件事分开：NNUE 提供局面估分，历史表帮助排序或修正，搜索比较后续变化。这几部分配合决定引擎把时间花在哪里。

源码：评估修正的计算与更新、搜索中的评估入口。

象棋规则：相同盘面，不一定是同一个问题 ​

搜索中不仅要检查将军和无合法着法，还要处理长将、长捉、重复局面及自然限招等情况。相同盘面再次出现，不代表必然和棋。

rule_judge() 先用快速过滤判断是否值得追查历史，再沿状态链检查将军与捉子。已确定的裁决可直接返回；部分搜索内重复给出分数界限，供搜索收窄窗口后继续。

判断时要分别核对走法是否合法、历史是否触发裁决、缓存结果是否适用。具体生成步骤、循环回看与被捉棋子身份的交集，见局面表示与规则。

源码：重复与规则处理。棋规背景另见 象棋棋规疑云。

多线程、MultiPV 与时间：怎样分配这次思考 ​

多线程让工作线程推进各自的搜索，并共享置换表；部分历史信息按 NUMA 节点共享。线程既会重复工作，也会利用其他线程留下的信息，收益取决于局面、硬件和搜索条件。

MultiPV为多个根候选保留主要变化，需要额外的根搜索。它适合比较备选棋；在相同时间内，候选增加会分摊单条主线的计算预算。

时间管理先根据剩余时间、加秒、待走步数和 Move Overhead 等计算预算，再参考分数下降、最佳走法是否稳定等情况调整。固定时间、节点数等限制也会影响何时停止。迭代加深让引擎能在这些限制下逐步改进已有答案。

源码：线程启动与结果选择、时间预算、搜索中的时间调整。相关设置见 UCI 选项。

源码与延伸阅读 ​

从哪里读 Pikafish 源码 ​

以下链接全部固定到本文核对的提交，避免以后代码变化后行号对应不上：

继续理解算法 ​

Chessprogramming Wiki 适合查术语和通用思路；其中很多例子针对国际象棋。阅读时应区分通用搜索方法与具体棋规，Pikafish 是否实际采用某个方法，以本页对应源码为准。