Geekly articles weekly

电脑如何下棋？


最近挑战计算机的中村光（Hikaru Nakamura），一台

计算机早已击败了一个国际象棋的人，而如今最强大的国际象棋手甚至无法击败一台旧笔记本电脑。现在，国际象棋引擎用于分析游戏，搜索新选项并通过通信进行游戏。

如果您对国际象棋引擎的布置方式感兴趣，欢迎光临。

引言


一旦我确定国际象棋程序（它们也是引擎，以后会再介绍），只需记住玩过的大量游戏并找到它们在其中的当前位置并采取正确的行动即可。我认为我是在某本书中读到的。

这无疑是非常幼稚的看法。第十步可以在国际象棋中获得新的位置。虽然棋，比位置较少第二，然而，后3招（中风-这是白色和黑色，厚度一门课程-移动只用一只手）移动的树组成的近120万台。此外，爱好者们考虑了从初始位置移动14次后的树的大小已经超过一年了，到目前为止已经增加了大约三分之一。

我也认为国际象棋程序，尽管长期以来赢得世界冠军的比赛仍然是最好的人所能达到的。这也不是真的。

在最近的人机迷你比赛中，世界上最强大的棋手之一中村光（Hikaru Nakamura）与世界上（两个）最强的国际象棋程序之一科莫多一起玩。该程序在24核Xeon上启动。由于人们无法再与计算机平等竞争，因此宗师级大师在以下四场比赛中均处于领先地位：
  • 在第一个游戏中-棋子和棋子：计算机播放黑色且没有f7棋子
  • 在第二个-只有典当中：计算机播放白色而没有典当f2
  • 第三，质量（车子和灯件之间的差异估计约为2个棋子）：没有a1车子的白色计算机，没有b8骑士和a8车子的男人。
  • 在第四步中-四步：一个人打白棋，而不是第一步，他在不越过棋盘中间的情况下进行了四步。

关于残障存在一些争议-例如，缺少f-pawn会在某种程度上削弱国王的实力，但是在cast割之后，这架车子开了一条空白。没有中央典当可能会带来更大的优势。4个招式有很好的位置优势，但是如果您像老印度后卫那样进行封闭式首秀，那么这个优势就很难消除。

此外，游戏中与对照45“15”出场，那就是每场比赛45分钟，15秒上传一举一动。通常，较短的控件会给计算机带来其他好处，而较长的控件会稍微增加一个人的机会。即使在一瞬间，计算机也将设法清除丢失的移动，而由于变异树的指数增长，分析中的每个后续改进都将花费更长的时间。

尽管如此，这里还是有一个障碍，这个人在比赛2.5-1.5中输掉了比赛，赢得了前三局，却输了第四局。同时，弱小宗师很自信地获胜盘中有2个棋子。因此，目前最好的程序比最好的人的优势在于残障的1到2个棋子之间。当然，这种评估是很粗略的，但是为了进行准确的评估，必须在人与程序之间玩几千场游戏，而且几乎没有人会这样做。请注意，经常在节目中注明的ELO等级与人员等级无关。

什么是国际象棋引擎？


为了使一个人可以用计算机下象棋，除了实际寻找最佳动作外，还需要GUI。幸运的是，发明了通用接口（甚至有两个，即Winboard和UCI，但大多数引擎使用UCI）用于GUI和国际象棋程序本身（引擎）之间的通信。因此，程序员可以专注于象棋游戏的算法，而无需考虑界面。硬币的反面是，创建GUI比编写引擎要无聊得多，然后免费的GUI显然会在付费的GUI上失败。与引擎不同，免费的Stockfish自信地与付费的Komodo争夺评级的第一线。

他们仍然怎么玩？


那么，现代国际象棋引擎如何工作？

董事会介绍


任何引擎的基础都是棋盘的表示。首先，有必要向计算机“解释”国际象棋的所有规则，并为其提供保持国际象棋位置的机会。没有这个，就不可能评估位置并采取行动。

有两种主要方法可以存储板的表示形式- 按形状或按单元。在第一种情况下，我们为每一块存储其在板上的位置，在第二种情况下，我们为每个单元存储存在的内容。每种方法都有其优点和缺点，但是目前所有顶级引擎都使用相同的板表示形式-位板。

位板


幸运的是，棋盘上有64个单元。因此，如果我们对每个单元使用一位，则可以将整个电路板存储为64位整数。
在一个变量中，我们将分别存储所有白色块，另一块-所有黑色块以及另外6个-每种图形类型（另一个选项-每种颜色和图形类型分别存储12个位板）。

此选项的优点是什么？
首先是记忆。正如我们稍后了解的那样，在分析过程中，电路板的表示被复制了很多次，因此，RAM被吞噬了。位板是最紧凑的棋盘表示形式之一。
其次，速度。许多计算（例如，可能移动的计算）归结为几个位运算。因此，例如，使用POPCNT指令可使现代发动机获得约15％的加速度。另外，在存在位板期间，发明了许多算法和优化方法，例如“魔术”位板。

搜寻


极小值


大多数象棋引擎的核心是minimax搜索算法或其对非max的修改。简而言之，我们沿着树下降，评估叶子，然后上升，每次为当前玩家选择最佳移动，将一个得分（黑色）最小化，将第二个得分（白色）最大化。因此得名。一旦扎根，我们就会获得对两个玩家都最佳的移动顺序。最小最大与非最大之间的区别在于，在第一种情况下，我们轮流选择具有最大和最小额定值的移动，而在第二种情况下，我们改变所有额定值的符号并始终选择最大额定值（我们知道它们来自何处）。这里和这里有更多细节。

Alpha Beta


第一个优化是alpha beta。 alpha-beta的想法很简单-如果我已经有了一个不错的举动，那么您可以切断显然更糟糕的举动。考虑一下左侧令人毛骨悚然的图片中的示例。假设玩家A有2个可能的举动-a3和b3。在分析a3的过程后，该程序的得分为+1.75。开始评估移动b3时，程序看到玩家B有两个移动-a6和a5。课程评估a6 +0.5。由于玩家B选择分数最低的动作，因此他不会选择分数高于0.5的动作，这意味着动作b3的估算值小于0.5，因此没有任何考虑。因此，b3的其余子树被切除。

对于裁剪，我们存储上下边界-alpha和beta。如果在分析过程中移动的得分高于beta，则当前节点被切断。如果分数高于alpha，则更新alpha。

alpha beta中的节点分为3类：
  1. PV节点 -评估落入窗口（在alpha和beta之间）的节点。根节点和最左边的节点始终是这种类型的节点。
  2. 剪切节点（或故障高节点）-发生beta剪切的节点。
  3. 全节点（或故障低节点）-根据评估，其移动没有超出alpha的节点。


整理动作


使用alpha beta时，移动顺序变得很重要。如果我们能把最好的举动放在首位，那么由于贝塔值截止，剩余的举动将被更快地分析。

除了使用哈希和上一次迭代中的最佳移动之外，还有几种用于对移动进行排序的技术。

对于捕获，例如，可以使用简单的启发式MVV-LVA（最有价值的受害者-最低价值的攻击者）。我们按照“受害者”值的降序对所有捕获物进行排序，然后在我们内部按照“攻击者”值的升序进行排序。显然，以典当方式获得女王通常比反之亦然。

对于“沉默”动作，使用“杀手”动作方法-导致beta截止的动作。通常在从散列和捕获中移动之后立即检查这些移动。

哈希表或排列表


尽管树很大，但其中的许多节点都是相同的。为了不对同一位置进行两次分析，计算机将分析结果存储在表格中，并且每次检查是否已经对该位置进行了现成的分析。通常，此表存储位置，等级，最佳移动和等级年龄的实际哈希值。填写表格时，需要用年龄来替换旧职位。

迭代搜索


如您所知，如果我们不能完全分析整个树，则minimax需要评估函数。然后到达一定深度，我们停止搜索，评估位置并开始爬树。但是这种方法需要预定的深度，并且不能提供高质量的中间结果。

迭代搜索解决了这些问题。首先，我们分析深度为1，然后分析深度为2，依此类推。因此，每次我们都比上一次下降得更深，直到分析停止。为了减少搜索树的大小，通常使用最后一次迭代的结果来截断当前树的故意错误动作。这种方法称为抽吸窗口，被普遍使用。

静态搜索


此方法旨在消除“水平效应”。仅在正确的深度停止搜索可能非常危险。想象一下，我们在交换皇后的中间停下了步伐–白衣拿走了黑人皇后，而下一步，黑人应该选白衣。但是目前，董事会中-怀特有一个额外的女王，静态评估从根本上是错误的。

为此，在进行静态评估之前，我们会检查所有捕获（有时甚至是检查器），并将树下移到没有可能的捕获和检查器的位置。自然，如果所有捕获都使估计值恶化，那么我们将返回当前位置的估计值。

选择性搜寻


选择性搜索的想法是花费更长的时间来考虑“有趣的”动作，而花费更少的时间来考虑不有趣的动作。为此，使用扩展名在某些位置增加搜索的深度，而缩写则减小搜索的深度。

如果移动是唯一的，或者比其他方法好得多，或者存在经过的棋子，则在捕获，跳棋的情况下，深度会增加。

剪裁


随着削减，一切都变得更加有趣。它们可以显着减小树的大小。

简要介绍剪辑：
  • - — , . , , . , , , , .
  • — , -. , , . (1-2).
  • — , , . . PV . .
  • Multi-Cut — M(, 6) C(, 3) Cut-node, .
  • null- — null- ( ) , . , , , , .


如果我们不能确定移动是否不好，可以使用缩写，因此不要将其切断，而只是减小深度。例如，如果当前位置的静态估算值小于alpha ，则为剃须的缩写。

由于对运动和截止进行了高质量的分类，现代发动机设法将分支系数降至2以下。因此，不幸的是，他们有时没有注意到非标准的受害者及其组合。

NegaScout和PVS


两种非常相似的技术，利用了以下事实：我们找到了PV节点（假设我们的举动排序很好），它很可能不会改变，也就是说，所有其余节点将返回比alpha更低的评级。因此，我们不是使用从alpha到beta的窗口进行搜索，而是使用从alpha到alpha + 1的窗口进行搜索，这使我们可以加快搜索速度。当然，如果在某个节点中我们得到了beta裁剪，则必须通过常规搜索重新对其进行欣赏。

两种方法之间的区别仅在于措辞-它们是大约同时开发的，但是是独立开发的，因此以不同的名称而闻名。

平行搜寻


alpha beta的并行化是一个单独的大话题。我将简要介绍一下，谁在乎，请查看“共享内存多处理器上的并行Alpha-Beta搜索”。困难在于，在并行搜索中，许多剪切节点在另一个线程找到反驳（安装Beta）之前被分析，而在顺序搜索中，如果排序良好，则许多这些节点将被剪切掉。

惰性SMP


一个非常简单的算法。我们只是通过相同的搜索同时启动所有线程。通信流经哈希表。懒惰的SMP出奇地有效，以至于高端Stockfish都使用YBW切换到了它。的确，一些人认为该改进是由于YBWC的实施不佳和过于激进的裁剪，而不是因为Lazy SMP的优势。

青年兄弟等待概念（YBWC）


应该对第一个节点（哥哥）进行全面分析，然后开始对其余节点（哥哥）进行并行分析。想法是一样的，第一步可以显着提高alpha值，甚至可以切断所有其他节点。

动态树分割（DTS）


快速而复杂的算法。关于速度的一些知识：搜索速度是通过ttd（到达深度的时间）来衡量的，也就是说，搜索到达特定深度的时间。该指标通常可用于比较不同版本的引擎或在不同数量的核心上运行的引擎的工作（尽管例如，Komodo使用更多可用核心增加了树的宽度）。另外，在运行期间，引擎以nps（每秒节点数）显示搜索速度。该指标更受欢迎，但它甚至不允许引擎与其自身进行比较。没有同步的惰性SMP几乎线性地增加了nps，但是由于大量不必要的工作，其ttd并不是那么令人印象深刻。对于DTS，nps和ttd 几乎相同。

老实说，我仍然不能完全弄清楚这个算法，尽管它效率很高，但实际上是在一对引擎中使用的。对于谁来说很有趣，请单击上面的链接。

等级


因此，我们到达了必要的深度，寻求了平静，最后，我们需要评估静态位置。

计算机将评估棋子的位置：+1.0表示白棋的优势等于1个棋子，-0.5表示黑棋的优势为一半的棋子。估计将死的棋子为300个棋子，已知移动到垫子x的位置为（300-0.01x）棋子。+299.85表示白方可以进行15次移动。在这种情况下，程序本身通常以整个估计值（以/ 100（1/100典当）为单位）运行。

评估位置时计算机会考虑哪些参数？

物质和流动性


最简单的事情。女王是9-12个棋子，新手是5-6个棋子，骑士和主教是2.5-4个棋子，典当分别是一个棋子。通常，材料是评估位置的有价值的试探法，任何位置优势通常最终都会转化为材料优势。

机动性被认为很简单-当前位置的可能移动次数。它们越多，玩家军队的机动性就越高。

形状位置表


板角上的骑士通常情况不好，靠近敌人后方的棋子变得越来越有价值，依此类推。对于每个数字，都会根据其在董事会中的位置来编制奖金和罚款表。

典当结构


  • 双典当 -同一垂直上的两个典当。通常很难用其他兵来保护它们，这被认为是一个弱点。
  • — , . , .
  • — , . ,
  • — , . , .



上述所有参数均会根据游戏的阶段以不同的方式影响游戏的评估。在开局中，经过的棋子没有任何意义，但是在最终游戏中，您需要将国王带到棋盘的中央，而不要躲在棋子的后面。

因此，许多引擎对残局和首次亮相都有单独的评级。他们根据棋盘上剩余的材料评估比赛的阶段，并据此评估-越接近比赛结束，对开局得分的影响越小，而最终比赛则越多。

其他


除了这些基本因素之外，引擎还可以在评估中添加一些其他因素，例如国王的安全性，锁死的零件，典当岛，对中心的控制等。

准确的评分或快速搜索？


传统争议：更有效，准确评估位置或达到更大的搜索深度。经验表明，过于“繁重”的评估功能是无效的。另一方面，在考虑更多因素的情况下进行更详细的评估通常会导致游戏更加“美丽”和“激进”。

首次亮相书籍和残局表


出道书


在计算机国际象棋黎明时，程序的首次亮相就显得微弱了。出道经常需要影响整个游戏的战略决策。另一方面，开放理论在人们中得到了很好的发展，对开放进行了反复的分析和记忆。因此，为计算机创建了一个类似的“内存”。从初始位置开始，构建了移动树并评估了每个移动。在游戏过程中，引擎仅以一定的概率选择了“好”动作之一。

从那时起，首张书越来越多，直到比赛结束时，都使用计算机分析了许多首张书。不需要它们，强大的引擎已经学会了首演，但是他们很快离开了主线。

残局表


回到介绍。记住在内存中存储许多位置并选择合适位置的想法。她在那儿。对于少量（最多7个）数字，将计算所有现有位置。也就是说，在这些位置，计算机开始完美播放，并以最少的移动次数获胜。减号是生成的大小和时间。创建这些表有助于研究残局。

表生成


我们使用一组特定的形状生成所有可能的位置（考虑对称性）。我们在其中找到并指定了垫子站立的所有位置。在下一个步骤中，我们表示可以使用垫子进入的所有位置-在这些位置中，将垫子旋转1圈。因此，我们发现有垫2,3,4，所有的项目549笔。在所有未标记的位置-平局。

纳利莫夫表


最早的残局表发布于1998年。对于每个位置，都存储了游戏结果以及理想游戏中向垫子移动的次数。所有六位数结尾的大小为1.2 TB。

罗蒙诺索夫表


2012年，莫斯科国立大学罗蒙诺索夫超级计算机计算了所有7位数字的结尾（除了6对1）。这些基础仅可用于赚钱，而这些是仅有的完整的七位数残局表。

y


事实标准。这些底座比Nalimov底座紧凑得多。它们由两部分组成-WDL（赢输赔率）和DTZ（距离归零距离）。WDL数据库旨在在搜索过程中使用。在表中找到树节点后，我们就可以在该位置获得游戏的确切结果。DTZ旨在在根中使用-它们将移动次数存储到移动的无效计数器（通过典当或捕获移动）。因此，WDL基础足以进行分析，而DTZ基础可用于分析最终结果。Syzygy的体积要小得多-六位数的WDL为68 GB，DTZ为83 GB。没有七位数的基数，因为它们的生成需要大约TB的RAM。

使用方法


Endgame表主要用于分析，游戏引擎的强度增加很小-ELO为20-30分。但是，由于现代引擎的搜索深度可能很大，因此首次亮相时仍然会从搜索树中查询残局基础。

其他有趣


长颈鹿或神经网络下棋


你们中有些人可能听说过神经网络上的国际象棋引擎达到了IM级别（正如我们在介绍中所了解的那样，对于引擎来说并不是那么酷）。它由 Matthew Lai 撰写并发布在Bitbucket上，不幸的是，由于他开始在Google DeepMind工作，因此停止了对它的研究。

调整参数


向引擎添加新功能并不困难，但是如何验证它带来了放大作用呢？最简单的选择是在新旧版本之间玩几局游戏，看看谁赢了。但是，如果改进很小，并且通常在添加了所有主要功能之后才发生，那么应该有几千个游戏，否则就没有可靠性。

fish鱼


有很多人在使用此引擎，因此需要检查他们的每个想法。在目前的发动机强度下，每次改进都会增加几个额定值，但最终，每年都会获得数十个值的稳定增长。

他们的解决方案对于开源来说是典型的-志愿者提供了驱动他们上成千上万游戏的能力。

剪辑


一个程序，通过使用具有不同参数的引擎游戏的结果通过线性回归来优化参数。缺点-任务量非常有限：要优化一百个参数（对于发动机来说是完全足够的数量），这是不可能的，至少是在足够的时间内。

特塞尔的调音


解决了先前方法的问题。我们拥有大量职位（作者从64,000场比赛中提供了900万个职位，我从近200,000个游戏中夺走了800万个职位），每一个我们都保存了比赛的结果（怀特赢了1，赢了0.5，输了0）。现在我们将误差最小化，该误差是结果之差的平方与估计的S形之和。该方法是有效且流行的，但不适用于所有引擎。

鳕鱼调整


领导者的另一种技巧。我们取一个等于x的参数，并用一个等于x-sigma和x + sigma的参数比较（成千上万）引擎。如果参数较大的发动机获胜，则将其稍微向上移动，否则将其向下移动一点，然后重复。

引擎比赛


在进行的所有竞争测试中，我想分别区分TCEC。它在功能强大的硬件，精心选择的开口和长久的控制方面与所有其他产品不同。在最后的决赛中，在2个Intel Xeon E5-2690v3上进行了100场比赛，它们具有256 GB的RAM和180'+ 30“的控制。在这种情况下，平局数量巨大，只有11场比赛有效。

结论


因此，在这篇较长的文章中，我简短地谈到了象棋引擎的结构。许多细节没有透露，我只是不知道或忘记说些什么。如有任何疑问，请在评论中写下。此外，如果您仔细打开本文中分散的所有链接，我将为您提供两个资源，您可能会注意到这些资源：

Source: https://habr.com/ru/post/zh-CN390821/

More articles:


All Articles