icecold轉的中日圍棋擂台好文真過癮。many thanx. 藏了。
萬教授是俺的老網友,搞純數學的,可一談體育,俺倆對着哈喇子長流。他寫過不少
體育方面好文。俺也存了點,轉來共享:
ZT萬精油: 墨 綠
送交者: dok-knife 於 2004/02/26 11:44:11 [溫柔一刀]
墨 綠
萬精油
墨綠的出現,同時震驚了中日韓三國棋院,一個共同的問題是:墨綠究竟是
誰?
──人民日報體育版2005年9月10日
看着《人民日報》的這篇報道,我心裡充滿了喜悅,自豪和得意。這世界上
除我之外再沒有第二個人知道墨綠的真實身份了。
一.引子
話要喲笤際昵八燈稹S桑桑攏塗蒲行∽檠兄瞥隼吹摹吧罾丁憊氏篤宄?
序,戰勝了當時的世界第一高手卡斯帕洛夫,西方輿論界為之譁然。被西方人作
為第一智力遊戲的國際象棋,人類被機器打成下手,驚呼當然是很自然的。但是,
在一片叫好聲中,紐約時報有一篇報道卻在幽默中表現出冷靜。它說:“我們這
里的大呼小叫,最多讓亞洲人(日本,中國和韓國)伸伸懶腰,不以為然。因為
對他們所玩的遊戲──圍棋──來說,計算機還處在原始時代”。
計算機圍棋程序處在原始時代,並不是因為沒人重視。事實上,相當大的人
力物力投入了圍棋程序的開發。個人的,集體的;有計算機專業人員,也有職業
棋手。最大的投入要數日本,他們的第五代機算機開發的一個重要課題就是圍棋
程序。台灣的億萬富翁應昌期先生生前還為此設了巨額獎金。說是在二十世紀末
如有計算機程序戰勝台灣職業棋手,則可得一百萬美元的獎金。如此種種,目前
的圍棋程序卻仍被冠以“原始時代”的雅號,追究起來其主要原因是圍棋太難。
國際象棋與它的難度相差不是一兩個數量級的問題。
我對圍棋程序的熱衷由來已久。我寫過很多別的遊戲程序,但對自己最喜愛
的圍棋卻一直沒敢寫,因為不知從何下手,想得到的思路別人早已試過了。這個
願望一直懸在那裡,心裡放不下,手上又搞不動。九八年上半年事情開始有了轉
機。由於工作需要,我接觸到一些遺傳編程(GENETIC PROGRAM-
MING)的東西。有一天讀一個樣板程序,突然想到也許可以用同樣的思路來
寫圍棋程序。程序開始的好壞不要緊,關鍵是要有很好的鑑別函數使其能合理地
進化。
二.原始版
照着樣板程序,很快就寫了一個原始程序。它沒有任何高級技術,只懂得提
子規則以及最後的點目。基本的想法是讓它自己與自己下,利用它懂得的這兩點
基本功能來進化出高級技術。這樣做成功的先例是有的。有人用這種想法寫過一
個BACKGAMMON的程序,沒有任何高級技術,完全利用基本規則,在它
自己與自己下完五萬盤以後,進化出一個可以與人類最強手對抗的程序。不幸的
是,同樣的想法不能搬到圍棋上來,因為圍棋的變化實在是太多了。事實很快證
明了這一點。我的原始程序進化來進化去,全是盲目的,看不出一點朝着好的方
向前進的跡象。根本算不上進化,最多只能叫變化。看來完全靠原始程序是不行
的,還得加一些高級一點的概念,比如角上的基本對應以及群體死活(而不是每
顆子的死活)概念。從理論上來說,這些概念都可以從基本規則中推出來。但是,
因為影響進化的因素幾乎都是局部的,像群體死活這類的高級概念很難進化出來,
但這些概念在基礎階段卻尤其重要。
加進這些高級概念以後,情況開始有了一點起色。要死的棋居然知道逃。雖
然明明逃不出去,但從局部來說,能延緩死亡時間就是進步。因為是程序同程序
下,逃不出去的棋有時也居然就給它逃出去了,這又進一步強化了這種愚蠢的下
法。但不管怎樣,相對於先前的盲目變化,這種暫時性的進步也是很可喜的。許
多別的高級概念也似乎有了一些模型。不過,從一些明顯的愚蠢變化中,我也發
現了許多原始程序的問題,並做了相應改動。就這樣程序自己的進化加上我的隨
時改動,半年以後這程序居然有了一點會下棋的樣子。再也沒有自己撞緊氣之類
的明顯錯誤,偶爾竟然會走出枷這樣的概念。這種時候我感到特別的驚喜。估計
照這樣下去,它就會逐漸強大起來。
遺憾的是事情並不按照這種理想的路子走下去。初始時期的快速進步逐漸緩
慢下來。因為總是程序跟程序自己下,沒有外來的影響,基因庫很快就達到局部
穩定狀態。不管再讓它們自己下多少盤,結果總是在原地打轉。而且,通過半年
的進化,中間的一些程序我已經看不懂,也不可以像開始那樣任意加上我的改動。
當然我可以同它下,讓它從我的下法中取得新變化的基因。但這種辦法是幾乎不
可以想象的慢,因為進化的過程需要很多很多盤才可以實現,而我是不可能一天
二十四小時都陪它下棋的。而且我也不會摹仿壞棋,我的棋下出去都是這程序不
可以接受的跳躍。於是這程序就這樣死在那裡。
由於我的心思完全套死在這個程序上,一個明顯的出路放在那裡我竟然一直
看不見。現在想起來很自然的事,當時卻一直想不到。我在網絡上下棋好多年了,
但一直把它當成消遣娛樂的地方,從來沒有想到過我的程序也可以從上面學棋。
有一天我突然意識到,只要寫一個界面程序,就可以把它一直掛在網上,一天二
十四小時與人對弈。
三.網上學棋
網上下棋的人很多,各種水平的都有,而且風格各異,正適合我的程序用來
學棋。我的程序掛在那裡,只要有人邀請,不管什麼水平,馬上就跟他下。這樣
一天二十四小時下下來,比我跟它下不知好了多少倍。一方面時間多,另一方面
網上可以找到很多初學者,學起來恰到好處。但真正的進化需要很多這樣的機會,
一天二十四小時我仍然嫌不夠。於是我又給我的界面引進了多線功能,也就是說
同時可以有好幾個同樣的程序在下棋。只要有人邀請,他就馬上開一盤。這樣一
來每天都可以下很多盤,進化的機會也就多起來。每到周末我就對程序作一次全
面整理。一個月以後,我的程序有了明顯進步。而且居然有了帶星號的27級。
雖然很差,但比起最低級別,還算是贏面占多。這使我很興奮,這至少說明它是
在進步,而且這是在沒有我介入的情況下獲得的。又過了一個月,它又升到26
級。
高興之餘也發現了新問題。這所謂自我學習,就是要不斷產生新的子程序,
新的模式。久而久之,程序就變得越來越大,運行起來就越來越慢。像生物學上
的進化一樣,新產生出來的東西並不是都有用的。事實上,我們人類的DNA鏈
上絕大部分都是沒有用的。開始階段我還可以用人工的辦法把那些沒有用的東西
去掉。到後來,新產生的東西越來越多,靠人工是完全不能勝任了。而且,最嚴
重的是,我的判定並不可靠。我認為沒有用的東西或許在意想不到的地方有用。
這個問題困惑了我很久,我的程序也從網上取了下來,因為我不能再讓它產生新
的子程序。
正在我不知從哪裡突破的時候,有一天在網上看見一篇講進化論中的用進廢
退原理。我突然意識到我的程序中就缺少這麼一個機制。於是,我就在我的程序
里加了這樣一個檢驗程序。如果一個模式或者一個子程序在一定時間裡沒有被調
用過,主程序就自動把它去掉。這樣一來,它雖然失去了一些可能產生好基因的
途徑,但主要障礙清除了,又創造出許多別的機會。很有意思的是,我發現有一
個子程序被調用的特別多,就把它取出來看一看。一般來說它自已進化出來的子
程序我是看不懂的。但我這次存了心一定要看它是幹什麼用的。花了好幾個晚上
一步步地看,終於發現它居然是用來判斷征子是否有利的。這種子程序都能進化
出來,我對它的前途產生了很大的信心。
重新上網以後,每天都有新程序產生,也有一些舊程序和模式被清除。程序
逐漸快了起來(因為開始堆積的廢物太多)。等級分又開始往上走,半年以後升
到了15級。這時候它的棋已經下得有模有樣,尤其是局部戰鬥,已經有一定的
殺力。但圍棋不是單靠局部拼殺定勝負的,必須要有整體觀念,而這整體觀念是
不能從15級的對手中學來的。這程序又像上次那樣停在那裡,長久沒有進步。
好幾個月都一直是15級。
四.向專家學棋
一般來說進化都是局部性的,在局部上有優勢的走法就很自然地被保留下來,
這樣永遠也不會有整體觀念的突破。雖然加進了突變的概念,但也最多產生出枷、
飛、伸大腿這樣的局部技術,棄子取勢這樣的整體觀念是不可能自動進化出來的。
有一天我在網上看富士通決賽,好幾步棋都看不懂,仍然看得精精有味。突
然想到要學棋並不一定只學完全懂的棋。專家的棋看多了,走起棋來自然而然就
有了好形,而且也知道什麼地方是大場。所謂“熟讀唐詩三百首,不會作詩也會
吟”就是這個道理。想到了這個思路,剩下的就好辦了。專家的棋網上有的是,
要多少有多少。幾個晚上就從網上搞來了上千盤棋譜。我先給我的程序加了一些
模式識別的功能,然後就讓它沒日沒夜地打起譜來了。從打譜中學會了占大場,
占完大場後接下來的變化它並不清楚。但這不是什麼問題,因為這些變化大都是
局部的,而我這程序的強項就是局部變化。幾個星期下來,再把它放到網上的時
候,棋力已經大長,在同級棋手中所向披靡,很快就升到7級,然後與7級的棋
手盤旋了幾個星期又慢慢地升到6級,5級,4級。
我這個程序的成長與我們大多數人學任何新東西一樣,都是一個階梯一個階
梯地上。許多人到了某個階梯,因為沒有明師指點,就長期停在那裡。我自己就
認識很多下棋十幾二十年都不長棋,打牌十多年不長牌,打球十多年不長球的人,
因為他們總是邁不過眼前這個階梯。這是由遊戲本身內在的複雜性所決定的,與
學它的人無關。我這程序也一樣,每過一段時間就要遇見一個階梯而停步不前。
IGS的4級似乎就是這樣一個階梯。它長到4級以後就再也不長了,長期停在
那裡。
說起來,IGS的4級已經比現在其它所有的圍棋程序高出一大截,如果拿
出去賣已經很可以大賺一筆了。但這不是我想要的,我的最終目的是要產生一個
戰勝專業棋手的程序。IGS的4級與專業棋手還有很大的差距。雖然如此,這
個級別的棋已經有相當的水平,再往上進步已經不能單靠計算,還要講究對棋有
感覺。而感覺這個東西是現在的任何程序都不具備的。這次停下來,一停就是半
年。雖然也隨時在網上與別人下棋,但總是沒有長進。出路在哪裡呢?
五.模糊函數與量子波
計算機程序的一大優點是對任何棋形都可以有個好壞判斷,在搜索範圍內一
切都不會錯過。可是,從某種意義上來說這也是一種缺點。一切都靠算,能覆蓋
的面積自然就少了。而且,許多棋的好壞要到十幾步甚至幾十步以後才會表現出
來,這是不可能算出來的,主要是靠感覺。另外,一個棋形的好壞並不是一成不
變的,在某些情況下壞棋形也會有好價值。就連被認為是最壞棋形的空三角也經
常在專業棋手的對局中出現。如果我們把一個棋形的好壞價值定死了,就沒有產
生這種變化的可能。我很早就想過要把模糊函數的概念弄到我的判斷程序裡面去。
可是無論怎樣模糊,在運算過程中,模糊量的大小還是得人為地規定。對一個固
定棋形還是會算出同樣的結果(雖然結果以模糊的形式出現)。
每一塊棋除了死變化以外,都是有生命的。它的生命力以輻射方式向外散發,
所以有“空提一子三十目”的說法。固定的程序是沒有辦法算出這種生命力來的。
有一天讀到一篇講量子計算的文章,突然想到可以試一試在我的程序中加入量子
波。這樣一切運算都以概率的方式出現,沒有固定結果,但通常會產生最自然和
理想的結果。加進去以後,它果然變得豐富多采起來。居然可以走出很多從前絕
對想不到的棋。不過,加進量子運算以後,效率變得比較低,搜索範圍變小了,
棋力居然比以前小有退步。但我並不為此失望,退一步進兩步,只要大方向是朝
前就行。關鍵是方法,效率問題總是有辦法提高的。後來我花了一些時間把程序
徹底整理了一下,又把我的計算機硬件升了級。如此一來,它的運算效率比以前
增加了一倍,棋力也隨之猛長起來,而且這次長起來就沒有停。幾個月下來就升
到一段(1D?),而且根本沒有停的意思。我的興趣也跟着高起來,隨時隨地
都在思考它的問題和解決辦法。什麼事情都想看看對我的程序是否有幫助,連開
車等紅燈都在想這最短路徑問題是否可以用到這程序的搜索路徑中去。這樣一來,
新的想法天天都有。
IGS是國際性的網站,任何時候世界上總有一半的地方是白天,也就是說
任何時候都有人下棋。我的任何新想法都可以立即得到是否有用的驗證。我每天
下班回家就全力撲在它上面。不斷地改進,不斷地加上新的想法。我把這程序沒
日沒夜地掛在網上,它的棋力每天都在長。兩年下來它終於達到4D?。
這個程序的運作很依賴計算機的速度,這包括主機速度,硬盤閱讀速度,以
及內存容量。為了充分發揮它的潛力,我當然想給它配置最好的裝備,這就需要
錢。而且如果想買剛上市的新產品,就要花大錢。台灣每年一次的計算機圍棋比
賽,如果能拿第一名,就可以得到相當數量的獎金,至少買新機器不成問題。但
我又不願引起別人的注意。於是我把我的程序簡裝了以後去參加這個比賽。所謂
簡裝就是拿掉一些子程序。但我的程序比別的程序高出太多,拿掉子程序後我又
給它加了一些限制,基本上就是讓它每盤能贏,但總在十目以內。最後一輪以前,
我的程序全勝,即使輸掉最後一盤也穩拿第一。於是,我在最後一場比賽前又拿
掉了最主要的子程序,輸了最後一盤。這樣別人都認為它與別的程序屬於一個檔
次。我又不像別的參賽人總想打名聲好賣他們的程序,而是拿了第一名的獎金就
趕快走人。因此,我的程序雖然拿了第一,卻沒有造成什麼影響。第二年的比賽
我沒有去參加,這程序就漸漸地從大家的記憶中消失。有少數人記得,也只知道
它大約是業餘5級的水平。
六.墨綠問世
在達到4D?以前,我的程序有輸有贏。雖然贏比輸多多了(從30K升到
4D?),但並沒有引起人們的注意。我覺得該是給它起名字打名氣的時候了。
起什麼名字好呢?因為我的最終目的是要打敗人類最高手,所以一定要起一個與
深藍類似的名字。開始想叫它“深綠”,但又覺得與深藍靠得太近。而且,深藍
的“深”有深層搜索的意思。我這個程序主要原理並不在深層搜索。叫它“淺綠”
又覺得名字不夠響亮。正在為起名字的事犯愁,恰好有多年不見的朋友來訪,說
是下一盤棋敘敘舊。於是從壁櫥里拿出已經起灰的雲子。這幾年雖然也常下棋,
但都是在網上下,手上摸的都是鼠標,這棋子已經有好幾年沒有摸過了。手裡摸
着這棋子,突然想到以前朋友曾告訴我鑑別真假雲子的辦法。說是把黑子拿起來
對着光看,真雲子會成墨綠色。這真是踏破鐵鞋無覓處,得來全不費功夫。“墨
綠”這個名字真是太合適不過了。既與深藍相近,又有神秘深邃的意思。名字想
好以後我就立即在IGS為它註冊了一個4D的賬號,英文名叫SLATEGR
EEN。
這時墨綠的棋力實際上已經比一般4D?強,但為了安全起見,開始只找弱
4D下。主要目的是要連勝以造成轟動效應。IGS的概率指令可以用來判別強
弱4D。因為它一天24小時全掛在上面,能找到對手就下,沒有對手就跟自已
下(我機器上還同時運行着另一個與它同時進化出來的程序)。幾個星期下來,
它連勝40盤,並且打成了5D?。一般人到了這種水平,一年半載也長不了什
麼棋。而墨綠不一樣,它每下一盤棋都以最優方式重新整理內部聯絡,也就是說
它一直都在長棋。打成5D?的時候,它的棋力其實已經高於5D?。所以,跟
5D?下也一直贏。幾個月以後又升到了6D?。6D?的級別,加上七八十盤
的連勝很快引起了大家的注意。每次下棋的時候總有很多人觀看,這種時候我特
別得意。由於連勝,找它下棋的人越來越多,甚至還有7D?以上的。為保險起
見,它只接受同級人的挑戰。不到7D?就不接受7D?的挑戰,而且也不跟新
賬號下。因為這些人或許是正在上升途中,實力可能很強。
因為墨綠成年累月都掛在網上,形形色色的人都會碰到。在4D?以前,時
不時就會遇見耍賴的。開始的時候,耍賴對墨綠沒有什麼用處,因為他不在乎輸
贏,而且有的是時間。打到4D?以後這個問題就變得比較嚴重起來。因為要用
連勝造影響,就一盤都不能輸。如果遇見逃跑的還好,一個月以後IGS會自動
判逃跑者負。可有時候墨綠明明大勝的棋,我這邊突然斷線。等我再連回去對方
已經跑了,這樣IGS算墨綠逃跑。好在4D?以上的人已經比較有棋品,這樣
干的不多。連勝二十盤的時候被我遇到過一次。於是我在它的程序里專門加了一
句等候此人的指令。除非它一個月內不出現(屆時IGS系統會算墨綠逃跑而判
負),只要他一出現,墨綠就會抓住他。4D?的人棋癮都已經很大了,要讓這
樣的人一個月不上IGS是很不容易的。這些耍賴的人往往是出來探一下頭,如
果有他們欠棋的人在線上,他們就立即斷線。由於墨綠有了這句等候他的指令,
使得他連探頭的時間都沒有。他逃跑一星期後又聯進了IGS,剛聯進不到5秒
鍾就被墨綠髮現,他還沒來得及打退出的指令,墨綠已經恢復了他所欠的棋,這
時候再要退出就算他逃跑,所以他只好把這盤棋下完,輸棋走人。
另外經常碰到的是打聽消息的。一般來說,墨綠對別人的問題一律不理。但
有時如果我在看棋,我就會幫它回答一些問題。“你是不是職業棋手?”“是。”
“你現在在哪裡?”“計算機里。”“你24小時都泡在這裡,不干別的事嗎?”
“是。”我總是用這種怎樣解釋都可以的答案來回答。
七.墨綠成長
墨綠的實力現在已遠遠高出我的實力,我跟它下棋幾乎總是輸。但因為我是
看着它長大的,知道它的一些別人不知道的弱點,所以偶爾我也可以贏它一盤。
但它如果在同一個弱點上連續兩次吃虧,就會彌補掉這個弱點。因為我已經不可
能去改它的程序了,只能通過這種辦法來克服它的弱點,好象也很有效。我有時
為了特意讓它暴露出它的弱點,就跳過它的程序幫它走棋。為此還產生過一個小
鬧劇。
墨綠到了4D?以後,常常走出出乎我意料的棋。基本上要好幾步以後我才
能理解那一步的目的。有一次雙方殺得很緊張時對方打吃,我覺得它只能長出去,
否則棋筋被人提了就全完了。可是墨綠沒有長出去,而是長考起來。我在旁邊看
得着急,以為它又出現什麼漏洞,就擅自幫它長了出去。等到對方下一步棋走出
來,我才知道它剛才為什麼要長考,也意識到我幫了倒忙。對方的下一子同時威
脅到兩塊棋,在另一塊棋補一手後,剛才接上的一子又被堵了下來。幾個回合下
來,墨綠損失十幾目棋。在此之前,墨綠一直沒有輸過。由於我的幫忙,眼看它
的上百連勝就要被破了。好在墨綠的棋現在已經比一般的6D?高出一截,而且
我很早以前給他加的風險係數現在起了作用。墨綠下棋的最終目的是贏,贏多贏
少都不重要。所以它隨時都在算自己領先多少。領先多了就走風險很小的棋,平
手或微微領先時就走風險相對大一點的棋。現在落後很多,到了走風險很大的棋
的時候了。風險大的棋大多都是無理棋。只要對方應對正確,下無理棋的一方會
損失更多的目。沒想到對方在墨綠一連串的無理棋下,居然沒有採取應有的手法,
而是一味地退讓。大約自己認為領先很多,隨便收收官就可以贏了。而且,鬼使
神差,對方有一步棋居然應錯了次序,吃了大虧,雙方的目數一下就拉近了。收
官的時候墨綠又再賺了幾目,最後剛好贏了半目。真懸!從那以後,我再也沒有
幫它走過棋了。
上面那盤棋是墨綠連勝以來贏的目數最少的一盤棋。說起贏棋目數,與墨綠
下棋的人都覺得很惱火。因為收官基本都是靠死算,是它的強項。一般一盤棋到
了收官階段,它幾乎可以把各種變化都考慮到,然後宣布對方輸多少目。如果對
方繼續下,而且沒有按最佳下法下,它就會重新算一遍然後宣布一個新目數。剛
才還說“黑輸3目半”,現在或許說“黑輸5目半”,9目,13目,就這樣一
直收到結束。開始我給它加這個功能是覺得好玩,後來就成了一個節目,許多觀
戰者覺得這樣很好玩。不過這讓輸棋的那方感到很不是滋味,好象被人宣布“你
死定了”,然後自己一步步朝墳墓走去。
採用選對手的辦法的結果又是只贏不輸。因為它實際上總是與比它弱的人下,
而且又不會出現昏着。沒過多久,它就升到了7D?,然後是8D?。
八.爭挑戰權
8D?已經有不少專業棋手。由於連勝,墨綠的名氣在IGS上已經到了家
喻戶曉的地步。只要是它的棋,總有上百人觀看,有時超過500人。它的思路
與人不一樣,常常在大家意想不到的地方走棋,所以看的人特別多。尤其是職業
棋手,都想來研究它的棋路。它基本也不照定式走棋。如果算出來的棋路與定式
相同(大部分如此),就按定式走棋。如果算出來與定式不同,它也沒有一般棋
手的忌諱,總是按着自己算出來的路數走,根本不管定式不定式。這樣一來,它
的棋中產生出很多“新”定式,這就更吸引眾多專業棋手了。大家開始都以為它
是某個超一流棋手。看它保持上百盤不敗,大家一致認為它是李昌鎬。可看它的
棋路又完全不像李。而且有人觀察很仔細,發現有一次墨綠在IGS下棋的時候,
李昌鎬正在中國下富士通決賽。所以可以斷定它不是李昌鎬。用同樣的方法,大
家很快推出它不是中日韓三國任何一個等級分排前20名的棋手。這樣一來,迷
團就越來越大。看它下棋和找它下棋的人也越來越多。
由於連勝,墨綠很快升到了9D?。而且在信息欄里宣布只與9D?下棋。
IGS上的9D?很少,就10來個。而且大多是以前的賬號。如果別的9D?
宣布只與9D?下棋,也許就找不到人下了。可墨綠的上百的連勝在職業棋手中
造成了很大的轟動,大家都想來找它較量一下。可是要打到9D?必需要從7D
開始。有些職業九段想請IGS管理員直接給他們9D?的賬號。可IGS認為
這正是吸引職業棋手來下棋的好機會,於是宣布絕不破例。這樣一來,一大堆想
找墨綠下棋的職業棋手湧進IGS,從7D開始往上打。好象本因坊之類的頭銜
比賽,先在循環圈裡打,打出循環圈(升成9D?)才可以同墨綠下。
從7D?要打到9D?需要下很多盤棋,職業棋手一般不願意花時間下這些
棋。於是有些賬號有好幾個人在下,而且都是很強的九段,大家分任務,每人必
需贏多少盤。不到兩個月,IGS出現了好幾個新的9D?。這些人一旦打進9
D?就再也不相互下棋,而是追着墨綠下。墨綠當然是來者不拒。不過這兩個月
以來,墨綠與另一個同時進化出來的墨綠程序一直在下棋,棋力又有了長進,已
經高出了這些職業九段。所以,與這些新9D?下,又是只贏不輸。雖然現在在
IGS上下得少了,但由於只贏不輸,積分仍然慢慢往上爬,最後終於升到了1
0D?。