网络在线手游棋牌 棋牌热点 为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来

其实啊,怎么说呢。放个视频吧,象棋可以这么少,围棋却很难,大概你就明白了。一招一式尽在掌控中。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图南北棋王快棋决胜千里https://www.zhihu.com/video/1126962796432273408

因为深蓝的开发团队里边有个下象棋的(不是)。


写了一大堆,觉得还是删了得好,几句话就能总结嘛。

深蓝解决了“需要计算时该怎么办”这个问题。

阿尔法围棋解决了“当计算不能解决所有问题时该怎么办”

人工智能的目标是“当计算解决不了任何问题时该怎么办”

象棋到围棋,是一个从“有详细规则”到“有简单规则”的过程,是一个逐渐剥离“计算力”,凸显“谋略”的过程。

是一个考验人工智能到底智不智的过程。


反对一下个别只谈状态数的回答。

无论是象棋还是围棋,都不是靠穷举爆破赢的。

我还以为“状态数差距太大”的结论应该因为阿尔法狗事件变得比较广为人知了。然后看了一眼答案,发现目前6个回答中没有写对的……


贴一下象棋和围棋各自的总状态数:

中国象棋状态总数为7.54×10^39.88(诡异的数字……出自《智能系统学报》动态规划求解中国象棋状态总数)

围棋状态总数为2.1×10^151次方(普林斯顿研究人员计算结果)。

都是合法状态,保证能走的出来,比如围棋的棋盘上不能有死子等等。所以,如果要求爆搜剪枝破解的话(因为这就是象棋的机器解法),围棋要比象棋晚多少年才能被机器暴力破解呢?

根据摩尔定律是每18~24个月翻一倍,这个定律至今为止50年不到,不断在放缓,现在已经是3年以上翻一倍了。我们假设不放缓,2年翻一倍。

(2.1×10^151)/(7.54×10^39.88) > 2^360,翻倍360次。也就是说,在人类发明了可以暴力破解象棋的计算机之后,如果摩尔定律不放缓的话,人类最早可以在720年之后发明可以暴力破解围棋的计算机。


为啥在象棋打败人类之后20年围棋就能打败人类了,这要归功于两个方面:

一个是机器学习的方法,这和爆搜剪枝完全不是一个概念的东西。但是如果要做到真正让计算机知道所有的可能状态,则爆搜是必须的,不能使用机器学习。国际象棋打败人类就是用爆搜剪枝。

第二个就是人类太弱了,能保证打败人类就行了,不需要知道所有状态。


更新:推荐另外一个更好的回答。本回答中“状态数的差距”和“搜索剪枝与机器学习方法差别的论述”虽然应该没错,但象棋的估价函数好写(比如每个子值多少)使得搜索的剪枝部分可以进行应当是更加关键的理由。也就是只有拥有良好的估价函数才能剪枝,于是象棋搜索好剪枝,围棋搜索很不好剪枝,所以象棋先战胜了人类,而围棋只好换算法。

https://www.zhihu.com/answer/737053043

外行一答,总的来说,围棋的计算量比象棋大很多,据说全宇宙的尘埃也不及围棋的变化多。但是alpha go不是靠穷举和里暴力计算赢的,靠以前“深蓝”的策略,现在也赢不了人类。

象棋的棋盘小,子数少。象棋开局,每个子都摆在棋盘上,每个子都有规矩(如象走田,马走日),可走的位置并不很多,用穷举法很容易算尽。而且到后期,有很多经典残局,只要想办法将局势导入残局,胜负很容易判定并决策。而且每个子的价值都有区别,兑子时很好判断。

围棋纵横19路,361个点。开局棋盘无子,第一个子可以落在任何一点,要按以前的“傻算”,第一手的计算量是最大的,依次递减。每个子下落基本没什么规矩,对计算机来说,比象棋多指数级的计算量。围棋每个子的价值是根据它的位置和时间来决定的,彼时的闲招,也可能成为此时的要害,走错次序,每个子的价值就有天壤之别,常常处于变化之中,在算法上又是一道难题。

alpha go是算法上的胜利

先说答案吧。象棋和围棋这两种棋类游戏都属于完美信息游戏,不管从状态空间复杂度,还是游戏树复杂度上来说,围棋都远远领先于下表中其他棋类游戏。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图1

大家或许会疑惑,这个表是怎么得来的?

另一个延伸问题是:随着 AI 逐个攻克双陆棋、国际跳棋、国际象棋、围棋,AI 仍在继续挑战难度更高的游戏,例如扑克、桥牌、麻将这类不完美信息游戏,这些游戏里哪个对 AI 来说更难玩呢?

这篇回答就一次性为大家解析棋牌类游戏 AI 的难度~


游戏复杂度与游戏难度并不等价

首先需要提醒大家,游戏的复杂度与难度并不完全等价,游戏难度除了与游戏本身的复杂度有关以外,还与战略等多种要素相关,也就是说,数学上更复杂的游戏,玩起来不一定更难。

一般来说,我们可以根据信息的暴露程度将游戏分为两大类:完美信息游戏(Perfect-Information Games)和不完美信息游戏(Imperfect-Information Games)。如果所有的参与者,在游戏的任何阶段都可以访问所有关于游戏(包括对手)状态及其可能延续的信息,那么称这类游戏为完美信息游戏;否则称为不完美信息游戏。围棋、象棋等棋类游戏,对局双方可以看到局面的所有信息,属于完美信息游戏;而扑克、桥牌、麻将等游戏,虽然每个参与者都能看到对手打过的牌,但并不知道对手的手牌和游戏的底牌,也就是说各个对局者所掌握的信息是不对称的,因此属于不完美信息游戏。

完美信息游戏和不完美信息游戏难度的衡量指标通常是有区别的。对于完美信息游戏,通常游戏的复杂度就决定了难度,我们可以用状态空间复杂度(State-Space Complexity)和游戏树复杂度(Game-Tree Complexity)对其难度进行衡量;而对于不完美信息游戏,隐藏信息对于游戏的难度影响很大,我们可以用信息集(Information Set)数目和信息集平均大小对其难度进行衡量。

完美信息游戏:状态空间和游戏树的复杂度

状态空间复杂度(State-Space Complexity)

游戏的状态空间复杂度(SSC)是指从游戏的初始状态开始,可以达到的所有符合规则的状态的总数。例如棋类游戏中,每移动一枚棋子或捕获一个棋子,就创造了一个新的棋盘状态,所有这些棋盘状态构成游戏的状态空间。通常情况下,很难精确地计算出游戏的状态空间大小,只能给出一个粗略的估计。一种最常用的估计方法是通过包含一些不符合规则或不可能在游戏中出现的状态, 从而计算出状态空间大小的一个上界(Upper Bound)。例如在估计围棋状态数目上界的时候,允许出现棋面全部为白棋或者全部为黑棋的极端情况。

事实上,即便像井字棋这样简单的游戏,其状态空间也是很大的。井字棋的盘面上共有9(3×3)个位置,每个位置可能的取值有三种:X,O或空白,因此总的状态数目为3的9次方即19863个。当然,这其中包含许多不符合规则的状态,因为我们在这里估计的是状态空间大小的上界。由此,我们可以得到井字棋的状态空间复杂度约为10^4(即19863≈10^4)。这种计算方法可以很容易地推广到更大的棋盘和更加复杂的棋类游戏。比如围棋有361(19×19)个位置,每个位置可以放置白子或黑子或者空置,利用上述方法,可以确定围棋的状态空间复杂度约为10^172 (即3^361≈10^172)。在表1中,我们给出了常见的完美信息棋类游戏的状态空间复杂度。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图2

游戏树复杂度(Game-Tree Complexity)

游戏树复杂度(GTC)表示某个游戏的所有不同游戏路径的数目。游戏树复杂度比状态空间复杂度要大得多,因为同一个状态可以对应于不同的博弈顺序。例如,在图2的井字棋游戏中,棋面上有两个 X 和一个 O,这个状态可能由两种不同的方式形成,具体的形成过程由第一个 X 的下子位置所决定。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图3

与状态空间类似,游戏树复杂度的精确值也很难计算。常用的方法是估计其合理的下界:GTC≥b^p,其中 b 表示玩家每回合可用的平均合法移动数目,p 表示平均游戏长度。由此可以看出,拥有更多合法移动的游戏比合法移动较少的游戏更复杂,另外游戏的平均长度也是影响游戏树复杂度的关键因素。

根据经验,井字棋、象棋以及围棋每一步的平均合法移动数目分别为4、35和250;平均游戏长度分别为9、80和150。因此利用上面的公式,可以得出井字棋的游戏树复杂度为10^5 (即4^9≈10^5),国际象棋是10^123 (即35^80≈10^123),而围棋是10^360 (即250^150≈10^360)。更多完美信息棋牌类游戏的游戏树复杂度参见表1。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图4

在传统的完美信息棋牌游戏中,围棋不管从状态空间复杂度,还是游戏树复杂度上都远远领先其他棋牌类游戏。2017年,AlphaZero 利用 MCTS 和深度强化学习,成功解决了包括围棋在内的多个完美信息游戏。目前,学术界研究的热点则转向不完美信息游戏和即时策略游戏等。

不完美信息游戏:信息集数目和平均大小

对于不完美信息游戏,我们仍然可以同完美信息游戏一样计算其状态空间复杂度和游戏树复杂度。然而,在不完美信息游戏中,由于信息是不完全、非对称的(例如扑克和麻将中对手的手牌和游戏剩余的底牌都是未知的),因此对于参与者来说许多不同的游戏状态看起来是无法区分的。例如在扑克游戏中,自己拿了两张 K,对方拿了不同的牌对应不同的状态;但是从自己的视角看,这些状态其实是不可区分的。我们把每组这种无法区分的游戏状态称为一个信息集。

显然,对于不完美信息游戏而言,合理的游戏策略应该建立在信息集而不是游戏状态之上,因为我们依赖未知信息来细粒度出招是没有意义的。相应地,当我们衡量不完美信息游戏的难度的时候,也应该依据信息集的数目,而不是游戏状态空间的大小。信息集的数目通常小于状态空间的数目。对于完美信息游戏,由于所有信息都是已知的,每个信息集只包含一个游戏状态,因此它的信息集数目与状态空间数目是相等的。

除了信息集的数目,还有一个重要的指标:信息集的平均大小,即在信息集中平均有多少不可区分的游戏状态。以两人德州扑克为例,假定我们的手牌是 AA,考虑对手的手牌为 AK 或者 AQ 两种不同情况。因为信息不完全,我们无法区分当前局势到底处在哪个状态,因此会把两种情况都归到同一个信息集。在两人德州扑克中,信息集的大小最多为1326(从52张牌中选择2张:C_52^2),也就是约为10^3。容易看出,信息集的数目反映了不完美信息游戏中所有可能的决策节点的数目,而信息集的平均大小则反映了游戏中每个局面背后隐藏信息的数量。显然,信息集平均大小越大,其中包含的未知信息就越多,因此决策的难度就越高。事实上,信息集的平均大小直接影响采用搜索算法的可行性:当对手的隐藏状态非常多时,传统的搜索算法基本上是无从下手的。因此信息集的平均大小也可以作为游戏难度的衡量指标。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图5

无限注德州扑克的信息集数目很大,但是因为只有两张不可见的牌,其隐藏信息很少,信息集的平均大小很小。桥牌和麻将由于是每个玩家手里可以有13张未知的手牌,因此隐藏信息的数量远远超过了德州扑克。表2给出了德州扑克、桥牌和麻将的信息集数目和信息集的平均大小。

如果我们以信息集数目和信息集平均大小为准则,来对比像围棋这样的完美信息游戏和表2中的几种不完美信息游戏,会得到非常有意思的结果。如图3所示,围棋和德州扑克的信息集平均大小远远小于桥牌和麻将。AI 在围棋和德州扑克上的成功很大程度依赖于搜索算法,因为搜索可以最大程度地发挥计算机的计算优势。但是因为巨大的信息集平均大小带来的环境不确定性,传统的搜索算法在桥牌和麻将面前很难发挥同样的功效。

为什么人工智能先打败象棋顶尖选手,再打败围棋顶尖选手,而不是反过来插图6

回顾游戏 AI 的历史,目前大部分完美信息游戏(如国际象棋、围棋等)以及信息集平均大小较小的不完美信息游戏(如两人德州扑克和多人德州扑克等)都有了相当好的解决方法。然而,对于桥牌和麻将这类含有大量隐藏信息的不完美信息游戏,需要我们发明全新的方法论,才能有所突破,而这需要 AI 算法的研究者们持之以恒地探索。

延伸阅读:游戏难度的计算方法

定约桥牌(只考虑打牌阶段)
信息集数目:以防守一方为例,按照游戏轮次来计算。第一轮,每个玩家只能看到自己的13张牌,因此第一轮信息集数目为C_52^13=6.3×10^11。第二轮,每个玩家剩余12张牌,玩家只能看到自己的12张手牌以及第一轮出的四张牌,因此第二轮信息集数目为C_52^13 C_13^1 C_39^1 C_38^1 C_37^1=C_52^13 A_13^1 A_39^3。以此类推,第三轮信息集数目为C_52^13 C_13^1 C_12^1 C_39^1 C_38^1 C_37^1 C_36^1 C_35^1 C_34^1=C_52^13 A_13^2 A_39^6 … 第13轮信息集数目为C_52^13 A_13^12 A_39^36。总的信息集数目为各轮信息集的和,即C_52^13 (1+A_13^1 A_39^3+⋯+A_13^12 A_39^36)≈1.35×10^67。
信息集平均大小:以防守一方为例,第一轮,其他选手有13张牌,所以每个信息集大小为C_39^13 C_26^13 C_13^13。第二轮,每位对手还剩12张牌,因此每个信息集大小为C_36^12 C_24^12 C_12^12。以此类推,第13轮,每个信息集大小为C_3^1 C_2^1。对每一轮的信息集大小求平均,得到桥牌的信息集平均大小≈6.77×10^15。

麻将
信息集数目:每一局麻将结束的时候,底下有14张牌不会被用到,所以不考虑吃碰杠的情况下,每一局至多会进行17.5轮(136减去13×4共52张手牌再减去14张底牌,总共剩70张牌,每一轮出4张)。与桥牌类似,依然按照游戏轮次来计算。第一轮,每个玩家只能看到自己的13张牌,因此第一轮信息集数目为C_136^13(为了计算方便,不考虑重复手牌)。第二轮,由于第一轮每个玩家各出一张牌,一副麻将总共有34种不同的牌,所以第一轮出的四张牌所有可能的情况至多为34^4,因此第二轮信息集数目为C_136^13 ∙34^4。以此类推,第18轮信息集数目为C_136^13 ∙34^68。总的信息集数目为各轮信息集的和,即C_136^13 (1+34^4+⋯+34^68)≈7×10^121。
信息集平均大小:第一轮,除去自己13张手牌,总共剩余123张牌,每位对手13张牌,所以每个信息集大小为C_123^13 C_110^13 C_97^13(为了计算方便,不考虑重复手牌)。第二轮,除去自己13张手牌,以及第一轮出的四张牌,总共剩余119张牌,因此每个信息集大小为C_119^13 C_106^13 C_93^13。以此类推,第18轮,每个信息集大小为C_55^13 C_42^13 C_29^13。对每一轮的信息集大小求平均,得到麻将的信息集平均大小≈1.07×10^48。

参考文献:

[1]L.V. Allis, Searching for solutions in games and artificial intelligence, Ph.D.Thesis, University of Limburg, Maastricht, 1994.

[2]van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Games solved: now and in the future. Artif. Intell. 134, 277–311 (2002).

[3]Game Complexity I: State-Space & Game-Tree Complexitieshttps://www.pipmodern.com/feed/state-space-game-tree-complexity

[4]Game Complexity III: Artificial Intelligencehttps://www.pipmodern.com/feed/complexity-artificial-intelligence[5]M. Johanson, Measuring the size of large no-limit poker games, Technical Report TR13-01, Department of Computing Science, University of Alberta (2013).[6]Wiki: Game complexityen.wikipedia.org/wiki/Game_complexity


本账号为微软亚洲研究院的官方知乎账号。本账号立足于计算机领域,特别是人工智能相关的前沿研究,旨在为人工智能的相关研究提供范例,从专业的角度促进公众对人工智能的理解,并为研究人员提供讨论和参与的开放平台,从而共建计算机领域的未来。

微软亚洲研究院的每一位专家都是我们的智囊团,你在这个账号可以阅读到来自计算机科学领域各个不同方向的专家们的见解。请大家不要吝惜手里的“邀请”,让我们在分享中共同进步。

也欢迎大家关注我们的微博和微信 (ID:MSRAsia) 账号,了解更多我们的研究。

本文来自网络,不代表网络在线手游棋牌立场,转载请注明出处:https://mip.qidake.com/265/

作者: qipai

上一篇
下一篇

返回顶部