电脑是如何下棋的
围棋起源于中国，是最古老的棋类运动之一，我们常说的“琴棋书画”中的“棋”就是指围棋。喜欢下棋吗?有没有和计算机下过?现在，弈棋计算机的棋艺日益高强。让我们通过分析以围棋和国际象棋为代表的弈棋计算机，对人工智能的研究有一个更为深入的理解。
弈棋计算机
弈棋自古被视为一种关乎智力的高级挑战。和其他智力测试相比，弈棋具有直接对抗的特点，没有什么比在紧张的对局中看到对手一手精妙凶狠的棋招更能让人感觉到一种智力上的刺激和挑战了。弈棋相比于其他牌类游戏而言，随机和不可控因素更小，因此对局双方的决策能够更直接地控制整个局面的走势，这进一步增强了智力的对抗性。
毫不意外，在国际象棋更加流行的西方国家，人工智能领域自创建之初就在考虑如何制造一个会下国际象棋的机器。几乎所有人工智能先驱，包括信息论创始人香农、“人工智能”之父约翰·麦卡锡(JohnMcCarthy)、计算机科学创始人图灵，都曾严肃思考过制造国际象棋机器的问题。20世纪80年代初，贝尔实验室的工程师们(其中包括著名操作系统Unix的联合创作者肯·汤姆森)开发出历史上第一个具有人类大师级水平的国际象棋机器“Belle”。到80年代末，卡内基梅隆大学的许峰雄博士在“Bella”的思路基础上(将在后面详细介绍)进一步改进，研制出了第一个特级大师水平的国际象棋机器，取名“深思”(源自《银河系漫游指南》中的超级计算机)。随后许博士加入IBM研究院，在那里和其他几个团队成员一起研制出了实力更强的弈棋机器“深蓝”，并最终于1997年的一场历史性的人机大战中以3.5：2.5的比分战胜了人类国际象棋冠军卡斯帕罗夫(卡斯帕罗夫不但是当时的人类冠军，同时也是人类历史上国际象棋等级分最高的职业选手)。
在围棋更加流行的东方，围棋大师的头衔同样是智力超群的象征。自从计算机在国际象棋上挑战人类成功之后，所有人的目光就聚焦在了围棋这项古老的东方棋类运动上。但是对计算机来说围棋似乎是个比国际象棋更“难”的东西。1985年，企业家应昌期先生悬赏一百万美金寻找能够打败人类职业棋手的计算机，可时至30年后的今日仍然没有一台计算机能够做到。20世纪90年代，以我国陈志行教授开发的“手谈”程序以及著名开源软件组织GNU开发的“GNUGo”程序为代表的“计算机围棋冠军”们，棋力尚且不及人类的业余初段。进入21世纪之后，研究者们开始探索一套被称为“蒙特卡洛树搜索”的全新思路(将在后面详细介绍)，并终于在2006年在9×9的“小棋盘”上率先产生突破。以法国的MoGo和CrazyStone为代表的新一代围棋程序在9路围棋上基本已经达到人类职业棋手的水平，甚至曾在公开场合战胜过职业棋手周俊勋九段。另一方面在真正的19路围棋棋盘上，以日本的ZEN(天顶围棋)和法国的CrazyStone为代表的一流围棋程序沿着“蒙特卡洛方法”的思路不断改进，在和人类顶尖职业棋手进行的一系列让子棋比赛中屡有佳绩，而近些年人类棋手能“让”计算机的子数也越来越少。最有趣的是在2013年，计算机程序CrazyStone在受让四子的情况下战胜被称为“人脑计算机”的日本棋手石田芳夫九段，并被认为已有业余五～六段的水平。
截至目前，尽管计算机在公平的`围棋比赛中还不足以直接抗衡人类职业棋手，但相关的研究热度却很高，大家普遍对近期前景持较为乐观的态度。“深蓝之父”许峰雄博士甚至在2007年10月的一期《IEEESpectrum》杂志上表示，相信10年内超级计算机将能挑战世界冠军级别的人类棋手。
计算机下棋的思考模式
现在主流弈棋计算机的基本“思考模式”很简单，就是对当前局面下的每一种合法走法所直接导致的局面进行评估，然后选择“获胜概率”最高的局面所对应的那个走法。也就是说“准确评估给定局面的胜率”是主流弈棋计算机的核心问题，同时也是主要难点所在。在进一步深入讨论这一核心技术问题之前，我们先在基本思考模式层面简单比较一下计算机棋手与人类棋手的异同。
可以说，计算机的基本策略是所有“人类有可能采用”的策略中最原始最简单的一种。毫无疑问人类的思考模式中必然也包含“局面评估”的部分，但是人类至少还同时拥有另一个重要的思考模式——战略性思考，也就是把一个基本目标有效分解成一系列“子目标”。
以围棋为例，“获胜”是围棋的最终目的，而胜的定义是“结束比赛时拥有更多棋子和空”(中国规则)。但是人类棋手在对弈时显然并不是每时每刻都在基于这个“胜”的定义进行思考的——通常我们只在棋局进入中后期时才经常性地“数目”。在对弈的大部分时间里我们是在思考诸如“如何借助右上角黑棋的毛病扩张”、“如何做活”、“如何侵消对手的模样”、“如何在劫争中转换”、“如何分断”等等一系列具体问题。我们注意到每一个这样的“具体问题”实际上是改变了思考的目标，把一个“求胜”的问题转化成了一系列“分断”或者“做活”之类的子问题。这样的一个“战略计划”，其背后的逻辑当然是，我们的大脑相信在当前情况下“分断对手大龙”是最有可能导致最终赢棋的子目标。一旦确立了子目标，人类棋手便集中精力考虑具体战术走法来完成这个子目标，而不是“赢棋”这个最终目标。与之不同的是，目前主流的弈棋计算机从基本思考模式上并不依赖于“生成并确定子目标”的战略能力。在大多数时刻，这些弈棋计算机只关心一个问题，就是按照“胜”的基本定义来赢得比赛*1。“在当前局面下，我走在x点的话最终能赢几子”，计算机就是通过不停地重复问自己这个问题来完成对弈的。尽管这听起来很“原始”，但正如前面所说，这样思考的计算机却已经在很多棋类中达到了相当令人惊讶的水平!
