局面表示与规则
引擎保存棋子位置、行棋方、将军信息和走棋历史。局面价值由当前盘面与到达它的路径共同决定,长将、长捉和自然限招尤其依赖历史。
本文核对 official Pikafish 提交 1c66b9b。下文解释这份源码的实际流程;不同版本及规则选项应结合各自实现阅读。搜索方法见搜索算法。
几个文件分别管什么?
| 文件 | 主要职责 |
|---|---|
types.h | 定义棋子、颜色、格点和走法。 |
bitboard.h | 用位运算表示、组合一组格点。 |
attacks.h/.cpp | 根据位置与阻挡关系,查询攻击范围。 |
movegen.h/.cpp | 把起点、可达终点与目标集合组合成走法。 |
position.h/.cpp | 保存局面,处理落子撤销、将帅安全与历史规则。 |
例如马的攻击查询先处理马腿;生成器将可达点组成候选;legal() 再检查走后将帅安全。源码入口:基础类型、生成与过滤、攻击查询。
同一张棋盘,为什么要存几份信息?
Position 同时维护按格点排列的 board、按棋子种类和颜色划分的位棋盘,以及棋子数量。三者服务于不同查询:查某点是什么子,访问数组;取全部红车,组合颜色和棋子种类集合;找攻击范围内的敌子,对两个集合求交集。
位棋盘每一位对应一个格点,Pikafish 用 128 位容纳 90 个格点。行、列、半边棋盘和九宫也有相应集合。走棋和撤销时,这些表示必须同步更新,搜索才能继续使用它们。
车炮线路、马腿和象眼的攻击查询可用预先建立的表加速,Magic 与 PEXT/PDEP 是其中的索引计算路径,详见位棋盘与攻击表。
具体怎样生成一步棋?
generate_moves() 先取出行棋方某类棋子的位棋盘,用 pop_lsb() 逐个取出起点,再计算攻击范围并与 target 求交集。结果集合中每个终点都组成一个 Move(from, to)。
| 请求 | target 的含义 |
|---|---|
CAPTURES | 对方棋子所在的格点。 |
QUIETS | 空格点;生成的非吃子着法仍可能将军。 |
PSEUDO_LEGAL | 己方棋子以外的格点。 |
EVASIONS | 根据将军线路收窄目标,并补充特殊解将方式。 |
炮在这里分两路处理:吃子查询炮的隔子攻击范围,再与敌子求交集;非吃子查询车的直线范围,再与空点求交集。
例如,只看 e 列,炮在 e2,己方棋子在 e5,敌子在 e8,中间其余点为空。向这一方向的非吃子候选为 e2e3、e2e4;吃子候选为 e2e8,e5 充当炮架。e6、e7 在炮架之后,炮无法跳过去停在空点上。
马在 e4 时,向上两条候选是 e4d6、e4f6;如果 e5 有子,这两个点都会被马腿阻挡。兵卒的攻击查询还接收颜色,处理前进方向与过河后的横走;士、将帅和象的表处理九宫、半边棋盘及象眼等限制。
被单子将军时,生成器先考虑吃掉将军子、垫入线路和移动将帅;炮将还补上“移走己方炮架”的候选。遇到多个将军子,则生成全部伪合法候选交给安全检查。最后,generate<LEGAL>() 用 pos.legal() 过滤;过滤时以列表末项覆盖非法项,缩短列表。
这些候选的棋理优劣随后由排序和搜索判断。源码:逐类生成、炮的两路生成和应将分支。
落子与撤销:保存返回所需的信息
搜索反复试走一步、递归计算,再退回原处。Pikafish 直接修改当前 Position,并建立一个 StateInfo:保存哈希键、计数、将军信息、刚走的棋和被吃的子,previous 指向上一状态。部分字段复制,另一些增量更新。
undo_move() 将移动的棋子放回,恢复被吃的子,并让状态指针退回上一项。恢复棋盘、哈希和历史计数必须成套完成,这样下一条分支才会从相同起点计算。实战着法和搜索中的临时着法都沿各自的状态链组织。
Zobrist 哈希:快速定位局面
Zobrist 为“某种棋子在某个点”准备数值,再把盘面对应项和行棋方用异或组合成键。走棋时异或掉起点、异或进终点,吃子时再移除被吃子的项;同一个数异或两次抵消,所以更新只涉及发生变化的部分。
基本键 st->key 为 64 位,主要对应布局与行棋方,存在哈希碰撞的可能。用于缓存的 key() 还结合限招计数的分组和重复过滤信息作调整。重复检测以基本键追查状态链,长将与长捉的具体结果由链中的将军和走棋信息决定。
相同布局可以来自不同的将捉历史,因此读缓存代码时,还要核对规则检查和缓存保护。详见置换表。
源码:准备 Zobrist 数表、建立基本键、增量更新、缓存键调整。
走法合法性与历史裁决
legal() 以候选已满足基本走法为前提。它先构造走后的占用集合 (pieces() ^ from) | to:移除起点,保留或加入终点。将帅移动时检查目的地受攻击情况;其他棋子移动时检查己方将帅的原位置,吃子还要排除已被吃掉的攻击者。维护的牵制与阻挡信息允许部分着法走快速路径。
checkers_to() 在新占用关系下检查兵卒、马、车、炮及将帅照面。移动炮架可能使炮将出现或消失,移动马腿可能打开马将,所以检查会使用走后的阻挡关系。
历史裁决交给 rule_judge():搜索走入新节点后,结合之前的将军、捉子、重复和限招信息处理胜负或和棋。有些搜索内重复只提供分数界限,供搜索收窄窗口。
源码:legal 与将帅攻击查询、规则判定。相关概览见规则与搜索。
怎样找到并裁决一段循环?
这份实现先计算可回看长度:考虑吃子后的计数、额外将军步和距最近搜索空步的距离。至少有四步可回看,且 Bloom 过滤器提示可能存在重复时,才沿 previous 链每次回退两步,比较同一行棋方的基本键。过滤器节省无关检查,命中后仍会逐项比较哈希键。
回退时分别累计两方是否步步将军。一方长将,就用决定性胜负分处理;双方长将,结果为和。双方都没有步步将军时,再在局面副本上调用 detect_chases() 检查长捉。
本版本还区分实战历史与根节点之后的搜索路径:在根节点及以前找到两次先前出现,或在根之后符合条件地找到一次先前出现,会进入相应重复分支。三次出现及已确定的循环和棋可直接返回;部分搜索内第二次出现的胜负预判继续检查是否可能转为和棋。此时 rule_judge() 可留下 result 而返回 false,搜索据此调整 alpha 或 beta 后继续。
这描述的是本页固定提交中的搜索实现。实际对局应使用与平台匹配的棋规;比较其他规则版本时,还要核对重复次数、捉的定义和双方违规的裁决方式。
捉子怎么认,怎样确认一直捉同一子?
chased() 返回一个棋子身份集合,每一位对应一个被捉棋子。函数先筛选攻击者与目标:这份实现允许将帅、兵卒长捉,目标中的未过河兵卒和对将帅的攻击也有专门排除;受到牵制的攻击者只保留相应牵制者目标。
候选攻击通过 chase_legal() 检查以后,代码按棋种分支处理。马或炮攻击车,以及士象攻击符合条件的更强棋子,进入直接记捉分支。其他候选则临时模拟吃子,查找目标点的回吃者,逐个检查回吃是否使将帅安全;若存在合法回吃,这个分支就排除该候选捉。相同棋种之间的互攻,还要处理对称攻击与牵制的例外。
detect_chases() 给双方现存棋子分配身份编号,并在回退时让编号随棋子移动,确保跟踪的是同一枚棋子。每步比较走前、走后的被捉集合,取 after & ~before 得到该步新造成的捉,再不断与此前集合求交集。
例如两步新捉的目标集合分别是 {马 A, 炮 B} 和 {炮 B, 车 C},交集留下 {炮 B}。如果每步换捉对象,最终交集可能为空。遍历结束,一方仍有共同目标、另一方没有时,前者因长捉判负;双方都有或都没有共同目标,则返回和棋。遍历遇到将军的情况还另有分支,不能直接套用这个集合例子。
源码:轻量吃子模拟、捉子筛选与身份交集。棋规背景见象棋棋规疑云。
自然限招与特定子力和局
do_move() 维护自然限招计数。这份代码中,吃子会清零计数和双方将军次数;每方超过十次的将军及对应应将有计数豁免。到 rule60 >= 120 时,rule_judge() 先看是否还有合法走法:有则判和,没有则按无合法着法判负,保留最后一步造成胜负的情况。
随后还有特定子力组合的和局识别。代码先要求盘上无兵卒,再依据车马炮、士象配置分为直接和局或需要检查终局的情况。后一类先检查当前是否已无合法着法,再逐步检查是否存在一步使对手无合法着法的路线。这些条件对应源码列出的组合,适用范围应逐项核对。
用 FEN 与着法序列重建历史
FEN 保存棋子、行棋方和计数。set(fen) 据此建立新的起始状态,逐着将捉和之前的重复需要另行提供。复现历史相关问题时,应保存起始 FEN 与后续着法,再用 position … moves … 逐步建立状态链。
报告规则问题时,提供起始 FEN、后续着法、版本、规则设置和预期裁决。FEN 解析负责格式与局面条件检查;若要确认某盘面从开局可达,还需要相应棋谱或另外的可达性分析。
源码:FEN 初始化、从起点重放着法;命令形式见 UCI 协议。
perft 与规则回归各怎样测试?
perft 用 MoveList<LEGAL>、do_move() 和 undo_move() 展开至指定正深度,统计到达这一深度的走法路径。不同顺序即使到达同一盘面,也分别计数。根节点还输出每步的计数,帮助定位少生成或多生成的分支。
perft 的递归只枚举走法,完整历史规则由独立回归用例验证。两者覆盖范围如下:
| 测试 | 主要回答的问题 |
|---|---|
| perft | 走法生成、将帅安全过滤和落子撤销是否符合预期计数? |
| 棋规回归 | 给定起点与历史后,是否在正确时点作出预期裁决? |
| 搜索回归与对弈测试 | 搜索是否异常,改动对实战结果有何影响? |
perft 不调用 rule_judge();长将、长捉和限招需要包含完整历史的测试,棋力变化需要对弈统计。源码:perft 实现。
