电脑围棋软件与人工智能

　　围棋作为唯一的一种电脑下不赢人的大众棋类，是何原因导致？谷歌的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中成绩最好的是Google DeepMind开发的AlphaGo ，曾在2015年10月，在没有任何让子的情况下以5：0完胜职业围棋二段樊麾。这是人类历史上，围棋AI第一次在公平比赛中战胜职业选手。

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

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

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