围棋起源于中国，是最古老的棋类运动之一，我们常说的“琴棋书画”中的“棋”就是指围棋。
围棋盘由19条横线和19条竖线组成，共有19 19＝361个交叉点。此外，也有13 13、9 9的小棋盘。围棋子分为黑白两色，对弈双方各执一种颜色的棋子，轮流将一枚棋子下在交叉点上。终局时，占领(围起)的“地盘”(即其中的交叉点个数)多的一方获胜。
空白的交叉点称为“目”，围到的地盘又称为“空”。对弈过程中，棋手经常会“数目”，也就是计算双方目前所围的“空”的大小，以此判断形势优劣。
对弈双方的水平差距较大时，常会采用让子棋的方式，也就是水平较弱的一方先在棋盘的固定位置放上1～9个子(分别称为让先、让二子、让三子……)，然后双方再轮流落子。
本文转自《科学世界》
你喜欢下棋吗？有没有和计算机下过？现在，弈棋计算机的棋艺日益高强。让我们通过分析以围棋和国际象棋为代表的弈棋计算机，对人工智能的研究有一个更为深入的理解。
弈棋计算机
弈棋自古被视为一种关乎智力的高级挑战。和其他智力测试相比，弈棋具有直接对抗的特点，没有什么比在紧张的对局中看到对手一手精妙凶狠的棋招更能让人感觉到一种智力上的刺激和挑战了。弈棋相比于其他牌类游戏而言，随机和不可控因素更小，因此对局双方的决策能够更直接地控制整个局面的走势，这进一 步增强了智力的对抗性。
毫不意外，在国际象棋更加流行的西方国家，人工智能领域自创建之初就在考虑如何制造一个会下国际象棋的机器。几乎所有人工智能先驱，包括信息论 创始人香农、“人工智能”之父约翰·麦卡锡(John McCarthy)、计算机科学创始人图灵，都曾严肃思考过制造国际象棋机器的问题。20世纪80年代初，贝尔实验室的工程师们(其中包括著名操作系统 Unix的联合创作者肯·汤姆森)开发出历史上第一个具有人类大师级水平的国际象棋机器“Belle”。到80年代末，卡内基梅隆大学的许峰雄博士在 “Bella”的思路基础上(将在后面详细介绍)进一步改进，研制出了第一个特级大师水平的国际象棋机器，取名“深思”(源自《银河系漫游指南》中的超级 计算机)。随后，许博士加入IBM研究院，在那里和其他几个团队成员一起研制出了实力更强的弈棋机器“深蓝”，并最终于1997年的一场历史性的人机大战 中以3.5：2.5的比分战胜了人类国际象棋冠军卡斯帕罗夫(卡斯帕罗夫不但是当时的人类冠军，同时也是人类历史上国际象棋等级分最高的职业选手)。
在围棋更加流行的东方，围棋大师的头衔同样是智力超群的象征。自从计算机在国际象棋上挑战人类成功之后，所有人的目光就聚焦在了围棋这项古老的 东方棋类运动上。然而对计算机来说，围棋似乎是个比国际象棋更“难”的东西。1985年，企业家应昌期先生悬赏一百万美金寻找能够打败人类职业棋手的计算 机，可时至30年后的今日仍然没有一台计算机能够做到。20世纪90年代，以我国陈志行教授开发的“手谈”程序以及著名开源软件组织GNU开发的“GNU Go”程序为代表的“计算机围棋冠军”们，棋力尚且不及人类的业余初段。进入21世纪之后，研究者们开始探索一套被称为“蒙特卡洛树搜索”的全新思路(将 在后面详细介绍)，并终于在2006年在9 9的“小棋盘”上率先产生突破。以法国的MoGo和CrazyStone为代表的新一代围棋程序在9路围棋上 基本已经达到人类职业棋手的水平，甚至曾在公开场合战胜过职业棋手周俊勋九段。另一方面，在真正的19路围棋棋盘上，以日本的ZEN(天顶围棋)和法国的 CrazyStone为代表的一流围棋程序沿着“蒙特卡洛方法”的思路不断改进，在和人类顶尖职业棋手进行的一系列让子棋比赛中屡有佳绩，而近些年人类棋 手能“让”计算机的子数也越来越少。最有趣的是在2013年，计算机程序CrazyStone在受让四子的情况下战胜被称为“人脑计算机”的日本棋手石田 芳夫九段，并被认为已有业余五～六段的水平。
截至目前，尽管计算机在公平的围棋比赛中还不足以直接抗衡人类职业棋手，但相关的研究热度却很高，大家普遍对近期前景持较为乐观的态度。“深蓝 之父”许峰雄博士甚至在2007年10月的一期《IEEE Spectrum》杂志上表示，相信10年内超级计算机将能挑战世界冠军级别的人类棋手。
(框文)【围棋
围棋起源于中国，是最古老的棋类运动之一，我们常说的“琴棋书画”中的“棋”就是指围棋。
(图)【左为唐代《围棋仕女图》绢画，1972年出土于吐鲁番阿斯塔那；右为隋代白釉瓷围棋盘，1959年出土于河南安阳。图/维基百科】
(图)】
计算机下棋的思考模式
现在主流弈棋计算机的基本“思考模式”很简单，就是对当前局面下的每一种合法走法所直接导致的局面进行评估，然后选择“获胜概率”最高的局面所对应的那个走法。也就是说，“准确评估给定局面的胜率”是主流弈棋计算机的核心问题，同时也是主要难点所在。在进一步深入讨论这一核心技术问题之前，我们先在基本思考模式层面简单比较一下计算机棋手与人类棋手的异同。
可以说，计算机的基本策略是所有“人类有可能采用”的策略中最原始最简单的一种。毫无疑问，人类的思考模式中必然也包含“局面评估”的部分，然而人类至少还同时拥有另一个重要的思考模式——战略性思考，也就是把一个基本目标有效分解成一系列“子目标”。
以围棋为例，“获胜”是围棋的最终目的，而胜的定义是“结束比赛时拥有更多棋子和空”(中国规则)。但是人类棋手在对弈时显然并不是每时每刻都在基于这个“胜”的定义进行思考的——通常我们只在棋局进入中后期时才经常性地“数目”。在对弈的大部分时间里我们是在思考诸如“如何借助右上角黑棋的毛病扩张”、“如何做活”、“如何侵消对手的模样”、“如何在劫争中转换”、“如何分断”等等一系列具体问题。我们注意到，每一个这样的“具体问题”实际上是改变了思考的目标，把一个“求胜”的问题转化成了一系列“分断”或者“做活”之类的子问题。这样的一个“战略计划”，其背后的逻辑当然是，我们的大脑相信在当前情况下“分断对手大龙”是最有可能导致最终赢棋的子目标。一旦确立了子目标，人类棋手便集中精力考虑具体战术走法来完成这个子目标，而不是“赢棋”这个最终目标。与之不同的是，目前主流的弈棋计算机从基本思考模式上并不依赖于“生成并确定子目标”的战略能力。在大多数时刻，这些弈棋计算机只关心一个问题，就是按照“胜”的基本定义来赢得比赛////1。“在当前局面下，我走在x点的话最终能赢几子”，计算机就是通过不停地重复问自己这个问题来完成对弈的。尽管这听起来很“原始”，但正如前面所说，这样思考的计算机却已经在很多棋类中达到了相当令人惊讶的水平！
现在我们回到“评估局面胜率”这一计算机弈棋的核心问题上。主流方法中一次局面评估通常由被称为“静态评估”和“动态评估”的两个部分协同配合完成。
基于“特征识别”的静态评估
黑方影响的区域 | 白方影响的区域
对围棋局面基于“粒子-场”模型的静态评估结果
局面静态评估好比人类棋手的“感觉”(也叫“第一感”、“棋感”)。
目前使用的方法很容易理解。就像网上经常遇到的性格测试：让一个人做10道选择题，每道题如果选A加1分，选B不加分，然后根据10道题的总分对这个人的性格进行分类，0～2分的是黏液质性格，8～10分的是多血质性格…… 国际象棋的局面静态评估过程和性格测试非常类似，对于一个给定的局面(对应性格测试里的一个人)，评估算法问“当前局面里我方有没有皇后”，有的话加10分，没有不加分；再问“有没有兵”，有的话每个兵加1分，没有不加分……然后评估算法把所有问题的总分加起来，总分越高代表该局面胜率越大。
我们看到，计算机对国际象棋局面的静态评估过程相当于给局面做了一次测试卷，其中每一道测试题对应了局面的一个特征。一般来说，优秀的国际象棋计算机所使用的“测试卷”中的每一道题都是由人类大师根据自己多年的弈棋经验精心设计的，而里面每道题的“分值”或者由象棋大师直接设定，或者由计算机根据海量棋谱通过被称为“机器学习”的技术自行决定。
前一种方法往往面临的一个问题是，人类大师其实根本就不用这种“给局面做测试卷”的方式思考，所以他们的经验有时很难直接指导分值设定。而在后一种基于机器学习技术的做法下，象棋大师除了设计用于评估局面的“考题”(每道题分值待定)之外，“只”需要对用于“训练”计算机的棋谱中出现的每一个局面打一个“局面总分”(这个总分并不基于大师为计算机设计的任何“考题”，而是直接根据自己的经验得出)，计算机就可以自动为每道考题选择一个合适的分值，使得当我们使用如此学习出来的分值去考察棋谱中的每个局面时，由“考卷”累加得到的分数都恰好比较接近象棋大师根据经验为该局面评估的分数！
围棋计算机程序使用的静态评估过程一般也基于类似的“打分原理”。只不过围棋里面棋子的“位置特征”比“数量特征”更重要，所以围棋程序在选取特征时往往并不基于单个棋子，而是基于由若干子组成的“基本形状”。更重要的区别是，围棋局面评估并不仅仅是把来自每个特征的得分简单相加，而是基于一些更复杂有趣的综合过程。
比如，在这方面有一类很有意思的研究叫做“基于动态系统的围棋局面评估”。这种观点把围棋棋盘看作一个二维“静力场”，里面每一个棋子或每一个基本形状拥有一个类似于“电荷”的属性，并根据这个属性向外辐射“影响力”，强度随着距离递减。这样，对于给定局面，棋盘中的每一个点都具有一个“场强”，它根据来自棋盘上所有黑子和白子的影响力相互叠加和抵消后决定。所有点的场强可以通过多轮迭代计算得出(类似于物理中求解“多体问题”的过程)，根据这些场强我们就可以决定对于棋盘中每一个点，黑白哪一方“势力”更大。
从某种意义上讲，基于动态系统的围棋局面评估实际就是在试图建立一套“围棋世界里的物理定律”，使得依据这些定律做出的判断符合顶级高手间的实战经验，或甚至是符合“完美走法”下的结果。当然，目前的“粒子-场”模型可能更多只是对我们所熟知的经典力学模型的简单模仿，也许我们应该基于一套完全不同的理论来描述围棋棋盘里的天地(比如基于概率模型)，又或许从原则上根本不存在能够精确描述局面走势的“围棋定律”…… 无论如何，对围棋局面静态评估的研究一旦产生突破，很有可能使得人类对围棋这项古老棋类运动本身产生更深刻的理解，同时也会极大地改变围棋弈棋计算机研究的现状。
截至目前，对围棋局面的静态评估效果还远远比不上国际象棋，一般只对处于棋局初期的局面有一定作用，而对当棋局进入激烈厮杀后的中后盘，尚未找到有效的静态评估方法。下面马上就要提到，正是由于静态评估部分的缺陷，直接导致了围棋程序在“局面动态评估”部分采用了一套与国际象棋程序差异很大的策略。
另外值得注意的是，在上述局面静态评估的构建过程中，机器作为一个“智能个体”，最多参与到特征的“权重”设定，而对于更重要的“应该使用什么样的特征”以及“根据什么方式对所有特征进行整合”的问题则完全由人类专家负责。可以说，“特征自动提取”一直是机器学习这个人工智能分支多年来的主要挑战之一。后面还会再次提到这个问题。
基于“预测分析”的动态评估
如果说对棋局盘面的静态评估好比人类棋手的“感觉”过程，那么动态评估就好比人类棋手的“推理”过程。在静态评估中机器得益于人类专家的很多帮助，而动态评估的部分可是机器大显身手的地方了。
简单讲，“动态评估”试图对从当前盘面出发“有可能”出现的大量局面变化所导致的结果进行预判，并综合分析所有这些可能性，对当前盘面进行一次评估。这也是人类在动态环境中做决策时经常使用的策略，也就是希望通过“看得更远”来提前发觉潜在的危险或机会。
经过高度优化的弈棋计算机每秒钟可以计算数以亿计的变化，即使是运行在普通个人电脑上的弈棋程序也经常可以做到每秒计算几十万种变化，这种高速运算能力极大地弥补了计算机在静态评估时的不足。对于像国际象棋和围棋这种历史悠久的复杂棋类运动，只基于静态评估的计算机程序通常连入门级业余棋手都未必下得过，而一旦配备了动态评估能力之后，弈棋计算机却能达到普通棋手甚至人类世界冠军都无法达到的水平。
盘面动态评估可以说是计算机弈棋领域的研究重点所在，几十年来人工智能研究者和计算机科学研究者提出了许许多多的方法。这里我们简单介绍一些共通的基本原理，以及围棋和国际象棋这两个最受关注的棋类的主流动态评估方法。
基于一套给定规则，任意给定的棋局盘面会有一个“合法走法”的集合，其中每个走法都会把棋局引向一个新盘面，而这个新盘面又会有自己的另一个合法走法集合，每个走法又对应一个新的盘面。如果假设每个盘面都有 种合法走法，那么从当前盘面走一步之后一共有b种可能“到达”的盘面，两步之后有b^2种可能盘面，三步之后有b^3种可能……如此展开下去，从最初的给定盘面经过d步之后可能到达b^d种不同的盘面，它们就是在“未来d步内所有可能的局面变化”。
我们看到，从给定盘面开始的局势变化的复杂度是随考虑的步数呈指数级增长的。对于包括围棋和国际象棋的绝大多数复杂棋类运动而言，这意味着从原则上 不存在准确 计算盘面的最优结果的有效方法。不过，这对于对局双方来说未必是个坏消息——虽然我无法计算最优解，对手也同样无法计算。事实上一个游戏之所以成为游戏， 恰恰就是因为对局双方都相信对手不具备完美决策的能力，而自己要做的只是比对手 “错得更少一些”。
另一方面，对于弈棋计算机的设计者来说，“不可能对局势变化的所有可能性进行有效计算”意味着想做得比对手更好需要从原理上解决两个关键问题： (1)决定一个“筛选策略”，从所有从当前盘面出发有可能导致的变化中选择一部分作为“我们实际考虑的那些局面变化”；(2)决定一个“汇总策略”，把所 有实际考虑的变化的静态评估结果综合起来，对当前盘面的胜率完成评估。无论是国际象棋、中国象棋、围棋、或者其他如西洋跳棋、黑白棋、五子棋，所有棋类程 序的动态评估方法从根本上都符合由“筛选策略”和“汇总策略”组成的基本框架。它们之间的区别仅在于使用的具体策略不同，以及由此产生的针对实现特定策略 的优化手段的不同。
下面，我们就来看一下在最具代表性的国际象棋和围棋中，弈棋计算机分别使用的两套截然不同的动态评估策略吧。
“指数级增长”与“EXPTIME-Complete问题”
指数级增长可算是大规模计算第一大“拦路虎”了。在一个著名的传说中，国际象棋的发明者印度人塞萨(Sessa)向他的国王请求赏赐，他说，希望因为发明国际象棋棋盘的第一个格而得到一粒米，因为第二个格得到两粒米，因为第三格得到四粒米，如此在每后一个格都增加一倍的米量。不识指数级增长威力的国王欣然答允，甚至还有些责怪塞萨要求太少，然而事后才发现整个国库的米都倒干净了仍然无法填满整个棋盘。故事的结局是，国王恼羞之下偷偷派人把塞萨杀掉了。学过等比数列的现代人按一按计算器就知道，国王因为这64个棋盘格子总共要支出2^64-1=18446744073709551615>10^19粒米，这据估计已经超出整个人类历史上产米量的总和！
回到局势变化的复杂度问题上。即使10^19这样的天文数字也“只不过”是一个从当前盘面出发，每次只考虑2种走法，持续64步之后的可能性空间的大小。对于国际象棋和围棋这样的复杂棋类，从初始盘面出发穷尽所有变化的复杂度(也称穷举复杂度)更是大得难以想象。信息论创始人克劳德香农在1950年第一个估计出国际象棋的穷举复杂度大概在10^120种变化左右，具体数字被后人称为“香农数”。而围棋的穷举复杂度又远远超出国际象棋，达到了惊人的10^360。作为比较，目前可观测宇宙中的原子总数据估计“只有”10^75个。
有人会问，为了分析当前盘面一定要穷举所有未来走势的可能性吗？有没有可能存在一个高效的算法可以在避免遍历呈指数级增长的可能性空间的同时仍然对当前盘面做出准确评估呢？答案是，对于国际象棋和围棋，我们可以从数学上证明，不仅仅是穷举复杂度，其局势变化的计算复杂度也必须随所考虑的步数呈指数级增长！对于任意一个给定的盘面，我们定义这个盘面的“最优值”为当博弈双方都下出“完美走法”的情况下导致的最终博弈结果。如果一个盘面的最优值是“黑棋胜”，那就是说在黑棋自己不出错的情况下白棋无论如何努力都是必败的。理论计算机科学家先后在1981年和1983年证明国际象棋和围棋都属于EXPTIME-Complete类问题，这意味着“任何”能正确计算盘面最优值的方法所花费的时间“必然”随棋盘大小(亦或棋局的平均步数)呈指数级增长。事实上大部分流行的“双人零和”棋类的计算复杂度都是指数级的。有一些棋类如西洋跳棋、五子棋，它们的规模足够小，所以其初始盘面的最优值已经被计算出来了。但是像国际象棋和围棋这样的复杂棋类，计算其初始盘面的最优值，以现在的硬件计算能力看来还遥遥无期。
局面动态评估：“激进”与“保守”之间的平衡取舍
主流的国际象棋程序往往采用一种比较“保守”的局势筛选策略，搭配一种比较“激进”的信息汇总策略。而主流的围棋程序则正好相反，在局势筛选方面相当“大胆”，却对从这些局势变化收集来的信息的使用相当“谨慎”。这主要是由于目前对这两种棋类的盘面静态评估的质量不同导致的。
对于国际象棋，已经找到了一种在“很多情况”下可以既快速又相对准确地对盘面进行静态评估的方法——当遇到这类“大致可以进行静态评估”的盘面时，这个静态评估方法有相当的可信度，而对于其他情况的盘面却完全不起作用。由于拥有这样一个具有“部分可靠性”的静态评估，国际象棋程序的策略“从概念上”可以理解为是对从当前盘面出发的每一种可能的变化都不停向前展开，直到遇到一个可以大致静态评估的盘面或者超出了一个预定的“最大展开步数”为止。这样的“保守”选择策略使得计算机对于一定阶段之内的所有变化都有了大致评估。接下来计算机在“假设”这些评估是正确的前提下，计算按照完美下法哪一种变化是最优的。
根据硬件计算能力，计算机还会设定一个“最小展开步数”，即使一个变化在展开不到最小步数时就遇到了一个“比较好评估的局面”，系统依然会继续往前看，而不会就此停止。这是为了最大限度地弥补“对比较好评估的局面进行静态评估时依然有可能出错”的缺陷。在开发第一个人类大师级水平的计算机“Belle”的过程中，人们发现弈棋计算机的最小展开步数越大，其棋力越强。也就是说，原则上只要通过不断增强硬件的计算能力，国际象棋机器就可以通过看得越来越深而下得越来越好。
1997年的“深蓝”计算机在配备了400多块专门设计的硬件加速卡之后，获得了每秒钟展开并评估2亿次盘面的恐怖计算能力，历史上第一次代表机器战胜了人类国际象棋冠军。在随后的十几年里，按照“摩尔定律”增长的计算机硬件能力变得愈加强大，计算机又先后多次战胜人类国际象棋冠军。越来越多的人相信，机器在国际象棋领域早已超越了人类的弈棋能力。
然而，计算机能够战胜人类国际象棋冠军并不全靠超强的硬件计算能力，软件算法方面的持续改进同样必不可少，甚至影响更大。
比如上面提到，国际象棋系统在“概念上”穷尽了一定步数之内的所有变化。但在真实的弈棋计算机中，一系列优化算法使得系统在不完全展开某些变化的同时也能够得到和完全展开一样(或类似)的效果。这样节省下来的时间可以用于把已知变化“看得更深”，从而极大提高了系统在“概念上”的等效计算能力。
其中最经典的例子是由人工智能先驱约翰·麦卡锡提出的////剪枝法，它巧妙利用了“国际象棋是双人零和游戏”的特点，以最优的方式避免所有不必要的变化展开。
零和游戏
又称零和博弈(Zero-Sum Game)，是博弈论中的一个概念，指游戏(博弈)双方是竞争而不是合作关系，或者说是一种“你死我活”的状态。例如两人对弈，一方赢，另一方必然是输，不存在“双赢”。赢棋得1分，输棋减1分，两人得分之和就总是0，所以称为零和游戏。
