为什么目前计算机能够打败国际象棋冠军,但还不能击败职业围棋高手?

Question

如题所述

Answer 1

能，“狗”已经击败了李世乭

直接考虑棋盘上可能出现的状态。
我们考虑任意在棋盘上摆棋子，成为一种棋盘“状态”，而不要顾及这状态是通过什么走法走出来、以及一个智商正常的人可不可能走出这棋局的。考虑到你所设想的那台“知道所有可能性”的电脑是“知道所有可能性”的，显然每一种摆法我们都应当考虑（我国际象棋下得不好，一下子想不出来有没有状态是无法走出的，除了没王），包括白方十六子俱全，黑方只剩一个光头王了这种状态。正常人肯定下不出来，但是要考虑不正常的人，不能让程序这时候茫然无措了呀。另外这个状态对于该黑方走和对于该白方走肯定是不一样的。

然后我们的电脑将把这些状态全部存起来，并且开始提前做一些运算：计算每个状态（布子情况+落子方）是对于黑方必胜，白方必胜，还是必和，同时把对于落子方而言的最优决策记下来。
怎么计算？
从终态倒推。先把显然可以区分胜负（将死，和棋）的状态标记好，然后对于每一个状态（方便陈述，假设此时由黑方落子）：

如果不管怎么落子，之后形成的每一个的状态都已经被标记好胜负态，那么：

如果这些状态每一个都是白方必胜，那么当前状态也只能是白方必胜，走到这儿黑方就可以滚粗了；
如果这些状态中有至少一个是和棋，剩下都是白方必胜，那么记下来此时黑方应该走那步能走到和棋状态的，并把当前状态标记成和棋；
如果这些状态中至少有一个是黑方必胜，那么记下来此时黑方应该走那步能走到黑方必胜状态的，并把当前状态标记为黑方必胜。
如果有一步落子之后，形成一个我还不知道它胜负态的状态，那么先不管它，以后再说。
容易知道，这样倒推大概也是可以把所有状态都标记好的（重复局面的和棋比较复杂，我觉得特殊处理应该能搞，等大神纠正）。如果我们通过这样的提前运算，能知道对于所有的状态的胜负态和最优决策，这游戏确实就不用玩了，计算机必赢无疑，至少是和。

另外这里还有个小推论：如果真的可以得到这个表，那么最开始的局面：布子刚刚完成，其实最后的结局已经定了。因为开局也是一个状态，也有其必胜、必负、必和态。

但我们能不能拿到这个表呢？

现在我要开始算，所有的状态数有多少。
首先从白方的16子中，选出在场上的棋子。王肯定在。所以，白方有x子存活，这x子不同组合的方案是（C代表组合数）：

显然黑子也是一样，为了方便理解换个变量名

然后把这个子放到棋盘上，显然就是个排列数：

统计所有的x和y，所以最后总的状态数：

这个状态数大概是个什么水平？
用斯特林渐近公式（感兴趣自己查吧~）大约可以搞出一个精确近似？
不过我比较懒，暴力给个不精确下界，就算忽略两个组合数当成1，只考虑排列数，而且只考虑最后一项
这个数就大约是以上了。
再乘上前面的组合数，然后对每一项求和……
我物理学得很烂，但我猜，就算我们以一个原子作为存储单元，打碎月球来做我们的硬盘都不太够……

所以，你所说的那个方案，思路是对的，现实是不可能的。现在的电脑玩国际象棋，还是要用Machine Learning，Monte-Carlo，或者暴力alpha-beta之类的搜索算法和调参数技巧来解决。

出现不可战胜的电脑？人几乎不可战胜的电脑，现在已经遍地是了。但这些“战无不胜”的电脑，和电脑下，还能是“不可战胜”的嘛？理论上战无一败的电脑，要等到上面说的那个暴力打表建立起来才行。