我对提供百分之几速度的微小优化不感兴趣。我对 alpha-beta 搜索最重要的启发式方法很感兴趣。以及评估功能的最重要组成部分。
我对具有最大（改进/代码大小）比率的算法特别感兴趣。（不是（改进/复杂性））。
谢谢。
PS Killer move heuristic 就是一个完美的例子——易于实现且功能强大。启发式数据库太复杂了。
Łukasz Lew
问问题
3485 次
8 回答
13
不确定您是否已经意识到这一点，但请查看国际象棋编程 Wiki——这是一个很好的资源，几乎涵盖了现代国际象棋 AI 的各个方面。特别是，关于您的问题，请参阅主页上的“搜索和评估”部分（在“原则主题”下）。您还可以发现这里列出的一些程序中使用的一些有趣的技术。如果您的问题仍然没有得到解答，我绝对建议您在国际象棋编程论坛中提问，那里可能有更多的专家来回答。（并不是说您不一定会在这里得到好的答案，只是更有可能在特定主题的专家论坛上）。
于 2009-02-07T12:54:14.100 回答
4
MTD(f)或MTD 变体之一是对标准alpha-beta的重大改进，前提是您在评估函数中没有非常精细的细节并假设您正在使用杀手启发式。历史启发式也很有用。
最受好评的国际象棋程序Rybka显然已经放弃了 MDT(f)，转而支持在非 PV 节点上具有零吸气窗口的PVS 。
扩展的无效修剪，它结合了正常的无效修剪和深度剃刀，理论上是不合理的，但在实践中非常有效。
迭代深化是另一种有用的技术。我在这里列出了很多很好的国际象棋编程链接。
于 2009-02-07T19:41:44.807 回答
2
尽管国际象棋编程文献中讨论了许多基于启发式的优化（我的意思是在不实际搜索的情况下增加树深度的方法），但我认为它们中的大多数很少使用。原因是它们在理论上是很好的性能提升器，但在实践中却不是。
有时这些启发式方法也会返回一个糟糕的（我的意思是不是最好的）举动。
与我交谈过的人总是建议优化 alpha-beta 搜索并在代码中实现迭代深化，而不是尝试添加其他启发式方法。
主要原因是计算机的处理能力正在提高，研究[我想需要引用]表明，使用其全部 CPU 时间将 alpha-beta 树强制到最大深度的程序总是跑得比分裂的程序快。他们在一定水平的 alpha-beta 和一些启发式之间的时间。
尽管使用一些启发式方法来扩展树深度可能弊大于利，但您可以将许多性能提升器添加到 alpha-beta 搜索算法中。
我相信你知道要让 alpha-beta 完全按照它的预期工作，你应该有一个移动排序机制（迭代深化）。迭代深化可以为您带来大约 10% 的性能提升。
在 alpha beta 中添加主要变异搜索技术可能会给您额外的 10% 提升。
也试试MTD(f ) 算法。它还可以提高引擎的性能。
于 2009-02-07T16:09:42.553 回答
1
尚未提及的一种启发式方法是Null move pruning。
此外，Ed Schröder 有一个很棒的页面解释了他在他的 Rebel 引擎中使用的一些技巧，以及每个技巧对速度/性能的贡献：Inside Rebel
于 2009-02-10T01:18:41.343 回答
1
使用带有zobrist 哈希的转置表
只需要很少的代码来实现[每次移动或取消移动一个 XOR，以及在游戏树中递归之前的一个 if 语句]，并且好处非常好，特别是如果您已经在使用迭代深化，并且它非常可调整（使用更大的表、更小的表、替换策略等）
于 2009-02-10T01:29:54.750 回答
0
Killer move 是小代码大小和移动顺序的巨大改进的一个很好的例子。
于 2009-02-07T16:20:36.743 回答
0
大多数棋盘游戏 AI 算法都基于http://en.wikipedia.org/wiki/Minmax MinMax。目标是最大限度地减少他们的选择，同时最大限度地增加您的选择。尽管对于国际象棋，这是一个非常大且代价高昂的运行时问题。为了帮助减少这种情况，您可以将 minmax 与以前玩过的游戏的数据库结合起来。任何具有相似棋盘位置并建立了关于如何为您的颜色赢得该布局的模式的游戏都可以用于“分析”下一步移动的位置。
我对你所说的改进/代码大小有点困惑。您真的是指改进/运行时分析（大 O(n) 与 o(n)）吗？如果是这种情况，请与 IBM 和 big blue 或 Microsoft 的 Parallels 团队联系。在 PDC 上，我和一个人（他的名字现在忘记了我）进行了交谈，他正在使用每个对手使用 8 个核心来演示麻将，他们在游戏算法设计比赛中获得了第一名（他的名字也让我忘记了）。
我认为没有任何“固定”算法可以始终赢得国际象棋并且做得非常快。您必须这样做的方式是在一个非常大的基于字典的数据库中索引每个可能的以前玩过的游戏，并预先缓存每个游戏的分析。在我看来，这将是一个非常复杂的算法，并且将是一个非常糟糕的改进/复杂性问题。
于 2009-02-07T17:51:47.027 回答
0
我可能有点跑题了，但“最先进的”国际象棋程序使用诸如 Deep Blue 之类的 MPI 来获得巨大的并行能力。
试想一下，并行处理在现代国际象棋中扮演着重要的角色
于 2009-02-10T01:28:41.350 回答