开发白皮书

基于MTD(f)算法的直棋游戏的设计和开发

介绍

本文描述了 Sanmill 直棋游戏程序的设计，重点介绍了核心算法设计。本文描述了一些受益于基于知识的方法的搜索方法的组合。

直棋是一款经典的“两人零和、全信息、非意外”游戏。该程序使用极小极大搜索算法搜索博弈树，并使用 Alpha-Beta 剪枝、MTD(f) 算法、迭代深化搜索和置换表优化博弈树。通过对直棋博弈的研究和分析，在博弈算法上进行了大量的设计和优化。提升算法效率和智能水平。

为了提高性能，游戏算法引擎核心使用C++编写，App的GUI使用Flutter编写，Flutter 前端和游戏引擎之间暂时使用平台通道传递消息，未来还将优化为使用 FFI 的形式。

代码总量约为 240,000+ 行。游戏算法引擎自主开发。仅在线程管理和UCI模块沿用了国际象棋引擎Stockfish约500行代码。

使用UCI接口的目的是创建一个通用的框架，也可以被其他直棋游戏开发者引用和连接。

概述

硬件环境

Android手机

1.5GHz CPU 或更高

1GB RAM 或更高

屏幕分辨率为 480x960 或更大尺寸

Android 4.2 或更高版本

iOS手机

暂未支持，不过基于FFI的iOS支持已经纳入开发日程。

个人电脑

Flutter 版正在开发中。

Qt 版本可用。目前GUI有一些Bug，所以一般只在算法改进后用于AI自我对战，测试算法效果。该版本支持加载完美数据库。

开发环境

Android Studio 4.1.3

Visual Studio Community 2022

Flutter 2.8.1

Android SDK 版本 31.0

Android NDK 版本 22.x

编程语言

游戏引擎是使用 C++ 编写的。App入口代码使用Java编写，UI使用Dart编写。

特征

实现直棋游戏，支持人机对战、双人对战、机器对战三种战斗模式，支持多种直棋规则变体，包括支持成三棋、打三棋、九人莫里斯、十二人莫里斯等，支持棋盘是否有对角线，支持是否“飞棋规则”，支持是否允许采取吃掉已成三的棋子等各种规则变体。支持UI主元素颜色的设置，支持难度等级、AI的风格、是否播放音效、先招，支持棋谱显示、统计数据展示。支持恢复默认设置。

技术特点

程序游戏引擎使用MTD(f)和Alpha-Beta剪枝等博弈树搜索算法来执行最优搜索方法，通过走法排序、置换表和缓存预取来提高性能，并通过迭代深化搜索方法来控制搜索时长。使用 Flutter 开发 UI 以提高可移植性。

直棋游戏

直棋游戏为一个双人游戏，通常棋盘为同心的数个正方形，并用直线或斜线将不同的正方形相连结。直棋普遍以消灭对方吃子能力，或困毙对方为胜。

直棋流传于世界各地，有许多规则变体，名称亦不相同。譬如在国内：

闽台称为“直棋”、“放直棋”、“行直棋”；
苗族、四川、广东阳江等地称为“三棋”
壮族称为“棋三”、“盘三”；
广东湛江等地称为“成三棋”；
广东揭西、河北延庆等地称为“下三棋”；
湘西土家族、侗族、河北涉县等地称为“打三棋”；
瑶族、重庆等地称为“三三棋”；
广东海康称为“走城”；
云南大理称为“乘棋”、“城棋”；
湖北麻城称为“龙棋”、成龙棋”；
北京称为“连儿棋“；
其他地区还有“花窗棋”、“风车棋”、“删棋”、“三子棋”、“连三”、“九子棋”、“九连棋”、“九人毛利”、“十二子棋”等称呼。

本游戏支持各种不同的规则变体设置，让玩家能设置自己熟悉的规则畅玩。新的规则支持仍在不断添加中。

各地直棋变体都依循的共通规则为，开始将手中的棋子以双方轮流的顺序放入棋盘上。当手中的棋子都已经放完后，才可以着法棋子。因此直棋游戏至少拥有两个不同阶段。如果造成三个己方棋子连成一线，俗称此情况为“直”，或“三连”，就可以吃掉棋盘上对方的一颗棋子，并且吃掉的棋子不能再放回棋盘上。游戏进行至某方无棋子可着法，或是盘面上的棋子少于两颗，则该方判定为输。因为双方轮流着法棋子，所以有机会发生走过的盘面又再一次出现，造成循环的盘面，在双方都不改变行子方式的情形下有可能产生和棋的结果。

游戏在一个有 24 点的棋盘上进行，棋子可以放在棋盘上。最初，棋盘是空的，两个玩家各拿着九或十二个棋子。拿着白色棋子的玩家开始。

        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

两名玩家都从九个棋子开始。

游戏经历三个阶段：

开局阶段

玩家交替将棋子放在一个空点上。

中局阶段

当所有的棋子都放好后，游戏进行到中局。在这里，玩家可以将他的一颗棋子着法到相邻的空位。如果在游戏中的任何时候，玩家成功地将他的三颗棋子排成一排这被称为“直”，或“三连”，便可以移除任何不属于直棋一部分的对手的棋子。

残局阶段

一旦玩家只剩下三颗棋子，就开始进入残局阶段了。轮到他时，拥有三颗棋子的玩家可以将他的一颗棋子跳到棋盘上的任何空位。

游戏以下列方式结束：

少于三颗棋子的玩家输棋。
无法进行合法着法的玩家输棋。
如果中局或残局中曾经出现三次重复局面，则游戏为平局。

设计意图

直棋在世界各地有不同的变体。最受欢迎的变体——九人莫里斯已被证明，当双方均走出完美着法的情况下，最终是和棋。这一结果是通过瑞士的计算机科学家，后来曾经在谷歌工作过的 Ralph Gasser 博士使用 Alpha-Beta 搜索和残局数据库于上世纪90年代实现并证明的。1995 年在Jürg Nievergelt 领导下的苏黎世联邦理工学院，在那里 Ralph Gasser 博士研究了计算机游戏中的穷举搜索和逆行分析，即前向和后向搜索。1993年，他以这种方式解决了九人莫里斯游戏，使用从终端节点开始的逆行分析和从根开始的 α-β搜索相结合的方式来解决。

逆行分析用于计算所有中局和残局位置的数据库（大约 100 亿个不同的位置）。这些位置被分成 28 个独立的数据库，以棋盘上的棋子数量为特征，即所有 3 个白棋对个 3 黑棋位置（3-3）、以及4-3、4-4 .…… 一直到 9-9 的位置。

对开局阶段进行 18 层 Alpha-Beta 搜索，然后找到初始位置的值（空棋盘）。只需要 9-9、9-8 和 8-8 数据库来确定比赛是平局。

一些工具正在使用数据库来完善无与伦比的 AI，例如：

King of Mill

http://muehle.jochen-hoenicke.de/

https://www.mad-weasel.de/morris.html

数据库非常大，对于九人莫里斯，我们需要建一个80GB的数据库，只能在PC上使用或者放服务器通过App查询。由于数据库庞大，建立一个所有规则变体的数据库是不现实的，所以这个程序通常只支持标准规则的九人莫里斯。

支持多种规则变体是该程序的特点。另一方面，在不使用庞大数据库的情况下，我们希望利用先进的搜索算法和人类知识，尽可能的提高智力水平。

另外，对于PC的Qt版本，目前已经支持使用九人莫里斯游戏——完美玩电脑建立的数据库。不幸的是，这不是标准规则。它在大方面遵循规则，但在一些小规则上存在差异。需要指出的是，目前我们还没有得到标准规则的详细文本。我们只是通过与其他程序的比较来验证猜测规则的标准。而支持访问该数据库的主要目的是评估AI算法的能力，并通过对完美AI的绘制率来衡量算法的有效性。其他标准规则的数据库暂时不开放源代码和接口，无法连接。

未来我们可能会使用构建完美AI数据库的算法来构建自己的数据库，但这需要服务器存储数据库的成本。预计短期内我们不会有这个计划。中期来看，更可行的方式是通过残局数据库或NNUE进行训练，以更低的成本继续提升智力水平。

Sanmill 项目所需的代码、工具和数据在 GitHub 和 Gitee 上共享。只所以开源，是因为开放源代码和开放数据是取得项目快速进展的关键因素。我们的最终目标是凝聚社区的力量，让 Sanmill 成为直棋事实上的标准实现方案，为全世界的直棋爱好者带来乐趣，特别是在中国、欧洲、南非和其他直棋游戏流行的地方。

组件

算法引擎

引擎模块负责根据指定的位置和谁先下等状态信息，搜索返回UI模块的最佳动作之一。它分为以下子模块：

位棋盘
局面评估
哈希表（无锁化）
直棋游戏相关逻辑
着法生成
着法选择
配置管理
规则管理
最佳着法搜索
线程管理
置换表
UCI通用接口
UCI 选项管理

用户界面前端

UI模块：通过Flutter开发，Flutter具有开发效率高、Android/iOS双端UI一致性、UI美观、可媲美Native性能等优点。

UI 模块分为以下几个模块：

直棋逻辑模块，基本上就是将直棋逻辑模块的算法引擎翻译成 Dart 语言；具体分为游戏逻辑模块、直棋行为模块、位置管理模块、着法历史模块等。

引擎通信模块：负责与C++编写的游戏引擎进行交互。

命令模块：用于管理和游戏引擎交互的命令队列；

数据库：Hive数据库管理；

绘图模块：包括棋盘绘制和棋子绘制；

服务模块：包括音频服务；

风格模块：包括主题风格、色彩风格；

页面模块：包括棋盘页面、侧边菜单页面、游戏设置页面、主题设置页面、规则设置页面、帮助页面、关于页面、许可页面以及各种UI组件；

多语言数据：包括英文和中文字符串文本资源。

算法设计

极小极大

Minimax，一种算法，用于在一定数量的着法后确定零和游戏中的得分，根据评估函数获得最佳玩法。该算法可以这样解释：在单层搜索中，只检查长度为 1 的着法序列，走棋的一方（最大玩家）可以在玩完所有可能的着法后简单地查看评估。选择评价最好的着法。但是对于两层搜索，当对手也走棋时，事情变得更加复杂。对手（最小玩家）也选择获得最高分的着法。因此，每一步的得分现在是对手所能做的最差的得分。

历史

Jaap van den Herik 的论文（1983 年）详细介绍了有关该主题的已知出版物。它得出的结论是，尽管约翰·冯·诺伊曼通常与该概念相关联（1928 年），但首要地位可能属于Émile Borel。此外，有一个可以想象的说法，即第一个获得信用的人应该归于查尔斯·巴贝奇。Von Neumann 定义的原始极小极大值是基于游戏终端位置的精确值，而Norbert Wiener建议的极小极大值搜索基于距离游戏结束几步之遥的位置的启发式评估。

执行

下面是间接递归深度优先搜索的伪代码。为了清楚起见，省略了递归调用之前和之后的着法。

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算法（ Alpha-Beta Pruning, Alpha-Beta Heuristic）是对极小极大搜索算法的显著增强，它消除了应用分支定界技术搜索博弈树的大部分的需要。值得注意的是，它做到了这一点，没有任何忽视更好着法的潜力。如果一个人已经找到了一个很好的举动并寻找替代方案，那么一个反驳就足以避免它。无需寻找更强有力的反驳。该算法维护两个值，alpha和beta . 它们代表了最大化玩家被保证的最低分数和最小化玩家被保证的最高分数。

怎么运行的

假设轮到白方下棋，我们正在搜索深度2（即，我们考虑白方的所有走法，以及黑方对这些走法的所有反应。）首先，我们选择白方可能的走法之一——让我们称之为可能的着法#1。我们考虑这一举动以及黑棋对这一举动的所有可能反应。在此分析之后，我们确定做出可能的着法 #1 是一个偶数位置。然后，我们继续考虑白方可能的另一步棋（可能棋步#2）。当我们考虑黑方的第一个可能反步时，我们发现下棋会导致黑方赢得棋子！在这种情况下，我们可以放心地忽略黑方对可能着法#2 的所有其他可能反应，因为我们已经知道可能着法#1 更好。我们真的不可能的着法＃2有多糟糕。也许另一个可能的反应会赢得一个棋子，但这并不重要，因为我们知道通过玩可能的着法 #1*至少可以实现平局。*对Possible Move #1 的全面分析给了我们一个下限。我们知道我们至少可以做到这一点，所以任何明显更糟的事情都可以忽略不计。

然而，当我们进入 3 或更大的搜索深度时，情况变得更加复杂，因为现在两个玩家都可以做出影响游戏树的选择。现在我们必须同时保持下限和上限（称为Alpha和Beta）。我们保持下限，因为如果着法太糟糕，我们不会考虑它。但是我们也必须保持一个上限，因为如果在深度 3 或更高的着法导致了一个太好的延续，其他玩家不会允许它，因为在游戏树的更高处有一个更好的着法，他本来可以玩来避免这种情况的。一个玩家的下限是另一个玩家的上限。

储蓄

alpha-beta 的节省是相当可观的。如果一个标准的极小极大搜索树有x 个节点，那么一个编写良好的程序中的 alpha-beta 树的节点数可以接近x的平方根。但是，您实际上可以切割多少个节点取决于您的游戏树的有序程度。如果您总是首先搜索可能的最佳着法，则您消除了大多数节点。当然，我们并不总是知道最好的棋步是什么，否则我们一开始就不必搜索。相反，如果我们总是在更好的着法之前搜索更糟糕的着法，我们根本无法切割树的任何部分！出于这个原因，良好的着法顺序非常重要，并且是编写一个好的国际象棋程序的许多努力的重点。正如所指出的Levin在 1961 年，假设每个访问的节点不断着法b并且搜索深度为 n，则 alpha-beta 中的最大叶子数等于 minimax，b ^ n。考虑到总是最好的着法，它是b ^ ceil(n/2)加上b ^ floor(n/2)减一。下表显示了最小叶数，这也证明了奇偶效应：

Negamax搜索

通常，为了简单起见，使用Negamax算法。这意味着对一个位置的评价等于从对手的角度否定评价。这是因为国际象棋的零和特性：一方的胜利是另一方的损失。

Negamax搜索是 minimax 搜索的一种变体形式，它依赖于两人游戏的零和特性。

$\max(a,b)=-\min(-a,-b)$ 该算法依赖于简化极小极大算法的实现这一事实。更准确地说，在这样的游戏中，一个位置对玩家 A 的价值是对玩家 B 的价值的否定。因此，着法中的玩家寻找一个最大化该着法产生的否定值的着法：这个后续位置必须根据定义已被对手重视。无论 A 还是 B 在着法，上一句的推理都有效。这意味着可以使用一个程序来评估两个位置。这是对 minimax 的编码简化，它要求 A 选择具有最大值后继者的着法，而 B 选择具有最小值后继者的着法。

它不应与negascout混淆，这是一种通过巧妙使用1980 年代发现的alpha-beta 剪枝来快速计算极小值或负极大值的算法。请注意，alpha-beta 剪枝本身就是一种通过避免搜索某些不感兴趣的位置来快速计算位置的极小值或负极大值的方法。

大多数对抗性搜索引擎都是使用某种形式的负最大搜索进行编码的。

基于 Negamax 的算法

NegaMax 在与使用 minimax 搜索算法相同的游戏树上运行。树中的每个节点和根节点都是两人游戏的游戏状态（例如游戏棋盘配置）。到子节点的转换表示即将从给定节点进行游戏的玩家可用的着法。

Negamax 搜索的目标是找到在根节点玩的玩家的节点得分值。下面的伪代码显示了 negamax 基本算法，具有可配置的最大搜索深度限制：

function negamax(node, depth, color) is
    if depth = 0 or node is a terminal node then
        return color × the heuristic value of node
    value := −∞
    for each child of node do
        value := max(value, negamax(child, depth − 1, −color))
    return −value

(* Initial call for Player A's root node *)
negamax(rootNode, depth, 1)

(* Initial call for Player B's root node *)
negamax(rootNode, depth, −1)

根节点从其直接子节点之一继承其分数。最终设置根节点最佳分数的子节点也代表了最好的棋步。尽管显示的 negamax 函数仅返回节点的最佳分数，但实际的 negamax 实现将保留并返回根节点的最佳着法和最佳分数。对于非根节点，只有节点的最佳分数是必不可少的。对于非根节点，节点的最佳着法不是保留或返回的必要条件。

令人困惑的是如何计算当前节点的启发式值。在这个实现中，这个值总是从玩家 A 的角度来计算的，玩家 A 的颜色值为 1。换句话说，较高的启发式值总是代表对玩家 A 更有利的情况。这与正常的极小极大算法的行为相同。由于 negamax 和颜色参数的取反，启发式值不一定与节点的返回值相同。negamax 节点的返回值是从节点当前玩家的角度来看的启发式分数。

Negamax 分数与玩家 A 将要玩的节点的 minimax 分数匹配，并且玩家 A 是 minimax 等效项中的最大化玩家。Negamax 总是搜索其所有节点的最大值。因此，对于玩家 B 节点，最小最大分数是其负最大分数的否定。玩家 B 是极小极大等价物中的最小化玩家。

negamax 实现的变化可能会省略颜色参数。在这种情况下，启发式评估函数必须从节点当前玩家的角度返回值。

带有 alpha-beta 修剪的 Negamax

minimax 的算法优化也同样适用于 Negamax 。Alpha-beta 剪枝可以减少 Negamax 算法在搜索树中评估的节点数量，就像它与 minimax 算法一起使用一样。

使用 alpha-beta 剪枝的深度有限负最大搜索的伪代码如下：

function negamax(node, depth, α, β, color) is
    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 := −∞
    foreach child in childNodes do
        value := max(value, −negamax(child, depth − 1, −β, −α, −color))
        α := max(α, value)
        if α ≥ β then
            break (* cut-off *)
    return value

(* Initial call for Player A's root node *)
negamax(rootNode, depth, −∞, +∞, 1)

Alpha (α) 和 beta (β) 表示给定树深度处子节点值的下限和上限。Negamax 将根节点的参数 α 和 β 设置为可能的最低和最高值。其他搜索算法，例如negascout和MTD-f，可以用替代值初始化 α 和 β 以进一步提高树搜索性能。

当 negamax 遇到 alpha/beta 范围之外的子节点值时，negamax 搜索会切断，从而从探索中修剪博弈树的部分。截止是基于节点返回值的隐式。在其初始 α 和 β 范围内找到的节点值是节点的准确（或真实）值。该值与 negamax 基本算法将返回的结果相同，没有截止值和任何 α 和 β 界限。如果节点返回值超出范围，则该值表示节点精确值的上限（如果值 ≤ α）或下限（如果值 ≥ β）。Alpha-beta 剪枝最终会丢弃任何值绑定的结果。这些值既不贡献也不影响其根节点处的负最大值。

此伪代码显示了 alpha-beta 修剪的失败软变体。Fail-soft 从不直接返回 α 或 β 作为节点值。因此，节点值可能在使用 negamax 函数调用设置的初始 α 和 β 范围边界之外。相反，fail-hard alpha-beta 剪枝总是将节点值限制在 α 和 β 的范围内。

此实现还显示了在评估子节点的foreach 循环之前的可选着法顺序。着法排序是对 alpha-beta 修剪的优化，它试图猜测产生节点分数的最可能的子节点。该算法首先搜索这些子节点。正确猜测的结果是更早且更频繁地发生 alpha/beta 截断，从而从搜索树中剪除额外的博弈树分支和剩余的子节点。

带有 alpha-beta 修剪和置换表的 Negamax

置换表选择性地记忆博弈树中节点的值。换位是一个术语参考，它可以通过不同的游戏着法序列以不止一种方式到达给定的游戏板位置。

当 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

(* Initial call for Player A's root node *)
negamax(rootNode, depth, −∞, +∞, 1)

negamax 中的 Alpha/beta 修剪和最大搜索深度约束可能导致对博弈树中节点的部分、不精确和完全跳过的评估。这使得为 negamax 添加置换表优化变得复杂。仅跟踪表中节点的值是不够的，因为值可能不是节点的真实值。因此，代码必须保留和恢复值与 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;
            }
        }
    }

笔记

因为米尔可能有一方关闭一个米尔然后继续拿对手的棋子的状态，而不是换到另一边，所以奇偶层可能没有严格划分为博弈的两侧，所以是需要判断迭代过程后边是否发生变化，然后再决定是否取相反数。

MTD(f) 搜索算法

MTD(f) 是由 Aske Plaat、Jonathan Schaeffer、Wim Pijls 和 Arie de Bruin 于 1994 年开发的极小极大搜索算法。对锦标赛级国际象棋、跳棋和黑白棋程序的实验表明，它是一种高效的极小极大算法。名称 MTD(f) 是 MTD(n,f)（具有节点 n 和值 f 的内存增强测试驱动程序）的缩写。它是 alpha-beta 修剪算法的替代方案。

起源

MTD(f) 首次在由 Aske Plaat、Jonathan Schaeffer、Wim Pijls 和 Arie de Bruin 撰写的阿尔伯塔大学技术报告中进行了描述，[2] 该报告后来获得了 1994/1995 年 ICCA Novag 最佳计算机国际象棋出版物奖。MTD(f) 算法是为了理解 SSS* 算法的研究成果而创建的，SSS* 算法是 George Stockman 于 1979 年发明的最佳优先搜索算法。SSS* 被发现等同于一系列 alpha-beta 调用，前提是该 alpha-beta 使用了存储，例如功能良好的置换表。

名称 MTD(f) 代表 Memory-enhanced Test Driver，参考 Judea Pearl 的测试算法，该算法执行零窗口搜索。MTD(f) 在 Aske Plaat 1996 年的博士论文中有深入描述。论文。

零窗口搜索

MTD(f) 仅通过执行零窗口 alpha-beta 搜索得出其效率，并具有“良好”界限（可变 beta）。在 NegaScout 中，搜索以宽搜索窗口调用，如在 AlphaBeta(root, −INFINITY, +INFINITY, depth) 中，因此在一次调用中返回值介于 alpha 和 beta 的值之间。在 MTD(f) 中，AlphaBeta 失败高或低，分别返回 minimax 值的下限或上限。零窗口调用会导致更多的截止，但返回的信息更少——只有极小值的界限。为了找到极小最大值，MTD(f) 多次调用 AlphaBeta，向它收敛并最终找到准确的值。置换表在内存中存储和检索树的先前搜索部分，以减少重新探索部分搜索树的开销。

代码

Value MTDF(Position *pos, Sanmill::Stack<Position> &ss, Value firstguess,
           Depth depth, Depth originDepth, Move &bestMove)
{
    Value g = firstguess;
    Value lowerbound = -VALUE_INFINITE;
    Value upperbound = VALUE_INFINITE;
    Value beta;

    while (lowerbound < upperbound) {
        if (g == lowerbound) {
            beta = g + VALUE_MTDF_WINDOW;
        } else {
            beta = g;
        }
    
        g = search(pos, ss, depth, 
                   originDepth, beta - VALUE_MTDF_WINDOW, 
                   beta,  bestMove);

        if (g < beta) {
            upperbound = g;     // fail low
        } else {
            lowerbound = g;     // fail high
        }
    }
    
    return g;
}

firstguess

首先，猜测最佳值。算法收敛得越快越好。第一次调用可能为 0。

depth

循环的深度。迭代加深深度优先搜索可以通过多次调用来完成，MTDF()并d在f.

表现

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)。

迭代深化深度优先搜索

在计算机科学中，迭代加深搜索，或更具体地迭代加深深度优先搜索（IDS 或 IDDFS）是一种状态空间/图搜索策略，其中深度优先搜索的深度限制版本随着深度限制的增加而重复运行直到找到目标。IDDFS 像广度优先搜索一样是最优的，但使用的内存要少得多；在每次迭代中，它以与深度优先搜索相同的顺序访问搜索树中的节点，但第一次访问节点的累积顺序实际上是广度优先的。

有向图算法

function IDDFS(root) is
    for depth from 0 to ∞ do
        found, remaining ← DLS(root, depth)
        if found ≠ null then
            return found
        else if not remaining then
            return null

function DLS(node, depth) is
    if depth = 0 then
        if node is a goal then
            return (node, true)
        else
            return (null, true)    (Not found, but may have children)

    else if depth > 0 then
        any_remaining ← false
        foreach child of node do
            found, remaining ← DLS(child, depth−1)
            if found ≠ null then
                return (found, true)   
            if remaining then
                any_remaining ← true    (At least one node found at depth, let IDDFS deepen)
        return (null, any_remaining)

如果找到目标节点，则DLS展开递归返回，不再进行迭代。否则，如果在该深度级别上至少存在一个节点，则剩余标志将使IDDFS继续。

2 元组可用作返回值来指示IDDFS继续深化或停止，以防树深度和目标成员资格是先验未知的。另一种解决方案可以使用标记值来表示未找到或剩余级别结果。

特性

IDDFS 结合了深度优先搜索的空间效率和广度优先搜索的完整性（当分支因子有限时）。如果存在解决方案，它将找到具有最少弧的解决方案路径。

由于迭代加深访问状态多次，可能看起来很浪费，但事实证明它并没有那么昂贵，因为在树中大多数节点都在底层，所以如果上层被多次访问也没关系次。

IDDFS 游戏内树搜索的主要优势在于，较早的搜索倾向于改进常用的启发式算法，例如杀手启发式和 alpha-beta 剪枝，从而更准确地估计最终深度的各个节点的得分搜索可能会发生，并且搜索完成得更快，因为它以更好的顺序完成。例如，如果首先搜索最佳着法，则 alpha-beta 修剪是最有效的。

第二个优点是算法的响应能力。因为早期迭代使用较小的 d 值，所以它们执行得非常快。这允许算法几乎立即提供结果的早期指示，然后随着 d 的增加进行细化。当在交互式环境中使用时，例如在国际象棋程序中，该功能允许程序在任何时候使用它迄今为止完成的搜索中找到的当前最佳着法进行游戏。这可以表述为搜索核心的每个深度都会草草产生解决方案的更好近似值，尽管在每个步骤中完成的工作是递归的。这对于不产生中间结果的传统深度优先搜索是不可能的。

笔记

一种理论是枚举深度从小到大，对博弈树进行彻底搜索，通过浅搜索得到节点的大致排序，作为深度遍历的启发信息，增强了Alpha-Beta剪枝的效果。但是由于下面提到的直棋着法排序加速 Alpha-Beta 剪枝效果已经非常显着，所以这种方法不是很有效，所以没有使用该方案。

着法排序

为了使alpha-beta算法表现良好，首先需要搜索最佳着法。对于PV-nodes和预期的 Cut-nodes尤其如此。目标是接近最小树。另一方面 - 在 Cut-nodes - 最好的着法并不总是最便宜的反驳，例如参见增强的转置 cut off。在迭代深化框架中最重要的是尝试将上一次迭代的主要变化作为下一次迭代的最左边路径，这可能由显式三角 PV 表应用或由换位表。

典型的着法顺序

在使用指定的着法分数生成着法之后，国际象棋程序通常不会对整个着法列表进行排序，而是在每次获取着法时执行选择排序。例外是距地平线有一定距离的根节点和其他PV 节点，在这些节点中，人们可能会付出额外的努力来对着法进行评分和排序。出于性能原因，许多程序试图将捕获或非捕获的着法生成保存在预期的剪切节点处，但如果在此位置证明它们是合法的，则首先尝试散列着法或杀手。

在 Sanmill 中，此举利用了人类知识，排序包括以下内容：

可以让自己这边收更多的直棋；
可以防止对手关闭更多的直棋；
尽可能让水滴的另一边靠近禁点，因为禁点在着法阶段会变空；
拿对手的棋子和他自己的棋子接近；
拿对手的棋子和自己的棋子相邻；
优先取对手着法能力强，即相邻空号数；此外，会尝试以下方法来选择降低优先级：
如果拿对方的棋子和对方连续三个相邻的，尽量不要拿；
如果对方的取子和自己的子不相邻，宁可不取；

如果方法具有相同的优先级，请考虑以下因素：
将棋盘计数划分为重要点并优先考虑高优先级点。相邻的点越多，优先级越高。
如果优先级相同，则默认使用随机排序，视配置而定，防止人类在同一曲折的道路上一次次获胜，提高可玩性。

铣削着法排序在着法拾取器模块中实现。

评估

评估，一种启发式函数，用于确定位置的相对值，即获胜的机会。如果我们能在每一行中看到比赛的结束，评估将只有 -1（输）、0（平局）和 1（赢）的值，引擎应该只搜索深度 1 以获得最好的举动。然而在实践中，我们不知道位置的确切值，所以我们必须做一个近似，主要目的是比较位置，引擎现在必须深入搜索，找到给定时间段内得分最高的位置。

最近，有两种主要的评估方法：传统和多层神经网络。本页重点介绍考虑 两侧片数差异的显式特征的传统方式。

国际象棋初学者从棋子本身的价值开始学习这样做。计算机评估功能也将物料平衡的价值作为最重要的方面，然后添加其他考虑因素。

从哪儿开始

编写评估函数时首先要考虑的是如何在Minimax或更常见的NegaMax框架中对着法进行评分。虽然 Minimax 通常将白方与最大玩家关联，将黑方与最小玩家相关联，并且始终从白方的角度进行评估，但 NegaMax 需要与要着法的一侧进行不对称评估。我们可以看到，一个棋子本身不能得分——而是棋子的结果（即棋盘的位置评估是棋子的结果）。

相对着法侧

为了让NegaMax工作，返回相对于被评估边的分数很重要。例如，考虑一个简单的评估，它只考虑材料和着法性：

materialScore = 5  * (wPiece-bPiece)

mobilityScore = mobilityWt * (wMobility-bMobility) [Currently not implemented]

返回相对于要着法的一侧的分数（who2Move = +1 表示白色，-1 表示黑色）：

Eval  = (materialScore + mobilityScore) * who2Move

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

置换表

转置表，首先在格林布拉特的程序Mac Hack VI中使用，是一个存储先前执行搜索结果的数据库。这是一种在几乎没有负面影响的情况下大大减少国际象棋树的搜索空间的方法。这些程序在他们的蛮力搜索过程中，一次又一次地遇到相同的位置，但是来自不同的着法序列，这被称为换位。转置（和反驳）表是源自动态规划的技术，动态规划是由 Richard E. Bellman创造的术语在 1950 年代，当编程意味着规划时，动态规划被设想为优化规划多阶段过程。

怎么运行的

当搜索遇到换位时，“记住”上次检查位置时确定的内容是有益的，而不是再次重做整个搜索。出于这个原因，国际象棋程序有一个置换表，它是一个大型哈希表，存储有关先前搜索的位置、搜索深度以及我们对它们的结论的信息。即使相关置换表条目的深度（草稿）不够大，或者不包含截止的右边界，从先前搜索中获得的最佳（或足够好）着法也可以改善着法顺序，并节省搜索时间. 在迭代深化中尤其如此框架，从以前的迭代中获得有价值的表命中。

哈希函数

散列函数将国际象棋位置转换为几乎唯一的标量签名，允许快速索引计算以及存储位置的节省空间验证。

两者，更常见的 Zobrist 散列和 BCH 散列都使用快速散列函数，以提供散列密钥或签名作为一种Gödel国际象棋位置数，今天通常为64位宽，对于直棋，32 位就足够了。它们在make和unmake 着法期间通过自身逆异或或通过加法与减法进行增量更新。

地址计算

该索引不是基于整个哈希键，因为这通常是一个 64 位或 32 位的数字，并且由于当前的硬件限制，没有足够大的哈希表来容纳它。因此，计算地址或索引需要以条目数为模的签名，对于两个大小的表的幂，哈希键的较低部分，相应地被“与”指令屏蔽。

碰撞

从位置到签名的满射映射以及更密集的索引范围意味着冲突，不同的位置共享相同的条目，出于两个不同的原因，希望是罕见的模棱两可的键（type-1 错误），或经常模棱两可的索引（type- 2 个错误）。

存储什么信息

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

Zobrist-或BCH-key，在探测时查看位置是否正确
Best- or Refutation move [目前未实施]
深度（草稿）
得分，无论是 综合界限和价值 ，还是以其他方式
节点类型
年龄用于确定何时覆盖游戏期间搜索先前位置的条目。

表项类型

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

替换策略

因为置换表中的条目数量有限，并且在现代国际象棋程序中它们可以很快填满，所以有必要制定一个方案，程序可以通过该方案来决定哪些条目最有价值，即替换方案。当程序尝试将位置存储在已经有不同条目的表槽中时，替换方案用于解决索引冲突。替换方案有两个相反的考虑：

搜索到高深度的条目比搜索到低深度的条目在每个表命中节省更多工作。
更接近树的叶子的条目更有可能被多次搜索，从而使它们的表命中率更高。此外，最近搜索过的条目更有可能再次被搜索。
大多数表现良好的替代策略都混合了这些考虑因素。

执行

在博弈树中，许多节点通过不同的路径到达，但位置相同，如果节点与博弈树处于同一级别，则得分相同。在 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)将相应的层次结构、分数和值类型存储在位置键下。根据某个位置的信息，快速找到Hash表中对应的记录。使用 Zobrist Hash 方法，构造一个由 32 位随机数、、和组成的数组Key psq，PIECE_TYPE_NB其中SQUARE_NB32 位随机值用于PieceType类型为 inboard coordinates的片段(x, y)。与棋盘上所有类型棋子的随机数不同，或者，通过将结果保存在 32 位可变密钥中，获得位置的特征。因此，当一段 type1 从(x1, y1)to着法时(x2, y2)，只需对当前BoardKey值执行以下操作：

将要移出的棋子从棋盘上移出，键为 psq(type1) x1,(“表示位差或运算，下同”;
如果目标坐标有其他类型类型类型的碎片，它们也被删除，则键是 psq。
将着法的棋子放入目标坐标，key s, psq s, type1 s x2 s y2。异见者或操作在计算机内执行得非常快，从而加快了计算机的计算速度。

key值相同的位置，直棋对应的line可能不同，所以定义a3个2位边常量，当line边转换时，key和边或。

由于一方当前在同一个位置可以拿的棋子数量不同，应该认为是不同的位置，为了解决这个问题，程序采用了使用32位密钥的高两位的方法来存储当前位置可以带的孩子的数量。

前面提到的MTD(f)算法在搜索过程中会逐渐逼近你要找的值，很多节点可能会被多次搜索。因此，本程序使用这种基于Hash的置换表将搜索到的节点保存在内存中，以便再次搜索时可以直接取出，避免重新搜索。

预取

程序使用重要的性能改进来缓存靠近处理器的必要数据。预取可以显着减少访问数据所需的时间。大多数现代处理器具有三种类型的内存：

• 一级缓存通常支持单周期访问 • 二级缓存支持双周期访问 • 系统内存支持更长的访问时间

为了最大限度地减少访问延迟并因此提高性能，最好将数据保存在最近的内存中。手动执行此任务称为预爬网。GCC 通过内置函数支持手动预爬取数据__builtin_prefetch。

该程序在Alpha-Beta搜索阶段递归调用更深的搜索，第一个方法生成器通过手动预爬关键位置的执行生成，提高了性能。

GCC 中的数据预取框架支持多种目标的能力。GCC 中涉及预取数据的优化将相关信息传递给特定于目标的预取支持，它可以利用它或忽略它。此处有关 GCC 目标中数据预取支持的信息最初是作为确定 GCC 的prefetchRTL 模式的操作数的输入而收集的，但对于那些添加新的预取优化的人可能会继续有用。

位棋盘

位棋盘，也称为位集或位图，或更好的方形集，用于以棋子为中心的方式表示国际象棋程序中的棋盘。位棋盘本质上是最多64 个元素的有限集合——棋盘的所有方格，每方位一位。其他棋盘尺寸更大的棋盘游戏也可以使用集合表示，但经典国际象棋具有一个64 位字或寄存器覆盖整个棋盘的优势。对位棋盘更友好的是带有 32 位位棋盘和更少位棋盘的Checkers 棋子类型比国际象棋。

布景板

为了表示棋盘，我们通常需要为每种棋子类型和颜色提供一个位棋盘——可能封装在一个类或结构中，或者作为一个位棋盘数组作为位置对象的一部分。位棋盘内的一位意味着在某个方格上存在这种类型的一块 - 由位位置一对一关联。

位棋盘基础知识

当然，位棋盘不仅仅是关于片段的存在——它是一种通用的、按集合的数据结构，适合一个 64 位寄存器。例如，位棋盘可以表示攻击和防御集合、着法目标集合等。

Bitboard-历史

位组的一般方法是由Mikhail R. Shura-Bura 在1952 年提出的。进行棋盘游戏的位棋盘方法似乎也是在 1952 年由Christopher Strachey在他的 Ferranti棋盘格程序中使用白、黑和国王位棋盘发明的Mark 1和 1950 年代中期Arthur Samuel在他的检查程序中也是如此。在计算机国际象棋中， Georgy Adelson-Velsky等人首先描述了位棋盘。1967 年，1970 年重印。在Kaissa和Chess中使用了位棋盘。Robert Hyatt发明并出版了Rotated Bitboards90 年代与Ernst A. Heinz的 Peter Gillgasch是位棋盘历史上的另一个里程碑。Steffan Westcott 的创新在 32 位x86处理器上过于昂贵，应该重新考虑x86-64和SIMD 指令。随着快速 64 位乘法和更快内存的出现，由Lasse Hansen提出并由Pradu Kannan改进的 Magic Bitboards已经超越了 Rotated。

分析

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

位棋盘可以具有高信息密度。
单个填充或什至空的位棋盘具有低信息密度。
位棋盘在回答诸如正方形 x 上的哪一块等问题方面很弱。在make / unmake期间保留冗余邮箱板表示并增加一些更新成本的原因之一。
位棋盘可以使用按位指令在所有方格上并行操作。这是位棋盘支持者使用的主要论点之一，因为它允许评估的灵活性。
位棋盘在 32 位处理器上相当不利，因为每个位计算必须分成两条或更多条指令。由于大多数现代处理器现在都是 64 位的，这一点有所减弱。
位棋盘通常依赖于位旋转和各种优化技巧以及特定硬件架构的特殊指令，例如位扫描和人口计数。最佳代码需要C / C++中的机器相关头文件。可移植代码可能并非对所有处理器都是最佳的。
位棋盘上的一些操作不太通用，fi 移位。这需要额外的代码开销。