电脑围棋软件与人工智能
人工智能
作者: 月光博客
2016-02-28 13:19:10
分享到:
[ 久闻导读 ] 围棋作为唯一的一种电脑下不赢人的大众棋类,是何原因导致?谷歌的AlphaGo能战胜世界超一流棋手吗?现代人工智能是怎么解决围棋软件庞大的数据处理量?本文将对电脑围棋软件和人工智能相关问题进行一番探讨和分析。

围棋是一种策略性两人棋类游戏,有这悠久而古老的历史,中国古时称“弈”,西方名称“Go”。围棋起源于中国,春秋战国时代即有记载,隋唐时经朝鲜传入日本,中兴于日本,近现代之后开始在国际上逐渐普及,目前职业围棋水平最高的国家是中国和韩国。

电脑围棋的发展历史

电脑围棋是人工智能(AI)的一个领域,该领域致力于开发出可以下围棋的电脑程序。自古以来,棋类游戏一直被视为顶级人类智力试金石,人工智能(AI)挑战棋类大师的也被看做人工智能发展的里程碑。

电脑围棋软件与人工智能

最早的电脑围棋程序是1968年Albert Lindsey Zobrist开发的,他引入了一个评估函数对棋局进行分析,来估算双方占空的大小,然而,在国际象棋里能够得心应手地杀败世界冠军,放在围棋里却行不通了,在相当长的一段时间里,业界的普遍观点是电脑围棋只能达到业余棋手的水准。

然而,从2006年开始,随着蒙特卡洛树搜索和机器学习在围棋上的应用,电脑围棋水平有了突飞猛进的增长,棋力普遍提升到业余高段的水准。

蒙特卡洛树搜索算法的出现,可以看作是人工智能取得突破性进展的标志:计算机的思考方式,已经有点接近人类的思维方式了。目前使用蒙特卡洛树搜索的围棋对弈软件有疯石围棋(CrazyStone)、银星围棋(SilverStar)、天顶围棋(ZEN)等电脑围棋程序都取得了不错的成绩。

2011年8月欧洲围棋大会,电脑围棋软件ZEN在19路盘上让五子击败日本职业棋手林耕三六段。2012年3月,ZEN被让四子击败了日本超一流棋手武宫正树九段,这是围棋程序首次在让四子的情况下战胜第一流职业选手。2013年,CrazyStone被让四子击败日本石田芳夫九段,2014年,CrazyStone被让四子击败日本依田纪基九段。可见围棋软件进步迅速,至少比起十年前对弈水平已经提高一大截,受让四子优势明显。

2015年10月,同样基于蒙特卡洛树搜索的Google旗下人工智能公司DeepMind开发的AlphaGo,在没有任何让子的情况下,以五战全胜的成绩击败了欧洲围棋冠军:职业围棋二段樊麾,这也是电脑围棋程序首次击败围棋职业棋手。AlphaGo的下一个考验是拥有14个世界冠军头衔的韩国棋手李世石九段,李世石将于2016年3月与AlphaGo进行五番棋对弈。

何为“蒙特卡洛算法”

蒙特卡洛算法或称计算机随机模拟方法,是一种基于“随机数”的计算方法,这一方法源于美国在一战中研制原子弹的“曼哈顿计划”。频率决定概率,围棋对弈软件将最常见的对弈定式及棋形输入其中,从而达到较短时间提高棋力的功效。用通俗的语言解释了这种算法:“简单来说,人脑下围棋靠的是逻辑思维,而蒙特卡洛算法就是一个抽样调查的方法。其实就是一个赌博概率式的方法,如果电脑下100盘棋,用这种下法赢了60盘,用另一种下法只赢了50盘,那么,它就会认定第一种下法,而淘汰另一种下法。”

围棋的人工智能为什么那么难?

在国际象棋界,计算机早已经战胜最顶尖棋手。1997年,IBM的“深蓝”电脑程序在正常时限的比赛中首次击败了当时排名世界第一的棋手卡斯帕罗夫。2006年,人类最后一次打败顶尖的国际象棋AI,众多国际象棋特级大师面对象棋软件一筹莫展,竟没有一次胜绩。

然而,围棋一直被认为是人工智能领域里的非常困难的挑战。当如IBM深蓝那样的超级电脑,已经能够击败世界上最好的国际象棋棋手的同时;围棋软件却始终无法击败世界顶级围棋棋手。

那么,为什么让电脑模拟出围棋的人工智能有那么难呢?

1. 围棋的棋盘

围棋的棋盘很大(19×19),因此通常被认为是难以编写围棋程序的一个重要原因。围棋棋盘上每一点,都有黑,白,空,三种情况,棋盘上共有19*19=361个点,每回合有250种可能,一盘棋可长达150回合。同时,围棋有3^361种局面,而可观测到的宇宙,原子数量才10^80,可能产生的局数呈指数级增长。

相比之下中国象棋9*9,国际象棋8*8,平均每回合只有35种可能,一盘棋有80回合;因此国际象棋和中国象棋AI的算法可以枚举所有可能招法,但这种思路却无法应用在围棋上。

2. 下棋的规则和估值函数

国际象棋和中国象棋每个棋子的价值都有所不同,棋子的走动必须遵守一定的规则,例如国际象棋,开局的时候可以动8个兵(*2)和两个马(*2)共20种招法,虽然开局到中期招法会多一点,但是总数也就是几十种。中国象棋也是一样,开局5个兵+炮(12)+士相*2+马*4+车*2*3+将帅共28种,跟国际象棋差不多。但围棋的下子没有限制,开局有361种选择,所有着法都有可能。

象棋游戏判断局面也简单,将军的加分,攻击强子加分,被将军或者有强子被攻击减分,控制范围大的加分,国际象棋里即将升变的兵加分,中国象棋里接近底线的兵减分,粗略一算就可以有个相对不错的判断。

在下棋的过程中,象棋的棋子数逐渐减少,使游戏逐渐简化。但是,围棋却是棋子数逐渐增多,每下一子,都会使局势变得更复杂。

在胜负方面,囯际象棋目标明确,只要杀死国王即可。

因此,国际象棋和中国象棋都可以有一个较为简单的估值函数,使得高水平象棋AI的软件易于开发。

反观围棋,却缺少这种简单的估值函数,围棋的每个棋子的价值都是可变的,没有王和帅这样的攻击目标,每颗棋子一会是棋筋,一会又是废子,电脑难以实现“估值”。

在胜负方面,围棋的胜负不是要杀对方棋子,而是占更多的地,每一步有数百种以上的走法,算法的

相关文章

  • 验证码: 看不清?点击更换 看不清? 点击更换
  • 意见反馈
    意见反馈
    返回顶部