位置:首页 > 商学院 >

蒙特卡洛算法与电脑围棋

作者:四川新闻 | 发布时间:2018-11-19 15

  作者:黄铂钧(微软亚洲研究院),本文转自《科学世界》

  你喜欢下棋吗?有没有和计算机下过?现在,弈棋计算机的棋艺日益高强。让我们通过分析以围棋和国际象棋为代表的弈棋计算机,对人工智能的研究有一个更为深入的理解。

  弈棋计算机

  弈棋自古被视为一种关乎智力的高级挑战。和其他智力测试相比,弈棋具有直接对抗的特点,没有什么比在紧张的对局中看到对手一手精妙凶狠的棋招更 能让人感觉到一种智力上的刺激和挑战了。弈棋相比于其他牌类游戏而言,随机和不可控因素更小,因此对局双方的决策能够更直接地控制整个局面的走势,这进一步增强了智力的对抗性。

  毫不意外,在国际象棋更加流行的西方国家,人工智能领域自创建之初就在考虑如何制造一个会下国际象棋的机器。几乎所有人工智能先驱,包括信息论 创始人香农、“人工智能”之父约翰·麦卡锡(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年内超级计算机将能挑战世界冠军级别的人类棋手。