電腦是如何下棋的：深入了解人工智能(2)

局面靜態評估好比人類棋手的“感覺”(也叫“第一感”、“棋感”)。

目前使用的方法很容易理解。就像網上經常遇到的性格測試：讓一個人做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類問題，這意味“任何”能正確計算盤面最優值的方法所花費的時間“必然”隨棋盤大小(亦或棋局的平均步數)呈指數級增長。事實上大部分流行的“雙人零和”棋類的計算複雜度都是指數級的。有一些棋類如西洋跳棋、五子棋，它們的規模足夠小，所以其初始盤面的最優值已經被計算出來了。但是像國際象棋和圍棋這樣的複雜棋類，計算其初始盤面的最優值，以現在的硬件計算能力看來還遙遙無期。

[2]