Sanmill 直棋应用程序开发白皮书

本文档详细阐述了 Sanmill 直棋程序的设计与开发过程，特别关注核心算法的设计与实现。我们将介绍一种结合了多种基于知识的搜索策略的方法。

直棋是一款经典的 "两人零和、完全信息、非偶然" 的游戏。Sanmill 程序采用最小搜索算法对博弈树进行搜索，并使用 Alpha-Beta 剪枝、MTD(f) 算法、迭代深化搜索和置换表来优化博弈树搜索过程。在对直棋游戏进行深入研究和分析的基础上，我们对游戏算法进行了大量的设计和优化，使程序达到了很高的智能水平。

为了提高性能，游戏算法引擎采用 C++ 编写，为了实现跨平台兼容性，App 的 GUI 使用了 Flutter 进行开发。我们利用平台通道在 Flutter UI 和游戏引擎之间进行数据交互。

代码总量约为 250,000 多行。游戏算法引擎是独立开发的，代码风格力求模仿 Stockfish。在线程管理和 UCI 模块中，我们借鉴了国际象棋引擎 Stockfish 的约 300 行代码。

我们采用 UCI 接口，以期创建一个通用框架，供其他直棋程序的开发者参考和借鉴。

概览

硬件需求

Android 手机

CPU: 1.5GHz 或更高
内存: 1GB 或更高
屏幕分辨率: 480x960 或更高
系统版本: Android 4.4 或更高

iOS 设备

系统版本: iOS 12 以上

PC

系统版本: Windows 7 以上
支持从 Windows 10/11 微软应用商店下载
Qt 版本已推出，仅用于算法改进后的自战和测试算法效果，支持加载完美的 AI 数据库

开发环境

Android Studio 4.1.3
Visual Studio Community 2031
Flutter 3.3.x
Android SDK version 31.0
Android NDK version 21.1

编程语言

游戏引擎: C++
Android 入口代码: Java
iOS 入口代码: Objective-C
用户界面: Dart（基于 Flutter 框架）

开发宗旨

开发此直棋应用程序旨在为用户提供一种娱乐和放松的方式，同时推广这一悠久历史的经典棋盘游戏。

功能特点

本直棋应用程序包含丰富的功能，包括：

支持人机对战、双人对战、机器对战三种游戏模式；
支持多种直棋规则变体，如九子直棋、十二子直棋，可自定义棋盘对角线设置，可选择是否使用 "飞子规则"，以及是否允许走封闭直棋等；
提供丰富的个性化设置，包括 UI 主要元素颜色、难度等级、AI 下棋方式、音效开关、先后手等；
支持查看走棋历史、展示统计数据；
提供恢复默认设置功能。

在 Android 平台上，应用程序能在意外崩溃的情况下收集相关信息。经过用户同意后，可通过 E-mail 客户端发送崩溃和诊断信息以帮助改进程序。其他平台暂不提供此功能。

技术亮点

本程序的游戏引擎采用 MTD(f) 和 Alpha-Beta 剪枝等博弈树搜索算法来实现最佳搜索策略。通过着法排序、置换表和预取技术来提高性能，同时使用迭代深化搜索方法对搜索时间进行控制。为了提高可移植性，我们采用了 Flutter 开发 UI。

直棋游戏简介

直棋，起源于古罗马，是一类在旧大陆广泛流传的两人传统棋类游戏。其吃子方式类似于方棋，采用成型吃子法。直棋规则和棋名因地域而异，但通常棋盘由数个同心正方形组成，正方形之间通过直线或斜线连接。

直棋在中国各地广泛流传，深受人们喜爱，并逐渐演变出众多变体，如 "三棋"、"成三棋"、"打三棋"、"连三"、"走城"、"龙棋"、"九子棋" 等。

本游戏在一个有 24 个点的棋盘上进行。棋盘最初为空，两名棋手各持有 9 个或 12 个棋子。持有白色棋子的一方率先开始游戏。

        X --- X --- X
        |     |     |
        | X - X - X |
        | |   |   | |
        | | X-X-X | |
        X-X-X   X-X-X
        | | X-X-X | |
        | |   |   | |
        | X - X - X |
        |     |     |
        X --- X --- X

        X --- X --- X
        |\    |    /|
        | X - X - X |
        | |\  |  /| |
        | | X-X-X | |
        X-X-X   X-X-X
        | | X-X-X | |
        | |/  |  \| |
        | X - X - X |
        |/    |    \|
        X --- X --- X

游戏共有三个阶段：

开局阶段

玩家轮流将棋子放置在空点上。

中盘阶段

当所有棋子都被放置后，玩家可以将棋子移动至任意相邻的空点。

残局阶段

当一名棋手仅剩下三个棋子时，他可以将任意棋子跳至任何空点。

开局时，玩家轮流放置棋子。随后，他们可以将棋子移至任意空位。当棋子放置完毕后，游戏进入中盘阶段。在此阶段，玩家可以将棋子移至相邻的空点。如果玩家在游戏过程中将三颗棋子排成一直线 —— 这被称为“直”（或“成三”、“连线”） —— 他们可以移除对手任意一颗非成三棋子。

当玩家仅剩三颗棋子时，游戏进入残局阶段。此时，该玩家可以将棋子跳至棋盘上的任意空点。

游戏的结束条件有以下几种：

当一名棋手的棋子数量少于三颗时，该棋手失败。
当一名棋手无法进行合法移动时，该棋手失败。
如果中盘或残局阶段的棋局重复出现，则判定为平局。

在直棋爱好者中，存在两个争议问题。首先，在开局时，可能会出现两个“成三”的情况。在这种情况下，是否应允许玩家移除对手一个或两个棋子？我们的实现支持这两种可能。其次，关于一名棋手刚完成一个成三，但对手的所有棋子均处于成三状态的情况。此时，该棋手是否可以移除一颗对手的棋子？在我们的实现中，这一规则是可配置的。

设计理念

如今市面上存在许多不同版本的直棋游戏。最流行的一种——九子标准直棋，被证明是平局。这个结果是由Palph Gasser通过使用Alpha-Beta搜索和终盘数据库技术实现的。

逆向分析法用于计算所有中盘和残局位置的数据库（约100亿个不同位置）。这些局面被划分为28个独立的数据库，根据棋盘上的棋子数量进行分类，例如3个白棋对3个黑棋的局面，4-3、4-4...直到9-9的局面。

接着对开局阶段进行18层的Alpha-Beta搜索，确定初始位置（空棋盘）的价值。只需要9-9、9-8和8-8的数据库就可以确认对局是平局。

目前一些实现正在使用数据库来完善无敌的人工智能，例如：

King Of Muehle
http://muehle.jochen-hoenicke.de/
https://www.mad-weasel.de/morris.html

由于数据库非常庞大，通常需要为游戏规则建立一个80GB的数据库，此数据库仅适用于PC或通过App查询的服务器。由于数据库的庞大，为所有规则变体建立数据库是不现实的，因此本程序主要支持九子直棋的标准规则。

支持各种规则变体是本程序的特色。另一方面，在不使用庞大数据库的情况下，我们希望利用先进的搜索算法和人类智慧，尽可能提高智能水平，并细分难度等级，让玩家体验到升级的乐趣。

此外，对于PC的Qt版本，我们已经支持使用九子直棋游戏——完美的游戏电脑建立的数据库。遗憾的是，这不是一个标准的九子直棋规则。它在主要方面遵循规则，但在一些细节上存在差异，我们认为这可能是原作者的疏忽导致的。值得指出的是，我们目前还没有获得标准规则的详细文本。我们仅通过与其他程序的比较来验证和推测规则的标准。而支持访问该数据库的主要目的是评估人工智能算法的能力，通过对完美人工智能的平局率来衡量算法的有效性。其他标准规则的数据库暂时没有开放源代码和接口，因此无法连接。

未来，我们可能会使用建立完美人工智能数据库的算法来创建我们自己的数据库，但这需要承担存储数据库的服务器成本。预计我们在短期内不会实施这个计划。从中期来看，通过终局数据库或NNUE进行训练，以较低成本继续提高智能水平会更为可行。

我们正在分享和免费分发Sanmill项目所需的代码、工具和数据。我们之所以这样做，是因为我们相信开放软件和开放数据是实现快速进步的关键因素。我们的最终目标是汇集社区的力量，使Sanmill成为一个强大的程序，为全球直棋爱好者带来乐趣，特别是在欧洲、南非、中国以及其他直棋游戏广泛传播的地区。

总之，我们的设计意图是在不借助庞大数据库的情况下，通过先进的搜索算法和丰富的人类知识，尽可能提高智能水平。同时，支持各种规则变体，使玩家可以根据自己的喜好选择并体验到不同难度等级的乐趣。我们将继续努力，为直棋爱好者提供更高质量的游戏体验。

模块

算法引擎

算法引擎模块负责根据给定的棋盘位置和状态信息（如谁先行棋）搜索最佳着法，并将结果返回至用户界面模块。算法引擎可分为以下几个子模块：

位棋盘表示
局面评估（又称“审局”）
无锁哈希表
直棋游戏逻辑处理
着法生成器
着法选择器
配置管理
规则管理
最佳着法搜索
线程管理
置换表
通用国际象棋接口（UCI）
UCI 选项管理

UI 前端

UI 模块采用 Flutter 进行开发，具备高开发效率、跨平台一致性、美观的用户界面以及与原生性能相当的优势。UI 模块可细分为以下几个部分：

直棋逻辑模块：将算法引擎中的直棋逻辑模块翻译成 Dart 语言，包括游戏逻辑、直棋行为、位置管理、移动历史等子模块。
引擎通信模块：负责与使用 C++ 编写的游戏引擎进行交互。
命令模块：管理与游戏引擎交互的命令队列。
配置管理：主要负责 Hive 数据库管理。
绘制模块：包括棋盘绘制和棋子绘制。
服务模块：包括音频服务。
风格模块：包括主题风格和颜色风格。
页面模块：包括棋盘页面、侧边菜单页面、游戏设置页面、主题设置页面、规则设置页面、帮助页面、关于页面、许可页面以及各种 UI 组件。
多语言支持：包括英文和中文字符串文本资源。

这样的模块划分有助于实现功能的清晰划分和高效协同，提高整个项目的开发和维护效率。

算法设计

极小化极大算法

程序采用 Alpha-Beta 搜索算法的变种进行实现。为了深入了解 Alpha-Beta 算法，首先需要掌握 Minimax（极小化极大算法）的基本原理。

在计算机科学领域，编写人机博弈程序是一项极富挑战性的任务。诸如国际象棋等棋类游戏的博弈程序便是其中的典型代表。这些程序往往遵循一种名为 Minimax 的算法，结合各种子算法共同实现。

Minimax 算法，即极小化极大算法，旨在找出失败可能性最大的情况中的最小值。它广泛应用于双方对抗的棋类游戏和程序中，如五子棋、象棋等。在这类游戏中，两名玩家轮流进行操作。Minimax 算法作为基于搜索的博弈算法的基础，是一种零和算法。一方在所有可选项中选择能使自己优势最大化的选项，而另一方则选择使对手优势最小化的方法。

Minimax 算法的核心思想是悲观主义，即假设对手每一步都会使我方处于当前理论上最不利的局面。换句话说，假设对手具有完美决策能力。因此，我方的策略应当是在对手的最优决策下使自身损失最小的选择。

Minimax 算法并不寻求理论上的最优解，因为理论最优解往往取决于对手是否足够愚蠢。在 Minimax 算法中，我方始终处于主动地位。如果对手每一步都做出完美决策，那么我方可以达到预期的最小损失局面。如果对手未能做出完美决策，我方可能会达到比预计最悲观情况更好的结局。总之，我方的目标是在最坏情况中选择最好的策略。

解决博弈问题的一般方法是将局面组织成一棵树，其中树的每个节点表示一种局面，父子关系表示从父局面经过一步可以到达子局面。Minimax 算法也遵循这一原则，通过搜索以当前局面为根的局面树来确定下一步的选择。局面树搜索算法的核心在于评估每个局面的价值。

实现

以下是 Minimax 算法的间接递归深度优先搜索的伪代码。为简单起见，省略了递归调用前后的 make making 和 unmaking。

int maxi ( int depth ) {
    if ( depth == 0 ) return evaluate ();
    int max = -oo;
    for ( all moves) {
        score = mini ( depth - 1 );
        if ( score > max )
            max = score;
    }
    return max;
}

int mini ( int depth ) {
    if ( depth == 0 ) return -evaluate ();
    int min = +oo;
    for ( all moves) {
        score = maxi ( depth - 1 );
        if ( score < min )
            min = score;
    }
    return min;
}

Alpha-Beta 剪枝

Alpha-Beta 剪枝是一种高效搜索算法，旨在减少极小化极大算法（Minimax 算法）搜索树的节点数。作为一种对抗性搜索算法，它主要应用于机器对战的二人游戏（如井字棋、象棋、围棋等）。当算法评估出某策略的后续走法比之前策略的效果还差时，将停止计算该策略的后续发展。尽管该算法剪去了不影响最终决策的分枝，但其得出的结论与极小化极大算法相同。

历史

1958 年，Allen Newell 和 Herbert A. Simon 使用了 John McCarthy 提出的所谓的“近似”Alpha-Beta 算法，这个算法当时已经经过多次改进。亚瑟·李·塞谬尔（Arthur Samuel）有一个早期版本，同时Richards、Hart、Levine 和/或 Edwards 在美国分别独立发现了 Alpha-Beta 剪枝算法。1956 年达特默思会议上，McCarthy 提出了类似的理念，并在 1961 年向他的一群学生（包括 MIT 的 Alan Kotok）推荐。Alexander Brudno 独立发现了 Alpha-Beta 算法，并在 1963 年发布了成果。1975 年，Donald Knuth 和 Ronald W. Moore 对算法进行了优化，Judea Pearl 则在 1982 年证明了其最优性。

改进原版极小化极大算法

Alpha-Beta 剪枝算法的优势在于减少搜索树的分枝，将搜索时间集中在“更有希望”的子树上，从而提高搜索深度。与极小化极大算法一样，它也属于分支限界类算法。当节点搜索顺序达到最优化或近似最优化（即将最佳选择放在各节点的首位）时，在相同的时间内搜索深度可达极小化极大算法的两倍以上。

在分枝因子为 b，搜索深度为 d 层的情况下，需要评估的最大叶节点数目为 O(b^d) —— 即与简单极小化极大搜索相同。若着法排序最优（即始终优先搜索最佳着法），则需要评估的最大叶节点数目按层数奇偶性，分别约为 O(b^{d/2})。其中层数为偶数时，搜索因子相当于减少了其平方根，等于能以同深度搜索两次。实际上，由于节点生成顺序是随机的，实际需要评估的节点平均约为 O(b^{3d/4})。

在 Alpha-Beta 剪枝中，子树通常会被先手方优势或后手方优势暂时主导。如果招式排序错误，这种优势会多次切换，每次都会导致效率下降。随着层数加深，局面数量会呈指数性增长，因此早期招式的排序价值很大。尽管改善任意深度的排序都可以指数性减少总搜索局面，但相对经济的方法是对临近根节点深度的所有局面进行排序。在实践中，着法排序通常由早期、小型搜索决定，例如通过迭代加深。

Alpha-Beta 算法使用两个值 alpha 和 beta，分别代表大分玩家可接受的最高分以及小分玩家可接受的最低分。alpha 和 beta 的初始值分别为正负无穷大，即双方玩家都从可能的最低分开始游戏。当选择某节点的特定分枝后，小分玩家可接受的最低分可能小于大分玩家可接受的最高分（beta <= alpha）。在这种情况下，父节点不应选择这个节点，因为这将导致父节点分数降低，所以该分枝的其他节点没有必要继续探索。

综上所述，Alpha-Beta 剪枝算法在减少搜索树分枝、提高搜索深度和效率方面具有明显优势，从而使得在有限的时间内能够找到更优的解决方案。这使得该算法在二人对战游戏领域得到广泛应用，如国际象棋、围棋等。

伪代码

下面为一有限可靠性版本的 Alpha-Beta 剪枝的伪代码：

function alphabeta(node, depth, α, β, maximizingPlayer) // node = 结点，depth = 深度，maximizingPlayer = 大分玩家
    if depth = 0 or node 是叶子结点
            return 结点的评估值
        if maximizingPlayer
            v := -∞
            for 每个子结点
                v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) // child = 子结点
                α := max(α, v)
                if β ≤ α
                    break // β 裁剪
            return v
        else
            v := ∞
            for 每个子结点
                v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
                β := min(β, v)
                if β ≤ α
                    break // α 裁剪
            return v

(* 初始调用 *)
alphabeta(origin, depth, -∞, +∞, TRUE) // origin = 初始结点

在这个有限可靠性的 Alpha-Beta 算法中，当 v 超出调用参数α和β构成的区间时（v < α 或 v > β），alphabeta 函数会返回值 v。相对而言，强化的有限可靠性 Alpha-Beta 算法限制函数返回在 α 与 β 区间内的值。

Negamax 算法

负极大值搜索（Negamax）是极小化极大算法（Minimax）的一个变种，适用于搜索二人零和游戏的最佳着法。

负极大值算法简化了极小化极大算法，其核心原理基于以下等式：max(a, b) = -min(-a, -b)。具体而言，一个着法对玩家 A 的估值等于对玩家 B 的估值的相反数。因此，当前玩家需要找到一个使其估值的相反数最大化的着法——其后继着法的分数必须由对方玩家评估。这种思路适用于玩家 A 和 B，意味着同一个过程可以应用于两个玩家。因此，负极大值算法是对极小化极大算法的简化，不需要针对 A 返回极大值而对 B 返回极小值。

请勿将负极大值算法与 NegaScout 算法混淆。NegaScout 算法是 Alpha-Beta 剪枝算法的一种巧妙应用，用于快速计算极小化极大值或负极大值，该算法始于 1980 年代。值得注意的是，Alpha-Beta 剪枝算法本身的目标就是通过放弃搜索无用路径来加快计算极小化极大值或负极大值。

许多对抗性搜索算法都是基于负极大值算法实现的。

基本的负极大值算法

负极大值算法和极小化极大算法采用相同的搜索树，每个节点（包括根节点）都代表了双人游戏中的一个游戏状态，例如棋盘上的一种布局。节点到子节点的转换则代表了当前玩家的一种可能着法。

负极大值搜索的目标是找到作为根节点的当前玩家的估值。以下伪代码展示了负极大值算法的基本逻辑，其中搜索的最大深度作为参数传入：

function negamax(node, depth, color)
   if depth = 0 or node is a terminal node
        return color * the heuristic value of node

    bestValue := −∞
    foreach child of node
        v := −negamax(child, depth − 1, −color)
        bestValue := max( bestValue, v )
    return bestValue

// 玩家 A 的初始调用
rootNegamaxValue := negamax(rootNode, depth, 1)
rootMinimaxValue := rootNegamaxValue

// 玩家 B 的初始调用
rootNegamaxValue := negamax(rootNode, depth, -1)
rootMinimaxValue := -rootNegamaxValue

根节点的分数是从某个子节点的值直接继承过来的，被选中的最佳分数子节点即代表了此步的最佳着法。虽然该段伪代码仅返回 bestValue 作为最佳分数，但在实际应用中，需要同时为根节点返回分数和最佳着法。在基本的负极大值算法中，根节点仅需关心最佳分数，而非根节点的最佳着法无需保存或返回。

有一点可能会引起困惑，即当前节点的估值如何计算。在上述伪代码中，该值始终以玩家 A 的角度给出，其 color 值为 1。换言之，高估值意味着局势对 A 更有利，这与通常的极大极小值算法保持一致。估值结果并不一定与节点的返回值（bestValue）一致，因为还需要在 negamax 函数中乘以 color 参数。节点的返回值（bestValue）是从当前玩家角度给出的估值。

负极大值的得分与极大极小值算法中，当当前玩家为 A 时的估值相同，即将玩家 A 视为极大值玩家。负极大值算法会搜索所有子节点以寻找最大值。对于玩家 B 层的节点，极大极小值分数正好是负极大值分数的相反数，玩家 B 相当于极大极小值算法中的极小层。

另一种变体是省略 color 参数。如果省略，则估值函数必须以当前玩家的视角返回估值（也就是估值函数必须知道当前玩家是谁，对 A 和对 B 的返回值是相反数）。

带 Alpha-Beta 剪枝的负极大值算法

对极大极小值算法的优化同样可以应用于负极大值算法。正如在极大极小值算法中的作用一样，Alpha-Beta 剪枝能减少负极大值算法所需搜索的节点数。

以下伪代码展示了一个带有 Alpha-Beta 剪枝的负极大值算法：

function negamax(node, depth, α, β, color)
    if depth = 0 or node is a terminal node
        return color * the heuristic value of node

    childNodes := GenerateMoves(node)
    childNodes := OrderMoves(childNodes)
    bestValue := −∞
    foreach child in childNodes
        v := −negamax(child, depth − 1, −β, −α, −color)
        bestValue := max( bestValue, v )
        α := max( α, v )
        if α ≥ β
            break
    return bestValue

// 玩家 A 的初始调用
rootNegamaxValue := negamax(rootNode, depth, −∞, +∞, 1)

α（alpha）和 β（beta）分别代表在给定树深度下子节点值的下限和上限。Negamax 将根节点的参数 α 和 β 设置为可能的最低和最高值。其他搜索算法，例如 NegaScout 和 MTD-f，可能会针对搜索树中某个层级的节点估值下界（α）和上界（β）来设定更精确的值，以优化搜索性能。

当算法检测到一个超出 [α,β] 范围的值时，会剪除该子树——如上述伪代码中第12行的 break。因此，就无需搜索该子树。剪枝完全基于节点的返回值——bestValue。若一个节点返回的值在其初始 α 和 β 范围内，则认为返回值是准确的，该值将作为算法返回的值，不需要剪枝和边界限制。如果一个节点的返回值超出了该范围，那么该值代表了节点估值的上界（如果 value ≤ α）或下界（如果 value ≥ β）。Alpha-Beta 剪枝最终会丢弃任何超出范围的值，因为这些值对最终的搜索结果没有影响。

带 Alpha-Beta 剪枝以及置换表的负极大值算法

置换表（Transposition table）有选择地对棋局树中的节点值进行记忆化（Memoization）。置换是一个术语，表示一个给定的棋盘位置可以通过不同的棋步序列以多种方式达到。

当 negamax 搜索对局树并多次遇到同一节点时，置换表可以返回该节点先前计算出的数值，从而避免对该节点数值的冗长和重复计算。这样，Negamax 的性能得到了提升，特别是对于那些许多路径共同导致一个特定节点的博弈树。

下面的伪代码展示了如何将置换表功能集成到带有 Alpha-Beta 剪枝的 Negamax 算法中：

function negamax (node, depth, α, β, color) is
    alphaOrig := α

    (* Transposition Table Lookup; node is the lookup key for ttEntry *)
    ttEntry := transpositionTableLookup (node)
    if ttEntry is valid and ttEntry.depth ≥ depth then
        if ttEntry.flag = EXACT then
            return ttEntry.value
        else if ttEntry.flag = LOWERBOUND then
            α := max (α, ttEntry.value)
        else if ttEntry.flag = UPPERBOUND then
            β := min (β, ttEntry.value)

        if α ≥ β then
            return ttEntry.value

    if depth = 0 or node is a terminal node then
        return color × the heuristic value of the node

    childNodes := generateMoves (node)
    childNodes := orderMoves (childNodes)
    value := −∞
    for each child in childNodes do
        value := max (value, −negamax (child, depth − 1, −β, −α, −color))
        α := max (α, value)
        if α ≥ β then
            break

    (* Transposition Table Store; node is the lookup key for ttEntry *)
    ttEntry.value := value
    if value ≤ alphaOrig then
        ttEntry.flag := UPPERBOUND
    else if value ≥ β then
        ttEntry.flag := LOWERBOUND
    else
        ttEntry.flag := EXACT
    ttEntry.depth := depth
    transpositionTableStore (node, ttEntry)

    return value

(* 玩家 A 的初始调用 *)
negamax (rootNode, depth, −∞, +∞, 1)

在 Negamax 算法中，Alpha-Beta 剪枝和最大搜索深度限制可能导致博弈树中部分不精确的节点评估和完全跳过的节点。这使得为 Negamax 增加置换表优化变得复杂。仅在表中跟踪节点的值是不够的，因为值可能并非节点的真实值。因此，代码必须保留并恢复 value 与 alpha/beta 参数的关系以及每个置换表项的搜索深度。

置换表通常是有损的，会省略或覆盖其表中某些博弈树节点的先前值。这是必要的，因为 Negamax 访问的节点数量往往远远超过置换表的大小。丢失或省略的表项是非关键性的，不会影响 Negamax 的结果。然而，丢失的条目可能导致 Negamax 更频繁地重新计算某些博弈树节点的值，从而影响性能。

实现

在 Sanmill 中，关键的实现代码如下所示:

    for (int i = 0;  i < moveCount;  i++) {
        ss.push (*(pos));
        const Color before = pos->sideToMove;
        Move move = mp. moves [i]. move;
        pos->do_move (move);
        const Color after = pos->sideToMove;

        If (after != before) {
            value = -search (pos, ss, depth - 1 + epsilon,
                            originDepth, -beta, -alpha, bestMove);
        } else {
            value = search (pos, ss, depth - 1 + epsilon,
                           originDepth, alpha, beta, bestMove);
        }

        pos->undo_move (ss);

        if (value >= bestValue) {
            bestValue = value;

            if (value > alpha) {
                if (depth == originDepth) {
                    bestMove = move;
                }

                break;
            }
        }
    }

注意

由于直棋可能会出现一方成三后继续吃对方的棋子，而不是换成另一方的状态，所以奇数层和偶数层可能不会被严格划分为对局的两方。因此，在迭代过程后有必要确定一方是否发生变化，然后决定是否取反。

主要变例搜索 (PVS)

在 Alpha-Beta 剪枝算法中，由于存在剪枝，搜索过程并不完整，所以剪枝算法得到的估值不一定是准确值。通过分析可知，对于函数调用：

value = alpha_beta(alpha, beta);

当 alpha < value < beta 时，此估值一定是准确值；此搜索节点称为 PV（Principal Variation，主要变例）节点。当 value ≤ alpha时，此估值将不是准确值，而只是估值上限；此搜索节点称为 alpha 节点。当 value ≥ beta 时，此估值也不是准确值，而只是估值下限；此搜索节点称为 beta 节点。

如上所述，α-β剪枝算法主要关注(alpha, beta)区间，也称为搜索窗口。相较于 alpha 节点和 beta 节点，程序在搜索 PV 节点时耗时较长。减小搜索窗口的宽度会增加剪枝的可能性，从而缩短搜索时间。特别是当窗口宽度减为零，即搜索窗口为 (t-1, t) 时，这便形成了零宽窗口（亦称为极小窗口）。零宽窗口搜索的结果仅有两种：估值在窗口下方的 alpha 节点，或估值在窗口上方的 beta 节点。零宽窗口搜索能够方便地判别估值的取值范围，由于不会出现 PV 节点，该判别过程具有很高的效率，因此广泛应用于各种优化的 α-β 剪枝算法中。

主要变例搜索（Principal Variation Search，简称 PVS）算法便是一种采用零宽窗口技术、针对 PV 节点进行优化的剪枝算法，也被称为极小窗口搜索（Minimal Window Search）算法。Tony Marsland 和 Murray Campbell（1982）最早提出了 PVS 算法，随后，Alexander Reinefeld（1983）也提出了类似的 NegaScout 算法，并证明了其正确性。

接下来我们将探讨 PVS 算法的优化方式。在前面介绍的 α-β 剪枝算法中，每走一步棋后，我们总是使用以下形式进行递归搜索：

value = -alpha_beta(-beta, -alpha);

然而，对于 PVS 算法，它首先假设已经找到了最佳估值（其值为 alpha），接着应用零宽窗口搜索以快速判断此假设的正确性：

value = -alpha_beta(-alpha-1, -alpha);

若零宽窗口搜索的结果为 value ≤ alpha，则说明之前的假设是正确的，即这一步棋不会产生更好的估值，程序将直接放弃这步棋。在这种情况下，由于采用了零宽窗口搜索，搜索时间将显著减少。

但是，如果零宽窗口搜索的结果显示之前的假设是错误的，那么还需要重新进行一次常规窗口的搜索。在这种情况下，PVS 算法实际上多进行了一次零宽窗口搜索。然而，由于零宽窗口搜索所需时间相对较少，且出现前一种情况的概率通常较大，因此额外进行一次零宽窗口搜索的代价是值得的。下面是 PVS 算法的代码：

int pvs(int alpha, int beta, int depth, int pass = 0){
    // 当前最佳分值，预设为负无穷大
    int best_value = -INF_VALUE;
    // 尝试每个下棋位置
    for (int pos = A1; pos <= H8; ++pos) {
        // 试着下这步棋，如果棋步合法
        if (make_move(pos)) {
            int value;
            // 如果到达预定的搜索深度，直接给出局面估值
            if (depth <= 1) value = -evaluation();
            // 如果尚未找到有效节点……
            else if (best_value == -INF_VALUE
                // ……或者零宽窗口搜索表明存在更好的结果……
                || (value = -pvs(-alpha-1, -alpha, depth-1, 0)) > alpha
                // ……且不会引发剪枝
                && (alpha = value) < beta) {
                    // 进行常规窗口搜索
                    value = -pvs(-beta, -alpha, depth-1, 0);
            }
            // 撤消棋步
            undo_move(pos);
            // 如果这步棋引发剪枝
            if (value >= beta) {
                // 立即返回当前最佳结果
                return value;
            }
            // 如果这步棋更好
            if (value > best_value) {
                // 保存更好的结果
                best_value = value;
                // 更新估值下限
                if (value > alpha) alpha = value;
            }
        }
    }
    // 如果没有合法棋步
    if (best_value == -INF_VALUE) {
        // 如果上一步棋也是跳步，表明对局结束
        if (pass) {
            // 直接给出精确比分
            best_value = get_score();
        // 否则这步棋跳步
        } else {
            make_pass();
            // 递归搜索，并标明该跳步
            best_value = -pvs(-beta, -alpha, depth, 1);
            // 撤消跳步
            undo_pass();
        }
    }
    // 返回最佳结果
    return best_value;
}

由于 PVS 算法的高效性是基于已找到最佳估值的假设之上的，所以在尚未找到有效节点时，可以只进行常规窗口搜索。

总的来说，PVS 算法的速度通常会比常规α-β剪枝算法更快。如果将 PVS 算法与着法排序、散列表等优化技术相结合，算法的高效性将得到更好的体现。

MTD(f) 算法

正如前文所述，零宽窗口搜索（又称为极小窗口搜索）的结果只有两种：要么估值在窗口之上，要么估值在窗口之下。因此，当我们对某个区间进行搜索时，可以选择区间上的一个点进行零宽窗口搜索尝试。利用这种一分为二的特点，可以缩小估值的取值范围。确定新的估值区间后，我们还可以再次进行尝试。通过反复尝试，可以不断缩小搜索范围，最终找到局面估值。

在选择每次尝试的值时，通常的方法是采用二分法，即每次都选择估值区间的中点进行尝试。采用二分法的效率确实较高，但荷兰计算机科学家 Aske Plaat 通过研究发现，在多次搜索尝试过程中，局面估值往往会出现在前一次搜索的返回值附近，而机械地选择中点作为新的尝试值并不是最高效的方法。因此，他提出了一种选择前一次搜索返回值作为新尝试值的 MTD 算法（Memory-enhanced Test Driver，缓存增强试探法）——MTD(f)。以下是 MTD(f) 算法的代码：

int mtd(int alpha, int beta, int depth, int test) {
    int best_value;
    do {
        // 进行零宽窗口试探
        best_value = alpha_beta(test-1, test, depth, 0);
        // 如果是alpha节点
        if (best_value < test) {
            // 更新估值上限，并将此做为新的试探值
            test = beta = best_value;
        // 否则是beta节点
        } else {
            // 更新估值下限
            alpha = best_value;
            // 新的试探值
            test = best_value + 1;
        }
    } while (alpha < beta);
    return best_value;
}

MTD(f)算法简便且高效。然而，由于MTD(f)算法需要对同一局面进行多次搜索，因此采用散列表是必要的，否则无法充分体现其高效性。这也是MTD算法名称中缓存增强（Memory-enhanced）的含义所在。实践证明，在同样应用散列表的情况下，MTD(f)算法的搜索速度通常会比PVS算法稍快，MTD(f)算法的高效性已得到广泛认可。

在应用MTD(f)算法时，需要一个初始试探值，一般可以简单地选取初始搜索区间的中点，当然也可以根据具体情况选择更有利于搜索的值。由于该算法必须采用散列表，散列表的性能对于整体算法的效率至关重要。另外，估值的取值范围大小也会影响MTD(f)算法的搜索速度。通常情况下，估值越粗略（即取值范围较小），搜索速度会越快，因为试探次数较少。

若算法需要求解最佳棋步，那么最佳棋步的选取问题应引起注意。尽管MTD(f)在每次零宽窗口试探后都会得到一个新的最佳棋步，但对于alpha节点（best_value < test时），我们所得到的“最佳棋步”只是满足估值上限的棋步，而非真正最佳的棋步。因此，我们应舍弃这种虚假的最佳棋步，保留上一次搜索结果。

算法性能

NegaScout算法递归地调用零窗口搜索。MTD(f)从搜索树的根部开始调用零窗口搜索。在象棋、跳棋和黑白棋等游戏中，MTD(f)算法的实现在实践中比其他搜索算法（如 NegaScout）更具效率（搜索更少的节点）。为了使NegaScout或MTD(f)等搜索算法有效地执行，转置表必须运作良好。否则，例如，当发生哈希碰撞时，子树将被重新扩展。当MTD(f)算法应用于具有明显奇偶效应的程序时，即搜索树根节点在偶数搜索深度时得分较高，而在奇数搜索深度时得分较低，建议使用单独的f值作为搜索起始值，尽量接近最小值。否则，搜索需要更多次迭代才能收敛到最小值，特别是对于具有细粒度评估功能的评价函数。

零窗口搜索相较于宽窗口搜索更快地达到截止点，因此它们比宽窗口搜索更高效。然而，在某种程度上，它们也更难以妥协。由于MTD(f)仅使用零窗口搜索，而Alpha-Beta和NegaScout同时使用宽窗口搜索，MTD(f)表现得更为高效。然而，对于具有较大奇数/偶数波动和细粒度评估功能的引擎来说，较宽的搜索窗口相对较为宽容。正因如此，一些国际象棋引擎尚未改用MTD(f)。在对Chinook（跳棋）、Phoenix（国际象棋）和Keyano（黑白棋）等锦标赛级程序进行测试时，MTD(f)算法的表现优于所有其他搜索算法。

近期的算法，如最佳节点搜索，被建议优于MTD(f)。

迭代加深搜索

通常情况下，程序搜索得越深，其棋力就越强。如果搜索深度足以搜索到终局，便能得到真正的最佳棋步和精确比分。然而，随着搜索深度的增加，搜索所需时间也将急剧上升。在实际下棋或比赛过程中，时间往往是有限的。例如，在常规黑白棋比赛中，双方的总用时通常限定为20分钟。受时间限制，程序的搜索深度无法事先确定，需要在下棋过程中动态调整。为此，程序在每步棋时可以根据剩余时间合理分配当前步棋的思考时间。然而，由于程序软硬件环境的差异和局面的不断变化，搜索深度与搜索时间之间没有固定关系，因此搜索深度仍然无法确定。在这种情况下，可以采用迭代深化搜索（Iterative Deepening Search）。迭代深化搜索的代码如下：

    // 如果进一步搜索的深度未超过剩余空位数
    while (++depth <= n_empty) {
        // 进一步搜索
        value = alpha_beta(-INF_VALUE, INF_VALUE, depth);
        // 如果超时
        if (TIME_OUT) break;
    }

为了储存搜索到的最佳棋步结果，我们引入全局变量result。

// 无穷大分值
#define INF_VALUE 10000
// 初始搜索深度
#define MIN_DEPTH 4
// 测试是否超时
#define TIME_OUT (stop_clock && clock() >= stop_clock)
// 最佳棋步结果
static int result;
// 搜索终止时刻
static int stop_clock;

int alpha_beta(int alpha, int beta, int depth, int pass = 0){
    // 当前最佳棋步
    int best_move = PASS;
    // 当前最佳分值，预设为负无穷大
    int best_value = -INF_VALUE;
    // 尝试每个下棋位置
    for (int pos = A1; pos <= H8; ++pos) {
        // 试着下这步棋，如果棋步合法
        if (make_move(pos)) {
            int value;
            // 如果到达预定的搜索深度，直接给出局面估值
            if (dept <= 1) value = -evaluation();
            // 否则，对所形成的局面进行递归搜索
            else value = -alpha_beta(-beta, -alpha, depth - 1);
            // 撤消棋步
            undo_move(pos);
            // 如果超时
            if (TIME_OUT) return -INF_VALUE;
            // 如果这步棋引发剪枝
            if (value >= beta) {
                // 立即返回当前最佳结果
                result = pos;
                return value;
            }
            // 如果这步棋更好
            if (value > best_value) {
                // 保存更好的结果
                best_move = pos;
                best_value = value;
                // 更新估值下限
                if (value > alpha) alpha = value;
            }
        }
    }
    // 如果没有合法棋步
    if (best_value == -INF_VALUE) {
        // 如果上一步棋也是跳步，表明对局结束
        if (pass) {
            // 直接给出精确比分
            best_value = get_score();
        // 否则这步棋跳步
        } else {
            make_pass();
            // 递归搜索，并标明该跳步
            best_value = -alpha_beta(-beta, -alpha, depth, 1);
            // 撤消跳步
            undo_pass();
        }
    }
    // 返回最佳结果
    result = best_move;
    return best_value;
}

int ids(int time_remain){
    // 开始时刻
    int start_clock = clock();
    // 初始搜索深度
    int depth = MIN_DEPTH;
    // 初始搜索不限时，以确保得到一个正确的棋步
    stop_clock = 0;
    // 进行搜索深度
    int best_value = alpha_beta(-INF_VALUE, INF_VALUE, depth);
    int best_move = result;
    // 如果进一增加搜索深度步搜索的深度未超过剩余空位数
    while (++depth <= n_empty) {
        // 根据已进行的搜索情况重新调整搜索终止时刻
        stop_clock = start_clock + (clock_t)(time_remain * (CLOCKS_PER_SEC / 1000.) - (clock() - start_clock)) / ((n_empty - depth + 2) / 2);
        // 进行常规的剪枝算法
        int value = alpha_beta(-INF_VALUE, INF_VALUE, depth);
        // 如果超时
        if (TIME_OUT) break;
        // 更新最佳结果
        best_move = result;
        best_value = value;
    }
    // 返回最佳结果
    result = best_move;
    return best_value;
}

迭代深化搜索的思路相当直接：首先从较浅的搜索深度（如初始搜索深度设为1）开始进行搜索，然后逐步加深搜索深度进行后续搜索，直至时间耗尽为止。这样可以根据实际可用时间来确定搜索深度。当然，上述代码仅作示范，在实际应用中，alpha_beta()函数内部还应包含超时判断。如果某一搜索深度过程中时间用尽，搜索应立即终止，以避免等待本轮搜索结束而导致时间消耗殆尽。

你可能会注意到，只有最后一轮搜索才是真正有价值的，而在此之前的搜索看似在浪费时间。实际上，程序的搜索深度每增加一层，搜索时间通常成倍增长。大部分时间将用在最后一轮搜索上，而之前的搜索时间基本可以忽略。此外，迭代深化搜索可以与散列表结合使用，这样较浅层次搜索的结果将保存在散列表中，对更深层次搜索具有一定的指导作用。如果采用MTD(f)算法，前一次搜索的结果还可以作为更深一层搜索的初始探测值：

int deepening() {
    int value = 0;
    // 初始搜索深度
    int depth = 1;
    do {
        // 进行常规的MTD(f)算法
        value = mtd(value, depth);
        // 增加搜索深度
        depth++;
    // 直到时间用完
    } while (!time_out) ;
    return value;
}

实践证明，迭代深化搜索所需的时间仅比固定深度搜索略多；更为重要的是，这种算法适用于依赖时间进行搜索的场景。

在为每步棋分配思考时间上，还有许多优化方法可行。例如，当某一深度的搜索过程中发生超时，该轮搜索将被强制中止。由于搜索过程不完整，其结果通常需舍弃，从而导致一定程度的浪费。解决此问题的一个思路是，尽管每一轮搜索所需的时间无法预先确定，但搜索过程仍具有一定规律。根据前几轮搜索情况，可以大致预测本轮搜索所需时间。如果预测显示，剩余时间已不足以完成本轮搜索，则不再继续本轮搜索，而将剩余时间保留给下一步棋。

注意

有一种观点认为，从浅层到深层对博弈树进行完全搜索，通过浅层搜索获取节点的通用排序作为深层遍历的启发式信息，从而增强Alpha-Beta剪枝效果。然而，由于之前提到的直棋着法排序对于加速 Alpha-Beta 剪枝具有显著效果，因此这种方法的影响并不大，所以该方案没有被采用。

着法排序

为了优化 Alpha-Beta 算法的性能，需要优先搜索最佳着法。这对于 PV-节点和预期的 Cut-节点尤为重要。我们的目标是尽量减小搜索树的大小。另一方面，在 Cut-节点中，最佳行动并不总是最容易反驳的行动，例如请参见增强的转置切断。在迭代深化框架中，最重要的是尝试将前一次迭代的主要变体作为下一次迭代的最左路径，这可以通过明确的三角形 PV 表或隐含的转置表来实现。

典型的着法排序

在棋步生成和分配棋步分数之后，国际象棋程序通常不会对整个棋步列表进行排序，而是在每次提取棋步时执行选择排序。例外情况是根节点和与地平线距离较远的 PV-节点，这里我们可以投入额外的努力对棋步进行评分和排序。出于性能考虑，许多程序试图在预期的 Cut-Nodes 处节省捕获或非捕获棋步生成的时间，而是优先尝试哈希棋步或杀手棋步，如果它们在当前位置被证明是合法的。

在 Sanmill 中，着法排序利用了人类知识，排序包括以下几点：

优先选择能让己方连成三的着法。
优先选择能阻止对方连成三的着法。
尽可能让对方的棋子靠近禁点，因为禁点在移动阶段会变为空。
优先选择使对方的棋子与己方的棋子正好连线的着法。
优先选择吃掉与己方棋子相邻的对方棋子的着法。
优先选择吃掉对手具有较强移动能力的棋子，即相邻空点较多的棋子。
如果吃掉对方的棋子将导致对方的三个连续邻位，尽量避免吃掉。
如果对方吃掉的棋子与己方的棋子不相邻，宁可不吃。

在着法优先级相同时，可以考虑以下因素：

将棋盘上的点数划分为关键点，优先考虑高优先级的点。邻近点越多，优先级越高。
若优先级相同，则根据配置，默认采用随机排序。这样可以防止人类在同一棋局上屡次获胜，从而提高游戏的可玩性。

直棋的排序逻辑在着法选择模块中得以实现。

局面评估

评估是一个启发式函数，用于确定局面的[相对价值]，即获胜机会。如果我们能在每一步都看到对局的结束，那么评估将只有 -1（输）、0（平）和 1（赢）的值，而引擎仅需搜索到深度 1 便可获得最佳棋步。然而，在实践中，我们不知道一个局面的确切数值，所以我们必须做出一个近似值。主要目的是对比局面，引擎现在需要深入搜索，在给定的时间内找到最高分的局面。

近年来，有两种主要方法用于建立评估：传统方法和多层神经网络。鉴于后者仍在开发中，本文将重点介绍传统方法，特别关注双方棋子数量差异的显著特征。

初学者通常从棋子本身的价值开始学习评估。计算机评估功能也采用物质平衡的价值作为最重要的因素，然后再加上其他考量。

起点

编写评估函数时，首先要考虑如何在Minimax或更常见的NegaMax框架中进行评分。尽管Minimax通常将白方与最大玩家相关联，将黑方与最小玩家相关联，并始终从白方角度进行评估，但NegaMax需要对即将行动的一方进行非对称评估。这意味着我们不能对棋步本身进行评分，而是对棋步结果（即作为棋步结果的棋盘局面）进行评估。

评估函数

为了充分发挥NegaMax算法的效果，关键在于返回一个相对于被评估方的分数。例如，考虑一个简单的评估函数，它仅考虑物质平衡和行动力：

materialScore = 5  * (wPiece-bPiece)

mobilityScore = mobilityWt * (wMobility-bMobility)

根据落子方返回相对分数（who2Move = +1 表示白棋，-1 表示黑棋）

Eval  = (materialScore + mobilityScore) * who2Move

位置评估在评估模块中实现。

置换表

许多博弈树搜索算法并非一次性完成，如渴望搜索。在多次搜索同一个博弈树时，充分利用先前搜索的信息将显著提高搜索效率，保存先前搜索信息主要使用置换表。

置换表（Translation Table，TT）的原理是采用哈希表技术将已搜索的结点的局面特征、估值和其他相关信息记录下来。当待搜索结点的局面特征在哈希表中已有记录，且满足相关条件时，可直接利用置换表中的结果。

在对一个结点进行估值时，应先查找置换表。如果置换表未命中，再对该结点进行搜索。使用置换表时要及时更新，当计算出一个结点的估值时，应立即将这个结点的相关信息保存到置换表。为了加快处理速度，一般不采用再散列技术。一旦在写入置换表时发生冲突，直接覆盖相关数据项。只要在读取操作时避免读取错误数据即可，因此置换表的设计应使冲突概率很小。

置换表一般容量较大，以尽可能保存庞大博弈树各结点信息，并实现快速访问，因此通常采用哈希表技术实现。与一般哈希表不同的是，这里的哈希表通常不使用再散列技术。在哈希冲突较少时，不进行再散列，能有效提高处理速度。如果出现写冲突，直接覆盖。在读访问时只要不使用错误数据即可。

置换表中的一个数据项应包括详细信息，以描述对应博弈树的结点类型、该结点的搜索评估值以及评估值所对应的搜索深度等。评估值通常可分为两部分，分别保存结点的上限值和下限值。在渴望搜索和空窗探测等情况下，通常通过获取结点的上限值或下限值实现剪枝。这些值在进一步优化搜索过程中具有重要价值。若已获得某结点的准确评估值，可以将上限值和下限值设为相同以表示。在使用置换表时，应保持及时更新。置换表技术在当今机器博弈领域已经广泛应用，对提高搜索速度具有明显效果。

机器博弈中的博弈树通常非常庞大。由于 Alpha-Beta 搜索在一般情况下是边生成结点边搜索，因此并不需要保存整个博弈树，内存开销相对较小。然而，若置换表用于保存博弈树中所有已搜索过的结点信息，内存开销将变得巨大。从剪枝效率的角度考虑，由于博弈树顶层的剪枝对剪枝效率具有决定性影响，因此即使置换表仅保存较顶层的博弈树结点信息，也能显著提高剪枝效率。

在使用置换表时，还有一种情况需要特别注意：在许多情况下，将博弈树最末层结点保存到置换表中并无实际效果。这一点容易被忽视，从而导致置换表的使用效率降低和搜索速度减缓。置换表不仅能提高重复搜索的效率，还能有效地解决博弈图的搜索问题。因此，在设计和实现置换表时，应充分考虑其在不同层次结点上的作用，避免不必要的资源浪费。

算法流程

确定哈希函数：首先，需要确定一个哈希函数，将结点对应的局面映射为一个哈希值。通常，这个哈希值为一个32位整数。接着，根据该值计算出哈希地址。一种高效且简单的方法是将哈希值与置换表长度取余数，结果作为待访问的哈希表元素地址。
解决地址冲突：哈希函数可能产生地址冲突，即不同的哈希值映射到了同一地址。在这种情况下，32位的哈希值可能是不安全的。为此，置换表中的数据项还应包含一个唯一标识局面特征的校验值，通常为一个64位整数。尽管理论上64位整数也可能发生冲突，但这个概率非常小，在实际应用中可以忽略。在通过哈希函数找到置换表数据项地址后，需验证该数据项的校验值与待搜索结点对应的局面特征值是否一致。只有在二者一致的情况下，才认为查找命中。
记录估值类型：对于PV结点、All结点和Cut结点，后两种情况并非对应结点的精确估值。因此，置换表中的数据项不仅需记录对应结点的估值结果，还应同时记录估值类型，即是精确值、上界值还是下界值。
记录搜索深度：结点的估值结果与搜索深度有关。搜索深度越深，估值越准确。因此，置换表中的数据项还应记录结点对应的搜索深度。在下次搜索到相同局面A时，若置换表中已有相同局面A'，需比较A的搜索深度（Depth）与A'的搜索深度（Depth'）。只有在Depth' ≥ Depth的情况下，才能直接使用置换表中A'的估值信息。若Depth > Depth'，则置换表中对应结点的估值信息将失去意义，因为需要再向前搜索几步才能得到一个更准确的值。

综上，置换表中的一个数据项至少应包含以下数据：结点局面的64位校验值、搜索深度、估值以及估值类型。这些信息有助于确保正确地匹配和利用置换表中的数据，从而提高搜索效率和准确性。

Zobrist 哈希方法

Zobrist哈希方法是一种高效地生成特定局面下的32位哈希值和64位校验值的方法。首先创建一个64位数组Z[type][pos]，其中值表示类型为type的棋子在棋盘坐标pos的一个64位随机整数。通过对棋盘上所有棋子的随机数进行异或操作，结果保存在64位变量BoardKey中，从而得到该局面的校验值。具体步骤如下：

将要移动的棋子从棋盘上去除：BoardKey = BoardKey ^ Z[type1][pos1]（“^”表示按位异或运算）；
若目标位置有对方类型为type2的棋子被吃掉，则将其去除：BoardKey = BoardKey ^ Z[type2][pos2]；
将移动后的棋子置入目标坐标：BoardKey = BoardKey ^ Z[type1][pos2]。

要使用Zobrist哈希方法构造局面下的32位哈希值，方法与构造64位校验值相同，只需将64位整型变量改为32位即可。这样，结点哈希值的生成可以随着着法的执行或撤销逐步进行。

置换表长度（即包含的数据项数量）也是一个需要考虑的因素。置换表越长，发生地址冲突的概率越小，从而能保存更多局面信息，提高置换表命中率和算法性能。在国际象棋计算机博弈中，置换表长度每增加1倍，命中率约提高7%。但置换表长度并非越大越好，若长度超过物理内存承受能力，导致使用虚拟内存时，性能反而会快速下降。

更新置换表数据有两种策略：深度优先和随时替换。深度优先策略在写入置换表时，不比较校验值，只有当新数据对应的搜索深度大于置换表相应数据项的深度时，才替换原有数据。随时替换策略则注重实时性，对新估值的局面信息不作任何判断，立即更新置换表中对应的数据项。这两种策略根据实际需求和性能要求来选择。

哈希函数

哈希函数能将国际象棋局面转换为几乎唯一的标量签名，从而实现快速检索和节省空间的存储验证。常见的哈希函数包括：

Zobrist哈希
BCH哈希

Zobrist哈希和BCH哈希都使用高速哈希函数，为国际象棋局面提供哈希键或签名，类似于哥德尔数。现代应用通常采用64位宽度，而对于Mill，32位就足够了。它们在执行着法和撤销着法时，通过自逆异或或加法和减法操作实现。

地址计算

索引不是基于整个哈希键，因为它通常是一个64位或32位数字，由于当前硬件限制，没有足够大的哈希表来容纳。因此，需要通过签名取模来计算地址或索引。对于两个大小的幂表，可以通过'and'指令来获取哈希键的下部。

冲突

从局面到签名的映射以及更密集的索引范围意味着冲突，即不同的局面共享相同的条目。冲突可能是由于罕见的歧义键（类型1错误）或经常出现的歧义索引（类型2错误）引起的。

存储的信息

通常根据搜索来确定存储以下信息：

Zobrist-或BCH-key，用于检测时确认局面是否正确
最佳着法或反驳着法（目前尚未实施）
深度（草案）
评分，或者综合边界和值或者以其他方式
节点类型
年龄用于确定何时覆盖游戏期间搜索先前位置的条目。

表项类型

在Alpha-Beta搜索中，我们通常无法找到局面的确切价值。但我们很高兴地知道，该值要么太低要么太高，我们不必担心进一步搜索。当然，如果我们有确切的值，我们会将其存储在置换表中。但是，如果我们的局面值足够高以设置下限，或者足够低以设置上限，那么最好也存储该信息。因此，置换表中的每个条目都用节点类型标识，通常称为精确值、下限值或上限值。

置换表替换策略

由于在搜索过程中几步之前的结果仍然对当前步具有一定的参考价值，因此我们不必在每次搜索之前清空置换表，而是保留这些数据以供后续搜索使用！然而，随着棋局的演变，数据的可信度会逐渐降低。考虑到置换表的容量是有限的，相对于庞大的棋局空间，在出现重复局面时，我们需要确定哪些局面应该被存入置换表。目前针对单置换表策略，主要有深度优先替换和随时替换两种方法。

深度优先替换

这种策略的基本思路是：置换表中原有数据距离叶子节点越远（即搜索深度越深），其可信度越高。在写入哈希表时，如果置换表中已经存在相应的存储项，且待写入数据的搜索深度大于已存储数据的搜索深度，那么就替换原有数据；否则，说明待写入数据的可信度较低，不进行任何操作。读取数据时也进行相同的处理，只有当存储数据的深度大于当前搜索深度时，数据才被视为可信。这种策略强调对原有数据的利用，但可能导致某些最新信息因搜索深度问题而无法保留。

随时替换策略

这种策略的基本思路是：置换表中原有数据通常只包含较小的搜索子树，且原有搜索深度一般小于后来生成的搜索深度。因此，使用新生成的棋局信息立即替换置换表中原有数据，而不进行任何判断。这种策略具有很好的实时性，但可能导致表中具有较高搜索深度的数据大量丢失。

在 Sanmill 中，采用的是深度优先替换策略。

置换表实现

在博弈树中，许多节点可能具有不同的路径，但其局面相同。如果这些节点位于博弈树的相同层次，那么它们的得分是相同的。在 Alpha-Beta 搜索期间，程序利用置换表存储搜索到的节点局面的层次结构、分数和值类型。在后续的博弈树搜索中，首先查找置换表，如果发现相应的局面已被记录，且记录的层次结构与查找节点的层次结构相同或接近叶子节点，那么直接使用置换表中记录的分数；否则，将该节点的层次结构、分数和值类型信息添加到置换表中。在 Alpha-Beta 搜索过程中，博弈树的一个节点可能出现在以下三种情况之一：

BOUND_UPPER

节点得分未知，但大于或等于 Beta；
BOUND_LOWER

节点得分未知，但小于或等于 Alpha；
BOUND_EXACT

节点得分已知，位于 Alpha 和 Beta 之间，这是精确值。

BOUND_EXACT 类型可以作为当前节点的准确分数存储在置换表中，BOUND_UPPER 和 BOUND_LOWER 对应的边界值仍然可以帮助进一步剪枝，也可以放入置换表中。因此，记录置换表需要一个标志来表示值类型，即精确值，或者上边界（case 1），或者下边界（case 2）。在查找时，检查置换表中保存的结果是否直接代表当前节点的值，或使当前节点产生 Alpha-Beta 剪枝；如果不是，则继续查找该节点。

为了实现高效的置换表查找，我们需要将置换表设计为哈希表数组 TT，数组元素 TT(key) 存储 position key 下对应的层次结构、分数和值类型。根据某个局面的信息，快速在哈希表中找到相应的记录。使用 Zobrist Hash 方法，构造一个 32 位随机数数组，包含Key psq、PIECE_TYPE_NB 和 SQUARE_NB，其中 PieceType 类型棋子的 32 位随机值是内侧坐标 (x , y)。与棋盘上出现的所有类型棋子的随机数不同，通过将结果保存在 32 位可变密钥中，获取该局面的特征。

因此，当类型为 type1 的棋子从 (x1, y1) 移动到 (x2, y2) 时，只需对当前的 “BoardKey” 值执行以下操作：

1）将要移动的棋子从棋盘上移除，key 为 psq(type1, x1, y1)（“代表位差或运算，下同”）；

2）如果目标坐标有其他类型的棋子，也被移除，关键是 psq；

3）将移动的棋子放入目标坐标，key 为 psq(type1, x2, y2)。异或操作都在计算机内部进行得非常快，从而加快了计算速度。

键值可能会对应相同的局面，但直棋所在的行可能不同。因此，定义 32 位常量 a3，在行边转换时，键和 a3 进行或运算。

由于同一局面中一方可拿的棋子数量不同，应视为不同的局面。为了解决这个问题，程序采用了将当前局面中可拿走的棋子数量存储在 32 位密钥的高两位的方法。

前面提到的 MTD(f) 算法在搜索过程中逐渐逼近目标值，许多节点可能会被多次搜索。因此，本程序采用基于哈希的置换表将搜索到的节点保存在内存中，以便在后续搜索时直接取出，避免重新搜索。

综上所述，置换表在搜索算法中发挥着重要作用，能够有效地提高搜索效率并减少重复计算。通过采用合适的替换策略和高效的实现方法，我们可以充分利用置换表在博弈树搜索中的优势，从而提高整个搜索过程的性能。

数据预取

程序采用了一项重要的性能优化技术，即通过缓存靠近处理器的必要数据来减少数据访问时间。预取技术可以显著减少访问数据所需的时间。大多数现代处理器具有三种类型的内存：

一级缓存（L1 Cache）通常支持单周期访问
二级缓存（L2 Cache）支持双周期访问
系统内存（System Memory）支持较长的访问时间

为了尽量减少访问延迟并提高性能，我们需要将数据保存在离处理器最近的内存中。手动执行这个任务称为预取。GCC编译器通过内置函数 __builtin_prefetch 支持手动预取数据。

在本程序中，我们在 Alpha-Beta 搜索阶段递归调用更深层次的搜索，通过手动预取关键位置的第一个方法生成器来提高性能。

GCC 的数据预取框架支持各种目标的功能。GCC中涉及预取数据的优化将相关信息传递给特定目标的预取支持，后者可以选择使用或忽略这些信息。这些关于 GCC 目标中的数据预取支持的信息最初是作为输入来收集的，用于确定 GCC 的 “预取” RTL 模式的操作数，但对于那些添加新预取优化的开发者来说仍然有用。

位棋盘

Bitboards（又称 bitsets、bitmaps 或更恰当地称为 Square Sets）是一种以棋子为中心的表示国际象棋程序中棋盘的方法。位棋盘本质上是一个最多包含64个元素的有限集合，每个元素对应一个棋盘格，每格用一个比特（bit）表示。具有更大棋盘尺寸的棋盘游戏也可以使用类似的集合表示方法。然而，对于经典的国际象棋，一个64位字或寄存器就足以覆盖整个棋盘。相较于国际象棋，跳棋（Checkers）更适合使用32位位棋盘和较少的棋子类型。

位棋盘数组

为了表示棋盘，我们通常需要为每个棋子类型和颜色创建一个位棋盘，它们可能会被封装在一个类或结构中，或者作为位棋盘数组的一部分，作为位置对象。位棋盘中的一个比特表示某个格子上存在某种类型的棋子，位位置与棋盘格子一一对应。

方形映射注意事项
标准棋盘定义

位棋盘基础

位棋盘不仅关乎棋子的存在与否，它实际上是一种通用的、集合式（set-wise）数据结构，适合放在一个64位寄存器中。例如，位棋盘可用于表示攻击和防御集合、移动目标集合等。

位棋盘的历史

位棋盘的发展可以追溯到1952年，Mikhail R. Shura-Bura 提出了一种基于位的棋盘表示方法。同年，Christopher Strachey 在他的跳棋程序中使用了白色、黑色和国王位棋盘，该程序运行在 Ferranti Mark 1 计算机上。20世纪50年代中期，Arthur Samuel 也在他的跳棋程序中使用了位棋盘表示法。计算机国际象棋中的位棋盘最早由 Georgy Adelson-Velsky 等人描述，后来在1967年和1970年的 Kaissa 和 Chess 程序中得到应用。20世纪90年代，Robert Hyatt、Peter Gillgasch 和 Ernst A. Heinz 开发了 Rotated Bitboards 技术，成为位棋盘历史上的又一重要里程碑。Steffan Westcott 的创新使得位棋盘在32位 x86 处理器上昂贵，而在 x86-64 和 SIMD 指令上效果更好。随着64位乘法的加速以及内存的提速，Lasse Hansen 和 Pradu Kannan 的 Magic Bitboards 技术已经超越了旋转位棋盘。

分析

位棋盘的使用引发了许多关于其成本和收益的讨论。需要考虑的要点包括：

位棋盘具有高信息密度。
单个填充或空位棋盘的信息密度较低。
位棋盘在回答像“x格子上有什么棋子”这类问题时表现不佳。在实现棋子移动和撤销移动时需要额外处理。
位棋盘可以使用按位指令并行操作所有格子。这是位棋盘支持者使用的主要论点之一，因为它允许评估具有灵活性。
位棋盘在32位处理器上存在相当大的缺陷，因为每个按位计算必须分成两条或更多条指令。然而，由于大多数现代处理器现在都是64位的，这一点问题已经减轻。
位棋盘通常依赖于位操作技巧以及针对某些硬件架构的各种优化技巧和特殊指令，例如 [位扫描](https://www.chessprogramming .org/BitScan) 和人口计数。最佳代码需要用到 C/[C++](https://www.chessprogramming.org/Cpp）语言。可移植代码可能并非对所有处理器都是最佳的。
位棋盘上的一些操作不太通用，例如移动。这需要额外的代码开销。

实现

棋盘的表示方法是一个重要的问题。一般的方法是使用二维数组来表示棋盘，每个位置通常用一个字节表示。然而，在许多直棋类游戏中，每个位置的状态远远少于256种。对于这些游戏，位棋盘是节省空间和提高性能的有效方法。

简而言之，位棋盘是将棋盘中的每个格子用一个位来表示。在这种方法中，可以使用一个32位数的低24位来表示一个直棋的位棋盘，在多个地方用位操作替代数组操作以提高性能。

源文件解析

bitboard

实现了位棋盘的表示和操作，包括用位表示各个棋格的存在与否，以及对位棋盘进行按位与、按位或、按位异或、计算位数等基本操作。还提供了用于生成特定位图的宏定义，如表示两个棋格的位棋盘、表示三个棋格的位棋盘等。同时还提供了用于输出ASCII表示位棋盘的函数和用于初始化各种位棋盘表格的函数。

这个代码包含了一些位棋盘相关的操作和实用函数。下面是对代码的详细分析：

定义了设置位和清除位的宏，SET_BIT 和 CLEAR_BIT。
定义了用于生成多个位棋盘组合的宏，如 S2、S3 和 S4。
声明了一个名为 Bitboards 的命名空间，包含 init() 和 pretty() 函数。
定义了一些常量位棋盘，如 AllSquares、FileABB、FileBBB 等。
定义了用于计算 16 位数字中非零位数的数组 PopCnt16。
定义了一个数组 SquareBB，用于存储 32 个棋盘位置的位表示。
定义了一个名为 square_bb 的内联函数，它接收一个 Square 类型的参数并返回该位置的位棋盘表示。
定义了一系列位运算符重载，用于在位棋盘和棋盘位置之间进行位操作。
定义了一个名为 more_than_one 的常量表达式函数，用于检查位棋盘中是否有多于一个非零位。
定义了 rank_bb() 和 file_bb() 函数，用于获取给定位置的横排或纵列位棋盘。
定义了一个名为 popcount 的内联函数，用于计算位棋盘中非零位的数量。这里考虑了多种编译器和不同情况下的实现。
以下是 Bitboards::pretty() 函数的实现。它接受一个位棋盘参数，返回一个可打印的 ASCII 字符串表示。
以下是 Bitboards::init() 函数的实现。它初始化了位棋盘相关的数据结构，如 PopCnt16 和 SquareBB 数组。

这段代码基本上提供了一个位棋盘库，可以让程序更方便地处理位棋盘的操作。例如，它提供了一个函数来获取位棋盘中非零位的数量，方便进行棋子计数。同时，它还提供了一些实用函数，如在给定位置的横排或纵列上生成位棋盘。整体而言，这段代码为处理位棋盘提供了基础设施。

evaluate

这段代码主要用于评估直棋游戏中给定局面的价值。以下是代码的详细分析：

包含标准库字符串头文件以支持字符串操作。
包含自定义类型头文件 "types.h"。
声明一个名为 Position 的类。
在 Eval 命名空间中，声明一个名为 evaluate 的函数。

接下来的代码包含实现局面评估的类 Evaluation，这个类的核心方法是 value()，它负责计算给定局面的价值。

在匿名命名空间中定义 Evaluation 类。
构造函数 Evaluation(Position &p) 用于将局面的引用传递给类。
value() 函数计算局面的价值，该价值根据当前游戏阶段（如放置棋子、移动棋子等）以及游戏规则进行计算。根据不同的游戏动作（如选择、放置、移除等），局面的价值计算方式也会有所不同。此外，还考虑了游戏选项中的行动力设置。
在计算完局面的价值后，如果当前轮到黑方行动，价值需要取负数。
在一些特殊情况下（例如，当游戏规则允许棋子飞行且没有对角线时），如果局面的价值未达到已知赢局，将评估为平局。
在 Eval 命名空间中实现 evaluate() 函数，它实例化 Evaluation 类并调用其 value() 方法以计算给定局面的价值。

总之，这段代码提供了一个局面评估器，用于评估直棋游戏中给定局面的价值。评估器根据游戏的阶段、动作和规则计算局面价值，并在一些特殊情况下可能评估为平局。这个评估器可以作为直棋游戏的 AI 或搜索算法的一部分来使用。

hashnode

这段代码提供了一个基于模板的哈希表的基础设施，用于实现置换表。置换表用于存储搜索过程中已经探索过的局面及其评估值，以便在后续搜索中快速查找并避免重复计算。

代码主要包含两个类：HashNode 和 HashBucket。这两个类在 CTSL（并发线程安全库）命名空间中定义。

HashNode 类：表示键值对的节点。
- 默认构造函数和带有键值参数的构造函数。
- 析构函数。
- getKey、setValue、getValue 和 setKey 方法用于获取和设置键值对。
- 如果未禁用哈希桶功能（DISABLE_HASHBUCKET），则包含一个指向同一桶中下一个节点的指针 next。
HashBucket 类：表示哈希桶。哈希桶实现为单链表，每个桶都有一个虚拟头节点。
- 构造函数和析构函数。
- find 方法：在桶中查找与给定键匹配的节点。如果找到，将相应的值复制到参数 "value"，并返回 true。如果未找到，返回 false。使用 std::shared_lock 对桶进行共享访问（多个线程可以同时读取）。
- insert 方法：将键值对插入桶中。如果键已经存在，则更新值；否则，在桶中插入一个新节点。使用 std::unique_lock 对桶进行独占访问（一次只能有一个线程写入）。
- erase 方法：从桶中删除与给定键匹配的节点（如果找到）。使用 std::unique_lock 对桶进行独占访问。
- clear 方法：清空桶中的所有节点。使用 std::unique_lock 对桶进行独占访问。
- 私有成员包括指向桶头节点的指针 head 和用于保护桶的可变共享定时互斥体 mutex_。

这段代码提供了一个线程安全的哈希表实现，可以用于在多线程环境中构建置换表。利用这个哈希表，可以快速地存储、查找和删除键值对。使用哈希表的置换表可以提高搜索算法的效率，因为它可以避免在搜索过程中重复计算已探索过的局面。

hashmap

实现了一个线程安全的哈希表，使用开放寻址技术。在代码中定义了一个名为 HashMap 的模板类，它接受两个模板参数，一个是键类型 K，一个是值类型 V。另外，它还接受一个函数对象 F 作为哈希函数。默认情况下，F 是 std::key<K> 类型。请注意，此代码中哈希表的大小会在构造时确定，并在整个哈希表生命周期内保持不变。

主要成员函数如下：

构造函数：用于创建具有指定大小（默认为1031）的哈希表。哈希表的大小是质数，这有助于在哈希表中更好地分布键值对。
析构函数：用于释放哈希表分配的内存。
find：用于查找哈希表中与给定键匹配的条目。如果找到匹配的键，返回 true 并将对应的值复制到参数 "value"。如果未找到键，则返回 false。
insert：向哈希表插入一个键值对。如果键已存在，则更新其值；否则，在哈希表中插入一个具有给定键值对的新节点。
erase：如果找到，则从哈希表中删除给定键的条目。
clear：清除哈希表，即从中删除所有条目。
resize：调整哈希表的大小。目前该功能尚未实现。
dump：将哈希表的内容转储到指定的文件中。
load：从指定的文件中加载哈希表。
merge：将另一个哈希表与当前哈希表合并。
stat：统计哈希表中的条目数量。

此外，代码还定义了一个名为 HashNode 的模板类，用于表示哈希表中的节点。HashNode 类包含一个键和一个值，以及一些用于获取和设置键和值的成员函数。

请注意，此代码已禁用了部分功能，如哈希桶和哈希函数。这意味着在当前配置下，哈希表将使用键本身作为哈希值，并且不使用链地址解决冲突。此外，锁机制也已被禁用，因此在多线程环境下使用此代码时需要注意线程安全性问题。

main

这段代码是一个简单的主程序，用于初始化并运行一个支持 UCI（通用国际象棋接口）协议的引擎。UCI 是一种通用的国际象棋引擎通信协议，它允许不同的图形用户界面与国际象棋引擎进行交互。

代码首先包含了一些必要的头文件，如 "bitboard.h"、"position.h"、"search.h"、"thread.h" 和 "uci.h"。这些头文件分别定义了位棋盘、棋盘位置、搜索算法、线程和 UCI 协议的实现。

该代码定义了一个名为 main（或 eng_main 或 console_main，具体取决于编译选项）的函数。这是程序的入口点。在这个函数中，执行以下操作：

打印引擎信息，这通常包括引擎的名称、版本和作者等。
初始化 UCI 选项。
初始化位棋盘（Bitboards）数据结构，用于高效地表示和操作国际象棋棋盘。
初始化棋盘位置数据结构。
设置线程池的大小。线程池用于在搜索过程中并行处理任务，以提高性能。线程池的大小由选项 "Threads" 控制。
清除搜索数据，以确保在开始新搜索之前，之前的搜索数据不会干扰新搜索。
如果没有启用单元测试模式，进入 UCI 事件循环。在这个循环中，引擎将等待来自图形用户界面的命令，并根据 UCI 协议进行响应。
在程序结束时，将线程池大小设置为 0，以释放资源。

这段代码提供了一个 UCI 国际象棋引擎的简单框架。要实现一个完整的引擎，还需要实现其他功能，如生成合法的走子、评估棋盘位置和实现搜索算法等。

mills

这段代码涉及到的是Mills游戏（也称为Morris游戏）的相关实现。这是一种双人对弈游戏，棋盘由若干圆环和连接圆环的边组成，棋子放置在顶点上。代码中包含了棋盘的表示、初始化、以及一些关于棋子放置、移动和搜索深度的实现。

包含头文件：包括了一些自定义的头文件，如 "config.h"，"position.h"，"types.h"等，用于引入一些自定义的数据类型和函数声明。
定义了一系列字符串常量，用于表示游戏结束的各种原因。
Mills命名空间：该命名空间包含了一些Mills游戏相关的函数。
- adjacent_squares_init()：根据游戏规则初始化相邻顶点。
- mill_table_init()：根据游戏规则初始化磨坊（mill）表。
- move_priority_list_shuffle()：根据游戏规则和选项对可选移动列表进行洗牌操作，以提高搜索效率。
- is_star_squares_full()：检查星型顶点是否已满。
- get_search_depth()：根据当前游戏状态计算搜索深度。
初始化相邻顶点：函数adjacent_squares_init()根据游戏规则将预定义的邻接顶点矩阵复制到MoveList的相应数据成员中。
初始化磨坊表：函数mill_table_init()根据游戏规则将预定义的磨坊表复制到Position类的相应数据成员中。
对移动优先级列表进行洗牌：move_priority_list_shuffle()函数根据游戏选项和当前阶段对MoveList类的移动优先级列表进行洗牌操作。
判断星型顶点是否已满：is_star_squares_full()函数检查游戏中星型顶点是否已满。星型顶点是四个特殊顶点，位于棋盘内圈的四个角落。
计算搜索深度：get_search_depth()函数根据当前游戏阶段和选项计算搜索深度。搜索深度决定了AI搜索算法的深度，深度越大，AI越强大，但计算时间也更长。

总之，这段代码提供了Mills游戏的一些基本实现，包括棋盘表示、初始化、以及搜索深度计算等。

misc

这段代码主要提供了一些基础设施，包括时间测量、哈希表、线程同步输出、指针对齐、伪随机数生成器（PRNG）等。以下是对各部分的详细分析：

函数声明：声明了一些函数，包括引擎信息获取、编译器信息获取、缓存预取、日志记录、内存对齐分配与释放等。
时间点 TimePoint：定义了一个基于 std::chrono::milliseconds::rep 的别名，表示毫秒值。使用 static_assert 确保 TimePoint 是64位整数。
函数 now()：返回当前时间点，单位为毫秒。
哈希表模板 HashTable：一个模板类，根据给定的键值进行存储和访问。内部使用 std::vector 作为底层存储结构。
线程同步输出：定义了一个枚举 SyncCout，以及 operator<< 重载函数，用于实现线程同步输出。同时定义了 sync_cout 和 sync_endl 宏，方便使用。
指针对齐函数 align_ptr_up()：一个模板函数，将指针向上对齐到指定的对齐值。
伪随机数生成器 PRNG：一个类，实现了xorshift64star伪随机数生成算法。它具有良好的统计特性，如通过Dieharder和SmallCrush测试，无需热身等。成员函数 rand() 和 sparse_rand() 用于生成随机数。
函数 mul_hi64()：计算两个64位无符号整数的乘积的高64位。
Windows处理器组绑定：在Windows平台上，为了让一个进程能运行在多个逻辑处理器组上（通常意味着最多可使用64个内核），需要调用一些特定的平台API来设置每个线程的组亲和性。这里提供了一个名为 WinProcGroup 的命名空间，其中包含一个函数 bindThisThread(size_t idx)，用于实现线程绑定。这部分代码来源于Texel引擎，作者为Peter A-terlund。

movepick

这段代码实现了与棋盘上的置换表相关的功能。主要组成部分有：ExtMove结构体、MoveList模板类、MovePicker类和部分辅助函数。

ExtMove结构体： ExtMove结构体包含一个Move类型的move和一个int类型的value。结构体定义了一些操作符，方便对move和value进行操作。例如操作符<用于比较两个ExtMove对象的value值。
MoveList模板类： MoveList类是一个对generate()函数的简单包装。MoveList类根据给定的GenType（生成类型）提供了一系列关于走法的功能，如生成走法列表、获取列表大小、检查列表中是否包含特定走法等。
partial_insertion_sort()函数：这个函数对一个给定的ExtMove数组进行部分插入排序，根据走法的value值降序排序，只对高于给定limit的走法进行排序。
MovePicker类： MovePicker类负责在搜索过程中为每个位置选择一个合适的走法。构造函数接受一个Position引用，即棋盘上的当前局面。score()模板函数根据GenType为每个走法分配一个数值，用于排序。next_move()方法是MovePicker类的核心方法，每次调用时，它会返回一个新的伪合法走法，直到没有更多的走法。通过从生成的走法列表中选择分数最高的走法实现。

简要分析了这段代码的主要功能和部分实现细节。整体上，这段代码提供了与置换表相关的基础设施，实现了在给定局面下生成和选择最佳走法的功能。

option

这段代码定义了一个名为 GameOptions 的类，它用于储存与游戏相关的各种选项。类中的每个成员变量都有相应的 getter 和 setter 函数。以下是这些成员变量的功能：

skillLevel：表示 AI 的技能等级。
moveTime：表示每一步棋所需的时间。
aiIsLazy：表示 AI 是否懒惰，即是否会随机地忽略一些行动。
isAutoRestart：表示游戏是否自动重启。
isAutoChangeFirstMove：表示游戏是否自动更换先手。
resignIfMostLose：表示 AI 是否在大部分情况下输棋时投降。
shufflingEnabled：表示 AI 是否对具有相同评估的状态进行随机排序。
learnEndgame：表示是否启用残局学习。
algorithm：表示使用的搜索算法（0 = Alpha-Beta，1 = PVS，2 = MTDF）。
perfectAiEnabled：表示是否启用完美 AI。
IDSEnabled：表示是否启用迭代加深搜索（Iterative Deepening Search，IDS）。
depthExtension：表示是否启用搜索深度扩展。
openingBook：表示是否启用开局库。
drawOnHumanExperience：表示是否借鉴人类经验。
considerMobility：表示是否考虑棋子的移动性。
developerMode：表示是否启用开发者模式。

此外，这段代码中还有一个名为 gameOptions 的全局变量，它是 GameOptions 类的一个实例。这个全局变量可以在程序的其他部分中访问和修改，以改变游戏的行为。

position

这是一个包含棋盘表示、移动、撤销移动等方法的 Position 类的头文件。这个类使用 C++11 的语法，包含一些基本的 STL 头文件，如 vector 和 string，以及一些 Chess Engine 相关的头文件，如 rule.h 和 stack.h。以下是该头文件的主要内容：

StateInfo 结构体：存储还原 Position 对象到其之前状态所需的信息，包括 rule50 和 pliesFromNull 等。
Position 类：该类存储了关于棋盘表示、移动、撤销移动等的信息，包括一些重要的方法，如 do_move() 和 undo_move()。该类还包括 Mill Game 相关的方法和属性，如 get_board()、current_square()、get_phase()、get_action()、get_record() 等。该类还有一些重载的操作符，如 operator<<()。
select_piece()、put_piece()、remove_piece() 和 move_piece() 等方法，用于在棋盘上选择、放置、移除或移动棋子。
count() 模板方法，用于计算某种类型棋子的数目，例如在棋盘上或者在手中。
其他一些辅助方法。