残局库是预先计算得到的一组精确局面结果,适用于棋子数量或种类受限的博弈局面,尤其常见于国际象棋。对于覆盖范围内的每个局面,残局库会记录轮到走棋的一方能否强制获胜、是否在对手完美应对时必败,或能否确保和棋。有些格式还会记录距离将死或其他指定事件还有多少步。与启发式评估函数不同,残局库并不估算局面的价值,而是给出在一套明确规则下通过穷尽计算确定的结果。
覆盖范围与局面表示
国际象棋残局库通常按棋盘上的棋子数量上限分类,双方的王也计算在内。例如,五子残局库可以覆盖包含双王及另外三枚棋子的局面。一个具体的子力类别可以是王车对王象。
仅凭子力配置无法确定一个局面。查询时还必须区分:
- 各枚棋子所在的格子。
- 轮到哪一方走棋。
- 相关的特殊走法权利,例如吃过路兵。
- 残局库判定和棋时所需的其他规则状态。
许多实用格式不收录仍有王车易位权利的局面。五十回合规则所使用的半回合计数器,通常由查询软件处理,而不是直接纳入每个已存储的局面。依据重复局面提出和棋申诉同样取决于对局历史,而单独查询棋盘局面并不能反映这些历史信息。
因此,所谓“完整”覆盖是相对于特定规范而言的,包括允许出现的棋子、合法局面、支持的特殊走法,以及和棋规则的处理方式。覆盖某一子力类别的残局库,也依赖通过吃子和升变所到达局面的结果。
通过逆向分析构建
标准的构建方法是逆向分析:从结果已知的局面出发,向前追溯推理。这是在合法局面构成的有向图上进行的一种穷尽式动态规划。
简化的胜—和—负构建流程如下:
- 枚举选定覆盖范围内的所有合法局面。
- 识别终局局面,包括将死和逼和。
- 如果某个局面至少有一种合法走法能使对手进入必败局面,就将该局面标记为必胜。
- 如果某个非终局局面的每一种合法走法都会使对手进入必胜局面,就将该局面标记为必败。
- 反复执行,直到无法再传播任何结果。
- 将尚未确定结果的局面归为和棋。
最后一步有前提条件:必须正确规定局面图、边界局面的结果,以及对无限对局和和棋规则的处理方式。不能仅仅因为一次有限计算未能证明某个局面必胜,就认定它是和棋。
吃子会产生棋子更少的局面,因此构建时通常会使用此前生成的较小规模残局库。升变可能转入棋子总数相同的另一子力类别,也必须加以考虑。兵的移动还会引入额外的依赖关系,生成程序可以利用这些关系来组织计算。
这一过程与极小化极大算法的推理方式密切相关。必胜方只需有一种走法能够保持强制获胜;而要将一个局面判定为必败,则必须确认所有合法防守都会失败。与通常向前展开博弈树的方式不同,残局库生成过程力求求解覆盖范围内的整个局面空间,包括实际对局中不太可能出现的局面。
存储结果与距离指标
“最优走法”取决于所要优化的量。残局库使用多种指标,而这些指标推荐的走法未必相同。
胜—和—负
胜—和—负,简称 WDL,从轮到走棋一方的视角给出博弈论意义上的结果。基本的 WDL 结果不区分快速获胜与需要数百步才能取胜的情况。
有些格式采用更细致的分类,区分受五十回合规则影响的胜负。例如,Syzygy 残局库会将普通的胜负与受诅咒的胜局和受眷顾的败局区分开来。受诅咒的胜局是指忽略五十回合限制时可以获胜,但按其考虑该规则的解释则可守和的局面;受眷顾的败局则是防守方对应的结果。
这些类别必须结合相应格式的约定和当前对局状态来理解。
距将死步数
距将死步数,简称 DTM,衡量距离将死还有多远,约定必胜方尽量缩短这一距离,必败方则尽量延长。距离通常以半回合为单位,一方走一步即为一个半回合。
DTM 能精确回答最短多少步可以将死的问题。然而,传统的 DTM 值往往忽略五十回合规则。因此,某个在数学上可以强制达成的将死,在实际对局中可能无法实现,因为在取得必要进展之前,对手就可能有权申诉和棋。
距转换步数
距转换步数,简称 DTC,衡量距离某种指定的子力变化事件还有多远,通常指吃子或兵的升变。其确切定义取决于具体的残局库系统。
转换可以将漫长的残局分解为较小的问题。不过,最快实现转换并不一定意味着最快将死,而且仅凭这一点也不能保证符合按回合数判和的规则。
距归零步数
距归零步数,简称 DTZ,关注距离下一次使五十回合计数器归零的走法还有多远,即下一次走兵或吃子。实际定义也会考虑将死等终局结果,并可能编码与规则有关的区别。
DTZ 有助于在遵守回合计数限制的同时保持胜势。它并不只是到最近一次可走的兵步或吃子的距离:后续走法必须保持相应的博弈论结果。Syzygy 将 WDL 与 DTZ 信息结合使用。
和棋规则的重要性
精确结果始终是在指定规则下的精确结果。这一点在国际象棋中尤为重要,因为同样的棋子布局可能因之前的对局进程不同,而产生不同的实际后果。
根据五十回合规则,在双方达到规定回合数且期间没有走兵或吃子后,棋手可以申诉和棋。现代标准国际象棋规则还规定,如果双方各走了七十五步而没有发生上述任一事件,对局自动判和,但最后一步造成将死的情况除外。重复局面规则则进一步引入了对历史的依赖。
设想某个局面中,必胜方还需要二十个回合才能强制实现一次吃子。如果计数器刚刚归零,该局面可能确实是胜局;但如果已经连续四十个回合没有走兵或吃子,就未必如此。忽略计数器的残局库可以正确判定该局面在不受限制时能够获胜,却无法据此证明当前对局中也能获胜。
因此,软件必须将残局库信息与当前半回合计数、适用的竞赛规则,以及必要时的重复局面历史结合起来。
存储与查询
实际应用中的主要障碍是局面数量极其庞大。每增加一枚棋子,状态空间都会显著扩大,而生成过程所需的存储空间和工作内存,可能远大于最终压缩文件的大小。
具体实现通过以下方式降低这些成本:
- **规范化索引:**为每个支持的局面分配可复现的数值地址。
- **对称性约简:**通过允许的棋盘变换和同类棋子的互换,识别等价局面。
- **紧凑编码:**使用专门的数据结构存储结果和距离。
- **无损数据压缩:**在不改变已记录答案的前提下减少存储空间。
- **缓存与选择性加载:**将经常访问的信息保留在内存中,其他数据块则从存储设备读取。
并非所有表面上的对称关系都有效。兵的移动方式、升变方向和特殊走法权利,都限制了哪些变换能够保持局面的含义不变。
一次查询会将局面映射到相应的子力类别和索引,检索存储的结果,并对结果进行解释。选择走法时,可以查询各个合法后继局面,而不必为每个局面存储最佳走法。引擎可以在搜索期间使用紧凑的 WDL 数据,在选择走法时再查询体积更大的距离数据文件。
历史发展与主要系统
计算机生成的残局分析起步于计算机国际象棋发展的早期几十年。托马斯·施特勒莱因在 1970 年的博士研究中,对系统化残局计算作出了重要的早期贡献。此后,肯·汤普森生成了一批影响深远的残局库,并通过穷尽分析研究复杂残局。
后来出现了几个重要系统:
- 纳利莫夫残局库使距将死步数数据得到广泛传播,并成为国际象棋软件的标准资源。
- 罗蒙诺索夫残局库利用超级计算资源生成,于 2012 年将完整覆盖范围扩展到七子残局。
- Syzygy 残局库由罗纳德·德曼开发,注重紧凑的 WDL 和 DTZ 信息,以及与引擎的高效集成。完整的七子 Syzygy 数据随后于 2018 年问世。
这些系统在指标、索引、压缩和查询约定方面各不相同。因此,即便覆盖相同的子力配置,它们的输出也不一定可以互换使用。
应用与局限
当对局进入覆盖范围内的局面时,残局库可以让国际象棋引擎用精确信息取代不确定的评估。它们也能影响更早阶段的走法:如果搜索到达残局库覆盖的局面,就能获得该分支经过证明的结果,不过引擎仍须考虑这一结果是否与和棋规则相容。
在国际象棋分析中,残局库可用于核验残局习题、发现防守手段,并确定看似占优的局面是否真正能够获胜。它们揭示了一些需要极其漫长或有违直觉的调动才能获胜的局面,也表明某些传统残局判断并不完整。此外,残局库还能为搜索和评估软件提供结果精确的测试用例,包括通过机器学习开发的系统。
残局库的主要局限在于覆盖范围和结果解读。七子残局库无法直接回答八子局面的问题。它可以指出保持原有胜和负结果的走法,却未必能解释一个便于人类理解和运用的计划;某一距离指标偏好的走法,也可能与另一指标不同。结果的精确性还取决于生成过程是否正确、文件是否完整,以及索引和查询代码是否无误。
最后,即使实现了完整的残局覆盖,也不等于解决了整个国际象棋。它只求解了博弈状态空间中一个受限的区域;该区域之外的局面,仍然需要搜索、评估或其他方法来处理。