为什么国际象棋没有深度强化学习引擎,类似于 AlphaGo?

机器算法验证 神经网络 深度学习 强化学习 游戏
2022-02-13 22:43:44

长期以来,计算机一直能够使用“蛮力”技术下棋,搜索到一定深度,然后评估位置。然而,AlphaGo 计算机仅使用 ANN 来评估位置(据我所知,它不进行任何深度搜索)。是否有可能创建一个像 AlphaGo 下围棋一样下棋的国际象棋引擎?为什么没有人这样做?这个程序会比当今顶级的国际象棋引擎(和棋手)表现更好吗?

2个回答

编辑(阅读论文后):

我仔细阅读了这篇论文。让我们从谷歌在论文中声称的内容开始:

  • 他们用 Monte-Carlo-Tree-Search + 深度神经网络击败了 Stockfish
  • 这场比赛绝对是单方面的,AlphaZero 赢得了很多胜利,但 Stockfish 却没有
  • 他们能够在短短四个小时内完成
  • AlphaZero 像人一样玩

不幸的是,我认为这不是一篇好的期刊论文。我将通过链接进行解释(所以你知道我不是在做梦):

https://www.chess.com/news/view/alphazero-reactions-from-top-gms-stockfish-author

比赛结果本身并没有特别的意义,因为时间控制和 Stockfish 参数设置的选择相当奇怪:比赛以 1 分钟/移动的固定时间进行,这意味着 Stockfish 没有使用其时间管理启发式 (已经付出了很多努力来让 Stockfish 识别游戏中的关键点并决定何时在移动上花费一些额外的时间;在每次移动的固定时间,力量会受到很大的影响)。

Stockfish 不可能以每步一分钟的速度下最好的国际象棋。该程序不是为此而设计的。

  • Stockfish 运行在一台普通的商用机器上,而 AlphaZero 运行在一台为 AlphaZero 调整的 400 万多 TPU 机器上。这就像将您的高端台式机与廉价的 Android 手机相匹配。托德写道:

一个是在普通计算机上运行的传统国际象棋程序,另一个使用根本不同的技术,并且运行在无法购买的定制设计硬件上(如果购买的话,这将超出普通用户的预算)。

  • Google 无意中给 Stockfish 的 32 核机器提供了 64 个线程。我引用 GM Larry Kaufman(世界级计算机国际象棋专家)的话:

http://talkchess.com/forum/viewtopic.php?p=741987&highlight=#741987

我同意测试远非公平;另一个伤害 SF 的问题是,它显然是在 32 核机器上运行在 64 个线程上的,但是在该机器上只运行 32 个线程会更好,因为几乎没有 SMP 的好处来抵消大约 5 到 3 的减速。成本比也比我说的要高;我以为它是 64 核机器,但 32 核机器的成本大约是我猜测的一半。所以也许总而言之,30 比 1 的估计并不是那么糟糕。另一方面,我认为您低估了它可以进一步改进的程度。

对于这样的匹配,1GB 的哈希表是绝对不能接受的。Stockfish 会经常遇到哈希冲突。替换旧的哈希条目需要 CPU 周期。

  • Stockfish 不是为运行那么多线程而设计的。在我的 iOS 国际象棋应用程序中,只使用了几个线程。托德写道:

...正在玩的搜索线程比以往任何时候都多得多的测试...

  • Stockfish 在没有打开书或 6 件式 Syzygy 残局桌面的情况下运行。样本量不足。Stockfish 版本不是最新的。在这里讨论

结论

谷歌并没有毫无疑问地证明他们的方法优于 Stockfish。他们的数字是肤浅的,并且强烈偏向于 AlphaZero。他们的方法不能被独立的第三方复制。现在说深度学习是一种优于传统国际象棋编程的方法还为时过早。


编辑(2017 年 12 月):

Google Deepmind ( https://arxiv.org/pdf/1712.01815.pdf ) 有一篇关于国际象棋深度强化学习的新论文。从抽象上看,世界排名第一的Stockfish象棋引擎“令人信服”地被打败了。我认为这是自 1997 年深蓝比赛以来计算机国际象棋最重要的成就。一旦我详细阅读了这篇论文,我会更新我的答案。


原件(2017 年 12 月之前)

让我们澄清你的问题:

  • 不,国际象棋引擎使用蛮力。
  • AlphaGo确实使用树搜索,它使用蒙特卡洛树搜索如果您想被说服,请谷歌“蒙特卡洛树搜索 alphaGo ”。

ANN 可用于国际象棋引擎:

这个程序会比当今顶级的国际象棋引擎(和棋手)表现更好吗?

长颈鹿的演奏水平大约是国际大师级别,大约是 FIDE 2400 等级。然而,Stockfish、Houdini 和 Komodo 都在 FIDE 3000 左右。这是一个很大的差距。为什么?为什么不使用蒙特卡洛树搜索?

  • 国际象棋中的材料启发式很简单。大多数情况下,棋位的输赢只是通过计算棋盘上的材料。请记住计数材料不适用于围棋。材料计数比运行神经网络快几个数量级——这可以通过由 64 位整数表示的位板来完成。在 64 位系统上,只需几条机器指令即可完成。使用传统算法进行搜索比机器学习要快得多。每秒更高的节点转化为更深入的搜索。
  • 类似地,还有非常有用且便宜的技术,例如空步修剪、后期移动减少和杀手移动等。它们运行起来很便宜,而且对 AlphaGo 中使用的方法非常有效。
  • 国际象棋中的静态评估快速且有用
  • 机器学习对于优化参数很有用,但我们也有用于国际象棋的 SPSA 和 CLOP。
  • 国际象棋中有很多有用的树减少指标。Go 的情况要少得多。

有研究表明,蒙特卡洛树搜索不适用于国际象棋。围棋与国际象棋是不同的游戏。国际象棋算法不适用于围棋,因为国际象棋依赖于残酷的战术。战术可以说在国际象棋中更为重要。

现在,我们已经确定 MCTS 对 AlphaGo 很有效,但对国际象棋则不太适用。在以下情况下,深度学习会更有用:

  • 调整后的 NN 评估优于传统算法。然而......深度学习并不是魔法,作为程序员的你仍然需要进行编程。如前所述,我们有类似 SPSA 的东西,用于在国际象棋中进行参数调整的自我对弈。
  • 投资,钱!国际象棋中机器学习的钱不多。Stockfish 是免费和开源的,但强大到足以击败所有人类玩家。如果有人可以免费下载 Stockfish,Google 为什么要花费数百万美元?为什么要为 CPU 集群付费?谁来为人才买单?没有人愿意这样做,因为国际象棋被认为是一种“已解决”的游戏。

如果深度学习能够做到以下几点,它将击败传统算法:

  • 给定一个国际象棋位置,“感觉”它就像一个人类大师。例如,根据经验,人类大师不会进入糟糕的路线。传统算法和深度学习都无法做到这一点。您的 NN 模型可能会为您的职位提供 [0..1] 的概率,但这还不够好。

让我指出:

不,长颈鹿(@Tim 发布的链接)不使用蒙特卡洛树搜索。它使用常规的负最大算法。它所做的只是用 NN 替换常规评估函数,而且速度非常慢。

多一个:

尽管卡斯帕罗夫在 1997 年的比赛中被深蓝击败。《人性》在 2003-2005 年左右真的失传了,当时克拉姆尼克在一场比赛中输给了德普弗里茨,没有获胜,而迈克尔亚当斯在一场单边比赛中输给了集群机器。大约在那个时候,Rybka 被证明对世界上最好的球员来说也太强大了。

参考:

http://www.talkchess.com/forum/viewtopic.php?t=64096&postdays=0&postorder=asc&highlight=alphago+chess&topic_view=flat&start=0

我引用:

在国际象棋中,我们有物质性的概念,它已经对引擎的性能给出了合理的估计,并且可以快速计算。此外,游戏的许多其他方面可以用 Go 无法完成的静态评估函数进行编码。由于许多启发式方法和良好的评估,EBF(Effective-Branching-Factor)非常小。使用神经网络代替静态评估函数会明显降低引擎速度。

DeepBlue 已经击败了 Kasparov,所以这个问题可以用更简单的方法解决。这是可能的,因为国际象棋中可能的移动数量比围棋要少得多,所以这是一个更简单的问题。此外,请注意神经网络和蛮力都需要大量的计算资源(在这里您可以找到AlphaGo 背后的计算机照片,注意它甚至不使用 GPU,而是使用 TPU 进行计算)。围棋的大惊小怪是,当深蓝击败卡斯帕罗夫时,围棋社区认为围棋不可能做到这一点(出于许多不同的原因,但为了总结这些论点,我需要对游戏进行详细介绍去)。是的,你可以教 NN 下棋,马里奥,或者试着教它下棋星际争霸...

我想原因是你根本不经常在主流媒体上听到人们解决已经解决的问题的案例。

此外,您的前提是错误的,深度学习用于下棋,例如深度学习机器在 72 小时内自学国际象棋,在国际大师级别下棋中所述。另请参阅相应的论文Giraffe:使用深度强化学习下棋