阅读有关Google 如何解决翻译问题的信息让我开始思考。是否有可能通过分析数百万场比赛并在很大程度上(完全?)基于统计数据确定可能的最佳移动来构建强大的国际象棋引擎?有几个这样的国际象棋数据库(这是一个有 450 万场比赛的数据库),其中一个可能使用诸如所涉及玩家的评分、游戏的年龄(到国际象棋理论改进的因素)等等。为什么这不是构建国际象棋引擎的可行方法?
11 回答
类似的事情已经完成:这是打开书籍的基本概念。
由于游戏的性质,计算机 AI 一开始是出了名的糟糕,当时有很多可能性,最终目标仍然遥遥领先。当战术可能性开始形成时,它开始向中间改善,并且可以在远超过大多数人的能力的最终游戏中完美发挥。
为了帮助人工智能在一开始就做出好的动作,许多引擎依赖于打开书本:基本上是统计得出的动作流程图。分析了很多高评分玩家之间的游戏,推荐硬编码到“书”中,而位置还在“书”中,AI甚至没有“思考”,只是按照“书” “说。
有些人还可以记住开局的书(这主要是为什么 Fischer 发明了他的随机国际象棋变体,因此记住开局的效率要低得多)。部分由于这个原因,有时会在开始时做出非常规的举动,不是因为从统计上看它是历史上最好的举动,而是恰恰相反:它不是“已知”的位置,并且可以击败你的对手(人类或计算机)“出书”。
在光谱的另一端,有一个叫做endgame tablebase的东西,它基本上是一个以前分析过的残局位置的数据库。由于之前已经对位置进行了详尽的搜索,因此可以使用它来实现完美的游戏:给定任何位置,人们可以立即决定是赢、输还是平局,以及实现/避免结果的最佳方法是什么。
不过,在国际象棋中,这样的事情只适用于开局和残局。中间游戏的复杂性使游戏变得有趣。如果一个人可以简单地通过查表来下棋,那么这盘棋就不会像它那样令人兴奋、有趣和深刻。
好吧,450 万场比赛仍然只占所有可能比赛的很小一部分(无限小)。
虽然你会有大量的获胜和失败位置,但这会将问题减少到一组可用的参数。一个非常古老的问题,以神经网络作为标准方法。但是 NeuralNets 并没有赢得国际象棋比赛。
这种通用策略已经在各种游戏中进行了尝试。很多时候,人们通过让计算机自己玩来生成一个适当大的游戏数据库。一个快速的互联网搜索出现了http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf - 它建立在 Backgammon 先前的工作之上。不过,在国际象棋中,蛮力前瞻对计算机非常有效——而且一般来说,当您可以混合所有先前已知的关于问题的信息时,统计数据会更有效,而不是试图从数据中重新学习. 我注意到,在这个链接中,计算机在前瞻底部学习了相当于评估函数的内容,而不是整个过程。
有一些类似的东西在计算机围棋中效果很好——UCT 方法。它不使用一组已知的游戏,而是玩大量随机游戏,同时保持统计数据,这些数据会导致更高的获胜率。它从当前位置开始。
统计数据保存在移动树中(类似于极小极大中使用的移动树)并影响下一个随机游戏的选择 - 更频繁地选择具有较高获胜率的移动。树的生长也受到游戏的引导——通常每个游戏都会给树添加一片叶子。这导致有希望的路径被更深入地探索。
我喜欢这个想法,但是当考虑到自然语言中句子的上下文比棋盘位置的上下文需要的元素少得多时(即使这些句子的元素,即词,可能来自比国际象棋游戏的元素更大的集合,即棋子、马、兵等)
此外,多语言语料库(各种性质、各种语言的文档)的可用性远远超过人们可能以数字形式找到的国际象棋游戏的数量,特别是考虑到国际象棋分析需要整个游戏时,为了翻译目的,人们可以独立于文本的其余部分使用每个句子。
因此,除了游戏的开局部分(相对于其他游戏而言,棋盘位置没有太多机会发生分歧时)之外,引入一些统计意义所需的国际象棋游戏数量必须是天文...
必须运行,但我会回来对可能的国际象棋游戏数量(绝对和合理游戏的子集)进行具体估计,并且应该有效地证明 450 万场比赛是一个相对较小的样本。
国际象棋中大约有 10 123个博弈树,其中您在该数据库中有大约 4.5 × 10 6 个。我们可以忽略博弈树,而只考虑在 10 43到 10 50 个合法状态之间存在的状态空间复杂度。让我们假设该数据库中的所有游戏都有独特的移动,并且平均每场游戏有 1000 次移动,这给了我们 4.5 × 10 9个状态。取估计的下界 10 43个可能的状态,仅涵盖 4.5 × 10 -34的所有状态。我不知道排除旋转或反射的独特板位置的总数是多少,但它只会减少两倍左右,这不是很有帮助。
您需要将更多领域知识添加到统计引擎中,并找出两个给定棋盘位置之间的相似程度,因为您找不到匹配棋盘位置(包括反射和旋转)的概率为 10 35 。我认为这里最大的关键是找出两个给定的董事会职位是如何相似的。这将包含更多的领域知识,而不仅仅是简单的转换。
尽管如此,这是一个值得进一步探索的好主意,尽管鉴于国际象棋的复杂性和人们对它的兴趣,我怀疑它以前已经尝试过。
我会说是的,它可以工作。还没有人真正成功地尝试过,但为什么不使用统计方法寻找“模式”。我不考虑存储整个棋盘,因为要存储的棋盘位置数量非常多,而只是寻找特定的模式。
寻找模式
一个典型的国际象棋程序评估并给予公认模式的奖金,例如良好的防守棋子或开放的车线,另一方面对诸如双棋子的惩罚。
这样的模式可以在 64 位掩码中有效地编程。您将拥有重要位置的位掩码和这些位置的预期片段的位掩码。每种模式都需要时间来匹配,因此找到能够产生影响的模式非常重要。这就是使用谷歌统计方法的地方。它可以运行“历史”游戏并寻找模式。在它找到一个模式之后,它必须计算该模式的权重,看看改进的评估是否超过了开销。
我认为这将是一个相当大的尝试项目,对于博士论文来说甚至太多了。
机器学习最近取得了长足的进步,尤其是在 Google 团队使用 ML 击败 GO 冠军之后。现在也用国际象棋证明了这一点。看看麻省理工科技评论中的文章,https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master /
ML 的深度学习是对旧的神经网络自调整 AI 算法的增强。赖的示范并没有教机器国际象棋的基本规则,也没有关心比赛的结果。他只是给机器输入了一个庞大的游戏数据库,机器会计算出其余的并以合理的“人类”水平进行游戏。
我认为两大改进将是通过教它规则使其更有效,然后通过向它提供游戏的实际结果来引导它。然后与当前的国际象棋冠军一起训练,像 Stockfish 这样的引擎!:-)
我没有看到提到的一件事是考虑数据库中游戏玩家的评分。一些具有良好分贝百分比的开局是更好的玩家倾向于获胜并且很少谈论开局价值的结果。
事实上,我已经决定数据库只适用于一件事,那就是表明哪些动作很受欢迎。除此之外,您实际上是在扩展您对数据的解释,超出了它的价值。
同样,计算机分析仅显示计算机与计算机游戏的最佳结果。人与人之间的游戏是不同的,你不应该过分依赖计算机分析。
数据库和计算机分析都很有趣,但它们很容易被误解。谨防。
类似于击败人类大师的围棋程序的深度学习算法可能是杀手。不过,这需要很高的成本。然而,人们可能会使用从 GO 中学到的深度学习模式并将其应用于国际象棋。
钦梅,
我知道这是一个老话题,但这是我最近一直在探索的话题。上面回答的大多数人并没有真正得到你的问题。我认为,是的,值得分析过去的许多游戏以制定建议的动作。它会涵盖所有可能的动作吗?不,显然不是。但它涵盖了真实游戏中的所有现实动作。人类(或其他计算机算法)必须开始玩非常奇怪的动作才能摆脱困境。所以,你不能建立一个总是赢的“完美”算法,但如果它赢了很多,比如> 2200 FIDE评级,那还不错吧?如果你将开局和残局结合起来,不仅依赖于过去的移动分析,它还会使它成为一个更好的引擎。
可能的棋盘位置数量多到天文数字,但它是有限的,如果你删除愚蠢的位置,它会大大减少数量。是否可以在同一个文件中排列 4、5 或 6 个玩家棋子?是的,它会发生在真实的游戏中吗?怀疑。在对手“出局”的情况下,将基本的国际象棋大脑纳入您的逻辑。例如, Micro Max只有几百行代码。如果对手愚蠢地阻止了你的行动,他们可能会被一个简单的引擎击败。