看看你的電腦能有多高明，讓它下盤圍棋吧

十來年前電腦“深藍”一舉擊敗國際象棋大師卡斯帕羅夫，震驚了西方世界。然而這一新聞在東方頂多讓人打個哈欠而已。

圍棋，洋人眼裏黑石頭與白石頭的遊戲，與古老的東方曆史一樣深不可測，滲透著人類最高層次的思維與智慧。在如今科技日異千裏的時代，圍棋迷們發現，電腦要想正兒巴經地玩一把這一迄今為止最純粹的“人類”遊戲，還差得遠呢。

台灣的應昌期先生生前對推廣圍棋文化樂此不疲，曾懸賞一百四十萬美元征求第一台擊敗圍棋高手的電腦。重賞之下必有勇夫，電腦專家們絞盡腦汁，的確使電腦下圍棋的本領有所提高。在美國和日本舉行的國際電腦圍棋年賽，冠軍獎金約為兩萬五千美元。然而這些矮子裏拔出來的電腦冠將軍與學棋一年左右的人比賽時仍然不堪一擊。初學者便可以橫掃當今所有的圍棋電腦，用不著請一位卡斯帕羅夫。

如今電腦的運行速度越來越快，容積越來越大，但近年來下圍棋的本領仍在沒有多大長進，應老先生的賞金隻好留待後人來拿了。

“深藍”能夠擊敗國際象棋冠軍，靠得是基本的行棋知識再加上強大的檢索和運算能力。而這排山倒海般的能量在精妙的圍棋麵前完全無能為力。迄今最強的電腦圍棋程序之一“多麵圍棋”的設計者美國惠普電腦公司的工程師大衛•佛特蘭德說：“強力檢索對圍棋全無作用。你得寫出一個像人一樣精明的程序來。”

要使電腦下出的圍棋多少像點樣子，必須使其具備辨認各種微妙複雜的圖形的能力以及運用自身直覺經驗的能力。這種能力正是人類智慧的一大特點。如果真有一天電腦能打敗圍棋高手，那將標誌著人工智能開始成為實實在在的東西了，也將宣告又一個科技新時代的來臨。

下圍棋時，棋盤上的圖形如繽紛的花瓣逐漸展開蔓延。人的思維就沉浸於這些圖形構成的美妙世界中，一串串行雲流水般的行棋次序猶如一首首時而悠緩時而激昂的旋律。問題就在於如何使電腦能夠譜寫並體會這一視覺音樂。

表麵上看來，圍棋似乎比國際象棋簡單：64個方格上的國際象棋每一方各有16個棋子，等級從兵到王。每個棋子隻能根據規則以自己特有的方式移動，譬如象隻準走斜線；馬隻能L型進退；兵第一步時可向前走一格或兩格，以後隻能走一格，不準後退，吃子時須向前斜一格吃；此外還有王車易位、兵落底升後等各種規則。而圍棋則沒有那麽多複雜的規定。所有棋子都是一個模樣，對局者將黑白棋子分別放置在19路見方的棋盤的未被占據的交叉點上，直到雙方均認定無處可繼續落子，然後再根據雙方所占據的地盤的大小來決定勝負。國際象棋在開局時，全部棋子都在棋盤上，以後逐漸減少，直到一方的王被對方吃掉為止。而圍棋則是從零開始，361個交叉點，處處是戰場，有的地方硝煙彌漫，有的地方則風平浪靜，有時幾處同時燃起戰火。國際象棋好比是一場兵來將擋的中世紀戰爭，圍棋則更像是一場烽火連天的世界大戰，很多情況下很難說清哪一方領先。在世界專業水平的國際象棋比賽中，如果你丟掉一個兵，棋局的結果在絕大部分情況下便有定論。而在圍棋中，也許你在某一局部的戰鬥中丟盔棄甲、死傷累累，但比賽往往遠沒有結束，你還可以在別處卷土重來。

對於電腦來說，國際象棋與圍棋的種種區別是無法逾越的巨大鴻溝。由於每隻棋子移動方式的製約，國際象棋棋手在思考下一步棋時，大約隻有35種選擇。“深藍”等電腦會針對這些選擇加以分析，考慮對手的回應以及下幾個回合可能出現的情況。最好的國際象棋電腦程序可以分析到七、八個回合。這種信息檢索方式就好比一棵枝葉繁茂的大樹：主幹分出35個支幹，每個支幹再分成35個樹杈，每個樹杈再分成35個樹枝，如此類推。愈是高級的電腦程序所派生的樹枝樹杈的層次就愈多，最終達到每一片樹葉，即可供選擇的結果。如果要求電腦能思考到第七回合，即14步棋，便需要有35的14次方（十億萬億以上）片“樹葉”。每多一個回合，樹葉的數量就有爆炸性的增長。電腦工程師們使電腦能夠合理地“剪枝”，僅使一部分而非全部樹葉與主幹相連。盡管如此，能夠思索七個回合的國際象棋電腦每步棋仍然需要有五百億到六百億種選擇。

這樣的數字已足夠驚人，而電腦下圍棋則更不可思議。選擇之數的龐大繁密使迄今最強大的電腦也無法承受。下第一步棋，361個點的任何一點都是合法的，而第二步棋有360個選擇。隨著棋局的發展，選擇逐漸減少。但一般說來，每落一子平均約有200個選擇，而國際象棋僅有35個。也就是說，要國際象棋想兩個回合四步棋子，全部棋子在棋盤上的位置變化大約為150萬種（35x35x35x35=1,500,625），而圍棋則需要16億（200x200x200x200=1,600,000,000）。在布局階段數字還要大得多。再多一個回合，數字還會爆增：國際象棋為18億，圍棋為640億。如果要像“深藍”一樣思考7個回合14步棋，圍棋電腦的“樹葉”並非國際象棋的35的14次方，而是200的14次方之多。通過“剪枝”，還要剩下一億億種選擇。那麽，一台與“深藍”同等速度的圍棋電腦（即每秒種可分析二億種可能性）每下一子需要晝夜不停地想上一年半！而這一著冥思苦想一年又半載的棋沒準又是一著臭棋。



還遠不止如此。即使經過如此這般上天入地的檢索，圍棋電腦在與人對局時並占不了多大便宜。國際象棋電腦程序在經過大量的信息篩選之後試圖找到使其處於最佳位置的那一步棋，所采用的辦法是所謂價值評估的相當簡單但實用的公式：每個兵的價值為1、馬和象為3、車為5、後為9，然後將這一數字再與衡量棋盤上每個位置的強弱的另一數值相乘，從而得出某一棋子在當時的相對值。此外，還要其它一些公式用來決定某些概念的價值量，如王的安全程度百分比以及某一棋子暴露於攻擊的百分比等。這些並非一貫正確的教條已經足以使電腦具備相當水平了，使它對棋局的進展有個大致的掌握，再加上電腦裏輸入了很多一流棋手過去的棋局，下到某一步常可不時問問大師以往都是怎麽下的。而圍棋則不受那些簡單分析的約束。圍棋盤上並未像“王”一樣的棋子，每顆都是相等的。統計雙方吃子的多寡也不能說明什麽問題。有時某一著棋便可以滄海桑田，將對方苦心經營的領地化為己有，將對方的大龍變為自己的佐餐；有時又明明看到自己的棋行將被吃，而放下不走，另辟戰場。另外，棋譜數據庫也無多大作用，由於圍棋千變萬化，三四十步開外基本就是“you are on your own”的狀態了。

圍棋棋手們是通過對形狀的認識來評估棋局的進展，而對這些形狀的認識是無法做出幾何分析的。棋手完全依賴自身的經驗去感覺哪些形狀是好的或壞的。這一對棋形的感覺正是勝負的關鍵，也是棋手水平高低的關鍵。棋手不願意浪費自己的子力去無謂地攻擊對方活的形狀或試圖挽救自己死的形狀。有時麵臨複雜的戰鬥，棋手很難完全算清；有時又麵臨多種選擇，舉棋不定。此時棋手就用棋形整理思路，往往好看的棋形就是更具效率的、不易受到攻擊的。下出滯重、喪失變化的棋被稱為“俗手”，棋手會覺得下不出手，就完全不予考慮。這樣有時就出現有趣的“專業棋手的盲點”：有時一手“愚形”或“凝形”的棋卻是此時的最佳選擇，業餘棋手看得到，專業棋手卻想不到。

日本著名棋手大竹英雄號稱“美學大師”，對惡形惡狀的棋形深惡痛絕，寧可輸棋也要把棋下的漂亮，因而比其它日本棋手更為鄙視韓國圍棋，說曹熏玄的棋是“農民的棋”。其實棋形的漂亮與否雖然有大致的概念，但也會有不同的觀點。有的棋手喜歡輕靈的形狀，有的則愛好厚重的形狀，也就是所謂棋風的不同。與吳清源共同創造“新布局”的木穀實早期偏愛滴水不漏的堅實。一次在走角部的三三定式時，明明按常規應該“飛”，他卻笨笨地“爬”了一手，一邊把棋子打在棋盤上，一邊嘴裏還嘟囔著：“雖然先生看見要罵，還是要這樣下！”從此這一定式又有了新的變化，後人稱之為“木穀流”。

由此可見，與其說要教給電腦下棋的感覺，不如說要教給它人的感覺，這便是世界科技發展史上人工智能領域最根本的難題。



惠普的佛特蘭德先生給他的圍棋程序“多麵圍棋”輸入一些圍棋的基本概念，如對領地的保護意識及棋子互連的意識，並輸入二百多個高層次的戰術概念，如“攻擊弱棋”、“向處女地進行擴張”、“落後時開始無理侵入”等。“多麵圍棋”可辨認一千一百多個不同的形狀，每一種形狀都有一些可行的手數。像“深藍”一樣，“多麵圍棋”儲存了很多常用的開局定式及一些慣用套路。依賴這些儲存的知識，“多麵圍棋”每一步棋僅在五至十種可能性中做出選擇，而非理想的二百多種。

給電腦輸入一些概念是一回事，而教給它靈活運用這些概念又是另一回事。可接可不接的棋或可斷可不斷的棋什麽時候連接或切斷？什麽時候又無需連接或切斷？什麽是可棄之不用的廢子？什麽又是絕不可放棄的“棋筋”？比起人類對模糊概念的處理以及對經驗的靈活運用，電腦今天還是個嬰兒。

但圍棋電腦的設計師們仍然堅信，讓圍棋成為世界冠軍理論上是成立的。因為既然每一步棋的選擇是根據棋盤上的每一個位置的價值來決定的，也就是說圍棋從純粹意義上來講其實是數學的遊戲（我們也常聽棋手說這手棋很大、那個見小），所以隻要把每一個位置的數學價值準確計算出來，電腦就能成為圍棋高手。目前至少在收官階段（即收尾終局階段）可以做得到。

能夠擊敗人類的圍棋冠軍而贏得應昌期圍棋基金會懸賞的一百四十萬美元的獎金，是個在悠悠歲月中難圓的夢。該懸賞的獎金已於2000年過期了。當年應老先生推廣圍棋的精神可嘉，但把事情想得太簡單了。電腦專家們真希望把懸賞的截止日期推遲一兩個世紀。



（本文部分資料取材於紐約時報）

[路邊野花不採白不採]

回複cohomology的評論:
多謝老兄高見

[cohomology]

1. 頂你這篇文章
2. 就圍棋的迷人程度及複雜性來講，就像你說的，應該遠遠高於國際象棋。圍棋沒有在西方普及，我覺得深處還是他們的文明優越論在作怪。不過這個太有爭議了，社科上的問題很難講清楚，我覺得也講不清楚。擱下不講 ^_^.

我覺得概率在布局階段是有用的。這兒有必要稍微嚴格的定義一下：例如第一手走那？一般來講星，小目，為什麽隻有這幾個地方？從數學上講應該解釋成這樣： 走在那一步輸棋的數學期望最小？現代圍棋理論的發展表明應該有這樣的關係（當然沒有嚴格證明）：走星輸棋的數學期望和走星輸棋的數學期望非常接近，而這兩個數學期望值又明顯的小於比如走天元，目外等等的輸棋的數學期望值。

在棋盤上圖沒有形成之前，概率應該是 有用的。這時“隻此一手”應該解釋為這一手輸棋的數學期望最小。 這就是為什麽布局階段很多時候說二間高夾可以，二間低夾也可，取舍看對局者的風格。從數學角度來講，就是這兩種選擇輸棋的數學期望差不多。

一旦圖形成，我覺得，Graph 理論管理局部問題，這時局部的“隻此一手”及手筋應該可以從Graph理論當中得出，而概率則管全局問題：如它應該回答這樣的問題：應該在哪一個局部下子? 盯在一個局部連續下子是否可以得到全局利益最大化?何時在一個Graph上脫先？
總之Graph管局部，概率管全局。


在人工智能方麵，我覺得Godel不完全性定理及P是否等於NP的解決對這一領域的發展具有決定性的影響。當然前提是我們用圖靈機來實現人工智能。我覺得這兩個結果決定了人工智能的局限性。當然這個局限是從數學基礎論的角度來說。現實是人工智能一日千裏。但不知你注意到沒有，人工智能還主要在所有排列組合中如何高效選擇最佳或接近最佳的一種這樣的工作。從數學角度來看，還是在可數集範圍內（即此集合和自然數集合有一個1-1對應映射）. 它能不能在不可數集中選最佳方案，如在和實數集合相等價（即和實數集有一個1-1對應映射的）集合中選？我覺得不行。

一家之言，有錯誤的地方，付之一笑罷了。

[路邊野花不採白不採]

回複cohomology的評論:

再者，人的智慧是無窮的。誰也想象不到將來甚至五年之後的科技發展，人發明的電腦總會有戰勝人自己的那一天。圍棋電腦的落後的原因之一還是因為人投入的精力不夠。國際象棋在西方更為普及，使有關的電腦程序更先進。而當今西方仍然是圍棋沙漠，僅靠中日韓的努力還不夠。圍棋電腦的推廣還有賴於圍棋本身在全球的推廣。

[路邊野花不採白不採]

回複cohomology的評論:

謝謝這位網友的高見。的確，要電腦圍棋有所突破，需要有創新方式。就像人工智能領域的突破點不能拘泥於使機器人更有本領一樣。不過我覺得概率對下圍棋沒什麽作用。在布局階段之後，多數情況下是所謂“隻此一手”的絕對選擇。

[cohomology]

要在電腦下圍棋方麵有所突破，我覺得要在圍棋的數學理論方麵要有所建樹。我覺得現在的Algebraic Graph theory很有意思。也許是一個突破口。另外概率論的采用似乎也是必不可少的，比如用Random Matrices 理論。因為圍棋中數目巨大的可能性為概率的應用提供了很好的前提。甚至解析理論的應用也應該是有可能的。因為對一個圖，可以assiciate 一個 L-函數 ...... . 專業的東西說的太多了。 總之我覺得並不能局限在排列組合及消減排列組合的數目方麵。