圍棋起源於中國，是最古老的棋類運動之一，我們常說的「琴棋書畫」中的「棋」就是指圍棋。
「深藍」在1997年的一場歷史性的人機大戰中戰勝了人類國際象棋冠軍卡斯帕羅夫。圖/Peter Morgan
1996年，許峰雄博士代表「深藍」與卡斯佩羅夫對弈。
你喜歡下棋嗎?有沒有和計算機下過?現在，弈棋計算機的棋藝日益高強。讓我們通過分析以圍棋和國際象棋為代表的弈棋計算機，對人工智能的研究有一個更為深入的理解。
弈棋計算機
弈棋自古被視為一種關乎智力的高級挑戰。和其他智力測試相比，弈棋具有直接對抗的特點，沒有什麼比在緊張的對局中看到對手一手精妙兇狠的棋招更能讓人感覺到一種智力上的刺激和挑戰了。弈棋相比於其他牌類遊戲而言，隨機和不可控因素更小，因此對局雙方的決策能夠更直接地控制整個局面的走勢，這進一步增強了智力的對抗性。
毫不意外，在國際象棋更加流行的西方國家，人工智能領域自創建之初就在考慮如何製造一個會下國際象棋的機器。幾乎所有人工智能先驅，包括信息論創始人香農、「人工智能」之父約翰·麥卡錫(John McCarthy)、計算機科學創始人圖靈，都曾嚴肅思考過製造國際象棋機器的問題。20世紀80年代初，貝爾實驗室的工程師們(其中包括著名作業系統 Unix的聯合創作者肯·湯姆森)開發出歷史上第一個具有人類大師級水平的國際象棋機器「Belle」。到80年代末，卡內基梅隆大學的許峰雄博士在「Bella」的思路基礎上(將在後面詳細介紹)進一步改進，研製出了第一個特級大師水平的國際象棋機器，取名「深思」(源自《銀河系漫遊指南》中的超級計算機)。隨後，許博士加入IBM研究院，在那裏和其他幾個團隊成員一起研製出了實力更強的弈棋機器「深藍」，並最終於1997年的一場歷史性的人機大戰中以3.5：2.5的比分戰勝了人類國際象棋冠軍卡斯帕羅夫(卡斯帕羅夫不但是當時的人類冠軍，同時也是人類歷史上國際象棋等級分最高的職業選手)。
在圍棋更加流行的東方，圍棋大師的頭銜同樣是智力超群的象徵。自從計算機在國際象棋上挑戰人類成功之後，所有人的目光就聚焦在了圍棋這項古老的東方棋類運動上。然而對計算機來說，圍棋似乎是個比國際象棋更「難」的東西。1985年，企業家應昌期先生懸賞一百萬美金尋找能夠打敗人類職業棋手的計算機，可時至30年後的今日仍然沒有一台計算機能夠做到。20世紀90年代，以我國陳志行教授開發的「手談」程序以及著名開源軟件組織GNU開發的「GNU Go」程序為代表的「計算機圍棋冠軍」們，棋力尚且不及人類的業餘初段。進入21世紀之後，研究者們開始探索一套被稱為「蒙特卡洛樹搜索」的全新思路(將在後面詳細介紹)，並終於在2006年在9×9的「小棋盤」上率先產生突破。以法國的MoGo和CrazyStone為代表的新一代圍棋程序在9路圍棋上基本已經達到人類職業棋手的水平，甚至曾在公開場合戰勝過職業棋手周俊勛九段。另一方面，在真正的19路圍棋棋盤上，以日本的ZEN(天頂圍棋)和法國的 CrazyStone為代表的一流圍棋程序沿着「蒙特卡洛方法」的思路不斷改進，在和人類頂尖職業棋手進行的一系列讓子棋比賽中屢有佳績，而近些年人類棋手能「讓」計算機的子數也越來越少。最有趣的是在2013年，電腦程式CrazyStone在受讓四子的情況下戰勝被稱為「人腦計算機」的日本棋手石田芳夫九段，並被認為已有業餘五～六段的水平。
截至目前，儘管計算機在公平的圍棋比賽中還不足以直接抗衡人類職業棋手，但相關的研究熱度卻很高，大家普遍對近期前景持較為樂觀的態度。「深藍之父」許峰雄博士甚至在2007年10月的一期《IEEE Spectrum》雜誌上表示，相信10年內超級計算機將能挑戰世界冠軍級別的人類棋手。
圍棋起源於中國，是最古老的棋類運動之一，我們常說的「琴棋書畫」中的「棋」就是指圍棋。
左為唐代《圍棋仕女圖》絹畫，1972年出土於吐魯番阿斯塔那;右為隋代白釉瓷圍棋盤，1959年出土於河南安陽。圖/維基百科
計算機下棋的思考模式
現在主流弈棋計算機的基本「思考模式」很簡單，就是對當前局面下的每一種合法走法所直接導致的局面進行評估，然後選擇「獲勝概率」最高的局面所對應的那個走法。也就是說，「準確評估給定局面的勝率」是主流弈棋計算機的核心問題，同時也是主要難點所在。在進一步深入討論這一核心技術問題之前，我們先在基本思考模式層面簡單比較一下計算機棋手與人類棋手的異同。
可以說，計算機的基本策略是所有「人類有可能採用」的策略中最原始最簡單的一種。毫無疑問，人類的思考模式中必然也包含「局面評估」的部分，然而人類至少還同時擁有另一個重要的思考模式——戰略性思考，也就是把一個基本目標有效分解成一系列「子目標」。
以圍棋為例，「獲勝」是圍棋的最終目的，而勝的定義是「結束比賽時擁有更多棋子和空」(中國規則)。但是人類棋手在對弈時顯然並不是每時每刻都在基於這個「勝」的定義進行思考的——通常我們只在棋局進入中後期時才經常性地「數目」。在對弈的大部分時間裏我們是在思考諸如「如何藉助右上角黑棋的毛病擴張」、「如何做活」、「如何侵消對手的模樣」、「如何在劫爭中轉換」、「如何分斷」等等一系列具體問題。我們注意到，每一個這樣的「具體問題」實際上是改變了思考的目標，把一個「求勝」的問題轉化成了一系列「分斷」或者「做活」之類的子問題。這樣的一個「戰略計劃」，其背後的邏輯當然是，我們的大腦相信在當前情況下「分斷對手大龍」是最有可能導致最終贏棋的子目標。一旦確立了子目標，人類棋手便集中精力考慮具體戰術走法來完成這個子目標，而不是「贏棋」這個最終目標。與之不同的是，目前主流的弈棋計算機從基本思考模式上並不依賴於「生成並確定子目標」的戰略能力。在大多數時刻，這些弈棋計算機只關心一個問題，就是按照「勝」的基本定義來贏得比賽*1。「在當前局面下，我走在x點的話最終能贏几子」，計算機就是通過不停地重複問自己這個問題來完成對弈的。儘管這聽起來很「原始」，但正如前面所說，這樣思考的計算機卻已經在很多棋類中達到了相當令人驚訝的水平!
現在我們回到「評估局面勝率」這一計算機弈棋的核心問題上。主流方法中一次局面評估通常由被稱為「靜態評估」和「動態評估」的兩個部分協同配合完成。
基於「特徵識別」的靜態評估
黑方影響的區域白方影響的區域黑方影響的區域
對圍棋局面基於「粒子-場」模型的靜態評估結果
局面靜態評估好比人類棋手的「感覺」(也叫「第一感」、「棋感」)。
目前使用的方法很容易理解。就像網上經常遇到的性格測試：讓一個人做10道選擇題，每道題如果選A加1分，選B不加分，然後根據10道題的總分對這個人的性格進行分類，0～2分的是黏液質性格，8～10分的是多血質性格……國際象棋的局面靜態評估過程和性格測試非常類似，對於一個給定的局面(對應性格測試里的一個人)，評估算法問「當前局面里我方有沒有皇后」，有的話加10分，沒有不加分;再問「有沒有兵」，有的話每個兵加1分，沒有不加分……然後評估算法把所有問題的總分加起來，總分越高代表該局面勝率越大。
我們看到，計算機對國際象棋局面的靜態評估過程相當於給局面做了一次測試卷，其中每一道測試題對應了局面的一個特徵。一般來說，優秀的國際象棋計算機所使用的「測試卷」中的每一道題都是由人類大師根據自己多年的弈棋經驗精心設計的，而裏面每道題的「分值」或者由象棋大師直接設定，或者由計算機根據海量棋譜通過被稱為「機器學習」的技術自行決定。
前一種方法往往面臨的一個問題是，人類大師其實根本就不用這種「給局面做測試卷」的方式思考，所以他們的經驗有時很難直接指導分值設定。而在後一種基於機器學習技術的做法下，象棋大師除了設計用於評估局面的「考題」(每道題分值待定)之外，「只」需要對用於「訓練」計算機的棋譜中出現的每一個局面打一個「局面總分」(這個總分並不基於大師為計算機設計的任何「考題」，而是直接根據自己的經驗得出)，計算機就可以自動為每道考題選擇一個合適的分值，使得當我們使用如此學習出來的分值去考察棋譜中的每個局面時，由「考卷」累加得到的分數都恰好比較接近象棋大師根據經驗為該局面評估的分數!
圍棋電腦程式使用的靜態評估過程一般也基於類似的「打分原理」。只不過圍棋裏面棋子的「位置特徵」比「數量特徵」更重要，所以圍棋程序在選取特徵時往往並不基於單個棋子，而是基於由若干子組成的「基本形狀」。更重要的區別是，圍棋局面評估並不僅僅是把來自每個特徵的得分簡單相加，而是基於一些更複雜有趣的綜合過程。
比如，在這方面有一類很有意思的研究叫做「基於動態系統的圍棋局面評估」。這種觀點把圍棋棋盤看作一個二維「靜力場」，裏面每一個棋子或每一個基本形狀擁有一個類似於「電荷」的屬性，並根據這個屬性向外輻射「影響力」，強度隨着距離遞減。這樣，對於給定局面，棋盤中的每一個點都具有一個「場強」，它根據來自棋盤上所有黑子和白子的影響力相互疊加和抵消後決定。所有點的場強可以通過多輪疊代計算得出(類似於物理中求解「多體問題」的過程)，根據這些場強我們就可以決定對於棋盤中每一個點，黑白哪一方「勢力」更大。
從某種意義上講，基於動態系統的圍棋局面評估實際就是在試圖建立一套「圍棋世界裏的物理定律」，使得依據這些定律做出的判斷符合頂級高手間的實戰經驗，或甚至是符合「完美走法」下的結果。當然，目前的「粒子-場」模型可能更多只是對我們所熟知的經典力學模型的簡單模仿，也許我們應該基於一套完全不同的理論來描述圍棋棋盤裏的天地(比如基於概率模型)，又或許從原則上根本不存在能夠精確描述局面走勢的「圍棋定律」……無論如何，對圍棋局面靜態評估的研究一旦產生突破，很有可能使得人類對圍棋這項古老棋類運動本身產生更深刻的理解，同時也會極大地改變圍棋弈棋計算機研究的現狀。
截至目前，對圍棋局面的靜態評估效果還遠遠比不上國際象棋，一般只對處於棋局初期的局面有一定作用，而對當棋局進入激烈廝殺後的中後盤，尚未找到有效的靜態評估方法。下面馬上就要提到，正是由於靜態評估部分的缺陷，直接導致了圍棋程序在「局面動態評估」部分採用了一套與國際象棋程序差異很大的策略。
另外值得注意的是，在上述局面靜態評估的構建過程中，機器作為一個「智能個體」，最多參與到特徵的「權重」設定，而對於更重要的「應該使用什麼樣的特徵」以及「根據什麼方式對所有特徵進行整合」的問題則完全由人類專家負責。可以說，「特徵自動提取」一直是機器學習這個人工智能分支多年來的主要挑戰之一。後面還會再次提到這個問題。
基於「預測分析」的動態評估
如果說對棋局盤面的靜態評估好比人類棋手的「感覺」過程，那麼動態評估就好比人類棋手的「推理」過程。在靜態評估中機器得益於人類專家的很多幫助，而動態評估的部分可是機器大顯身手的地方了。
簡單講，「動態評估」試圖對從當前盤面出發「有可能」出現的大量局面變化所導致的結果進行預判，並綜合分析所有這些可能性，對當前盤面進行一次評估。這也是人類在動態環境中做決策時經常使用的策略，也就是希望通過「看得更遠」來提前發覺潛在的危險或機會。
經過高度優化的弈棋計算機每秒鐘可以計算數以億計的變化，即使是運行在普通個人電腦上的弈棋程序也經常可以做到每秒計算幾十萬種變化，這種高速運算能力極大地彌補了計算機在靜態評估時的不足。對於像國際象棋和圍棋這種歷史悠久的複雜棋類運動，只基於靜態評估的電腦程式通常連入門級業餘棋手都未必下得過，而一旦配備了動態評估能力之後，弈棋計算機卻能達到普通棋手甚至人類世界冠軍都無法達到的水平。
盤面動態評估可以說是計算機弈棋領域的研究重點所在，幾十年來人工智能研究者和計算機科學研究者提出了許許多多的方法。這裏我們簡單介紹一些共通的基本原理，以及圍棋和國際象棋這兩個最受關注的棋類的主流動態評估方法。
基於一套給定規則，任意給定的棋局盤面會有一個「合法走法」的集合，其中每個走法都會把棋局引向一個新盤面，而這個新盤面又會有自己的另一個合法走法集合，每個走法又對應一個新的盤面。如果假設每個盤面都有種合法走法，那麼從當前盤面走一步之後一共有b種可能「到達」的盤面，兩步之後有b^2種可能盤面，三步之後有b^3種可能……如此展開下去，從最初的給定盤面經過d步之後可能到達b^d種不同的盤面，它們就是在「未來d步內所有可能的局面變化」。
我們看到，從給定盤面開始的局勢變化的複雜度是隨考慮的步數呈指數級增長的。對於包括圍棋和國際象棋的絕大多數複雜棋類運動而言，這意味着從原則上不存在準確計算盤面的最優結果的有效方法。不過，這對於對局雙方來說未必是個壞消息——雖然我無法計算最優解，對手也同樣無法計算。事實上一個遊戲之所以成為遊戲，恰恰就是因為對局雙方都相信對手不具備完美決策的能力，而自己要做的只是比對手「錯得更少一些」。
另一方面，對於弈棋計算機的設計者來說，「不可能對局勢變化的所有可能性進行有效計算」意味着想做得比對手更好需要從原理上解決兩個關鍵問題：(1)決定一個「篩選策略」，從所有從當前盤面出發有可能導致的變化中選擇一部分作為「我們實際考慮的那些局面變化」;(2)決定一個「匯總策略」，把所有實際考慮的變化的靜態評估結果綜合起來，對當前盤面的勝率完成評估。無論是國際象棋、中國象棋、圍棋、或者其他如西洋跳棋、黑白棋、五子棋，所有棋類程序的動態評估方法從根本上都符合由「篩選策略」和「匯總策略」組成的基本框架。它們之間的區別僅在於使用的具體策略不同，以及由此產生的針對實現特定策略的優化手段的不同。
下面，我們就來看一下在最具代表性的國際象棋和圍棋中，弈棋計算機分別使用的兩套截然不同的動態評估策略吧。
「指數級增長」與「EXPTIME-Complete問題」
指數級增長可算是大規模計算第一大「攔路虎」了。在一個著名的傳說中，國際象棋的發明者印度人塞薩(Sessa)向他的國王請求賞賜，他說，希望因為發明國際象棋棋盤的第一個格而得到一粒米，因為第二個格得到兩粒米，因為第三格得到四粒米，如此在每後一個格都增加一倍的米量。不識指數級增長威力的國王欣然答允，甚至還有些責怪塞薩要求太少，然而事後才發現整個國庫的米都倒乾淨了仍然無法填滿整個棋盤。故事的結局是，國王惱羞之下偷偷派人把塞薩殺掉了。學過等比數列的現代人按一按計算器就知道，國王因為這64個棋盤格子總共要支出2^64-1=18446744073709551615>10^19粒米，這據估計已經超出整個人類歷史上產米量的總和!
回到局勢變化的複雜度問題上。即使10^19這樣的天文數字也「只不過」是一個從當前盤面出發，每次只考慮2種走法，持續64步之後的可能性空間的大小。對於國際象棋和圍棋這樣的複雜棋類，從初始盤面出發窮盡所有變化的複雜度(也稱窮舉複雜度)更是大得難以想像。信息論創始人克勞德香農在1950年第一個估計出國際象棋的窮舉複雜度大概在10^120種變化左右，具體數字被後人稱為「香農數」。而圍棋的窮舉複雜度又遠遠超出國際象棋，達到了驚人的10^360。作為比較，目前可觀測宇宙中的原子總數據估計「只有」10^75個。
有人會問，為了分析當前盤面一定要窮舉所有未來走勢的可能性嗎?有沒有可能存在一個高效的算法可以在避免遍歷呈指數級增長的可能性空間的同時仍然對當前盤面做出準確評估呢?答案是，對於國際象棋和圍棋，我們可以從數學上證明，不僅僅是窮舉複雜度，其局勢變化的計算複雜度也必須隨所考慮的步數呈指數級增長!對於任意一個給定的盤面，我們定義這個盤面的「最優值」為當博弈雙方都下出「完美走法」的情況下導致的最終博弈結果。如果一個盤面的最優值是「黑棋勝」，那就是說在黑棋自己不出錯的情況下白棋無論如何努力都是必敗的。理論計算機科學家先後在1981年和1983年證明國際象棋和圍棋都屬於EXPTIME-Complete類問題，這意味着「任何」能正確計算盤面最優值的方法所花費的時間「必然」隨棋盤大小(亦或棋局的平均步數)呈指數級增長。事實上大部分流行的「雙人零和」棋類的計算複雜度都是指數級的。有一些棋類如西洋跳棋、五子棋，它們的規模足夠小，所以其初始盤面的最優值已經被計算出來了。但是像國際象棋和圍棋這樣的複雜棋類，計算其初始盤面的最優值，以現在的硬件計算能力看來還遙遙無期。
局面動態評估：「激進」與「保守」之間的平衡取捨
主流的國際象棋程序往往採用一種比較「保守」的局勢篩選策略，搭配一種比較「激進」的信息匯總策略。而主流的圍棋程序則正好相反，在局勢篩選方面相當「大膽」，卻對從這些局勢變化收集來的信息的使用相當「謹慎」。這主要是由於目前對這兩種棋類的盤面靜態評估的質量不同導致的。
對於國際象棋，已經找到了一種在「很多情況」下可以既快速又相對準確地對盤面進行靜態評估的方法——當遇到這類「大致可以進行靜態評估」的盤面時，這個靜態評估方法有相當的可信度，而對於其他情況的盤面卻完全不起作用。由於擁有這樣一個具有「部分可靠性」的靜態評估，國際象棋程序的策略「從概念上」可以理解為是對從當前盤面出發的每一種可能的變化都不停向前展開，直到遇到一個可以大致靜態評估的盤面或者超出了一個預定的「最大展開步數」為止。這樣的「保守」選擇策略使得計算機對於一定階段之內的所有變化都有了大致評估。接下來計算機在「假設」這些評估是正確的前提下，計算按照完美下法哪一種變化是最優的。
根據硬件計算能力，計算機還會設定一個「最小展開步數」，即使一個變化在展開不到最小步數時就遇到了一個「比較好評估的局面」，系統依然會繼續往前看，而不會就此停止。這是為了最大限度地彌補「對比較好評估的局面進行靜態評估時依然有可能出錯」的缺陷。在開發第一個人類大師級水平的計算機「Belle」的過程中，人們發現弈棋計算機的最小展開步數越大，其棋力越強。也就是說，原則上只要通過不斷增強硬件的計算能力，國際象棋機器就可以通過看得越來越深而下得越來越好。
1997年的「深藍」計算機在配備了400多塊專門設計的硬件加速卡之後，獲得了每秒鐘展開並評估2億次盤面的恐怖計算能力，歷史上第一次代表機器戰勝了人類國際象棋冠軍。在隨後的十幾年裏，按照「摩爾定律」增長的計算機硬件能力變得愈加強大，計算機又先後多次戰勝人類國際象棋冠軍。越來越多的人相信，機器在國際象棋領域早已超越了人類的弈棋能力。
然而，計算機能夠戰勝人類國際象棋冠軍並不全靠超強的硬件計算能力，軟件算法方面的持續改進同樣必不可少，甚至影響更大。
比如上面提到，國際象棋系統在「概念上」窮盡了一定步數之內的所有變化。但在真實的弈棋計算機中，一系列優化算法使得系統在不完全展開某些變化的同時也能夠得到和完全展開一樣(或類似)的效果。這樣節省下來的時間可以用於把已知變化「看得更深」，從而極大提高了系統在「概念上」的等效計算能力。
其中最經典的例子是由人工智能先驅約翰·麥卡錫提出的αβ剪枝法，它巧妙利用了「國際象棋是雙人零和遊戲」的特點，以最優的方式避免所有不必要的變化展開。
根據計算機科學家唐納德·克努特(Donald Knuth)的數學分析，在理想情況下，αβ剪枝法僅需評估所有b^d個變化中的b^(d/2)個，就可以保證得到和評估所有b^d個變化完全一樣的結果。換句話說，我們需要增加倍硬件計算能力才能使動態評估加深一步，而使用αβ剪枝法則可以使動態評估輕鬆增加整整一倍的「思考深度」*2!
αβ剪枝法成型於20世紀60年代，是國際象棋弈棋的諸多優化算法里最經典的一種。如今的國際象棋程序中還使用了大量其他優化方法，使得實際的動態評估過程遠遠比簡單的「枚舉」要高效得多，只是「從概念上」，它們從評估質量上等效(或接近)於一次對未來若干步內所有局勢變化的窮舉展開而已。
αβ剪枝法的一個簡單示例。
假設A盤面下我方行動，並試圖最大化我方勝率;而B盤面下對手行動，並試圖最小化我方勝率。如果A代表當前盤面，而B代表我方走了某一步之後到達的新盤面。現在假設已知B盤面下對手存在一種走法使得我方勝率至多有30%，同時已知A盤面下我方存在一種走法使得我方勝率至少有40%，那麼我們已經可以確定無需再檢查B盤面下其他未展開的變化了。在層層展開的動態評估過程中這樣的「剪枝」可以反覆使用，從而大量減少需要實際評估的變化數量。
國際象棋的動態評估方法(或其變種)也廣泛應用於大多數其他棋類的對弈系統，其中很多達到或超越了人類冠軍的水平。然而，這套思路卻在圍棋博弈中遭遇了滑鐵盧。截至目前，沒有一個基於國際象棋的動態評估思路的圍棋系統可以超過人類業餘入門級水平。很多人把這一失敗歸因於圍棋比國際象棋更大的計算複雜度(這當然看起來是最明顯的原因之一)。
但是，根據許峰雄博士在2007年發表的那篇名為「Cracking GO」(破解圍棋)的文章，在擁有接近國際象棋的靜態評估質量的前提下，我們完全可以在軟件和硬件兩方面進行一系列優化，使得國際象棋的動態評估方法在圍棋中也達到類似的思考深度。如果我們假設圍棋大師們的智力並不顯著高於國際象棋大師的話，這樣的思考深度也許會使機器在圍棋上再次戰勝人類。也就是說，對於當今的硬件能力，圍棋的複雜度並不是不可逾越的鴻溝。那麼，到底是什麼原因導致國際象棋的策略無法適用於圍棋呢?
筆者的觀點是，「窮舉型」策略*3至今未在圍棋中廣泛應用，更大的障礙恐怕還是缺少一個像國際象棋那樣能夠對於「一大類」盤面進行「大致準確的評估」的方法。前面介紹靜態評估方法的部分已經提到了，目前圍棋盤面的靜態評估方法一般只在棋局前期黑白雙方尚未「短兵相接」時有一定效果。當棋局進入關鍵的中盤廝殺之後，如果仍然使用現有的靜態評估方法，我們就會發現：在達到硬件計算能力可承受的最大預判步數時，大部分棋局變化都處於不能「大致準確評估」的狀態。基於這些十分不「靠譜」的評估結果去考慮所謂「完美」走法，得到的結果自然也是不大靠譜的。
正是由於缺少「靠譜」的靜態評估方法，目前所有頂級圍棋程序轉而採取一種比較「謹慎」的信息匯總策略。
在國際象棋中，如果一個盤面有兩種走法，一個估計勝率30%，另一個估計勝率80%(如圖(a)中盤面B所示)，計算機會傾向於相信這些結果都是大概「靠譜」的，因此該盤面自身的勝率應該等於所有走法中的最優結果(我方盤面取最大值，對手盤面取最小值)，因此認為盤面B的勝率是30%。這是一種比較「激進」的信息匯總策略：當發現了30%勝率的走法時，系統會完全丟棄80%勝率的走法所帶來的信息，選擇全部相信30%勝率的走法。
相同情況下的不同信息匯總策略。(a)為以國際象棋程序為代表的「激進」策略，取最大(小)值為匯總結果;(b)～(d)為以圍棋程序為代表的「保守」策略，取加權平均值為匯總結果。其中(b)對應評估初期等權重下的結果，如果其中30%的靜態評估正確，則算法經過150次蒙特卡洛採樣後會導向(c)所示結果，否則會導向(d)所示結果。
而在圍棋程序中，計算機認為對每個盤面的直接靜態評估結果都是不可靠的，但是相信「對該盤面下所有走法的全部評估結果」卻整體上仍然對該盤面的勝率具有指向性。現有圍棋程序一般採用對所有評估結果進行加權平均的方式來體現這種指向性，其中「權重」基於對當前評估結果的可信度進行設定。舉例來說。在圖(b)中，假設對盤面B下兩種走法所直接導致的盤面進行靜態評估的結果勝率分別為30%和80%，而盤面C下的兩種走法勝率分別為50%和40%。因為這4個估計值可能都存在偏差，所以我們並不偏信其中任何一個;另一方面，在偏差沒有系統性地倒向「某一類盤面」或「某一類走法」的前提下，我們有理由相信這4個盤面評估結果具有相同的可信度(或「不可信度」)，因此應該具有相同的權重。所以在只知道這4個靜態評估結果的情況下，我們認為盤面B的評估勝率是0.5×30%+0.5×80%=55%，盤面C的評估勝率是0.5×50%+0.5×40%=45%。同時，這樣做出的對B和C的判斷自身仍然有可能存在偏差，所以在以盤面B和C為基礎再評估盤面A時也要考慮到這一點，因此A的評估結果同樣是B和C的結果的再次加權平均0.5×45%+0.5×55%=50%。
我們看到，這樣根據等權重得到的對A的評估結果實際上是綜合了所有當前已知信息之後給出的一個「模稜兩可」的評估。考慮到「已知信息」本質上的低可靠度，這也許就是我們在這種情況下「應該」得到的答案。當然，這樣一個僅僅基於4次靜態評估的結果並不是計算機給出的最終答案。對於一個給定盤面，我們考察的變化越多，獲取的信息量也越大，因此對這個盤面的評估值也傾向於更可靠，從而這個評估值在參與加權平均時也理應獲得更大的權重。換句話說，我們根據對一個盤面「深思熟慮」的程度來量化對其評估結果的「可信度」，認為一個進行大量分析後得到的評估結果在可信度上優於分析較少的評估結果。這就涉及到如何選擇那些需要進一步深思熟慮的變化的問題。
有意思的是，在採取較為謹慎的信息匯總策略的同時，圍棋程序在局勢變化的選擇策略上卻相當「大膽」。如果說國際象棋程序希望考察在一定階段內的所有變化，那麼圍棋程序卻只通過對所有這些變化進行某種有策略的採樣來進行評估，把更多的時間精力投入到那些「看似」更有希望的變化上。這就是被稱為蒙特卡洛樹搜索的動態評估方法。這種方法在「從當前盤面出發所有有可能的局勢變化」組成的巨大可能性空間中進行反覆採樣。通過巧妙設計的選擇策略，配合前面所說的基於加權平均值的信息匯總策略，計算機會根據已有的採樣結果調整新一輪採樣所選擇的變化，從而保證最優走法逐漸獲得更多的選擇機會，因此獲得更大的權重。這樣的長期結果是，大量採樣之後對當前盤面下所有走法的「加權平均」結果會逐漸逼近當前盤面的最優值!
仍然回到圖10的例子。我們看到圖(b)中基於4次靜態評估的加權平均結果高於圖(a)中按照傳統國際象棋思路得到的結果，這主要是因為我們對當前勝率評估為30%的這個盤面「不大信任」導致的。在接下來的動態評估採樣中有兩種可能：(1)當前的30%的評估結果是正確的，在這種情況下蒙特卡洛樹搜索算法對盤面B下的變化採樣會更傾向於30%這個走法，因此B的評估值會逐漸下降到接近30%，而這又會導致B的評估值低於C，因此C獲得更多採樣機會，從而在對A的加權平均評估時獲得比B更大的權重。如圖(c)所示，在150次採樣之後，A的評估值接近C，而C的評估值接近40%——這和圖(a)的評估結果一致(因為當初30%的靜態評估結果恰好是正確的!)。(2)如果圖(b)中30%的結果是錯誤的，假設機器經過對這個走法進一步考察(75次採樣)後發現它的勝率其實應該是80%。這種情況下，B的評估值會逐漸上升到80%，而這導致B相對於A的權重變高，因此A的評估值也隨之上升，從而得到和前面不一樣的最終評估結果。
總而言之，目前的主流圍棋程序試圖用一種系統性的方法去「管理」在評估過程中不可避免帶來的「不確定性」。截至目前，所有一流的圍棋程序全部採用蒙特卡洛樹搜索方法進行盤面動態評估////4。它們從基本「思維模式」和局面勝率評估的「基本框架」上繼承了以國際象棋弈棋計算機為代表的傳統方法;同時，採用蒙特卡洛採樣思想來進一步管理知識中的「不確定性」，在選擇策略上化保守為激進，在匯總策略上化激進為保守，在無法對變幻莫測的圍棋盤面進行有效靜態評估的情況下仍然達到了業餘高級水平的棋力。
弈棋計算機是人工智能嗎？
弈棋是一種刺激性極強的直接對抗。計算機弈棋代表了一種機器對人類的「符號意義上」的挑戰，因而備受關注。「人類弈棋大師在整體智力上超出常人」這一事實，也使得「計算機在弈棋上向人類高手發起的挑戰」被很自然地認作是一種關乎「智力極限」的挑戰。
那麼，從人工智能的角度，我們應該如何看待弈棋系統及其相關的研究活動呢?
首先我們應該意識到，被我們視為智力挑戰的問題，機器做起來往往未必困難;反而是一些人類覺得稀鬆平常的腦力活動，機器實現起來卻可能非常困難。比如速算曾經同樣是智力超群的象徵，但是現代計算機無論在計算速度還是準確率上都毫無爭議地完勝人類。要理性衡量計算機弈棋與人工智能的關係，還要對照上期我們總結的人工智能的主要特徵來分析。
根據人工智能的主要特徵，雖然弈棋滿足了智能行為的標準，但目前的所有計算機弈棋系統都不滿足通用性要求，因此還不能算是完整的人工智能系統。考慮到國際象棋領域裏一台「不算完整人工智能系統」的機器已經戰勝了人類，那麼當圍棋機器戰勝人類的那一天到來的時候，也未必就意味着什麼人工智能新時代的開始。
然而，「弈棋系統本身不是人工智能系統」不代表「弈棋系統研究不是人工智能研究」。棋類運動被稱為是人工智能領域的「果蠅」，我們對果蠅進行研究，根本目的並不是為了製造一個「更強壯的果蠅」，而是為了以此探索一些具有普遍性的生物系統規律，幫忙我們認識和研究比果蠅更複雜的生物系統。在筆者看來，弈棋系統研究在人工智能方面的意義主要有兩個，第一個是為相關的自動推理/規劃、自動學習、知識表示等等人工智能技術提供實驗場所，第二個就是為打敗人類而發明的如「推演」和「規劃」部分的相關技術在通用智能中的推廣和應用。
最後，一個經常被提及的話題是關於如何對待人類領域知識在弈棋系統中的作用。有些人認為，使用了「人類職業棋手」的知識的弈棋系統有「作弊」之嫌，認為弈棋系統只有「零知識」才算真本領。筆者認為沒有必要苛求於此。所謂名師出高徒，有幾個人類冠軍是自學成才的?即使是職業棋手的知識也不一定是他自己想出來的，畢竟人類已經積累了上千年的領域知識。事實上，能夠積累、運用和傳授知識正是人類智能最厲害的地方之一，而「知識表示與管理」也是通用人工智能系統的必要組成部分。
另一方面，「形式化人類領域知識」也並不是「顯然可行」的事情。國際象棋方面，是在深藍成功之後才真正證明國際象棋大師的經驗「可以」形式化表達(深藍團隊在這方面做了大量工作)，而圍棋盤面靜態評估甚至至今尚未找到有效形式化的方法。可以說，針對圍棋弈棋的研究在知識表示上尚處於努力證明「可以形式化」的階段;而與此同時，「通用博弈比賽」相關的研究則已經開始對「統一化的知識表示」的初步探索。
有意思的是，在採取較為謹慎的信息匯總策略的同時，圍棋程序在局勢變化的選擇策略上卻相當「大膽」。如果說國際象棋程序希望考察在一定階段內的所有變化，那麼圍棋程序卻只通過對所有這些變化進行某種有策略的採樣來進行評估，把更多的時間精力投入到那些「看似」更有希望的變化上。這就是被稱為蒙特卡洛樹搜索的動態評估方法。這種方法在「從當前盤面出發所有有可能的局勢變化」組成的巨大可能性空間中進行反覆採樣。通過巧妙設計的選擇策略，配合前面所說的基於加權平均值的信息匯總策略，計算機會根據已有的採樣結果調整新一輪採樣所選擇的變化，從而保證最優走法逐漸獲得更多的選擇機會，因此獲得更大的權重。這樣的長期結果是，大量採樣之後對當前盤面下所有走法的「加權平均」結果會逐漸逼近當前盤面的最優值!
仍然回到圖10的例子。我們看到圖(b)中基於4次靜態評估的加權平均結果高於圖(a)中按照傳統國際象棋思路得到的結果，這主要是因為我們對當前勝率評估為30%的這個盤面「不大信任」導致的。在接下來的動態評估採樣中有兩種可能：(1)當前的30%的評估結果是正確的，在這種情況下蒙特卡洛樹搜索算法對盤面B下的變化採樣會更傾向於30%這個走法，因此B的評估值會逐漸下降到接近30%，而這又會導致B的評估值低於C，因此C獲得更多採樣機會，從而在對A的加權平均評估時獲得比B更大的權重。如圖(c)所示，在150次採樣之後，A的評估值接近C，而C的評估值接近40%——這和圖(a)的評估結果一致(因為當初30%的靜態評估結果恰好是正確的!)。(2)如果圖(b)中30%的結果是錯誤的，假設機器經過對這個走法進一步考察(75次採樣)後發現它的勝率其實應該是80%。這種情況下，B的評估值會逐漸上升到80%，而這導致B相對於A的權重變高，因此A的評估值也隨之上升，從而得到和前面不一樣的最終評估結果。
總而言之，目前的主流圍棋程序試圖用一種系統性的方法去「管理」在評估過程中不可避免帶來的「不確定性」。截至目前，所有一流的圍棋程序全部採用蒙特卡洛樹搜索方法進行盤面動態評估////4。它們從基本「思維模式」和局面勝率評估的「基本框架」上繼承了以國際象棋弈棋計算機為代表的傳統方法;同時，採用蒙特卡洛採樣思想來進一步管理知識中的「不確定性」，在選擇策略上化保守為激進，在匯總策略上化激進為保守，在無法對變幻莫測的圍棋盤面進行有效靜態評估的情況下仍然達到了業餘高級水平的棋力。
蒙特卡洛樹搜索法
使用蒙特卡羅方法估算π值。圖/維基百科
選取的隨機點(n)越多，估計值離π的真值越近。圖/維基百科
這種選擇很大程度上跟現有圍棋弈棋系統對盤面靜態評估方法的整體捨棄有關。前面提到，由於人們在設計具有一定通用性的圍棋盤面靜態評估函數的問題上長期止步不前，大概在2002年之後人們開始思考採用另一種完全不同的方式對盤面進行快速評估，這就是蒙特卡洛採樣。
做為一種通用的計算方法，蒙特卡洛採樣法的思想是當我們在求解一個確定但未知的值的時候，「在概念上」巧妙構造一個隨機過程，使得這個隨機過程的某個數字特徵依概率收斂於我們要求的值，然後「在實際操作中」通過對該隨機過程進行採樣來對這個值進行統計估計。
比如說，一種計算圓周率////的蒙特卡洛方法是，在一個二維坐標系中////和////對應的方形區域裏隨機選取若干個點，並判斷每個點////是否落在「以原點為圓心半徑為1的單位圓」內(也即判定////是否小於1)。根據中心極限定理，這些隨機點落在單位圓內的比例依大概率快速趨於////。所以我們選取的隨機點數量越多，越有可能得到的一個離的真值更接近的估計。
相同的「蒙特卡洛」思想也可以用於圍棋盤面評估。前面提到了，每個圍棋盤面都有一個「最優值」，對應於對弈雙方都採用完美走法的情況下該盤面的最終結果。對於圍棋已經證明，計算這個最優值的時間至少隨該盤面到終盤之間的步數呈指數級數增長(平均200步，每步平均增長200倍數量的可能盤面)。既然從理論上無法得到最優值，有沒有可能根據蒙特卡洛思想對整個可能性空間進行某種採樣，然後通過統計估值的方法逼近這個最優值呢?人們對這個問題的思考在2006年終於取得了突破性進展，提出了一種稱為蒙特卡洛樹搜索的動態評估方法。
需要指出的是，現有的蒙特卡洛樹搜索法雖然能保證大量採樣的結果最終收斂到盤面最優值，但為達到「足夠收斂」所需的採樣次數仍然是隨整個可能性空間的規模指數級增長的。但是在圍棋弈棋系統的實踐中，蒙特卡洛樹搜索在比賽時間受限的情況下確實表現出遠遠超過傳統方法的棋力。最近幾年人們受這一觀察的鼓舞，在選擇策略中加入更多和圍棋相關的專家知識，使得基於蒙特卡洛樹搜索的圍棋弈棋系統水平不斷提高。
弈棋計算機是人工智能嗎？
弈棋是一種刺激性極強的直接對抗。計算機弈棋代表了一種機器對人類的「符號意義上」的挑戰，因而備受關注。「人類弈棋大師在整體智力上超出常人」這一事實，也使得「計算機在弈棋上向人類高手發起的挑戰」被很自然地認作是一種關乎「智力極限」的挑戰。
那麼，從人工智能的角度，我們應該如何看待弈棋系統及其相關的研究活動呢?
首先我們應該意識到，被我們視為智力挑戰的問題，機器做起來往往未必困難;反而是一些人類覺得稀鬆平常的腦力活動，機器實現起來卻可能非常困難。比如速算曾經同樣是智力超群的象徵，但是現代計算機無論在計算速度還是準確率上都毫無爭議地完勝人類。要理性衡量計算機弈棋與人工智能的關係，還要對照上期我們總結的人工智能的主要特徵來分析。
根據人工智能的主要特徵，雖然弈棋滿足了智能行為的標準，但目前的所有計算機弈棋系統都不滿足通用性要求，因此還不能算是完整的人工智能系統。考慮到國際象棋領域裏一台「不算完整人工智能系統」的機器已經戰勝了人類，那麼當圍棋機器戰勝人類的那一天到來的時候，也未必就意味着什麼人工智能新時代的開始。
然而，「弈棋系統本身不是人工智能系統」不代表「弈棋系統研究不是人工智能研究」。棋類運動被稱為是人工智能領域的「果蠅」，我們對果蠅進行研究，根本目的並不是為了製造一個「更強壯的果蠅」，而是為了以此探索一些具有普遍性的生物系統規律，幫忙我們認識和研究比果蠅更複雜的生物系統。在筆者看來，弈棋系統研究在人工智能方面的意義主要有兩個，第一個是為相關的自動推理/規劃、自動學習、知識表示等等人工智能技術提供實驗場所，第二個就是為打敗人類而發明的如「推演」和「規劃」部分的相關技術在通用智能中的推廣和應用。
最後，一個經常被提及的話題是關於如何對待人類領域知識在弈棋系統中的作用。有些人認為，使用了「人類職業棋手」的知識的弈棋系統有「作弊」之嫌，認為弈棋系統只有「零知識」才算真本領。筆者認為沒有必要苛求於此。所謂名師出高徒，有幾個人類冠軍是自學成才的?即使是職業棋手的知識也不一定是他自己想出來的，畢竟人類已經積累了上千年的領域知識。事實上，能夠積累、運用和傳授知識正是人類智能最厲害的地方之一，而「知識表示與管理」也是通用人工智能系統的必要組成部分。
另一方面，「形式化人類領域知識」也並不是「顯然可行」的事情。國際象棋方面，是在深藍成功之後才真正證明國際象棋大師的經驗「可以」形式化表達(深藍團隊在這方面做了大量工作)，而圍棋盤面靜態評估甚至至今尚未找到有效形式化的方法。可以說，針對圍棋弈棋的研究在知識表示上尚處於努力證明「可以形式化」的階段;而與此同時，「通用博弈比賽」相關的研究則已經開始對「統一化的知識表示」的初步探索。
