青青子衿, 悠悠我心, 但为君故, 沉吟至今
« 数以千计使用百度代码的应用收集并泄露用户个人数据一批违规网络大V账号被关闭 »

电脑围棋软件与人工智能

  围棋作为唯一的一种电脑下不赢人的大众棋类,是何原因导致?谷歌的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的软件易于开发。

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

  在胜负方面,围棋的胜负不是要杀对方棋子,而是占更多的地,每一步有数百种以上的走法,算法的困难度明显要高得多。围棋中的厚势本身并没有目数,但可以直接围空或者通过攻击间接围空,而厚势本身的价值,电脑也不好判定。

  可见,电脑程序之所以能打败国象和象棋特级大师,依靠的是不知疲倦的高速检索能力,每一种开局、每一种防御在计算机强大的运算检索能力面前都不值一提。不过这种机械方法在围棋面前却失去了用武之地。

  电脑难以判断围棋形式,人类就可以轻松判定,虽然人类无法拥有大量数据分析,却有得天独厚的逻辑推理能力,从一手棋到后面十手,乃至几十手,都可以“算”出。在“蒙特卡洛算法”出来之前,一位智力正常的人学习下围棋,用不了几个月就可以击败现在所有的电脑围棋程序。

  围棋AI的未来

  目前围棋AI中成绩最好的是Google DeepMind开发的AlphaGo ,曾在2015年10月,在没有任何让子的情况下以5:0完胜职业围棋二段樊麾。这是人类历史上,围棋AI第一次在公平比赛中战胜职业选手。

  AlphaGo使用蒙特卡洛树搜索算法,借助值网络(value network)与策略网络(policy network)这两种深度神经网络,通过值网络来评估大量选点,并通过策略网络选择落点。AlphaGo最初通过模仿人类玩家,尝试匹配职业棋手的棋局,一旦它达到了一定的熟练程度,它开始和自己对弈大量棋局,使用强化学习进一步改善它。

  神经网络系统是以人类大脑为原型的信息处理模式,可以根据特定的输入产生特定输出,并实现图片识别、语音识别等功能。谷歌做了两个神经网络,一个神经网络用于动态评估——计算对手下一步棋落子的各自可能性,依靠计算机远远超过棋手的计算能力,在某种程度上会占据一定优势。另一个神经网络用于静态评估——评估棋局交战双方总体态势。

  此外,谷歌还输入了海量棋手对弈的棋谱,并让AlphaGo以棋谱的数据为基础进行了几千万局自我对局,充分丰富了数据库,并将预测对手下一步棋落子的准确率提升到57%。

  在下棋的过程中,辅以蒙特卡洛算法——因为围棋的各个棋子很难用数值进行打分量化,也不存在精确描述棋局的“围棋定律”,使得计算机在静态评估方面,单纯的高计算能力未必会强于职业棋手“棋感”之类的抽象思维。通用性的围棋盘面静态评估函数曾经是围棋人工智能的瓶颈,在引入蒙特卡洛算法后则很大程度上解决了这个问题。蒙特卡洛算法构造了一个随机的过程,并对过程采用进行统计评估,从而得出一个最优的解法。

  简单地说,蒙特卡罗算法对计算进行了筛选,对数据库中低胜率的选择直接抛弃,放弃了穷举法中那些大量消耗计算资源,但却没有意义的计算。明确了计算的主攻方向,使其对具有高胜率的选择有更加精确的计算和分析。特别是在选择策略中加入更多和围棋相关的专业知识,使得基于蒙特卡洛树搜索的围棋弈棋系统水平拥有和职业棋手较量的能力。

  2016年3月,AlphaGo将挑战世界冠军李世石九段。或许这一战,能够展示出目前围棋AI到底发展到了什么程度。

  参考文献:https://en.wikipedia.org/wiki/Computer_Go



  除非注明,月光博客文章均为原创,转载请以链接形式标明本文地址

  本文地址:http://www.williamlong.info/archives/4526.html
  • 文章排行:
  • 1.andrewsyb
  •  GOOGLE 的算法挺好的,人类未来在智能机器人,应该有更大的发展。 
  • 2016/2/27 8:56:47   支持(2)反对(0) 回复
  • 2.月光xia漫步
  • 很喜欢你的文章,平常都是使用rss订阅,看到一周没有新文章,等到博客上发现原来是rss订阅没有显示
    想不到这次竟然是沙-发,/呲牙
  • 2016/2/26 18:07:05   支持(1)反对(0) 回复
  • 4.不会飞的猪猪爱读书
  • “go”表示“围棋”,源自围棋的日语“碁”的发音ご
  • 2016/2/26 20:56:42   支持(0)反对(0) 回复

发表评论:

 请勿发送垃圾信息、广告、推广信息或链接,这样的信息将会被直接删除。

订阅博客

  • 订阅我的博客:订阅我的博客
  • 关注新浪微博:关注新浪微博
  • 关注腾讯微博:关注腾讯微博
  • 关注认证空间:关注QQ空间
  • 通过电子邮件订阅
  • 通过QQ邮件订阅

站内搜索

热文排行


月度排行

本站采用创作共用版权协议, 要求署名、非商业用途和相同方式共享. 转载本站内容必须也遵循“署名-非商业用途-相同方式共享”的创作共用协议.
This site is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.