国际象棋的统计方法？
阅读Google 如何解决翻译问题让我开始思考。是否有可能通过分析数百万盘棋并很大程度上（完全？）基于统计数据确定最佳可能的走法来构建强大的国际象棋引擎？有几个这样的国际象棋数据库（这个是一款拥有 450 万局游戏的游戏），并且可以使用相关因素（例如参与棋手的评分、游戏的年龄（考虑国际象棋理论的改进）等因素）对相同（或镜像或反射）位置的走法进行加权有什么理由说明这不是构建国际象棋引擎的可行方法吗？
Reading about how Google solves the translation problem got me thinking. Would it be possible to build a strong chess engine by analysing several million games and determining the best possible move based largely (completely?) on statistics? There are several such chess databases (this is one that has 4.5 million games), and one could potentially weight moves in identical (or mirrored or reflected) positions using factors such as the ratings of the players involved, how old the game is (to factor in improvements in chess theory) etc. Any reasons why this wouldn't be a feasible approach to building a chess engine?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（11）
类似的事情已经完成：这是打开书籍的基本概念。
由于游戏的性质，计算机人工智能在一开始就表现得很糟糕，因为有很多可能性，而最终目标仍然遥遥领先。当战术可能性开始形成时，它开始向中间改进，并且可以在最终游戏中完美发挥，远远超出大多数人的能力。
为了帮助人工智能在一开始就做出好的动作，许多引擎依赖于打开书籍：基本上是统计得出的动作流程图。许多高评分玩家之间的比赛被分析，推荐被硬编码到“书本”中，虽然位置仍在“书本”中，但AI甚至不“思考”，只是按照“书本”进行操作”说。
有些人还可以记住开卷（这就是费舍尔发明他的随机国际象棋变体的主要原因，这样记忆空缺的效率就会大大降低）。部分原因在于，有时一开始就会采取非常规的举动，并不是因为它是历史上统计上最好的举动，而是恰恰相反：它不是一个“已知”的位置，并且可以采取你的对手（人类或计算机）“从书中”。
另一方面，有一个名为 endgame tablebase 的东西，它基本上是一个数据库之前分析过残局位置。由于先前对位置进行了详尽的搜索，因此人们可以使用它来实现完美的游戏：给定任何位置，人们可以立即决定是赢、输还是平，以及实现/避免结果的最佳方式是什么。
不过，在国际象棋中，这样的事情只适用于开局和残局。中间游戏的复杂性使得游戏变得有趣。如果下棋只要查表就能下，那么棋局就不会那么刺激、有趣、有深度了。
Something like this is already done: it's the underlying concept of opening books.
Due to the nature of the game, computer AIs are notoriously bad in the beginning, when there are so many possibilities and the end goal is still far ahead. It starts to improve toward the middle, when tactical possibilities start to form, and can play perfectly in the end game far exceeding the capability of most humans.
To help the AI make good moves in the beginning, many engines rely on opening books instead: a statistically derived flowchart of moves, basically. Many games between highly rated players were analyzed, and recommendations are hard-coded into "the book", and while the positions are still in "the book", the AI doesn't even "think", and simply follow what "the book" says.
Some people can also memorize opening books (this is mostly why Fischer invented his random chess variant, so that memorization of openings becomes far less effective). Partly due to this, sometimes an unconventional move is made in the beginning, not because it's statistically the best move according to history, but precisely the opposite: it's not a "known" position, and can take your opponent (human or computer) "out of the book".
On the opposite end of the spectrum, there is something called endgame tablebase, which is basically a database of previously analyzed endgame positions. Since the positions were previously searched exhaustively, one can use this to enable perfect play: given any position, one can immediately decide if it's winning, losing, or draw, and what's the best way to achieve/avoid the outcome.
In chess, something like this is only feasible for the opening and endgame, though. The complexity of the middle game is what makes the game interesting. If one can play chess simply by looking up a table, then the game wouldn't be as exciting, interesting, and deep as it is.
好吧，450 万款游戏仍然只涵盖了所有可能游戏中非常小的（无穷小的）一部分。
虽然您会有大量的获胜和失败头寸，但这会留下将其减少到一组可用参数的问题。这是一个非常古老的问题，神经网络作为标准方法。但神经网络并没有赢得国际象棋锦标赛。
Well, 4.5 million games still only covers a very tiny (infinitesimal small) fraction of all possible games.
And while you would have a large number of winning and loosing positions, that would leave the problem of reducing that to a usable set of parameters. A very old problem, with neural networks as a standard approach. But NeuralNets aren't winning chess tournaments.
这种一般策略已在多种游戏中进行过尝试。人们经常通过让计算机自己玩来生成一个适当大的游戏数据库。快速互联网搜索会出现http:// www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf - 它建立在双陆棋之前的工作基础上。不过，在国际象棋中，强力前瞻对于计算机来说非常有效，而且一般来说，当您可以混合所有先前已知的有关问题的信息，而不是尝试从数据中重新学习时，统计数据会更有效。我注意到，在这个链接中，计算机了解了前瞻底部的评估函数，而不是整个过程。
This general strategy has been tried for a variety of games. Very often people generate a suitably large database of games by having the computer play itself. A quick internet search turns up http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf - which builds on previous work in Backgammon. In chess, brute force look-ahead is very effective for computers, though - and in general statistics is much more effective when you can mix in all of the previously known information about the problem, rather than trying to re-learn it from the data. I note that in this link the computer learnt what amounts to the evaluation function at the bottom of the look-ahead, not the whole process.
有一种类似的方法在计算机 Go 中运行得非常好 - UCT 方法。它不使用一组已知的游戏，而是玩大量随机游戏，同时保留统计数据，这些统计数据会导致更高的获胜率。它从当前位置开始执行此操作。
统计数据保存在移动树中（类似于极小极大中使用的树），并影响下一个要玩的随机游戏的选择 - 获胜率较高的移动会被更频繁地选择。树的生长也是由游戏引导的——通常每个游戏都会给树添加一片叶子。这导致人们更深入地探索有希望的道路。
There is something similar that works very well in computer Go - the UCT method. It does not use a known set of games but instead plays a huge number of random games while keeping statistics which moves lead to higher ratios of wins. It does so starting from the current position.
The statistics are kept in a tree of moves (similar to one used in minimax) and influence the choice of the next random game to play - the moves with higher win ratios are chosen more often. The growth of the tree is also guided by the games - usually each game adds a leaf to the tree. This leads to the promising paths being explored more deeply.
我喜欢这个想法，但考虑到自然语言句子的上下文需要的元素比棋盘位置的上下文少得多（尽管这些句子的元素，即单词，可能来自比国际象棋游戏的元素更大的集合，即游戏棋子、骑士、棋子等）
此外，多语言语料库的可用性（各种语言的各种性质的文档）远远超过了人们可以以数字形式找到的国际象棋游戏的数量，特别是考虑到对于国际象棋分析，人们需要整个游戏，因此出于翻译目的，人们可以独立于文本的其余部分使用每个句子。
因此，除了游戏的开局部分（当棋盘位置相对于其他游戏没有太多机会偏离时）之外，需要引入的国际象棋游戏数量一些统计意义必须是天文数字......
必须运行，但我会回来对可能的国际象棋游戏数量进行具体估计（绝对数量，以及合理游戏的子集） ，并且应该有效证明450万款游戏是一个相对较小的样本。
I like the idea, but the analogy [with text translation] seems to fall short when considering that the context of a sentence in natural language requires much fewer elements than the context of a chess board position (even though the elements of such sentences, namely words, may come from of a bigger set than the elements of a chess game, namely the game pieces, knight, pawn etc.)
Furthermore, the availability of multi-lingual corpus (documents of various nature, in various languages) far exceeds the number of chess games which one may find in a digital form, in particular when considering that for chess analysis one needs the whole game whereby, for translation purpose, one can use every sentence independently from the rest of the text.
As a result, and with the possible exception of the opening portion of the games (when the board positions haven't had much opportunity to diverge relatively to other games), the number of chess games required to introduce some statistical significance would have to be astronomical...
Gotta run, but I'll be back with specific estimates on the number of possible chess games (in the absolute, and in the subset of plausible games), and should effectively prove that 4.5 million games is a relatively small sample.
国际象棋中大约有 10123 博弈树，其中数据库中有大约 4.5 × 106 。我们可以忽略博弈树，只考虑状态空间复杂性，其合法状态介于 1043 和 1050 之间。假设该数据库中的所有游戏都有独特的走法，并且每场游戏平均有 1000 个走法，这为我们提供了 4.5 × 109 状态。采用估计的可能状态下限 1043，仅覆盖所有状态的 4.5 × 10-34。我不知道排除旋转或反射的独特棋盘位置的总数是多少，但这只会将其减少两倍左右，这并不是很有帮助。
您需要将更多领域知识添加到统计引擎中，并找出两个给定棋盘位置之间的相似程度，因为您有十分之一35的机会找不到匹配的棋盘位置（包括反射和旋转）。我认为这里最大的关键是找到两个给定的董事会职位有何相似之处。这将包含更多的领域知识，而不仅仅是简单的转换。
尽管如此，这是一个值得进一步探索的好主意，尽管考虑到国际象棋的复杂性和围绕它的兴趣，我怀疑以前已经尝试过它。
There are approximately 10123 game trees in chess out of which you have about 4.5 × 106 in that database. We can ignore the game trees, and only consider state-space complexity of which there are anywhere between 1043 and 1050 legal states. Let's assume that all games in that database have unique moves, and that there are 1000 moves on average per game, which gives us 4.5 × 109 states. Taking the estimated lower bound 1043 of possible states, that only covers 4.5 × 10-34 of all states. I don't know what is the total number of unique board positions that exclude rotations or reflections, but it will only reduce it by a factor of two or so, which is not very helpful.
You would need to add more domain knowledge into the statistical engine and find out the level of similarity between two given board positions as there is a 1 in 1035 chance that you will not find a matching board position (including reflections and rotations). I think the biggest key here would be finding how how two given board positions are similar. That will incorporate a lot more domain knowledge than just simple transformations.
It is a great idea nonetheless that is worth exploring further, although I suspect that it has been tried before given the complexity of chess and the interest around it.
我会说是的，它可以工作。还没有人真正成功地尝试过，但为什么不使用统计方法来寻找“模式”呢？我不考虑存储整个棋盘，因为要存储的棋盘位置多得天文数字，而只是寻找特定的模式。
寻找模式
典型的国际象棋程序会对公认的模式进行评估并给予奖励，例如良好的防守兵或开放的车线，另一方面对双兵等给予惩罚。
此类模式可以在 64 位掩码中高效编程。您将拥有重要位置的位掩码和这些位置中预期片段的位掩码。每个模式都需要时间来匹配，因此找到有影响的模式非常重要。这就是谷歌统计方法的用武之地。它可以运行“历史”游戏并寻找模式。找到模式后，它必须计算该模式的权重，并查看改进的评估是否超过开销。
我认为这将是一个相当庞大的项目，对于博士论文来说甚至太多了。
I would say yes, it could work. Nobody's really tried it successfully yet, but why not look for "patterns" using a statistical approach. I am not considering storing the whole board since there's astronomically many board positions to store, but merely looking for specific patterns.
Looking for Patterns
A typical chess program evaluates and gives bonuses for recognized patterns such as good defending pawn or an open rook line and on the other hand penalties for such as doubled pawns.
Such patterns could be programmed efficiently in 64-bit masks. You would have bit-masks for positions that matter and bit-masks for expected pieces in those positions. Each pattern takes time to match so it would be important to find the ones that makes a difference. That's where Google's statistical approach would be used. It could run through "historic" games and look for patterns. After it finds a pattern it would have to calculate a weight to the pattern and see if the improved evaluation outweighs the overhead.
I think this would be a rather huge project to try out, even too much for a PHD thesis.
机器学习最近取得了长足的进步，特别是在 Google 团队使用 ML 击败围棋冠军之后。现在国际象棋也证明了这一点。看看麻省理工学院技术评论中的文章，https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international -master/
ML 的深度学习是对旧的神经网络自调整 AI 算法的增强。赖的演示并没有教机器国际象棋的基本规则，也没有关心游戏的结果。他只需向机器输入大量游戏数据库，机器就会计算出其余部分并以合理的“人类”水平进行游戏。
我认为两大改进是通过教它规则来提高它的效率，然后通过向它提供游戏的实际结果来指导它。
然后，与当前的国际象棋冠军、像 Stockfish 这样的引擎一起训练！ :-)
Machine Learning has made big progressions lately, especially after the Google team beat the GO champion using ML. It has now also been demonstrated with chess. Take a look at the article in MIT technology Review, https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/
ML's Deep Learning is an enhancement to the old Neural Network self-tuning AI algorithms. Lai's demonstration didn't teach the machine the basic rules of chess or cared about the outcome of the games. He just fed the machine with a large database of games and the machine figured out the rest and played at a reasonable "human" level.
I assume two big enhancements would be to make it more efficient by teaching it the rules and then guide it by feeding it with the actual results of the games.
Then after that go train with the current chess champions, engines like Stockfish! :-)
类似于击败人类大师玩家的 GO 程序的深度学习算法可能是杀手。但这需要很高的成本。然而，人们可以使用从 GO 中学到的深度学习模式并应用
它到国际象棋。
Deep Learning algorithm similar to the GO program that defeated the Master Human player might be killer. It would require a high cost though. However, one might use the learned deep learning patterns from GO and apply
it to chess.
我没有看到提到的一件事是考虑数据库中游戏中玩家的评分。一些具有良好分贝百分比的开局是由于更好的玩家倾向于获胜并且很少谈论开局的价值的结果。
事实上，我认为数据库只适合一件事，那就是表明哪些动作是流行的。除此之外，你对数据的解释确实超出了它的价值。
同样，计算机分析仅显示计算机与计算机游戏的最佳结果。人与人之间的游戏是不同的，你不应该过于依赖计算机分析。
数据库和计算机分析都很有趣，但它们很容易被误解。提防。
One thing I have not seen mentioned is consideration for the ratings of the players in games in your database. Some openings with good db percentages are a result of the better player tending to win and say little about the value of the opening.
In fact I have decided that databases are good for only one thing and that is indicating what moves are popular. Beyond that you are really stretching your interpretation of the data beyond what it merits.
Similarly computer analysis only shows the best result for computer vs computer games. Games between humans are different and you should not rely too heavily on computer analysis.
Both the database and computer analysis is interesting but they can easily be misinterpreted. Be-ware.
Chinmay，
我知道这是一个老话题，但这是我最近一直在探索的一个话题。上面回答的大多数人并没有真正明白你的问题。我认为，是的，有必要分析过去的大量比赛来制定建议的行动。它会涵盖所有可能的动作吗？不，显然不是。但它涵盖了真实游戏中的所有真实动作。人类（或其他计算机算法）必须开始玩非常奇怪的动作才能摆脱困境。所以，你不可能建立一个一直获胜的“完美”算法，但如果它赢了很多，比如说 >2200 FIDE 评级，那也不错，对吧？如果你结合开局和残局，而不仅仅是依赖过去的着法分析，它就会成为一个更好的引擎。
可能的棋盘位置数量多得天文数字，但它是有限的，如果你删除愚蠢的位置，它的数量就会大大减少。是否可以将 4、5 或 6 个单人棋子排成一列？是的，在真实的游戏中会发生这种情况吗？对此表示怀疑。将基本的国际象棋大脑纳入你的逻辑中，以应对对手“超出规则”的情况。例如，Micro Max 只有几百行代码。如果对手愚蠢地阻止你的行动，他们可能可以通过简单的引擎击败。
Chinmay,
I know this is an old thread, but it's a topic I've been exploring lately. Most of the people who answered above didn't really get your question. I think that, yes, it is worth analyzing numerous games in the past to develop suggested moves. Will it cover all possible moves? No, obviously not. But it covers all realistic moves from real games. A human (or another computer algorithm) would have to start playing very strange moves to throw things off. So, you can't build a 'perfect' algorithm that wins all the time, but if it wins a lot, say a >2200 FIDE rating, it's not bad right? And if you incorporate Openings and Endgames, not just rely on past move analysis, it makes it an even better engine.
There are an astronomically high number of possible board positions, but it is finite, and if you remove the stupid positions it reduces the number quite a bit. Is it possible to have 4, 5 or 6 of one players pawns lined up in the same file? Yes, would it happen in a real game? Doubt it. Include a basic Chess brain into your logic for situations where the opponent goes 'off book'. Micro Max is only a couple hundred lines of code for example. If the opponent has played stupid to thwart your moves, they are probably beatable by a simple engine.