财新传媒 财新传媒

阅读:0
听报道

原文发表于科学松鼠会:[小红猪]围棋:需要更深的蓝

小红猪小分队 发表于 2010-08-11 18:26

电影《美丽心灵》稍前部分的一幕中,数学家约翰?纳什坐在普林斯顿大学的一个庭院里,正弯腰对着一个布满了黑和白的鹅卵石状棋子的棋盘思索。他在玩的是个名叫围棋的古老亚洲游戏。约翰先生本人就是因挑战这个游戏失败而开始了对博弈论中的数学的研究,最后获得了诺贝尔奖。

近几年,电脑专家们,尤其是专攻人工智能方面的专家们也感受到了这样的奇妙——包括这种沮丧感。

从前为其它的棋类游戏做电脑程序是相对容易的。就连国际象棋都已经被处理器的计算能力所征服了。五年前,一个名叫“深蓝”的电脑在国际象棋比赛中彻底击败了世界冠军加里?卡斯帕罗夫。这是由于国际象棋虽然复杂,但仍然可以被简化为蛮力计算来处理。

但是围棋不同,表面上看电脑和人类玩家都很容易学会,但实际上这个游戏具有的深度和复杂度使得一个人需要花费好多年才能成为高手。到现在为止,还没有一台电脑能在这方面超越人类的业余棋手。

这个游戏是在一块横竖方向上各有19条等距分布的线组成的网格上玩的。对弈者每次轮流在网格的交叉点上放一个黑色或白色的棋子。目标是用棋子围绕在格点周围来占领并保护领地。

研究围棋的程序员们认为它比国际象棋更能反映人类心灵那难以言喻的一面。对计算机编程,使其能模拟这个过程,这个挑战直插人工智能的核心问题,包括对学习与决策的研究,战略思想,知识表示,模式识别,还有可能是其中最有趣的一个—直觉。

人工智能先驱,斯坦福的名誉教授约翰?麦卡锡博士说:“有时一个优秀的围棋玩家走出一步棋,别的棋手都说这是一步妙着,但却不能解释为什么,甚至连自己怎么知道的都说不清。

科技公司“应用智能”的董事长,电脑设计师丹尼?希利斯博士认为围棋所具有的深度正适合用来做那种在详细了解一个例子的基础上进行的科学研究。他说:“我们要研究的是像遗传学中的果蝇那样具有代表性的东西。国际象棋是研究逻辑的“果蝇”,围棋却是研究直觉的“果蝇”。“

除了直觉外,模式识别也是这个游戏的重要部分。计算机在捣弄数字方面很在行,而人类则是天生就会匹配模式。即使从背后看去,人类也能一眼就认出相识的人。“每本围棋的教材里都写满了对各种各样的布局模式的建议” 麦卡锡博士说。

斯坦福大学的数学教授丹尼尔?邦普博士,利用闲暇时间做了一个叫GNU围棋的程序。“瞄一眼国际象棋的棋局,你就可以知道有没有什么大问题。”他说。但在围棋中的每个判断,都需要棋手学会将他们的模式匹配能力与逻辑,还有多年对弈的经验结合起来。

邦普博士说:“如果你去看高手们的比赛就会发现,有的棋手会走出一些看似很一般的棋,但到了最后却占据领先。而其他的棋手妙着连连。“”

我们可以从计算机围棋程序的性能看出围棋的难度。加州圣何塞的芯片设计师兼程序员大卫?福特兰说,近五年内这方面虽然取得了一定的进步,但却没有大的突破。他设计的“多面围棋”是少有的几个商业围棋游戏程序之一。

福特兰先生设计的这个程序在上个周末打败了14个其它的围棋程序—包括几个来自日本的,成为了加拿大埃德蒙顿一场锦标赛的最后胜利者。可即使是这样的一个程序,大部分水平不错的棋手也能轻易打败它。

围棋的挑战性部分来自处理速度。一个典型的国际象棋程序每秒可以衡量30万个棋盘布局,而“深蓝”的速度甚至是每秒2亿个棋盘布局。但据SmartGo的作者安德斯?基鲁尔夫的说法,大部分围棋程序在中盘的时候每秒只能衡量几十个棋盘布局。)

伦敦的计算机科学家迈克尔?里斯告诉我们,对于国际象棋,平均每人每步棋有25到35种走法。而对于围棋,这个数字达到240之多。所以一个下围棋的计算机要想达到“深蓝”在国际象棋上3秒钟思考的深度需要运行3万年之久。

如果欠缺的只是计算机的处理能力,那么解决方案的到来也只是时间问题,因为计算机的速度已经越来越快。但是面临的困难其实不止这一个。围棋程序不仅无法快速衡量棋盘布局,甚至连计算准确率都无法保证。

虽然如此,计算机围棋的难度越大,它的吸引力也就越大,这鼓励越来越多的程序员去研究人工智能的基础。研究生写出了不少与此相关的论文,世界各地不少的研究人员也向它投入了大量乃至全部的关注。

围棋游戏吸引了各行各业的人们。比如广州的退休化学教授陈志行,他编写的围棋程序《手谈》在电脑围棋领域占据优势数年之长。研究数论的邦普博士,现已50岁的他下围棋已有35年,四年前为了编写围棋软件他还自学了C语言。《围棋的面面观》的设计者福特兰先生现年44岁,已经在电脑围棋领域工作了20年了。他同时还是Ubicom的首席技术官,这是一间位于硅谷的小型半导体公司。

他们全都是非常厉害的棋手。但即使是编写一个较弱的围棋程序,也都需要一位围棋高手的支持。例如,福特兰先生编写过西洋跳棋、黑白棋和国际象棋的程序。它们的算法都非常相似,编写出一个相对比较强的程序并非难事。每个程序都花了他一两年的时间来完成。“但当我开始编写围棋程序时,”他说,“整个过程似乎无穷无尽。

福特兰先生说,在他刚开始玩围棋时,做的这个程序还特别弱。“因为我对这个游戏的了解还不深,所以其实写的很多东西都是不对的。”“

然而即使在他的技术进步之后,将其转化为程序仍然不是件简单的事。“当你观察布局时,意识会以某种方式流动,”邦普博士说,“或许你可以看出10种变化,但你也很难了解你意识深处的活动。即使是高手也很难做到这点。”

“我们认为我们已经很了解人类的基本行动规律了。” 邦普博士说,“早上我们起床,然后做早餐,如果你让一台电脑去做这些,很快你就会发现,对你来说十分简单的事情,对电脑来说却困难得令人惊讶。”

围棋也一样。“当你考虑各种可能性时,你的潜意识就在不断剪去无用的变化,”他说。“我们说不清楚这需要多少意识活动,但对于一个棋盘布局,可能我只需要关注10种变化,而计算机却需要查看成千上万个潜在布局才能得出结论,这个结论甚至可能是错误的。”

编写了Go4++的里斯博士也认同Dr. Bump的看法,Go4++曾经是一次比赛的冠军,上个周末的决赛中又获得了第二名。里斯博士是神经网络的专家。他认为,人类判断围棋局势的能力与辨认图像中物体的能力是类通的。他说以上这两件事对于一台电脑来说都相当难。

正因如此,福特兰先生说:“相比起国际象棋,编写一个强大的围棋程序可以更好地让我们明白如何让电脑像人一样思考。”

把全部时间放在研究围棋上的里斯博士说,他无法想象把时间花在别的事情上。“从根本上讲,这是个有趣而基础的问题,有着合适的难度。”他说:“如果它太容易,肯定早就被解决了。如果它太难,人们又会在沮丧中放弃它。”

福特兰说:“我想,长远来说,编写出优秀的围棋程序的唯一方法就是让它从自己的错误得到进步,这是典型的人工智能,而且现在还没人知道怎么实现。”现在只有一些电脑程序拥有一部分这种学习能力。

例如福特兰先生的程序,它在下棋时会引用一个包含围棋高手对局的数据库,而里斯博士的程序则会使用一个学习系统来判断走法。

里斯博士说他想创造一个可以分析专业选手的棋局并学习的程序。但想实现这个想法需要很多的精力。这会剥夺他改进现有的程序的时间。

看来,想在近期内创造出一个可以打败人类围棋高手的电脑是不可能的了,里斯博士说。“但我们可能可以取得相当的进步,这个问题仍会引起人们的兴趣。”他说:“我想,在以后相当长的一段时间内,它仍会是一个有趣的问题,引起人们的讨论。”

几个电脑围棋程序

如果你想尝试电脑围棋,可以去试试以下程序:

THE MANY FACES OF GO: www.smart-games.com

(只能在Windows上运行,包括一个免费的9×9版本)

GO4++: www.reiss.demon.co.uk/webgo/compgo.htm

(只能在Windows上运行)

HANDTALK: www.yutopian.com/go/

(只能在Windows上运行)

SMARTGO: www.smartgo.com/download.htm

(能在Windows和Macintosh上运行)

GNU GO: www.gnu.org/software/gnugo/gnugo.html

(能在Windows, Linux, 和Mac OS X上运行)

AIGO: www001.upp.so-net.ne.jp/iizuka/#contents-1

(能在Palm OS 3.0或更新版本上运行)

在线游戏

在线围棋游戏服务器:panda-igs.joyjoy.net/English/IGSsgc.html

“无名”围棋服务器:nngs.cosmic.org

照片:此角落处—围棋电脑程序们在加拿大阿尔伯塔省埃德蒙顿市的一场比赛中竞技。没有一个程序能下过一位经验丰富的人类选手。(伊恩杰克逊纽约时报报道)(pg. G1);

新选手—大卫?福特兰(上排中部)和丹尼尔邦普(上排左边)在观看他们设计的程序的比赛。对于邦普博士来说,做这个程序的难点在于分析人类在没有意识参与的情况下作出的决策。(照片由纽约时报伊恩杰克逊拍摄);

在这个针对初学者的棋局中,白棋为了应对黑棋的进攻而选择围绕黑棋并拿走一号黑棋,但之后黑棋很快拿走了对方3颗棋子。(英国围棋协会)(pg. G5)

原文地址

译者:摩耶   校对:fwjmath

话题:



0

推荐

科学松鼠会

科学松鼠会

4011篇文章 5年前更新

什么是科学松鼠会? 我们认为,对于部分人来说,科学就像一枚枚难以开启的坚果,虽味美却不易入口。 我们希望自己能够像松鼠一样,打开科学的坚硬外壳,将有营养的果仁剥出来,让人们能够领略到科学的美妙。 我们试图让科学传播并且流行起来。 这里是科学松鼠会的网站的一个镜像,大家的留言我们可能没办法一一回复,如果您有什么问题,欢迎到科学松鼠会的主站提问:http://songshuhui.net/

文章