logo标签列表

计算机象棋树搜索的现状是什么？

algorithmsearchheuristicschess
15

我对只能提高少数百分比速度的微小优化不感兴趣。 我对alpha-beta搜索中最重要的启发式和评估函数的最重要组成部分感兴趣。

我特别关注具有最高（改进/代码大小）比率的算法。(而不是改进/复杂性)。

谢谢。

附言 杀手着法启发式是一个完美的例子——易于实现且功能强大。 启发式数据库太过复杂。

8个回答
13

不确定你是否已经知道，但可以查看国际象棋编程维基 - 这是一个涵盖现代国际象棋人工智能几乎每个方面的优秀资源。特别是与你的问题相关的，在主页上的搜索和评估部分（在主要主题下）中查看。你还可以发现列在这里的一些程序中使用的一些有趣的技术。如果你的问题仍未得到答复，我强烈建议你在国际象棋编程论坛中提问，那里可能会有更多的专家回答。（并不是说你在这里就不会得到好的答案，只是在特定主题的专家论坛上更有可能）。

4

MTD(f)或其它MTD变体是对标准的alpha-beta算法的大幅改进，前提是你的评估函数没有太多细节，并且假定你正在使用killer heuristic。此外，历史启发式也很有用。

排名靠前的国际象棋程序Rybka显然已经放弃了MTD(f)，转而采用PVS，在非PV节点上使用零抽奖窗口。

扩展失败剪枝理论上不可靠，但实践中效果显著，它包括正常的失败剪枝和深度削减。

迭代加深是另一种有用的技术。我在这里列出了很多编写国际象棋程序的好资源。

2
尽管国际象棋编程文献中讨论了许多基于启发式的优化方法（我指的是增加树深度而不实际搜索），但我认为它们大多数很少被使用。原因是它们在理论上是良好的性能提升器，但在实践中并非如此。
有时这些启发式方法也可能返回错误的移动（我指的是不是最佳的移动）。
我与之交谈的人们总是建议优化alpha-beta搜索并将迭代加深算法实现到代码中，而不是尝试添加其他启发式方法。
主要原因是计算机处理能力正在增强，并且研究[需要引用]表明，那些利用全部CPU时间来强制执行alpha-beta树到最大深度的程序总是比那些在某些alpha-beta级别和一些启发式方法之间分配时间的程序更快。
尽管使用一些启发式方法来扩展树深度可能会带来更多的伤害，但您可以向alpha-beta搜索算法添加许多性能提升器。
我相信您知道为了使alpha-beta正常工作，应该有一个移动排序机制（迭代加深）。 迭代加深可以使您获得约10％的性能提升。
将主要变异搜索技术添加到alpha-beta中可能会再增加10％的性能提升。
也可以尝试MTD（f）算法。 它也可以增加您引擎的性能。
1

还有一个启发式方法没有被提及，那就是空置着法减枝。

此外，Ed Schröder有一个很棒的页面，解释了他在Rebel引擎中使用了许多技巧，以及每个技巧对速度/性能的贡献：深入Rebel

1

使用Zobrist哈希的置换表

实现它只需要很少的代码（每次移动或撤销一次XOR，以及在递归游戏树之前添加一个if语句），而且好处相当不错，特别是如果您已经在使用迭代加深，并且它非常易于调整（使用更大的表、更小的表、替换策略等）。

0

杀手着法是小代码尺寸和着法排序的巨大改进的良好示例。

0

大多数棋盘游戏的AI算法都是基于http://en.wikipedia.org/wiki/Minmax MinMax。目标是最小化对手的选择，同时最大化自己的选择。虽然在国际象棋中这是一个非常庞大且昂贵的运行时问题。为了帮助减少这个问题，可以将minmax与以前玩过的游戏的数据库相结合。任何具有类似棋盘位置并已经建立了如何赢得该布局的模式的游戏都可以用于“分析”下一步要移动到哪里。

我有点困惑你所说的improvement/code_size是什么意思。你真的是指改进/运行时分析（big O(n) vs. o(n)）吗？如果是这样，请与IBM和Big Blue或Microsoft的Parallels团队联系。在PDC上，我曾与一个人交谈过（他的名字现在我忘记了），他正在使用每个对手8个核心来演示麻将，并赢得了游戏算法设计比赛的第一名（这个比赛的名称也我忘记了）。

我认为目前没有任何“现成”的算法可以始终赢得棋局并且速度非常快。你需要做的是将每一场可能的先前比赛都索引到一个非常大的基于字典的数据库中，并预先缓存每场比赛的分析结果。这将是一个非常复杂的算法，而且在我看来，它只会带来很小的改进和更高的复杂度问题。
0

我可能有点跑题，但是“最先进”的国际象棋程序，比如Deep Blue使用MPI进行大规模并行计算。

只需考虑到并行处理在现代国际象棋中扮演着重要角色。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接