程序员经验分享-hwhale

国际象棋：高分支因子

2024-01-02

我正在尝试开发一个简单的国际象棋引擎，但我在其性能方面遇到了困难。我已经通过 alpha-beta 修剪和迭代加深（没有任何额外的启发式）实现了 Negamax，但是我无法获得超过 3-4 层的合理搜索时间。以下是我的程序从游戏开始时的日志的摘录：

2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 
2013-05-11 18:22:06,897 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 
2013-05-11 18:22:08,005 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 
2013-05-11 18:22:10,485 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6

它显示分支因子约为 10。我读到，通过正确的移动顺序，我应该得到 6 左右的值，所以我怀疑我的顺序是错误的。目前它的工作方式如下：

  1. 游戏树节点有一个其子节点的链表；最初，捕获和晋升被置于安静的行动之前
  2. 在搜索过程中，增加 alpha 或导致截止的子项将放置在列表的开头
  3. 下一次迭代深化PV应该首先搜索

这是排序动作的正确方法吗？我得到的分支因子是预期的吗？目前我正在使用一个简单的静态评估函数，仅考虑职位的实质性差异 - 这是否是截止率低的原因（如果也考虑数字的流动性，我会得到类似的结果）？诸如空着减少或杀手启发式等技术是否会有显着帮助（不是 10-15%，而是一个数量级）？我不期望我的引擎很强，但我希望分支因子约为 6。


我也用 C# 开发了一个国际象棋引擎，它的分支因子约为 2.5。绝对有可能将您的引擎改进多个数量级。如今，一般策略是基于良好的走法顺序，使用非常积极的走法修剪。为了能够看到一些深层的战术路线，你牺牲了一些正确性。

以下是我发现最有效的技术的概述。请注意，某些组件是互补的，其他组件是替代的，因此我给出的结果是一般准则。如果你没有坚实的基础，就不可能获得清单末尾的巨大收获。

  1. Just negamax https://web.archive.org/web/20180117214044/http://chessprogramming.wikispaces.com/Negamax with α-β剪枝 https://web.archive.org/web/20180822181422/https://chessprogramming.wikispaces.com/ALpha-Beta：3秒内深度4。

  2. Add 迭代深化 https://web.archive.org/web/20180823084957/http://chessprogramming.wikispaces.com/Iterative+Deepening and 空步启发法 https://web.archive.org/web/20180823081006/http://chessprogramming.wikispaces.com/Null+Move+Pruning：深度5。迭代加深在这一点上并没有太大帮助，但很容易实现。空值 移动包括跳过你的回合并看看你是否仍然可以得到 浅层搜索的 beta 截止值。如果可以的话，那么很可能是 修剪树是安全的，因为它几乎总是有利的 移动。

  3. 杀手启发法 https://web.archive.org/web/20180823084913/http://chessprogramming.wikispaces.com/Killer+Heuristic：深度 6。这涉及存储以下动作 导致 beta 截止，如果下次它们是合法的，首先尝试它们 你们处于相同的深度。你似乎在做类似的事情 已经。

  4. MVV/LVA 订购 https://web.archive.org/web/20180822154524/http://chessprogramming.wikispaces.com/MVV-LVA：深度 8。基本上，您想要将捕获 在走势顶部有很多潜在的物质净收益 列表。因此，如果棋子捕获了皇后，显然您应该首先搜索它。

  5. 位板表示 https://web.archive.org/web/20180822203740/https://chessprogramming.wikispaces.com/BitBoards：深度 10。这不会改善分支 因素，但这就是我到达这一点时所做的。抛弃 数组，使用UInt64s 代替，并使用 make/unmake 而不是 copy-make。如果您觉得困难，则无需使用魔法位板；有一些更简单的方法，但仍然非常快。位板极大地提高了性能 并使评估组件的编写变得容易。我从 perft(6) 需要几分钟到需要 3 秒。 （顺便说一句，编写 perft 函数是确保移动生成正确性的好方法）

  6. 换位表 https://web.archive.org/web/20180822054601/http://chessprogramming.wikispaces.com/Transposition+Table：深度 13。这提供了巨大的收益，但也 很难做到正确。绝对确定您的位置哈希 在实施该表之前是正确的。大部分的好处来自于 订购桌子给你带来了惊人的举动。永远储存最好的 进入桌子，每当你找到匹配的位置时，就尝试一下 第一的。

  7. 后期搬迁减少 https://web.archive.org/web/20180823084759/http://chessprogramming.wikispaces.com/Late+Move+Reductions：深度 16。这极大地增加了您的搜索深度，但强度增益更多 与其他技术相比，人工的。基本上是你的移动顺序 现在太好了，您只需完整搜索前几个即可 在一个节点中移动，你可以通过浅层搜索来检查其他节点。

  8. 徒劳修剪 https://web.archive.org/web/20180823084749/http://chessprogramming.wikispaces.com/Futility+Pruning：深度17。叶节点通过跳过移动来修剪 在考虑潜力时，提高节点价值的机会很小 物质收益。如果该位置的移动+静态评估的净潜在增益低于该位置的当前值，则跳过 对此举的评价。

还有各种其他组件也有帮助，但大多数都是次要的，有些是专有的。 :D 然而，这并不全在于高搜索深度和低分支因子。像静止搜索 https://web.archive.org/web/20180823084825/http://chessprogramming.wikispaces.com/Quiescence+Search恶化搜索深度，但对于任何引擎来说几乎都是必需的。没有它，你的引擎将遭受巨大的战术错误。您可能还想考虑检查扩展名 https://web.archive.org/web/20180820042316/https://chessprogramming.wikispaces.com/Check+Extensions and 单一回复扩展 https://web.archive.org/web/20180820035408/https://chessprogramming.wikispaces.com/One+Reply+Extensions。我还建议至少介绍一下方桌 https://web.archive.org/web/20180823075608/http://chessprogramming.wikispaces.com/Piece-Square+Tables到你的评估函数。这是一种非常简单的方法，可以极大地提高程序的位置知识；您可能会看到您的引擎播放更常见的开局。国际象棋编程是一种有趣的爱好，我希望大量的信息不会让您感到沮丧！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Chess

alphabetapruning

iterativedeepening

国际象棋：高分支因子 的相关文章

  • XTUOJ 1176 I Love Military Chess(模拟）

    xfeff xfeff I Love Military Chess Accepted 45 Submit 141Time Limit 1000 MS Memory Limit 65536 KB 题目描述 陆军棋 xff0c 又称陆战棋 xf

  • XTUOJ 1176 I Love Military Chess(模拟）

    xfeff xfeff I Love Military Chess Accepted 45 Submit 141Time Limit 1000 MS Memory Limit 65536 KB 题目描述 陆军棋 xff0c 又称陆战棋 xf

  • 实现 alpha-beta 剪枝算法时函数中的奇怪行为

    我已经实现了带有 alpha beta 修剪的极小极大算法 为了获得最佳动作 我将 alpha beta 算法称为rootAlphaBeta功能 然而 在rootAlphaBeta函数时 我发现了一些非常奇怪的行为 当我打电话给rootAl

  • 在 Rust 中，存储较大的类型更快还是存储较小的类型并始终强制转换它们更快？

    我正在用 Rust 开发一个国际象棋引擎 我有一个Move结构与from and to字段 它们是Square Square是一个包含一个结构体usize 这样我在访问该职位的棋盘元素时就可以直接使用它 因为在 Rust 中索引必须用usi

  • n 个皇后的快速启发式算法 (n > 1000)

    我写了两个程序 通过回溯算法将棋盘上的 n 个皇后放在一起 没有任何威胁 但这对于大 n 来说非常沉重 最后你可以运行 100 个皇后 通过爬山算法将棋盘上的 n 个皇后放在一起 没有任何威胁 这个算法比过去的解决方案更好 但是 300 个

  • 我的静态搜索有问题吗？

    当我尝试实现 QuiesenceSearch 时 我的基于 negamax 的人工智能不断出现奇怪的行为 我基于来自的伪代码here https chessprogramming wikispaces com Quiescence Sear

  • 更有效地检测检查（国际象棋）

    我目前正在开发一个国际象棋引擎 该引擎到目前为止正在运行 但需要很长时间才能生成棋步 由于必须生成许多移动 因此检查检测花费的时间是迄今为止最长的 在尝试了很多事情之后我陷入了困境 并且无法真正弄清楚如何提高效率 我是这样做的 为了检查移动

  • 了解使用无符号位板生成滑块移动的“o^(o-2r)”公式？

    我正在尝试做什么我正在尝试执行一些按位运算来创建国际象棋引擎 为了制作这个引擎 我需要能够生成棋子的动作 比如车 有一个方便的公式 https www chessprogramming org Subtracting a Rook from

  • 国际象棋：高分支因子

    我正在尝试开发一个简单的国际象棋引擎 但我在其性能方面遇到了困难 我已经通过 alpha beta 修剪和迭代加深 没有任何额外的启发式 实现了 Negamax 但是我无法获得超过 3 4 层的合理搜索时间 以下是我的程序从游戏开始时的日志

  • 有效存储棋局

    我已经阅读了大量与此问题相关的网络点击 但仍然没有找到任何明确的答案 我想做的是建立一个国际象棋棋局数据库 能够识别换位 通常是哪些棋子在哪些方格上 编辑 它还应该能够识别相似 但不完全相同 的位置 这是大约 20 年前的讨论 当时空间wa

  • 使用转置表进行 Alpha-beta 剪枝，迭代深化

    我正在尝试实现通过换位表增强的 alpha beta 最小 最大修剪 我使用这个伪代码作为参考 http people csail mit edu plaat mtdf html abmem http people csail mit ed

  • 如何在迭代加深/深度有限搜索中存储访问过的状态？

    更新 搜索第一个解决方案 对于普通的深度优先搜索很简单 只需使用哈希集 bool DFS currentState if myHashSet Contains currentState return else myHashSet Add c

  • 使用魔法位板生成滑动移动

    这是一个关于如何使用魔法位板验证国际象棋中的滑动棋子移动的大局的问题 只是为了澄清 我不是在问how魔法位板在内部工作 现在 关于这个问题的更多细节 我正在使用位板编写棋盘表示 并且我想使用魔术位板验证滑动棋子的移动 有人可以列出如何实现这

  • 与XBoard（国际象棋引擎）通信（C++/C）

    我只是在尝试制作一个基本的国际象棋引擎 我从中得到了很多建议http web archive org web 20070704121716 http www brucemo com compchess programming alphabe

  • 如何有效地编码/解码压缩的位置描述？

    我正在为日本象棋变体编写一个表库 为了索引表基数 我将每个国际象棋位置编码为整数 在编码步骤之一中 我对棋盘上棋子的位置进行编码 由于实际方法有点复杂 我就简单地解释一下这个问题 编码 在残局桌面中 我有 比方说 六个不同的棋子 我想将它们

  • 防止在线棋牌游戏作弊？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 在许多在线国际象棋大厅中 我见过 引擎 的实例 其中作弊者会在主游戏窗口的同时打开国际象棋程序 然后他会进行设置 以便将对手的动作传送

  • Minimax/ Alpha beta 剪枝移动顺序？

    我读过 例如 http radagast se othello Help order html http radagast se othello Help order html 首先搜索每个级别的最佳动作 可以使用迭代加深找到 使得搜索速度

  • 棋盘坐标

    我正在尝试用 Java 创建一个国际象棋程序 现在 我已经将棋盘与现有的部件一起完成 我可以用鼠标通过拖放来移动它们 我需要的是向两侧的方块添加坐标 就像在真正的板上一样 不一定要有什么奇特的东西 只是一个视觉效果 由于我没有使用图形绘制板

  • 使用 MinMax 和 Alpha-Beta 剪枝找到最佳移动

    我正在为游戏开发 AI 我想使用MinMax算法与Alpha Beta 修剪 我对它的工作原理有一个粗略的了解 但我仍然无法从头开始编写代码 所以我花了两天的时间在网上寻找某种伪代码 我的问题是 我在网上找到的每个伪代码似乎都是基于寻找最佳

  • 在编程计算机下棋时如何对棋盘进行建模？

    您将使用什么数据结构来表示计算机国际象棋程序的棋盘 对于严肃的国际象棋引擎来说 使用位板是在内存中表示棋盘的有效方法 位板比任何基于数组的表示更快 特别是在 64 位架构中 其中位板可以放入单个 CPU 寄存器中 位板 位板的基本思想是以

随机推荐

  • 使用 geom_smooth 将 glm 拟合到分数

    这篇文章有点相关这个帖子 https stackoverflow com questions 62974766 removing alpha transparency from ggplot legend and setting x axi

  • Java - 子类调用超级构造函数，该构造函数调用子类方法而不是它自己的方法

    我将从一个代码示例开始 class A public A f When accessed through super call this does not call A f as I had expected public void f I

  • Java 中的 Unicode 符号（箭头）

    我想在我的应用程序中使用以下符号作为按钮 箭头http img402 imageshack us img402 3176 arrowso jpg http img402 imageshack us img402 3176 arrowso j

  • 如何使用 Delphi 读取 Windows 事件日志的内容

    是否有一个类或函数允许您读取 Windows 事件日志 这是你打开后看到的日志事件vwr msc 理想情况下选择一个特定的日志 在我的例子中应用领域登录Windows日志 并根据日期和来源设置过滤器 您可以使用Win32 NTLogEven

  • 来自文字的静态 std::string 对象的宏

    假设我需要调用一个函数foo这需要一个常量std string我的代码中很多地方都引用了 int foo const std string foo bar foo baz 使用像这样的字符串文字调用函数将创建临时的std string对象

  • 在 adb logcat 输出中查看 Android 上 Qt 应用程序的日志记录的最简单方法是什么？

    NB I am notQtCreator 用户 我使用 qmake make 和 androiddeployqt 在构建脚本中构建 Android 应用程序 并使用 adb install 将它们部署到设备 我希望能够在 abd logca

  • git pre-commit hook，将文件添加到索引中

    我正在尝试编写一个简单的预提交挂钩来检查文件是否被修改 如果是 则压缩它并将其添加到当前索引中 如下所示 bin sh was the file modified mf git status grep jquery detectBrowse

  • 同步 AJAX 调用在 Chrome 中冻结之前的代码

    我想在执行同步 AJAX 调用时将按钮更改为加载状态 除了将按钮更改为加载状态的 jQuery 代码 在 Chrome 中 之外 它会冻结 直到 AJAX 调用完成 因此 加载状态将在 de ajax 调用后显示大约 1 毫秒 我在 JSF

  • OpenGL：快速离屏渲染

    我需要使用 OpenGL 在屏幕外渲染大量 数万 图像 我在Windows下运行并使用QT作为框架 解决方案只能是Windows 这并不重要 根据我使用谷歌的发现 有很多选择可以做到这一点本文 http www mesa3d org bri

  • 如何在python中将输入值与mysql数据库值进行比较

    所以我想将输入值与我的数据库值进行比较 如果输入值与数据库的值相同 我想print inputvalue 但如果不一样 我想print Data Does Not Exist 所以我尝试过这段代码 cur connection cursor

  • 是什么让 DCG 谓词变得昂贵？

    我正在构建一个定语从句语法来解析 20 000 段半自然文本 随着我的谓词数据库大小的增长 现在达到 1 200 条规则 解析字符串可能需要相当长的时间 特别是对于 DCG 目前无法解释的字符串 因为我尚未编码语法 对于包含 30 个单词的

  • 将 scotty 帖子的 do 替换为 >>=

    post introduceAnIdea do command lt jsonData json handle command 如何删除 do 并用 gt gt 更改它 post introduceAnIdea jsonData gt gt

  • 为什么网站的 MVC 需要单点入口？

    我看到许多网站的 MVC 实现都有一个单入口点 例如 index php 文件 然后解析 URL 以确定要运行哪个控制器 这对我来说似乎很奇怪 因为它涉及到必须使用 Apache 重写来重写 URL 并且页面足够多 单个文件会变得臃肿 为什

  • 什么是文件描述符，用简单的术语解释一下？

    与维基百科相比 文件描述符的更简化描述是什么 为什么需要它们 比如说 以shell进程为例 它是如何应用的呢 进程表是否包含多个文件描述符 如果是 为什么 简而言之 当您打开文件时 操作系统会创建一个条目来表示该文件并存储有关该打开文件的信

  • Circleci：pip install dlib 失败

    我有一个 python 项目需要dlib 我正在尝试设置 CircleCI 并编写我的config yml如下 Python CircleCI 2 0 configuration file Check https circleci com

  • NestJS：如何在 canActivate 中模拟 ExecutionContext

    我在模拟 Guard 中间件中的 ExecutionContext 时遇到问题 这是我的 RoleGuard 扩展 JwtGuard Injectable export class RoleGuard extends JwtAuthGuar

  • @Transactional注解

    之间有什么区别 为整个类添加 Transactional 注释 为每个方法添加 Transactional 注释 使用 spring 和 Hibernate 基本上 如果你用 Transactional http static spring

  • 如何“扫描”当前安装的 VCL 组件的完整列表

    我还没有找到真正满意的答案这个问题 https stackoverflow com questions 691989 full vcl class browser for delphi 现在正在考虑推出自己的 我有 ModelMaker 和

  • Entity Framework 4 v2 中与 POCO 的一对一关系

    我一直在寻找有关如何在 EF4v2 中与 POCO 建立一对一关系的示例 我发现很多例子只展示了如何创建一对多或多对多 你有这方面的资源吗 这对我有用 using System using System Collections Generi

  • 国际象棋：高分支因子

    我正在尝试开发一个简单的国际象棋引擎 但我在其性能方面遇到了困难 我已经通过 alpha beta 修剪和迭代加深 没有任何额外的启发式 实现了 Negamax 但是我无法获得超过 3 4 层的合理搜索时间 以下是我的程序从游戏开始时的日志

热门标签