原文地址

译者:摩耶   校对:fwjmath

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

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

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

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

这个游戏是在一块横竖方向上各有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上运行,包括一个免费的9x9版本)

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)

0
为您推荐

54 Responses to “[小红猪]围棋:需要更深的蓝”

  1. 冰兰音说道:

    沙发

  2. pohpih说道:

    能否整合“学习网络”功能,让程序在与高手的对决中不断成长?

    • John说道:

      个人感觉很难
      因为棋局的变化很多
      而围棋程序说到底就是一棵决策树
      如果不断维护,空间上一定吃不消
      而神经网络又无法像其他方案那样可以很好地运用遗传算法
      而且评价一着对棋局的影响(从而进行进化)又是非常困难的

      • Netson说道:

        我觉得也许决策树的思路根本上就不对……

        • Ted说道:

          同意...
          我觉得统计学可能是一个更好的方向

  3. Dong说道:

    最主要的还是美国玩围棋的少吧,计算机牛人不会玩,开发啥程序呢?

    • obi说道:

      勉强算是吧,因为使用的是九路围棋

    • DJ说道:

      没认真看吗..那里面说的是九路围棋,十九路围棋让7手还能赢..

    • wdwshj说道:

      对围棋程序来讲,棋格越少,它就越厉害。

      九格能战胜九段,但十九格时,业余的就都可能战胜不了。

  4. gentboy说道:

    此文甚好

  5. 围棋说道:

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

    这句话是不是有问题啊? 感觉少了半截

    • 摩耶说道:

      喵~反正原文是这样的,应该是没有少的。

      ''If you watch really strong players,'' Dr. Bump said, ''some seem to make fairly mundane moves, but at the end of the game they're ahead. Others do spectacular things.''

      • 白色獠牙说道:

        我感觉这句话不对。

        • 默星存说道:

          others应该不是指其它棋手,而是指其它“步”吧

          • 水木灵说道:

            就是其他棋手全盛时得李昌镐每一手都很普通确将无数天才斩于马下

    • lightson说道:

      这句话没问题,只不过翻译成汉语的时候稍微别扭一点
      原意是:有些棋手会下出俗手(其实可能是旁观者没看懂的好手),但俗手最后被证明是好手;但另一些棋手就是每一手都让人很赞叹。
      但是汉语里一般两层意思的字数要差不多,而英语里就没这个要求,所以看起来别扭。

  6. hbchendl说道:

    可能问题还是在于围棋的数学理论尚未开发出来。

  7. 流浪的鲥说道:

    围棋的规则和盘面都太复杂了。
    开始的定石对于电脑来说还可以靠记忆。
    但是越到后来越复杂,电脑只要算错一点就会输。
    而经验丰富的棋手知道怎样以退为进,放弃一部分去获取全局的胜利。
    FWJ你有没有想过编围棋这种恶心的程序?笑~~~

    • 沐右说道:

      我觉得围棋的规则和棋盘是太简单了,就是数量太大了。
      其实电脑需要考虑的就只是符合规则的可能走法,规则复杂的话,需要考虑的就少很多。
      九乘九的棋盘上计算机赢得九段高手都很正常,因为电脑可以穷举,这点人类做不到。
      但是在大棋盘上,穷举需要的计算能力和存储是目前的技术达不到的,所以电脑程序很难战胜围棋高手。

      • 流浪的鲥说道:

        明白了。
        因为规则少,所以下棋的方法太多,所以运算量太大。
        可是这样的运算量为什么人类会占优势呢?
        一个经过训练的业余高手比计算机究竟厉害在哪里?

        • wrench说道:

          目前来说 人比电脑强的地方就是 模式匹配

      • co说道:

        恩,赞成。感觉人下棋时会懂得抓住重点,而电脑就不便于判断,面对大量的方案数无从下手。象棋的规则很复杂,而且不时有将军、叫杀之类的,每次博弈可行方案数很少

  8. Mike说道:

    总有一天电脑会全面超越人脑

  9. adios说道:

    看Bump玩魔方的时候完全不知道他还有围棋这招~~~

  10. 阿拉伯说道:

    围棋软件成功之时,人工智能诞生之日。

  11. Cielo说道:

    对于计算机来说,九路盘更能体现优势吧˜
    我这种只学了一个学期围棋选修课的人,有时在九路盘也能下赢“手谈”…

    • wdwshj说道:

      想下赢围棋程序很简单,

      因为它不懂变化

  12. 单翼羽说道:

    觉得LZ“尝试电脑围棋”一句说的更精确一点能更好。刚看到以为是说“人机对弈”的意思,点开一开始两个科学家主页的链接都没找到相应程序,后来在HANDTALK里找到却发现只能看电脑自己和自己下(或者是我没读懂网页提示?)。当然,文章主题本来就不是这个,关于“直觉”和“逻辑”读的感觉很有收获。

  13. maxwell‘sdemon说道:

    这难道是“古之戏,算之望”?!

  14. fuzzylogic说道:

    翻译得有点问题。

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

    这里的“布局”不妥,当为“局面”。特指围棋的局面时,还可以说“参考图”。

  15. 阿拉伯说道:

    众所周知,围棋易学、难下,难在对每一手棋的价值判断与衡量上。
    价值判断要与死、活、势、利、甚至与对手心理有关。
    价值衡量是指先后手、取舍、攻守的战略思想权衡,同时对行棋次序,节奏,方向战术综合运用。
    围棋含有许多无形无量的模糊概念,无法量化,只能上升高度,用哲学勉强解释。
    现代的电脑,运算很快,但是由于我们对大脑的研究只在外围初期徘徊,对智能知之甚少,拿围棋来说,开发电脑的人们还找不到好方法,把人类智能用电脑演算,
    最笨的方法是采用穷变法,可是需要我们双向等待,等电脑运算速度更快,等围棋思维破题。

    • 燃玉说道:

      哲学,应该是模糊的一般性原理

      模糊数学在人工智能里面应用很多……

      我在想能否编写一个进化程序来自我学习……

  16. foxlan说道:

    电脑不会或者说还没有完全学会下围棋,是因为我们还没有完全研究透人脑的运作模式和算法,比如说,一个人在你两三米远处向你抛一个棒球过来,你会很轻松的接住它:抛出的力度,空中的抛物线轨迹,合适的拦截时间和地点——你几乎是瞬间完成了整个计算过程。如果要计算机加个机械臂完成这个工作就相当困难了。人脑对抽象图形的判断能力还是相当强大的,电脑要达到人脑的水平还需时日。“天网”想干掉我们必须先学会下围棋。

  17. wdwshj说道:

    “相当困难”是什么意思??
    拦截导弹,是不是一样的道理呢?????????

  18. foxlan说道:

    你觉得拦截导弹很容易?
    据我所知只有极少数国家掌握导弹拦截技术,而且拦截的成功率还不高。
    你无法理解“相当困难”的含义?

    • bababright说道:

      以现在的传感器和马达控制技术,接个棒球什么的还是非常简单的。
      须知密集阵也已经不是什么高科技了,连中国都会造了。

  19. nico说道:

    我猜想wdwshj听到foxlan说电脑加机械臂相当困难时,脑海里出现了“Iron Man”的机器人宠物冲咖啡的情景,或者nike的“跑酷”机器人试鞋子广告的画面....

    一句话,TV看得有点多....

  20. xxx说道:

    纳什的游戏不是围棋,是他自己发明的

  21. rillke说道:

    电脑要代替人吗?

  22. rillke说道:

    电脑要代替人吗?

  23. putmymindsofar说道:

    据我所知,纳什下的是他自己发明的一种棋。并不是围棋!所以看了第一段我就没看了。请作者考证一下。

  24. haithink说道:

    以后研究人工智能

  25. kisswind说道:

    总觉得围棋能用一种数学逼近一个最优解,这种数学可能还没有出现。有本关于围棋的书叫MathematicGo, 就是想用数学的方法解决,但目前看还行不通。

  26. mark说道:

    其实目前开发围棋软件游戏的编程设计人员的大脑比现在的游戏软件还不如,因为他们的设计方向就错了,软件就好比牛,下棋的过程让他们给设计成上坡,牛再有力气,也架不住这个上坡路长,总会有力不从心的时候,这也就是为什么下九路围棋时候电脑能下过人,而下十九格时就不行了。是设计思路有问题,本人有个成熟的设计方法,可以设计出能在十九格战胜人的软件,本人略懂编程,只提供方法,有想攻破此难关的编程人员可以和我联系markmzm2@sina.com。再有,就是按我的方法设计出软件,也不能称得上是人工智能,还差的远,只是有一点点,一点点的影子。

  27. hanaive说道:

    穷举法的思路明显不对,这不叫下棋。
    计算机如果能够下围棋,必须出现革命性的变化,包括软件和硬件。

  28. 山外青山说道:

    关键在于,对复杂形势的正确评估,本质上是模糊的图匹配问题。

  29. ellison说道:

    《围棋的面面观》的设计者福特兰先生现年44岁.
    ——程序叫做many faces of go, 通用的翻译是“多面围棋”。

  30. 农夫说道:

    围棋是东方游戏,欧美人不玩,欧美计算机理论和实践高手很少有知道围棋,开发围棋程序东方人计算机软件只是业余水准,用的也只是欧美人处理国际象棋的软件框架和方法,稍加修剪,自然玩不动。围棋自然很难,但打败局面一复杂就出错的人类还是很简单,只是没人有动力和财力去做。
    石佛仅以后盘少出昏着,就能称雄十年,而围棋后盘纯粹是个计算密集过程。IBM出于公司形象广告效应,会开发国际象棋,如IBM之类公司诞生在东方,围棋软件早出来了,十个石佛和李世石也难敌计算机。

  31. 农夫说道:

    盘少出昏着,就能称雄十年,而围棋后盘纯粹是个计算密集过程。IBM出于公司形象广告效应,会开发国际象棋,如IBM之类公司诞生在

  32. 王海涛说道:

    其实是法则的问题 一个世界体系 能够发展 很重要的考量就是它的法则 举个例子 如果 你是DND 那么即使 你是神灵 也就那样了 但是 如果 你是 日出东方 那就无解了 即使有解 你做的也不是简单的实力压制
    而是 解谜

  33. versugw www.kuaipu.com.cn说道:

    编写出优秀的围棋程序的唯一方法就是让它从自己的错误得到进步