Author Topic: 人机对话  (Read 13257 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
人机对话
« on: 三月 29, 2008, 10:37:28 am »
人机对话

“人战胜了机器”,这是本周美国围棋协会电子杂志的一个小标题。说是一个职业五段
在九乘九的棋盘上以二比一战胜围棋程序MOGO。读到这里,稍微有一点围棋程序常
识的人或许会问,有没有搞错?这说的是围棋程序吗?最好的围棋程序不是都要被让十
几子的吗?不会是国际象棋或五子棋吧?或者又是墨绿那样的虚幻东西。千真万确,这
是实实在在的围棋程序,不是只存在于虚幻世界里的墨绿。

说到墨绿,就必需要提到深蓝甚或它的前辈,浅蓝或者淡黄。我们还是从头说起。

让计算机下棋一直都是人工智能的一个重要课题之一。先是从简单的跳棋,五子棋之类
的搞起,后来搞国际象棋,围棋。虽说这些程序属于人工智能范畴,但实际上它们并没
有多少“智”的部分,主要部分都是在可行范围内搜索。各种研究也大都是怎样使搜索
更快更有效。它们缺乏“智”的部分的根本原因是我们自已就不是太清楚人类以怎样的
形式思考。比如你写一个名字问一个计算机系主任,这人是不是他系里的教授。系主任
马上就可以回答是或不是。如果你问计算机,计算机也可以马上正确地回答是或不是。
但计算机的方式是把这个名字与系统里所有名字比较以后得出的答案。计算机搜索很快,
全走一遍几乎可以瞬间完成。但我们知道系主任是不可能在短时间内把系里所有教授的
名单过一遍的。类似的问题还可以更进一步,如果有人拿一张照片问你这辈子有没有见
过这个人。一般情况下,你会很快告诉他有或没有。可是我们不能想象你在短时间内把
你这辈子(包括孩提时代)见过的人都检查一遍。那么你是怎样得出结论的呢?我们对
此还不是完全清楚。

懂计算机算法的人会说,计算机也不用把全部名单走一遍。它可以搞一种映射,拿到名
字后直接到映射位置找这个人(所谓Hash Table)。或者把东西分类按类别排除,几下
就找到相应的位置(比如K-D Tree)。或者在各种目标间加上大大小小的联接,然后按
联接排序。诸如此类的聪明方法都是人类在不懂得自已怎样思维的情况下设计出来的,
试图达到人类的思维效果。这些方法有用也很有效,在很多方面都有应用。但当要搜
索的空间实在太大(做表已经行不通)时,这些方法就不灵了,速度不够,内存也跟
不上。

人的大脑当然也不能存下这些大空间的东西。但人的大脑有一个很大的优点,那就是
“模式识别”(Pattern Recognition),不需要用到大搜索空间。前面的例子说明一个
人看见一张照片,几乎马上就可以知道他以前有没有见过这个人,不需要把他从前见过
的人都过一遍。再举一个真实的例子。在去年我参加的一个中国人的新年晚会上,有人
用黑管吹出[大海航行靠舵手]的曲子。虽然几十年没有听过这个曲子了,但下面的几
乎所有人都马上跟着哼起来。大家不需要在大脑里把以前听过的所有曲子过一遍来检索
到这个曲子。你或许要说这些东西大脑里都存着,只不过它有很快的方法搜到那里。这
“很快的方法”就是我们想要知道的。但我说的“模式识别”还不只是这些。再举一个
没有事先储存的例子。比如你去一个你常去的网站,打开网站后出现一整页的标题或文
章(以前从来没见过)。如果里面有任何地方提到你的名字(或ID),你几乎马上就
会注意到,并不需要你去一个字一个字地读整页内容。这种“模式识别”能力计算机
(或者说现在的人工智能)是没有的。所以,遇到大空间搜索问题计算机就显得很弱。

再回到下棋的问题。下棋的时候棋盘上可走的地方很多,但下棋的人并不是每种走法都
去考虑。比如一般情况下就不会有人去考虑在死角位置上走一子会有什么结果。那么哪
些位置需要考虑,哪些位置不需要考虑,这就是“模式识别”问题。计算机没有这种功
能,只好所有的位置都考虑,于是就产生了无穷大的搜索空间问题。几十年以前的国际
象棋程序就处于这种情况。因为大面积搜索不可行,就只能用一些自已设计的判别模式
进行选择性地搜索(模仿人的思维)。选择不见得对,搜索又不彻底,结果当然不会好
到哪里去。所幸的是,计算机领域里有一个莫尔规律(Moore's Law),说是计算机的速
度(以及别的相关能力)每一年半就会翻倍。几十倍上百倍地翻下去,以前速度和空间
不可行的搜索后来就变得可及或可行了。到了一九九七年,IBM的深蓝就硬是用“硬
搜索”(Brute Force)打败了人类国际象棋最高手Kasparov。当然深蓝还请了一些国际
象棋专家指点判别程序,但主要靠的还是硬搜索。

讲围棋怎么扯到国际象棋去了?我们现在就回头来讲围棋。

深蓝的方法可不可以平移到围棋上来?一般的共识是不可以。这里面有两个问题。

第一个是搜索空间。围棋的变化空间比国际象棋大很多数量级。有人估计围棋的变化空
间是10的170次方,相应的国际象棋变化空间是10的120次方,差别是10的
50次方。古人在形容很大的数的时候常用的一个词是“恒河沙数”,因为沙是他们知
道的最小的东西,而恒河是它们知道的最大的河。按《孙子算经》大数单位算,恒河沙
数等于10的52次方。这是受佛经影响的抽象单位,实际恒河沙数没有那么大。按物
理学家卡尔·萨根估计,地球上所有沙滩上的沙粒数目可能是10的20次方。就算恒河占
其中十分之一,也就是10的19次方。大至算一下,如果恒河中的每一颗沙都是一条恒河,
把这10的19次方条恒河组合成一条大恒河。这大恒河的沙数是10的38次方。围棋复杂
度与国际象棋复杂度的比例就是这大恒河与其中一颗沙的比例再乘上一万亿倍。10的
170次方可以与什么来比呢?现代人知道原子当然比沙要小很多,最大的东西也不能
大于可观测到的宇宙。有人算过,可观测到的宇宙中的原子个数大约是10的80次方。
假设每个原子就是一个宇宙,把这些所有宇宙中的原子个数加起来仍然不够10的170
方。有了这些背景,从现实意义来说,我们完全可以把围棋的变化空间10的170次
方当成无穷大,可望而不可及。当然,围棋程序并不需要搜索到底,只需要搜索到人类
下棋时搜索的深度就可以了。

如果要让一个围棋程序达到与深蓝同样深度的搜索,对计算机速度的要求是一百万倍以
上。这不是一两个莫尔规律可以解决的问题。

第二个问题,也是更严重的问题,就是判别好坏的问题。国际象棋的好坏可以有比较明
显的判别方法,比如吃掉对方的皇后基本上应该算是好棋。事实上深蓝的判别更简单,
搜索到几十步以后数子。如果某种走法剩的子数多,这种走法就算好(子数当然是加权
过的,比如皇后算九个兵之类的)。可是围棋没有很好的优劣判别方法。一个子的好坏
或许要到几十步以后才显示出来,或者与盘上十几格以外的子有关(比如征子的情况)。
而且吃子也不见得就一定是好事。

搜索空间大和判别优劣难这两个问题加起来,几乎就完全否定了深蓝的方法在围棋上的
应用。

由于意识到“硬搜索”在围棋上行不通,几乎所有围棋程序设计者都选择走“人工智能”
的路。也就是模仿人类的思维,搞模型识别,算死活,背定式等等。由于没能真正搞清
楚人类的思维方法,这些模仿都不是很成功。这些方法产生的最佳程序仍然处于很初等
的阶段,以至于我这样的一般围棋爱好者左手让它九子也没有问题。很多人甚至认为有
生之年看不到战胜人类最高手的围棋程序了。比如台湾的应昌期先生就没能在他的有生
之年看到哪怕是战胜业余初段的围棋程序,他放出的一百万美元大奖至今也没人能领。

在大家对围棋程序的前途悲观失望的时候,深蓝的主要创造者许峰雄放出话来:十年之
内可以看到战胜人类最高手的围棋程序。他的观点半年前发表在IEEE的杂志上。如
果是别人放出这种话,我一定把它当成痴人说梦,不去理会。但许峰雄不是一般人,他
腰下插着深蓝的金牌,说话还是有份量的。他的文章至少值得一读。

许峰雄说大家现在对“硬搜索”在围棋程序上不抱希望,就象几十年前大家对国际象棋
程序一样。纯“人工智能”的路现在看来效果不是很好,而“硬搜索”却有很大潜力。
我们都清楚,只要搜的足够深,“硬搜索”产生出来的程序是可以很强大的,不信可以
去问一问Kasparov。深蓝的搜索深度是,普遍搜索12层,特殊搜索40层以上。据他
估计,一个围棋程序要达到深蓝的搜索深度必需搜索10的19次方个节点。这看起来
是一个可望而不可及的数,但他认为是可以有办法把它拿下的。他的这个结论主要有四
个支撑点。

第一点,用Alaph-Beta搜索。Alpha-Beta不是什么新东西,计算机科学家很早就发明出
来。其主要思想是,在搜索某个节点时发现如果继续搜下去最好结果也不会好于到现在
为止在别的节点上搜到的最好结果,那就没有必要继续搜下去。比如这一步棋让对方一
大块死棋变活,大概就没有搜下去的必要。这个Alpha-Beta搜索可以把搜索空间缩小到
平方根,也就是从10的19次方到10的9。5次方。

第二点,加入零空间搜索。所谓零空间搜索相当于停走一步。我们看围棋比赛,偶尔会
听见观战者说这个时候即使白棋停走一步,黑棋也没得下,意思是白棋赢多了。零空间
搜索就是这个意思。由于国际象棋的特殊规则(有时停走一步反到有优势),深蓝不能
采用零空间搜索。但围棋完全可以采用零空间搜索。如果停走一步还有很大优势,则这
一路搜索就有很大价值(或者很没有价值,如果停走的是对方的话)。据他说加入零空
间搜索又可以把搜索空间开方。而且这个优势是深蓝没有的。

第三点,重复利用已有知识。比如一块棋活了,就不用老去算它的死活,除非附近有新
情况发生。这个“除非”在国际象棋上出现太多,因为棋盘太小,所以不好用。判断
“除非”所用的时间以及上下传递已知信息所花的时间使它的利用得不偿失。但围棋棋
盘大,很多时候一块棋的死活与别处无关,如果再用特殊硬件加速已知信息的交流,这
个优势在围棋程序上就可以很大。

最后一点又是莫尔规律。他说深蓝过去十年了。现在的新技术几乎可以把与深蓝有同等
能力的计算机放到一个PC上(深蓝用的是480个加有平行结构的超级处理器),再
过十年,速度又可以提高100倍。假如再加上几百个平行结构的联接,则又可以提高
几百倍。

把以上几点加在一起,可以消掉在深蓝搜索范围内围棋与国际象棋的一百万倍的差别。
十年以后我们将会有一个与深蓝有同等能力的围棋程序。如果假设围棋职业棋手与国际
象棋职业棋手搜索的深度一样的话,那么这个程序就可以打败人类最高手。

许峰雄是高手,他的话应该有一定的可信度。他说他的研究生已经开始着手这方面的工
作了。但是他的文章里始终没谈判别好坏问题,而我认为这是一个关键问题。因为没有
搜索到底,始终都存在判断好坏的问题。搜索到12步或者40步以后怎样决定结果的
好坏。四五十步棋的时候中盘或许刚开始,怎样判断什么是好什么是坏。这个问题大概
得输入一些专家知识。相当于当初深蓝让国际象棋大师作顾问。许峰雄现在在中国,找
专家当然不是什么难事。

对这个没搜索到底的问题有疑虑的人还不少。象我这样的人只是问一问,另外有些人就
要想法设计四十步以后的判断算法。还有些人更进一步,干脆搜索到底。且慢,你刚才
不是说搜到底是无穷大吗?怎么有人可以搜索到底。这又要扯到人工智能的另一个方法:
模拟。

围棋是完全信息游戏。不象桥牌或Poker,总有未知因素。桥牌要考虑牌形分布,大牌的
位置等等。Poker的未知因素就更明显,虽说手上的2,7是最烂的牌,但如果Flop出来
7,7,2,你的牌马上就变成强牌。围棋没有这个问题,对弈双方可以使用的一切招
术以及结果都没有未知成分。可是,虽说没有未知成分,但因为没有人能够算到底,这
些公开的信息并不是清楚地摆在双方的面前。想得深的就多一些信息,想得浅的就少一
些信息。下棋时对方给你设圈套就是只望你算不到那么深。好象一口井,只有竹杆够长
的人才能打到里面的水。有些问题,比如围棋程序问题,深一点或许不够,希望能深入
到底。可是太多的路径选择又不允许每条路径都走到底。这时候我们就采用一种叫做随
机模拟的方法。其基本思想是,虽然不能每条路都走到底,但选择一些路走到底是可以
的。在每个分岔点我们都随机的选一些岔道走下去。走到底以后看结果。如果某个结点
后随机选的岔道都显示这是一条好路,从概率上来说这是一条好路的可能信就很大。这
种随机模拟的算法在很多方面都有应用,尤其是在物理和工程上。第二次世界大战时美
国的一批造原子弹的物理学家(费米,冯。诺曼等)给这种随机模拟方法取了一个响亮
的名字叫Monte-Carlo。这是欧洲以赌场闻名的一个城市名字。这种算法和赌场都靠大量
的随机结果为其工作原理。

本文最开始说的围棋程序MOGO就是基于这种原里。MO就是Monte-Carlo的前两个字
母,GO就是英文围棋的名字。这个程序不需要背任何定识,做任何模式识别。只是随
机地在棋盘上选许多点,走一步以后再随机的选许多点,一直这样把一盘棋下完,然后
数子。因为一直走到底,胜负已经很清楚,不需要任何判断。如果某个点以后随机选择
的路径以最大胜率结束,这个点就被认为是最有利的点,程序就选这一步。顺便说一句,
MOGO的前辈(第一个在这方面有成就的程序)叫做疯棋(Crazy Go),我觉得这个
名字名副其实,因为它没有任何思想,完全像疯子一样在下棋。但是,这个看似疯狂而
且简单的原理居然弄出惊人的结果。首先是在计算机围棋比赛中战胜了所有其它对手。
在此之前,计算机围棋程序的冠军几乎一直都是陈志行教授写的[手谈]。陈志行教授
自己是围棋高手,又是计算机专家,把自己的许多想法都注入了[手谈],所以,它能
打败同类的其它程序。[手谈]可以说是一个典型的“人工智能”程序。没想到这个“人工
智能”高手遇到这么一个没有任何“智能”成分的傻瓜程序却无能为力。这一方面说明[手谈]
的所谓“人工智能”还有很多缺陷,另一方面也说明MOGO的算法有一定道理。

不光是对计算机程序,这种完全随机的模拟方法对人类也有优良表现。正规的19路棋
盘现在对它们来说还太大,于是从小棋盘开始。中国旅欧职业五段棋手郭娟与MOGO
的前身疯棋在小棋盘上下了很多盘。在7X7的棋盘上,疯棋执白从来不输,执黑也偶
尔能赢。在9X9的棋盘上与郭娟下了14盘,9胜5负。成绩还是很拿得出手的。
MOGO比疯棋又进化了一步,在最近的一次计算机围棋程序比赛上,MOGO与疯棋
的新版疯子(Crazy Stone)进行冠亚军决赛,MOGO大胜。看来MOGO要比疯棋强
很多。所以当另一职业五段2胜一负战胜MOGO时就成了大新闻。

出于好奇,我把MOGO与疯子的决赛棋谱调出来看了一下,同时发现一些可喜和可忧
的部分。可喜的是MOGO似乎能产生有很强的大局观的棋。对方在角上压过来时它居
然会脱先去占大场,而且这个大场不是三路或四路,而是在五路上。只看布局,很有武
宫正树宇宙流的风格。在对杀时还能走出单立这样的好棋。可忧的是它毕竟没有什么智
能,走到后来简直惨不忍睹,或者说愚不可及,比一个刚学棋一天的人都不如。毕竟它
们是一点智力都没有。从这一点上看,这条路还有得一阵走。另外,从小棋盘到大棋盘
进发的问题,还是由莫尔规律来掌握其进度吧。

写到这里,正好看到记者采访聂卫平谈到围棋程序,聂卫平说围棋程序不是还处在随便
一个人都可以让二十多子的水平吗?看来聂卫平需要有人给他更新一下有关围棋程序水
平的认识了。

MOGO与许峰雄的“硬搜索”都是朝非传统人工智能的方向走。如果有朝一日走出一
个没有任何智能却能打败人类最高手的程序,真的是一种悲哀。所以有人在围棋网络上
呼吁程序员们不要继续这种程序,要给人类留一块圣地。我想,挡是挡不住的,呼吁也
没有用。人们在前进的道路上总是要在不同的路径上进行探索。[手谈]是一条路,疯
棋又是一条路,还有别的许多路,我个人认为墨绿是更好的路。不同的路都走一走,才
知道哪条路好。从某种意义上来说,人类的进步不也正是一种Monte-Carlo过程吗?



GO,MOGO! GO,MORE GO。

--万精油--

二零零八年三月二十八日于波士顿西郊

注:有兴趣的读者可以到以下网址读到相关文章:

1。许峰雄:Cracking Go

http://spectrum.ieee.org/oct07/5552

2。MOGO与疯子对局

http://www.grappa.univ-lille3.fr/icga/round.php?tournament=167&round=7&id=2

3。墨绿

http://www.zhipingyou.com/qqsh/index.php?topic=280.0

« Last Edit: 三月 25, 2013, 02:55:25 pm by 万精油 »

tmshih

  • Newbie
  • *
  • Posts: 2
    • Email
Re: 人机对话
« Reply #1 on: 三月 30, 2008, 01:13:16 pm »
 Well written.  I enjoyed reading it very much.  万精油加油!!

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
关于恒河沙数
« Reply #2 on: 四月 02, 2008, 09:57:05 am »
我的文章里关于恒河沙数原来的话是“有好事者粗略地估计了一下,恒河沙数大概是10的52次方(存疑)”。恒河沙数是佛经里的词语。佛经是不限于地球的。我从前的理解,恒河大概应该等同于银河。百度上说恒河沙数大约等于10的52次方。如果恒河等同于银河,那么这个52次方或许可以说得过去。但又有人明确地说恒河是地球上的一条河,位于南亚,那么这个52肯定太大。

后来新语丝上有人指出:"恒河沙”是一个大数记数单位,10^52不是计算出来的。原贴如下:

-----------
《孙子算经》:「凡大数之法,万万曰亿,万亿曰兆,万兆曰京,万京曰垓,万垓曰秭,万秭曰穰,万穰曰沟,万沟曰涧,万涧曰正,万正曰载。」,由小到大依次为一、十、百、千、万、亿、兆、京、垓、秭、穰、沟、涧、正、载、极、恒河沙、阿僧、那由他、不可思议、无量大数,万以下是十进位,万以後则为万进位,即万万为亿,万亿为兆、万京为垓
按这样算,恒河沙=10^52
-----------

所以我把我的文章改成“按《孙子算经》大数单位算,恒河沙数等于10的52次方”。

顺便说一句,按那个大数单位,“载”竟然等于10的44次方。平常说的“千载难逢”竟然等于10的47次方年,比宇宙的历史都长。

--万精油--
« Last Edit: 二月 19, 2013, 12:58:33 pm by 万精油 »

萍踪侠影

  • Newbie
  • *
  • Posts: 19
    • Email
Re: 人机对话
« Reply #3 on: 四月 03, 2008, 07:03:23 am »
Account works fine now. Very interesting article. I'm learning some basic knowledge by reading your article.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
关于围棋的变数
« Reply #4 on: 四月 07, 2008, 01:30:42 pm »
关于围棋的变数

我在[人机对话]里说:“有人估计围棋的变化空间是10的170次方”。有人对此提出疑问。

围棋到底有多少种变化?这个问题本身就说明围棋的复杂性。因为到目前为止没有人能给出
一个标准答案。所谓10的170次方(准确地说是172次方)是一种最简单的估计。棋盘上361
个点(19X19),每个点可以有黑,白,空三种不同的状态。所以总共有3的361次方个状态,
也就是10的172次方。有意思的是,最近看到《梦溪笔谈》的一段摘文:

---------------
《梦溪笔谈》:唐僧一行曾算棋局都数,凡若干局尽之,余尝思之,此固易尔,但数多,非
世间名数可能言之·····大约连书万字四十三,即是局之大数(零中数不与)。
---------------

连书万字四十三是什么概念?一万等于10的4次方,43个一万就是10的172次方。我想沈括用
的就是3的361次方的算法。

有人说这种估计里面有很多不可能的状态(比如没有气的状态),看起来是高估了。其实
不然,这种估计实际上是大大的低估了。因为它没有考虑下棋的次序。同一个状态可以通
过许多种不同的次序达到。如果考虑下棋次序,比较简单的说法是361的阶乘。第一步
有361种选择,第二步有360种选择,等等等等。这还没有考虑倒扑,打劫,倒脱靴
之类的情况。就算以361的阶乘来算,也在七百六十位数以上。有人说考虑到对称性,
前几步没有那么大,就算再少几位数也远远大于10的172次方。

还有人加进倒扑,打劫,倒脱靴之类的情况,估计出上千位数,那才叫真正的离谱。

总结一下:我的[人机对话]用的是最保守的估计。

--万精油--