圍棋起源于中國(guó)，是最古老的棋類(lèi)運(yùn)動(dòng)之一，我們常說(shuō)的“琴棋書(shū)畫(huà)”中的“棋”就是指圍棋。

圍棋盤(pán)由19條橫線(xiàn)和19條豎線(xiàn)組成，共有19 19＝361個(gè)交叉點(diǎn)。此外，也有13 13、9 9的小棋盤(pán)。圍棋子分為黑白兩色，對(duì)弈雙方各執(zhí)一種顏色的棋子，輪流將一枚棋子下在交叉點(diǎn)上。終局時(shí)，占領(lǐng)(圍起)的“地盤(pán)”(即其中的交叉點(diǎn)個(gè)數(shù))多的一方獲勝。

空白的交叉點(diǎn)稱(chēng)為“目”，圍到的地盤(pán)又稱(chēng)為“空”。對(duì)弈過(guò)程中，棋手經(jīng)常會(huì)“數(shù)目”，也就是計(jì)算雙方目前所圍的“空”的大小，以此判斷形勢(shì)優(yōu)劣。

對(duì)弈雙方的水平差距較大時(shí)，常會(huì)采用讓子棋的方式，也就是水平較弱的一方先在棋盤(pán)的固定位置放上1～9個(gè)子(分別稱(chēng)為讓先、讓二子、讓三子……)，然后雙方再輪流落子。

本文轉(zhuǎn)自《科學(xué)世界》

你喜歡下棋嗎？有沒(méi)有和計(jì)算機(jī)下過(guò)？現(xiàn)在，弈棋計(jì)算機(jī)的棋藝日益高強(qiáng)。讓我們通過(guò)分析以圍棋和國(guó)際象棋為代表的弈棋計(jì)算機(jī)，對(duì)人工智能的研究有一個(gè)更為深入的理解。

弈棋計(jì)算機(jī)

弈棋自古被視為一種關(guān)乎智力的高級(jí)挑戰(zhàn)。和其他智力測(cè)試相比，弈棋具有直接對(duì)抗的特點(diǎn)，沒(méi)有什么比在緊張的對(duì)局中看到對(duì)手一手精妙兇狠的棋招更能讓人感覺(jué)到一種智力上的刺激和挑戰(zhàn)了。弈棋相比于其他牌類(lèi)游戲而言，隨機(jī)和不可控因素更小，因此對(duì)局雙方的決策能夠更直接地控制整個(gè)局面的走勢(shì)，這進(jìn)一 步增強(qiáng)了智力的對(duì)抗性。

毫不意外，在國(guó)際象棋更加流行的西方國(guó)家，人工智能領(lǐng)域自創(chuàng)建之初就在考慮如何制造一個(gè)會(huì)下國(guó)際象棋的機(jī)器。幾乎所有人工智能先驅(qū)，包括信息論 創(chuàng)始人香農(nóng)、“人工智能”之父約翰·麥卡錫(John  McCarthy)、計(jì)算機(jī)科學(xué)創(chuàng)始人圖靈，都曾嚴(yán)肅思考過(guò)制造國(guó)際象棋機(jī)器的問(wèn)題。20世紀(jì)80年代初，貝爾實(shí)驗(yàn)室的工程師們(其中包括著名操作系統(tǒng) Unix的聯(lián)合創(chuàng)作者肯·湯姆森)開(kāi)發(fā)出歷史上第一個(gè)具有人類(lèi)大師級(jí)水平的國(guó)際象棋機(jī)器“Belle”。到80年代末，卡內(nèi)基梅隆大學(xué)的許峰雄博士在 “Bella”的思路基礎(chǔ)上(將在后面詳細(xì)介紹)進(jìn)一步改進(jìn)，研制出了第一個(gè)特級(jí)大師水平的國(guó)際象棋機(jī)器，取名“深思”(源自《銀河系漫游指南》中的超級(jí) 計(jì)算機(jī))。隨后，許博士加入IBM研究院，在那里和其他幾個(gè)團(tuán)隊(duì)成員一起研制出了實(shí)力更強(qiáng)的弈棋機(jī)器“深藍(lán)”，并最終于1997年的一場(chǎng)歷史性的人機(jī)大戰(zhàn) 中以3.5：2.5的比分戰(zhàn)勝了人類(lèi)國(guó)際象棋冠軍卡斯帕羅夫(卡斯帕羅夫不但是當(dāng)時(shí)的人類(lèi)冠軍，同時(shí)也是人類(lèi)歷史上國(guó)際象棋等級(jí)分最高的職業(yè)選手)。

在圍棋更加流行的東方，圍棋大師的頭銜同樣是智力超群的象征。自從計(jì)算機(jī)在國(guó)際象棋上挑戰(zhàn)人類(lèi)成功之后，所有人的目光就聚焦在了圍棋這項(xiàng)古老的 東方棋類(lèi)運(yùn)動(dòng)上。然而對(duì)計(jì)算機(jī)來(lái)說(shuō)，圍棋似乎是個(gè)比國(guó)際象棋更“難”的東西。1985年，企業(yè)家應(yīng)昌期先生懸賞一百萬(wàn)美金尋找能夠打敗人類(lèi)職業(yè)棋手的計(jì)算 機(jī)，可時(shí)至30年后的今日仍然沒(méi)有一臺(tái)計(jì)算機(jī)能夠做到。20世紀(jì)90年代，以我國(guó)陳志行教授開(kāi)發(fā)的“手談”程序以及著名開(kāi)源軟件組織GNU開(kāi)發(fā)的“GNU   Go”程序?yàn)榇淼?ldquo;計(jì)算機(jī)圍棋冠軍”們，棋力尚且不及人類(lèi)的業(yè)余初段。進(jìn)入21世紀(jì)之后，研究者們開(kāi)始探索一套被稱(chēng)為“蒙特卡洛樹(shù)搜索”的全新思路(將 在后面詳細(xì)介紹)，并終于在2006年在9 9的“小棋盤(pán)”上率先產(chǎn)生突破。以法國(guó)的MoGo和CrazyStone為代表的新一代圍棋程序在9路圍棋上 基本已經(jīng)達(dá)到人類(lèi)職業(yè)棋手的水平，甚至曾在公開(kāi)場(chǎng)合戰(zhàn)勝過(guò)職業(yè)棋手周俊勛九段。另一方面，在真正的19路圍棋棋盤(pán)上，以日本的ZEN(天頂圍棋)和法國(guó)的 CrazyStone為代表的一流圍棋程序沿著“蒙特卡洛方法”的思路不斷改進(jìn)，在和人類(lèi)頂尖職業(yè)棋手進(jìn)行的一系列讓子棋比賽中屢有佳績(jī)，而近些年人類(lèi)棋 手能“讓”計(jì)算機(jī)的子數(shù)也越來(lái)越少。最有趣的是在2013年，計(jì)算機(jī)程序CrazyStone在受讓四子的情況下戰(zhàn)勝被稱(chēng)為“人腦計(jì)算機(jī)”的日本棋手石田 芳夫九段，并被認(rèn)為已有業(yè)余五～六段的水平。

截至目前，盡管計(jì)算機(jī)在公平的圍棋比賽中還不足以直接抗衡人類(lèi)職業(yè)棋手，但相關(guān)的研究熱度卻很高，大家普遍對(duì)近期前景持較為樂(lè)觀的態(tài)度。“深藍(lán) 之父”許峰雄博士甚至在2007年10月的一期《IEEE Spectrum》雜志上表示，相信10年內(nèi)超級(jí)計(jì)算機(jī)將能挑戰(zhàn)世界冠軍級(jí)別的人類(lèi)棋手。

(框文)【圍棋

圍棋起源于中國(guó)，是最古老的棋類(lèi)運(yùn)動(dòng)之一，我們常說(shuō)的“琴棋書(shū)畫(huà)”中的“棋”就是指圍棋。

(圖)【左為唐代《圍棋仕女圖》絹畫(huà)，1972年出土于吐魯番阿斯塔那；右為隋代白釉瓷圍棋盤(pán)，1959年出土于河南安陽(yáng)。圖/維基百科】

(圖)】

計(jì)算機(jī)下棋的思考模式

現(xiàn)在主流弈棋計(jì)算機(jī)的基本“思考模式”很簡(jiǎn)單，就是對(duì)當(dāng)前局面下的每一種合法走法所直接導(dǎo)致的局面進(jìn)行評(píng)估，然后選擇“獲勝概率”最高的局面所對(duì)應(yīng)的那個(gè)走法。也就是說(shuō)，“準(zhǔn)確評(píng)估給定局面的勝率”是主流弈棋計(jì)算機(jī)的核心問(wèn)題，同時(shí)也是主要難點(diǎn)所在。在進(jìn)一步深入討論這一核心技術(shù)問(wèn)題之前，我們先在基本思考模式層面簡(jiǎn)單比較一下計(jì)算機(jī)棋手與人類(lèi)棋手的異同。

可以說(shuō)，計(jì)算機(jī)的基本策略是所有“人類(lèi)有可能采用”的策略中最原始最簡(jiǎn)單的一種。毫無(wú)疑問(wèn)，人類(lèi)的思考模式中必然也包含“局面評(píng)估”的部分，然而人類(lèi)至少還同時(shí)擁有另一個(gè)重要的思考模式——戰(zhàn)略性思考，也就是把一個(gè)基本目標(biāo)有效分解成一系列“子目標(biāo)”。

以圍棋為例，“獲勝”是圍棋的最終目的，而勝的定義是“結(jié)束比賽時(shí)擁有更多棋子和空”(中國(guó)規(guī)則)。但是人類(lèi)棋手在對(duì)弈時(shí)顯然并不是每時(shí)每刻都在基于這個(gè)“勝”的定義進(jìn)行思考的——通常我們只在棋局進(jìn)入中后期時(shí)才經(jīng)常性地“數(shù)目”。在對(duì)弈的大部分時(shí)間里我們是在思考諸如“如何借助右上角黑棋的毛病擴(kuò)張”、“如何做活”、“如何侵消對(duì)手的模樣”、“如何在劫爭(zhēng)中轉(zhuǎn)換”、“如何分?jǐn)?rdquo;等等一系列具體問(wèn)題。我們注意到，每一個(gè)這樣的“具體問(wèn)題”實(shí)際上是改變了思考的目標(biāo)，把一個(gè)“求勝”的問(wèn)題轉(zhuǎn)化成了一系列“分?jǐn)?rdquo;或者“做活”之類(lèi)的子問(wèn)題。這樣的一個(gè)“戰(zhàn)略計(jì)劃”，其背后的邏輯當(dāng)然是，我們的大腦相信在當(dāng)前情況下“分?jǐn)鄬?duì)手大龍”是最有可能導(dǎo)致最終贏棋的子目標(biāo)。一旦確立了子目標(biāo)，人類(lèi)棋手便集中精力考慮具體戰(zhàn)術(shù)走法來(lái)完成這個(gè)子目標(biāo)，而不是“贏棋”這個(gè)最終目標(biāo)。與之不同的是，目前主流的弈棋計(jì)算機(jī)從基本思考模式上并不依賴(lài)于“生成并確定子目標(biāo)”的戰(zhàn)略能力。在大多數(shù)時(shí)刻，這些弈棋計(jì)算機(jī)只關(guān)心一個(gè)問(wèn)題，就是按照“勝”的基本定義來(lái)贏得比賽////1。“在當(dāng)前局面下，我走在x點(diǎn)的話(huà)最終能贏幾子”，計(jì)算機(jī)就是通過(guò)不停地重復(fù)問(wèn)自己這個(gè)問(wèn)題來(lái)完成對(duì)弈的。盡管這聽(tīng)起來(lái)很“原始”，但正如前面所說(shuō)，這樣思考的計(jì)算機(jī)卻已經(jīng)在很多棋類(lèi)中達(dá)到了相當(dāng)令人驚訝的水平！

現(xiàn)在我們回到“評(píng)估局面勝率”這一計(jì)算機(jī)弈棋的核心問(wèn)題上。主流方法中一次局面評(píng)估通常由被稱(chēng)為“靜態(tài)評(píng)估”和“動(dòng)態(tài)評(píng)估”的兩個(gè)部分協(xié)同配合完成。

基于“特征識(shí)別”的靜態(tài)評(píng)估

黑方影響的區(qū)域 | 白方影響的區(qū)域

對(duì)圍棋局面基于“粒子-場(chǎng)”模型的靜態(tài)評(píng)估結(jié)果

局面靜態(tài)評(píng)估好比人類(lèi)棋手的“感覺(jué)”(也叫“第一感”、“棋感”)。

目前使用的方法很容易理解。就像網(wǎng)上經(jīng)常遇到的性格測(cè)試：讓一個(gè)人做10道選擇題，每道題如果選A加1分，選B不加分，然后根據(jù)10道題的總分對(duì)這個(gè)人的性格進(jìn)行分類(lèi)，0～2分的是黏液質(zhì)性格，8～10分的是多血質(zhì)性格…… 國(guó)際象棋的局面靜態(tài)評(píng)估過(guò)程和性格測(cè)試非常類(lèi)似，對(duì)于一個(gè)給定的局面(對(duì)應(yīng)性格測(cè)試?yán)锏囊粋€(gè)人)，評(píng)估算法問(wèn)“當(dāng)前局面里我方有沒(méi)有皇后”，有的話(huà)加10分，沒(méi)有不加分；再問(wèn)“有沒(méi)有兵”，有的話(huà)每個(gè)兵加1分，沒(méi)有不加分……然后評(píng)估算法把所有問(wèn)題的總分加起來(lái)，總分越高代表該局面勝率越大。

我們看到，計(jì)算機(jī)對(duì)國(guó)際象棋局面的靜態(tài)評(píng)估過(guò)程相當(dāng)于給局面做了一次測(cè)試卷，其中每一道測(cè)試題對(duì)應(yīng)了局面的一個(gè)特征。一般來(lái)說(shuō)，優(yōu)秀的國(guó)際象棋計(jì)算機(jī)所使用的“測(cè)試卷”中的每一道題都是由人類(lèi)大師根據(jù)自己多年的弈棋經(jīng)驗(yàn)精心設(shè)計(jì)的，而里面每道題的“分值”或者由象棋大師直接設(shè)定，或者由計(jì)算機(jī)根據(jù)海量棋譜通過(guò)被稱(chēng)為“機(jī)器學(xué)習(xí)”的技術(shù)自行決定。

前一種方法往往面臨的一個(gè)問(wèn)題是，人類(lèi)大師其實(shí)根本就不用這種“給局面做測(cè)試卷”的方式思考，所以他們的經(jīng)驗(yàn)有時(shí)很難直接指導(dǎo)分值設(shè)定。而在后一種基于機(jī)器學(xué)習(xí)技術(shù)的做法下，象棋大師除了設(shè)計(jì)用于評(píng)估局面的“考題”(每道題分值待定)之外，“只”需要對(duì)用于“訓(xùn)練”計(jì)算機(jī)的棋譜中出現(xiàn)的每一個(gè)局面打一個(gè)“局面總分”(這個(gè)總分并不基于大師為計(jì)算機(jī)設(shè)計(jì)的任何“考題”，而是直接根據(jù)自己的經(jīng)驗(yàn)得出)，計(jì)算機(jī)就可以自動(dòng)為每道考題選擇一個(gè)合適的分值，使得當(dāng)我們使用如此學(xué)習(xí)出來(lái)的分值去考察棋譜中的每個(gè)局面時(shí)，由“考卷”累加得到的分?jǐn)?shù)都恰好比較接近象棋大師根據(jù)經(jīng)驗(yàn)為該局面評(píng)估的分?jǐn)?shù)！

圍棋計(jì)算機(jī)程序使用的靜態(tài)評(píng)估過(guò)程一般也基于類(lèi)似的“打分原理”。只不過(guò)圍棋里面棋子的“位置特征”比“數(shù)量特征”更重要，所以圍棋程序在選取特征時(shí)往往并不基于單個(gè)棋子，而是基于由若干子組成的“基本形狀”。更重要的區(qū)別是，圍棋局面評(píng)估并不僅僅是把來(lái)自每個(gè)特征的得分簡(jiǎn)單相加，而是基于一些更復(fù)雜有趣的綜合過(guò)程。

比如，在這方面有一類(lèi)很有意思的研究叫做“基于動(dòng)態(tài)系統(tǒng)的圍棋局面評(píng)估”。這種觀點(diǎn)把圍棋棋盤(pán)看作一個(gè)二維“靜力場(chǎng)”，里面每一個(gè)棋子或每一個(gè)基本形狀擁有一個(gè)類(lèi)似于“電荷”的屬性，并根據(jù)這個(gè)屬性向外輻射“影響力”，強(qiáng)度隨著距離遞減。這樣，對(duì)于給定局面，棋盤(pán)中的每一個(gè)點(diǎn)都具有一個(gè)“場(chǎng)強(qiáng)”，它根據(jù)來(lái)自棋盤(pán)上所有黑子和白子的影響力相互疊加和抵消后決定。所有點(diǎn)的場(chǎng)強(qiáng)可以通過(guò)多輪迭代計(jì)算得出(類(lèi)似于物理中求解“多體問(wèn)題”的過(guò)程)，根據(jù)這些場(chǎng)強(qiáng)我們就可以決定對(duì)于棋盤(pán)中每一個(gè)點(diǎn)，黑白哪一方“勢(shì)力”更大。

從某種意義上講，基于動(dòng)態(tài)系統(tǒng)的圍棋局面評(píng)估實(shí)際就是在試圖建立一套“圍棋世界里的物理定律”，使得依據(jù)這些定律做出的判斷符合頂級(jí)高手間的實(shí)戰(zhàn)經(jīng)驗(yàn)，或甚至是符合“完美走法”下的結(jié)果。當(dāng)然，目前的“粒子-場(chǎng)”模型可能更多只是對(duì)我們所熟知的經(jīng)典力學(xué)模型的簡(jiǎn)單模仿，也許我們應(yīng)該基于一套完全不同的理論來(lái)描述圍棋棋盤(pán)里的天地(比如基于概率模型)，又或許從原則上根本不存在能夠精確描述局面走勢(shì)的“圍棋定律”…… 無(wú)論如何，對(duì)圍棋局面靜態(tài)評(píng)估的研究一旦產(chǎn)生突破，很有可能使得人類(lèi)對(duì)圍棋這項(xiàng)古老棋類(lèi)運(yùn)動(dòng)本身產(chǎn)生更深刻的理解，同時(shí)也會(huì)極大地改變圍棋弈棋計(jì)算機(jī)研究的現(xiàn)狀。

截至目前，對(duì)圍棋局面的靜態(tài)評(píng)估效果還遠(yuǎn)遠(yuǎn)比不上國(guó)際象棋，一般只對(duì)處于棋局初期的局面有一定作用，而對(duì)當(dāng)棋局進(jìn)入激烈廝殺后的中后盤(pán)，尚未找到有效的靜態(tài)評(píng)估方法。下面馬上就要提到，正是由于靜態(tài)評(píng)估部分的缺陷，直接導(dǎo)致了圍棋程序在“局面動(dòng)態(tài)評(píng)估”部分采用了一套與國(guó)際象棋程序差異很大的策略。

另外值得注意的是，在上述局面靜態(tài)評(píng)估的構(gòu)建過(guò)程中，機(jī)器作為一個(gè)“智能個(gè)體”，最多參與到特征的“權(quán)重”設(shè)定，而對(duì)于更重要的“應(yīng)該使用什么樣的特征”以及“根據(jù)什么方式對(duì)所有特征進(jìn)行整合”的問(wèn)題則完全由人類(lèi)專(zhuān)家負(fù)責(zé)?？梢哉f(shuō)，“特征自動(dòng)提取”一直是機(jī)器學(xué)習(xí)這個(gè)人工智能分支多年來(lái)的主要挑戰(zhàn)之一。后面還會(huì)再次提到這個(gè)問(wèn)題。

基于“預(yù)測(cè)分析”的動(dòng)態(tài)評(píng)估

如果說(shuō)對(duì)棋局盤(pán)面的靜態(tài)評(píng)估好比人類(lèi)棋手的“感覺(jué)”過(guò)程，那么動(dòng)態(tài)評(píng)估就好比人類(lèi)棋手的“推理”過(guò)程。在靜態(tài)評(píng)估中機(jī)器得益于人類(lèi)專(zhuān)家的很多幫助，而動(dòng)態(tài)評(píng)估的部分可是機(jī)器大顯身手的地方了。

簡(jiǎn)單講，“動(dòng)態(tài)評(píng)估”試圖對(duì)從當(dāng)前盤(pán)面出發(fā)“有可能”出現(xiàn)的大量局面變化所導(dǎo)致的結(jié)果進(jìn)行預(yù)判，并綜合分析所有這些可能性，對(duì)當(dāng)前盤(pán)面進(jìn)行一次評(píng)估。這也是人類(lèi)在動(dòng)態(tài)環(huán)境中做決策時(shí)經(jīng)常使用的策略，也就是希望通過(guò)“看得更遠(yuǎn)”來(lái)提前發(fā)覺(jué)潛在的危險(xiǎn)或機(jī)會(huì)。

經(jīng)過(guò)高度優(yōu)化的弈棋計(jì)算機(jī)每秒鐘可以計(jì)算數(shù)以?xún)|計(jì)的變化，即使是運(yùn)行在普通個(gè)人電腦上的弈棋程序也經(jīng)?？梢宰龅矫棵胗?jì)算幾十萬(wàn)種變化，這種高速運(yùn)算能力極大地彌補(bǔ)了計(jì)算機(jī)在靜態(tài)評(píng)估時(shí)的不足。對(duì)于像國(guó)際象棋和圍棋這種歷史悠久的復(fù)雜棋類(lèi)運(yùn)動(dòng)，只基于靜態(tài)評(píng)估的計(jì)算機(jī)程序通常連入門(mén)級(jí)業(yè)余棋手都未必下得過(guò)，而一旦配備了動(dòng)態(tài)評(píng)估能力之后，弈棋計(jì)算機(jī)卻能達(dá)到普通棋手甚至人類(lèi)世界冠軍都無(wú)法達(dá)到的水平。

盤(pán)面動(dòng)態(tài)評(píng)估可以說(shuō)是計(jì)算機(jī)弈棋領(lǐng)域的研究重點(diǎn)所在，幾十年來(lái)人工智能研究者和計(jì)算機(jī)科學(xué)研究者提出了許許多多的方法。這里我們簡(jiǎn)單介紹一些共通的基本原理，以及圍棋和國(guó)際象棋這兩個(gè)最受關(guān)注的棋類(lèi)的主流動(dòng)態(tài)評(píng)估方法。

基于一套給定規(guī)則，任意給定的棋局盤(pán)面會(huì)有一個(gè)“合法走法”的集合，其中每個(gè)走法都會(huì)把棋局引向一個(gè)新盤(pán)面，而這個(gè)新盤(pán)面又會(huì)有自己的另一個(gè)合法走法集合，每個(gè)走法又對(duì)應(yīng)一個(gè)新的盤(pán)面。如果假設(shè)每個(gè)盤(pán)面都有  種合法走法，那么從當(dāng)前盤(pán)面走一步之后一共有b種可能“到達(dá)”的盤(pán)面，兩步之后有b^2種可能盤(pán)面，三步之后有b^3種可能……如此展開(kāi)下去，從最初的給定盤(pán)面經(jīng)過(guò)d步之后可能到達(dá)b^d種不同的盤(pán)面，它們就是在“未來(lái)d步內(nèi)所有可能的局面變化”。

我們看到，從給定盤(pán)面開(kāi)始的局勢(shì)變化的復(fù)雜度是隨考慮的步數(shù)呈指數(shù)級(jí)增長(zhǎng)的。對(duì)于包括圍棋和國(guó)際象棋的絕大多數(shù)復(fù)雜棋類(lèi)運(yùn)動(dòng)而言，這意味著從原則上 不存在準(zhǔn)確  計(jì)算盤(pán)面的最優(yōu)結(jié)果的有效方法。不過(guò)，這對(duì)于對(duì)局雙方來(lái)說(shuō)未必是個(gè)壞消息——雖然我無(wú)法計(jì)算最優(yōu)解，對(duì)手也同樣無(wú)法計(jì)算。事實(shí)上一個(gè)游戲之所以成為游戲， 恰恰就是因?yàn)閷?duì)局雙方都相信對(duì)手不具備完美決策的能力，而自己要做的只是比對(duì)手 “錯(cuò)得更少一些”。

另一方面，對(duì)于弈棋計(jì)算機(jī)的設(shè)計(jì)者來(lái)說(shuō)，“不可能對(duì)局勢(shì)變化的所有可能性進(jìn)行有效計(jì)算”意味著想做得比對(duì)手更好需要從原理上解決兩個(gè)關(guān)鍵問(wèn)題： (1)決定一個(gè)“篩選策略”，從所有從當(dāng)前盤(pán)面出發(fā)有可能導(dǎo)致的變化中選擇一部分作為“我們實(shí)際考慮的那些局面變化”；(2)決定一個(gè)“匯總策略”，把所 有實(shí)際考慮的變化的靜態(tài)評(píng)估結(jié)果綜合起來(lái)，對(duì)當(dāng)前盤(pán)面的勝率完成評(píng)估。無(wú)論是國(guó)際象棋、中國(guó)象棋、圍棋、或者其他如西洋跳棋、黑白棋、五子棋，所有棋類(lèi)程 序的動(dòng)態(tài)評(píng)估方法從根本上都符合由“篩選策略”和“匯總策略”組成的基本框架。它們之間的區(qū)別僅在于使用的具體策略不同，以及由此產(chǎn)生的針對(duì)實(shí)現(xiàn)特定策略 的優(yōu)化手段的不同。

下面，我們就來(lái)看一下在最具代表性的國(guó)際象棋和圍棋中，弈棋計(jì)算機(jī)分別使用的兩套截然不同的動(dòng)態(tài)評(píng)估策略吧。

“指數(shù)級(jí)增長(zhǎng)”與“EXPTIME-Complete問(wèn)題”　

指數(shù)級(jí)增長(zhǎng)可算是大規(guī)模計(jì)算第一大“攔路虎”了。在一個(gè)著名的傳說(shuō)中，國(guó)際象棋的發(fā)明者印度人塞薩(Sessa)向他的國(guó)王請(qǐng)求賞賜，他說(shuō)，希望因?yàn)榘l(fā)明國(guó)際象棋棋盤(pán)的第一個(gè)格而得到一粒米，因?yàn)榈诙€(gè)格得到兩粒米，因?yàn)榈谌竦玫剿牧Ｃ?，如此在每后一個(gè)格都增加一倍的米量。不識(shí)指數(shù)級(jí)增長(zhǎng)威力的國(guó)王欣然答允，甚至還有些責(zé)怪塞薩要求太少，然而事后才發(fā)現(xiàn)整個(gè)國(guó)庫(kù)的米都倒干凈了仍然無(wú)法填滿(mǎn)整個(gè)棋盤(pán)。故事的結(jié)局是，國(guó)王惱羞之下偷偷派人把塞薩殺掉了。學(xué)過(guò)等比數(shù)列的現(xiàn)代人按一按計(jì)算器就知道，國(guó)王因?yàn)檫@64個(gè)棋盤(pán)格子總共要支出2^64-1=18446744073709551615>10^19粒米，這據(jù)估計(jì)已經(jīng)超出整個(gè)人類(lèi)歷史上產(chǎn)米量的總和！

回到局勢(shì)變化的復(fù)雜度問(wèn)題上。即使10^19這樣的天文數(shù)字也“只不過(guò)”是一個(gè)從當(dāng)前盤(pán)面出發(fā)，每次只考慮2種走法，持續(xù)64步之后的可能性空間的大小。對(duì)于國(guó)際象棋和圍棋這樣的復(fù)雜棋類(lèi)，從初始盤(pán)面出發(fā)窮盡所有變化的復(fù)雜度(也稱(chēng)窮舉復(fù)雜度)更是大得難以想象。信息論創(chuàng)始人克勞德香農(nóng)在1950年第一個(gè)估計(jì)出國(guó)際象棋的窮舉復(fù)雜度大概在10^120種變化左右，具體數(shù)字被后人稱(chēng)為“香農(nóng)數(shù)”。而圍棋的窮舉復(fù)雜度又遠(yuǎn)遠(yuǎn)超出國(guó)際象棋，達(dá)到了驚人的10^360。作為比較，目前可觀測(cè)宇宙中的原子總數(shù)據(jù)估計(jì)“只有”10^75個(gè)。　

有人會(huì)問(wèn)，為了分析當(dāng)前盤(pán)面一定要窮舉所有未來(lái)走勢(shì)的可能性嗎？有沒(méi)有可能存在一個(gè)高效的算法可以在避免遍歷呈指數(shù)級(jí)增長(zhǎng)的可能性空間的同時(shí)仍然對(duì)當(dāng)前盤(pán)面做出準(zhǔn)確評(píng)估呢？答案是，對(duì)于國(guó)際象棋和圍棋，我們可以從數(shù)學(xué)上證明，不僅僅是窮舉復(fù)雜度，其局勢(shì)變化的計(jì)算復(fù)雜度也必須隨所考慮的步數(shù)呈指數(shù)級(jí)增長(zhǎng)！對(duì)于任意一個(gè)給定的盤(pán)面，我們定義這個(gè)盤(pán)面的“最優(yōu)值”為當(dāng)博弈雙方都下出“完美走法”的情況下導(dǎo)致的最終博弈結(jié)果。如果一個(gè)盤(pán)面的最優(yōu)值是“黑棋勝”，那就是說(shuō)在黑棋自己不出錯(cuò)的情況下白棋無(wú)論如何努力都是必?cái)〉摹＠碚撚?jì)算機(jī)科學(xué)家先后在1981年和1983年證明國(guó)際象棋和圍棋都屬于EXPTIME-Complete類(lèi)問(wèn)題，這意味著“任何”能正確計(jì)算盤(pán)面最優(yōu)值的方法所花費(fèi)的時(shí)間“必然”隨棋盤(pán)大小(亦或棋局的平均步數(shù))呈指數(shù)級(jí)增長(zhǎng)。事實(shí)上大部分流行的“雙人零和”棋類(lèi)的計(jì)算復(fù)雜度都是指數(shù)級(jí)的。有一些棋類(lèi)如西洋跳棋、五子棋，它們的規(guī)模足夠小，所以其初始盤(pán)面的最優(yōu)值已經(jīng)被計(jì)算出來(lái)了。但是像國(guó)際象棋和圍棋這樣的復(fù)雜棋類(lèi)，計(jì)算其初始盤(pán)面的最優(yōu)值，以現(xiàn)在的硬件計(jì)算能力看來(lái)還遙遙無(wú)期。

局面動(dòng)態(tài)評(píng)估：“激進(jìn)”與“保守”之間的平衡取舍

主流的國(guó)際象棋程序往往采用一種比較“保守”的局勢(shì)篩選策略，搭配一種比較“激進(jìn)”的信息匯總策略。而主流的圍棋程序則正好相反，在局勢(shì)篩選方面相當(dāng)“大膽”，卻對(duì)從這些局勢(shì)變化收集來(lái)的信息的使用相當(dāng)“謹(jǐn)慎”。這主要是由于目前對(duì)這兩種棋類(lèi)的盤(pán)面靜態(tài)評(píng)估的質(zhì)量不同導(dǎo)致的。

對(duì)于國(guó)際象棋，已經(jīng)找到了一種在“很多情況”下可以既快速又相對(duì)準(zhǔn)確地對(duì)盤(pán)面進(jìn)行靜態(tài)評(píng)估的方法——當(dāng)遇到這類(lèi)“大致可以進(jìn)行靜態(tài)評(píng)估”的盤(pán)面時(shí)，這個(gè)靜態(tài)評(píng)估方法有相當(dāng)?shù)目尚哦龋鴮?duì)于其他情況的盤(pán)面卻完全不起作用。由于擁有這樣一個(gè)具有“部分可靠性”的靜態(tài)評(píng)估，國(guó)際象棋程序的策略“從概念上”可以理解為是對(duì)從當(dāng)前盤(pán)面出發(fā)的每一種可能的變化都不停向前展開(kāi)，直到遇到一個(gè)可以大致靜態(tài)評(píng)估的盤(pán)面或者超出了一個(gè)預(yù)定的“最大展開(kāi)步數(shù)”為止。這樣的“保守”選擇策略使得計(jì)算機(jī)對(duì)于一定階段之內(nèi)的所有變化都有了大致評(píng)估。接下來(lái)計(jì)算機(jī)在“假設(shè)”這些評(píng)估是正確的前提下，計(jì)算按照完美下法哪一種變化是最優(yōu)的。

根據(jù)硬件計(jì)算能力，計(jì)算機(jī)還會(huì)設(shè)定一個(gè)“最小展開(kāi)步數(shù)”，即使一個(gè)變化在展開(kāi)不到最小步數(shù)時(shí)就遇到了一個(gè)“比較好評(píng)估的局面”，系統(tǒng)依然會(huì)繼續(xù)往前看，而不會(huì)就此停止。這是為了最大限度地彌補(bǔ)“對(duì)比較好評(píng)估的局面進(jìn)行靜態(tài)評(píng)估時(shí)依然有可能出錯(cuò)”的缺陷。在開(kāi)發(fā)第一個(gè)人類(lèi)大師級(jí)水平的計(jì)算機(jī)“Belle”的過(guò)程中，人們發(fā)現(xiàn)弈棋計(jì)算機(jī)的最小展開(kāi)步數(shù)越大，其棋力越強(qiáng)。也就是說(shuō)，原則上只要通過(guò)不斷增強(qiáng)硬件的計(jì)算能力，國(guó)際象棋機(jī)器就可以通過(guò)看得越來(lái)越深而下得越來(lái)越好。

1997年的“深藍(lán)”計(jì)算機(jī)在配備了400多塊專(zhuān)門(mén)設(shè)計(jì)的硬件加速卡之后，獲得了每秒鐘展開(kāi)并評(píng)估2億次盤(pán)面的恐怖計(jì)算能力，歷史上第一次代表機(jī)器戰(zhàn)勝了人類(lèi)國(guó)際象棋冠軍。在隨后的十幾年里，按照“摩爾定律”增長(zhǎng)的計(jì)算機(jī)硬件能力變得愈加強(qiáng)大，計(jì)算機(jī)又先后多次戰(zhàn)勝人類(lèi)國(guó)際象棋冠軍。越來(lái)越多的人相信，機(jī)器在國(guó)際象棋領(lǐng)域早已超越了人類(lèi)的弈棋能力。

然而，計(jì)算機(jī)能夠戰(zhàn)勝人類(lèi)國(guó)際象棋冠軍并不全靠超強(qiáng)的硬件計(jì)算能力，軟件算法方面的持續(xù)改進(jìn)同樣必不可少，甚至影響更大。

比如上面提到，國(guó)際象棋系統(tǒng)在“概念上”窮盡了一定步數(shù)之內(nèi)的所有變化。但在真實(shí)的弈棋計(jì)算機(jī)中，一系列優(yōu)化算法使得系統(tǒng)在不完全展開(kāi)某些變化的同時(shí)也能夠得到和完全展開(kāi)一樣(或類(lèi)似)的效果。這樣節(jié)省下來(lái)的時(shí)間可以用于把已知變化“看得更深”，從而極大提高了系統(tǒng)在“概念上”的等效計(jì)算能力。

其中最經(jīng)典的例子是由人工智能先驅(qū)約翰·麥卡錫提出的////剪枝法，它巧妙利用了“國(guó)際象棋是雙人零和游戲”的特點(diǎn)，以最優(yōu)的方式避免所有不必要的變化展開(kāi)。

零和游戲

 

又稱(chēng)零和博弈(Zero-Sum Game)，是博弈論中的一個(gè)概念，指游戲(博弈)雙方是競(jìng)爭(zhēng)而不是合作關(guān)系，或者說(shuō)是一種“你死我活”的狀態(tài)。例如兩人對(duì)弈，一方贏，另一方必然是輸，不存在“雙贏”。贏棋得1分，輸棋減1分，兩人得分之和就總是0，所以稱(chēng)為零和游戲。

根據(jù)計(jì)算機(jī)科學(xué)家唐納德·克努特(Donald Knuth)的數(shù)學(xué)分析，在理想情況下， 剪枝法僅需評(píng)估所有b^d個(gè)變化中的b^(d/2)個(gè)，就可以保證得到和評(píng)估所有b^d個(gè)變化完全一樣的結(jié)果。換句話(huà)說(shuō)，我們需要增加 倍硬件計(jì)算能力才能使動(dòng)態(tài)評(píng)估加深一步，而使用 剪枝法則可以使動(dòng)態(tài)評(píng)估輕松增加整整一倍的“思考深度”*2！

剪枝法成型于20世紀(jì)60年代，是國(guó)際象棋弈棋的諸多優(yōu)化算法里最經(jīng)典的一種。如今的國(guó)際象棋程序中還使用了大量其他優(yōu)化方法，使得實(shí)際的動(dòng)態(tài)評(píng)估過(guò)程遠(yuǎn)遠(yuǎn)比簡(jiǎn)單的“枚舉”要高效得多，只是“從概念上”，它們從評(píng)估質(zhì)量上等效(或接近)于一次對(duì)未來(lái)若干步內(nèi)所有局勢(shì)變化的窮舉展開(kāi)而已。

剪枝法的一個(gè)簡(jiǎn)單示例 。

假設(shè)A盤(pán)面下我方行動(dòng)，并試圖最大化我方勝率；而B(niǎo)盤(pán)面下對(duì)手行動(dòng)，并試圖最小化我方勝率。如果A代表當(dāng)前盤(pán)面，而B(niǎo)代表我方走了某一步之后到達(dá)的新盤(pán)面?，F(xiàn)在假設(shè)已知B盤(pán)面下對(duì)手存在一種走法使得我方勝率至多有30%，同時(shí)已知A盤(pán)面下我方存在一種走法使得我方勝率至少有40%，那么我們已經(jīng)可以確定無(wú)需再檢查B盤(pán)面下其他未展開(kāi)的變化了。在層層展開(kāi)的動(dòng)態(tài)評(píng)估過(guò)程中這樣的“剪枝”可以反復(fù)使用，從而大量減少需要實(shí)際評(píng)估的變化數(shù)量。

國(guó)際象棋的動(dòng)態(tài)評(píng)估方法(或其變種)也廣泛應(yīng)用于大多數(shù)其他棋類(lèi)的對(duì)弈系統(tǒng)，其中很多達(dá)到或超越了人類(lèi)冠軍的水平。然而，這套思路卻在圍棋博弈中遭遇了滑鐵盧。截至目前，沒(méi)有一個(gè)基于國(guó)際象棋的動(dòng)態(tài)評(píng)估思路的圍棋系統(tǒng)可以超過(guò)人類(lèi)業(yè)余入門(mén)級(jí)水平。很多人把這一失敗歸因于圍棋比國(guó)際象棋更大的計(jì)算復(fù)雜度(這當(dāng)然看起來(lái)是最明顯的原因之一)。

但是，根據(jù)許峰雄博士在2007年發(fā)表的那篇名為“Cracking GO”(破解圍棋)的文章，在擁有接近國(guó)際象棋的靜態(tài)評(píng)估質(zhì)量的前提下，我們完全可以在軟件和硬件兩方面進(jìn)行一系列優(yōu)化，使得國(guó)際象棋的動(dòng)態(tài)評(píng)估方法在圍棋中也達(dá)到類(lèi)似的思考深度。如果我們假設(shè)圍棋大師們的智力并不顯著高于國(guó)際象棋大師的話(huà)，這樣的思考深度也許會(huì)使機(jī)器在圍棋上再次戰(zhàn)勝人類(lèi)。也就是說(shuō)，對(duì)于當(dāng)今的硬件能力，圍棋的復(fù)雜度并不是不可逾越的鴻溝。那么，到底是什么原因?qū)е聡?guó)際象棋的策略無(wú)法適用于圍棋呢？

筆者的觀點(diǎn)是，“窮舉型” 策略////3至今未在圍棋中廣泛應(yīng)用，更大的障礙恐怕還是缺少一個(gè)像國(guó)際象棋那樣能夠?qū)τ?ldquo;一大類(lèi)”盤(pán)面進(jìn)行“大致準(zhǔn)確的評(píng)估”的方法。前面介紹靜態(tài)評(píng)估方法的部分已經(jīng)提到了，目前圍棋盤(pán)面的靜態(tài)評(píng)估方法一般只在棋局前期黑白雙方尚未“短兵相接”時(shí)有一定效果。當(dāng)棋局進(jìn)入關(guān)鍵的中盤(pán)廝殺之后，如果仍然使用現(xiàn)有的靜態(tài)評(píng)估方法，我們就會(huì)發(fā)現(xiàn)：在達(dá)到硬件計(jì)算能力可承受的最大預(yù)判步數(shù)時(shí)，大部分棋局變化都處于不能“大致準(zhǔn)確評(píng)估”的狀態(tài)?；谶@些十分不“靠譜”的評(píng)估結(jié)果去考慮所謂“完美”走法，得到的結(jié)果自然也是不大靠譜的。

正是由于缺少“靠譜”的靜態(tài)評(píng)估方法，目前所有頂級(jí)圍棋程序轉(zhuǎn)而采取一種比較“謹(jǐn)慎”的信息匯總策略。

在國(guó)際象棋中，如果一個(gè)盤(pán)面有兩種走法，一個(gè)估計(jì)勝率30%，另一個(gè)估計(jì)勝率80%(如圖(a)中盤(pán)面B所示)，計(jì)算機(jī)會(huì)傾向于相信這些結(jié)果都是大概“靠譜”的，因此該盤(pán)面自身的勝率應(yīng)該等于所有走法中的最優(yōu)結(jié)果(我方盤(pán)面取最大值，對(duì)手盤(pán)面取最小值)，因此認(rèn)為盤(pán)面B的勝率是30%。這是一種比較“激進(jìn)”的信息匯總策略：當(dāng)發(fā)現(xiàn)了30%勝率的走法時(shí)，系統(tǒng)會(huì)完全丟棄80%勝率的走法所帶來(lái)的信息，選擇全部相信30%勝率的走法。

而在圍棋程序中，計(jì)算機(jī)認(rèn)為對(duì)每個(gè)盤(pán)面的直接靜態(tài)評(píng)估結(jié)果都是不可靠的，但是相信“對(duì)該盤(pán)面下所有走法的全部評(píng)估結(jié)果”卻整體上仍然對(duì)該盤(pán)面的勝率具有指向性?，F(xiàn)有圍棋程序一般采用對(duì)所有評(píng)估結(jié)果進(jìn)行加權(quán)平均的方式來(lái)體現(xiàn)這種指向性，其中“權(quán)重”基于對(duì)當(dāng)前評(píng)估結(jié)果的可信度進(jìn)行設(shè)定。舉例來(lái)說(shuō)。在圖(b)中，假設(shè)對(duì)盤(pán)面B下兩種走法所直接導(dǎo)致的盤(pán)面進(jìn)行靜態(tài)評(píng)估的結(jié)果勝率分別為30%和80%，而盤(pán)面C下的兩種走法勝率分別為50%和40%。因?yàn)檫@4個(gè)估計(jì)值可能都存在偏差，所以我們并不偏信其中任何一個(gè)；另一方面，在偏差沒(méi)有系統(tǒng)性地倒向“某一類(lèi)盤(pán)面”或“某一類(lèi)走法”的前提下，我們有理由相信這4個(gè)盤(pán)面評(píng)估結(jié)果具有相同的可信度(或“不可信度”)，因此應(yīng)該具有相同的權(quán)重。所以在只知道這4個(gè)靜態(tài)評(píng)估結(jié)果的情況下，我們認(rèn)為盤(pán)面B的評(píng)估勝率是0.5 30%+0.5 80%=55%，盤(pán)面C的評(píng)估勝率是0.5 50%+0.5 40%=45%。同時(shí)，這樣做出的對(duì)B和C的判斷自身仍然有可能存在偏差，所以在以盤(pán)面B和C為基礎(chǔ)再評(píng)估盤(pán)面A時(shí)也要考慮到這一點(diǎn)，因此A的評(píng)估結(jié)果同樣是B和C的結(jié)果的再次加權(quán)平均0.5 45%+0.5 55%=50%。

我們看到，這樣根據(jù)等權(quán)重得到的對(duì)A的評(píng)估結(jié)果實(shí)際上是綜合了所有當(dāng)前已知信息之后給出的一個(gè)“模棱兩可”的評(píng)估。考慮到“已知信息”本質(zhì)上的低可靠度，這也許就是我們?cè)谶@種情況下“應(yīng)該”得到的答案。當(dāng)然，這樣一個(gè)僅僅基于4次靜態(tài)評(píng)估的結(jié)果并不是計(jì)算機(jī)給出的最終答案。對(duì)于一個(gè)給定盤(pán)面，我們考察的變化越多，獲取的信息量也越大，因此對(duì)這個(gè)盤(pán)面的評(píng)估值也傾向于更可靠，從而這個(gè)評(píng)估值在參與加權(quán)平均時(shí)也理應(yīng)獲得更大的權(quán)重。換句話(huà)說(shuō)，我們根據(jù)對(duì)一個(gè)盤(pán)面“深思熟慮”的程度來(lái)量化對(duì)其評(píng)估結(jié)果的“可信度”，認(rèn)為一個(gè)進(jìn)行大量分析后得到的評(píng)估結(jié)果在可信度上優(yōu)于分析較少的評(píng)估結(jié)果。這就涉及到如何選擇那些需要進(jìn)一步深思熟慮的變化的問(wèn)題。

相同情況下的不同信息匯總策略。(a)為以國(guó)際象棋程序?yàn)榇淼?ldquo;激進(jìn)”策略，取最大(小)值為匯總結(jié)果；(b)～(d)為以圍棋程序?yàn)榇淼?ldquo;保守”策略，取加權(quán)平均值為匯總結(jié)果。其中(b)對(duì)應(yīng)評(píng)估初期等權(quán)重下的結(jié)果，如果其中30%的靜態(tài)評(píng)估正確，則算法經(jīng)過(guò)150次蒙特卡洛采樣后會(huì)導(dǎo)向(c)所示結(jié)果，否則會(huì)導(dǎo)向(d)所示結(jié)果。

有意思的是，在采取較為謹(jǐn)慎的信息匯總策略的同時(shí)，圍棋程序在局勢(shì)變化的選擇策略上卻相當(dāng)“大膽”。如果說(shuō)國(guó)際象棋程序希望考察在一定階段內(nèi)的所有變化，那么圍棋程序卻只通過(guò)對(duì)所有這些變化進(jìn)行某種有策略的采樣來(lái)進(jìn)行評(píng)估，把更多的時(shí)間精力投入到那些“看似”更有希望的變化上。這就是被稱(chēng)為蒙特卡洛樹(shù)搜索的動(dòng)態(tài)評(píng)估方法。這種方法在“從當(dāng)前盤(pán)面出發(fā)所有有可能的局勢(shì)變化”組成的巨大可能性空間中進(jìn)行反復(fù)采樣。通過(guò)巧妙設(shè)計(jì)的選擇策略，配合前面所說(shuō)的基于加權(quán)平均值的信息匯總策略，計(jì)算機(jī)會(huì)根據(jù)已有的采樣結(jié)果調(diào)整新一輪采樣所選擇的變化，從而保證最優(yōu)走法逐漸獲得更多的選擇機(jī)會(huì)，因此獲得更大的權(quán)重。這樣的長(zhǎng)期結(jié)果是，大量采樣之后對(duì)當(dāng)前盤(pán)面下所有走法的“加權(quán)平均”結(jié)果會(huì)逐漸逼近當(dāng)前盤(pán)面的最優(yōu)值！

仍然回到圖10的例子。我們看到圖(b)中基于4次靜態(tài)評(píng)估的加權(quán)平均結(jié)果高于圖(a)中按照傳統(tǒng)國(guó)際象棋思路得到的結(jié)果，這主要是因?yàn)槲覀儗?duì)當(dāng)前勝率評(píng)估為30%的這個(gè)盤(pán)面“不大信任”導(dǎo)致的。在接下來(lái)的動(dòng)態(tài)評(píng)估采樣中有兩種可能：(1)當(dāng)前的30%的評(píng)估結(jié)果是正確的，在這種情況下蒙特卡洛樹(shù)搜索算法對(duì)盤(pán)面B下的變化采樣會(huì)更傾向于30%這個(gè)走法，因此B的評(píng)估值會(huì)逐漸下降到接近30%，而這又會(huì)導(dǎo)致B的評(píng)估值低于C，因此C獲得更多采樣機(jī)會(huì)，從而在對(duì)A的加權(quán)平均評(píng)估時(shí)獲得比B更大的權(quán)重。如圖(c)所示，在150次采樣之后，A的評(píng)估值接近C，而C的評(píng)估值接近40%——這和圖(a)的評(píng)估結(jié)果一致(因?yàn)楫?dāng)初30%的靜態(tài)評(píng)估結(jié)果恰好是正確的！)。(2)如果圖(b)中30%的結(jié)果是錯(cuò)誤的，假設(shè)機(jī)器經(jīng)過(guò)對(duì)這個(gè)走法進(jìn)一步考察(75次采樣)后發(fā)現(xiàn)它的勝率其實(shí)應(yīng)該是80%。這種情況下，B的評(píng)估值會(huì)逐漸上升到80%，而這導(dǎo)致B相對(duì)于A的權(quán)重變高，因此A的評(píng)估值也隨之上升，從而得到和前面不一樣的最終評(píng)估結(jié)果。

總而言之，目前的主流圍棋程序試圖用一種系統(tǒng)性的方法去“管理”在評(píng)估過(guò)程中不可避免帶來(lái)的“不確定性”。截至目前，所有一流的圍棋程序全部采用蒙特卡洛樹(shù)搜索方法進(jìn)行盤(pán)面動(dòng)態(tài)評(píng)估////4。它們從基本“思維模式”和局面勝率評(píng)估的“基本框架”上繼承了以國(guó)際象棋弈棋計(jì)算機(jī)為代表的傳統(tǒng)方法；同時(shí)，采用蒙特卡洛采樣思想來(lái)進(jìn)一步管理知識(shí)中的“不確定性”，在選擇策略上化保守為激進(jìn)，在匯總策略上化激進(jìn)為保守，在無(wú)法對(duì)變幻莫測(cè)的圍棋盤(pán)面進(jìn)行有效靜態(tài)評(píng)估的情況下仍然達(dá)到了業(yè)余高級(jí)水平的棋力。

蒙特卡洛樹(shù)搜索法

使用蒙特卡羅方法估算 值。圖/維基百科

 

選取的隨機(jī)點(diǎn)（n）越多，估計(jì)值離 的真值越近。圖/維基百科

　　這種選擇很大程度上跟現(xiàn)有圍棋弈棋系統(tǒng)對(duì)盤(pán)面靜態(tài)評(píng)估方法的整體舍棄有關(guān)。前面提到，由于人們?cè)谠O(shè)計(jì)具有一定通用性的圍棋盤(pán)面靜態(tài)評(píng)估函數(shù)的問(wèn)題上長(zhǎng)期止步不前，大概在2002年之后人們開(kāi)始思考采用另一種完全不同的方式對(duì)盤(pán)面進(jìn)行快速評(píng)估，這就是蒙特卡洛采樣。

 

　　做為一種通用的計(jì)算方法，蒙特卡洛采樣法的思想是當(dāng)我們?cè)谇蠼庖粋€(gè)確定但未知的值的時(shí)候，“在概念上”巧妙構(gòu)造一個(gè)隨機(jī)過(guò)程，使得這個(gè)隨機(jī)過(guò)程的某個(gè)數(shù)字特征依概率收斂于我們要求的值，然后“在實(shí)際操作中”通過(guò)對(duì)該隨機(jī)過(guò)程進(jìn)行采樣來(lái)對(duì)這個(gè)值進(jìn)行統(tǒng)計(jì)估計(jì)。

 

　　比如說(shuō)，一種計(jì)算圓周率////的蒙特卡洛方法是，在一個(gè)二維坐標(biāo)系中////和////對(duì)應(yīng)的方形區(qū)域里隨機(jī)選取若干個(gè)點(diǎn)，并判斷每個(gè)點(diǎn)////是否落在“以原點(diǎn)為圓心半徑為1的單位圓”內(nèi)(也即判定////是否小于1)。根據(jù)中心極限定理，這些隨機(jī)點(diǎn)落在單位圓內(nèi)的比例依大概率快速趨于////。所以我們選取的隨機(jī)點(diǎn)數(shù)量越多，越有可能得到的一個(gè)離的真值更接近的估計(jì)。

相同的“蒙特卡洛”思想也可以用于圍棋盤(pán)面評(píng)估。前面提到了，每個(gè)圍棋盤(pán)面都有一個(gè)“最優(yōu)值”，對(duì)應(yīng)于對(duì)弈雙方都采用完美走法的情況下該盤(pán)面的最終結(jié)果。對(duì)于圍棋已經(jīng)證明，計(jì)算這個(gè)最優(yōu)值的時(shí)間至少隨該盤(pán)面到終盤(pán)之間的步數(shù)呈指數(shù)級(jí)數(shù)增長(zhǎng)(平均200步，每步平均增長(zhǎng)200倍數(shù)量的可能盤(pán)面)。既然從理論上無(wú)法得到最優(yōu)值，有沒(méi)有可能根據(jù)蒙特卡洛思想對(duì)整個(gè)可能性空間進(jìn)行某種采樣，然后通過(guò)統(tǒng)計(jì)估值的方法逼近這個(gè)最優(yōu)值呢？人們對(duì)這個(gè)問(wèn)題的思考在2006年終于取得了突破性進(jìn)展，提出了一種稱(chēng)為蒙特卡洛樹(shù)搜索的動(dòng)態(tài)評(píng)估方法。

 

　　需要指出的是，現(xiàn)有的蒙特卡洛樹(shù)搜索法雖然能保證大量采樣的結(jié)果最終收斂到盤(pán)面最優(yōu)值，但為達(dá)到“足夠收斂”所需的采樣次數(shù)仍然是隨整個(gè)可能性空間的規(guī)模指數(shù)級(jí)增長(zhǎng)的。但是在圍棋弈棋系統(tǒng)的實(shí)踐中，蒙特卡洛樹(shù)搜索在比賽時(shí)間受限的情況下確實(shí)表現(xiàn)出遠(yuǎn)遠(yuǎn)超過(guò)傳統(tǒng)方法的棋力。最近幾年人們受這一觀察的鼓舞，在選擇策略中加入更多和圍棋相關(guān)的專(zhuān)家知識(shí)，使得基于蒙特卡洛樹(shù)搜索的圍棋弈棋系統(tǒng)水平不斷提高。

弈棋計(jì)算機(jī)是人工智能嗎？

弈棋是一種刺激性極強(qiáng)的直接對(duì)抗。計(jì)算機(jī)弈棋代表了一種機(jī)器對(duì)人類(lèi)的“符號(hào)意義上”的挑戰(zhàn)，因而備受關(guān)注。“人類(lèi)弈棋大師在整體智力上超出常人”這一事實(shí)，也使得“計(jì)算機(jī)在弈棋上向人類(lèi)高手發(fā)起的挑戰(zhàn)”被很自然地認(rèn)作是一種關(guān)乎“智力極限”的挑戰(zhàn)。

那么，從人工智能的角度，我們應(yīng)該如何看待弈棋系統(tǒng)及其相關(guān)的研究活動(dòng)呢？

首先我們應(yīng)該意識(shí)到，被我們視為智力挑戰(zhàn)的問(wèn)題，機(jī)器做起來(lái)往往未必困難；反而是一些人類(lèi)覺(jué)得稀松平常的腦力活動(dòng)，機(jī)器實(shí)現(xiàn)起來(lái)卻可能非常困難。比如速算曾經(jīng)同樣是智力超群的象征，但是現(xiàn)代計(jì)算機(jī)無(wú)論在計(jì)算速度還是準(zhǔn)確率上都毫無(wú)爭(zhēng)議地完勝人類(lèi)。要理性衡量計(jì)算機(jī)弈棋與人工智能的關(guān)系，還要對(duì)照上期我們總結(jié)的人工智能的主要特征來(lái)分析。

根據(jù)人工智能的主要特征，雖然弈棋滿(mǎn)足了智能行為的標(biāo)準(zhǔn)，但目前的所有計(jì)算機(jī)弈棋系統(tǒng)都不滿(mǎn)足通用性要求，因此還不能算是完整的人工智能系統(tǒng)。考慮到國(guó)際象棋領(lǐng)域里一臺(tái)“不算完整人工智能系統(tǒng)”的機(jī)器已經(jīng)戰(zhàn)勝了人類(lèi)，那么當(dāng)圍棋機(jī)器戰(zhàn)勝人類(lèi)的那一天到來(lái)的時(shí)候，也未必就意味著什么人工智能新時(shí)代的開(kāi)始。

然而，“弈棋系統(tǒng)本身不是人工智能系統(tǒng)”不代表“弈棋系統(tǒng)研究不是人工智能研究”。棋類(lèi)運(yùn)動(dòng)被稱(chēng)為是人工智能領(lǐng)域的“果蠅”，我們對(duì)果蠅進(jìn)行研究，根本目的并不是為了制造一個(gè)“更強(qiáng)壯的果蠅”，而是為了以此探索一些具有普遍性的生物系統(tǒng)規(guī)律，幫忙我們認(rèn)識(shí)和研究比果蠅更復(fù)雜的生物系統(tǒng)。在筆者看來(lái)，弈棋系統(tǒng)研究在人工智能方面的意義主要有兩個(gè)，第一個(gè)是為相關(guān)的自動(dòng)推理/規(guī)劃、自動(dòng)學(xué)習(xí)、知識(shí)表示等等人工智能技術(shù)提供實(shí)驗(yàn)場(chǎng)所，第二個(gè)就是為打敗人類(lèi)而發(fā)明的如“推演”和“規(guī)劃”部分的相關(guān)技術(shù)在通用智能中的推廣和應(yīng)用。

 最后，一個(gè)經(jīng)常被提及的話(huà)題是關(guān)于如何對(duì)待人類(lèi)領(lǐng)域知識(shí)在弈棋系統(tǒng)中的作用。有些人認(rèn)為，使用了“人類(lèi)職業(yè)棋手”的知識(shí)的弈棋系統(tǒng)有“作弊”之嫌，認(rèn)為弈棋系統(tǒng)只有“零知識(shí)”才算真本領(lǐng)。筆者認(rèn)為沒(méi)有必要苛求于此。所謂名師出高徒，有幾個(gè)人類(lèi)冠軍是自學(xué)成才的？即使是職業(yè)棋手的知識(shí)也不一定是他自己想出來(lái)的，畢竟人類(lèi)已經(jīng)積累了上千年的領(lǐng)域知識(shí)。事實(shí)上，能夠積累、運(yùn)用和傳授知識(shí)正是人類(lèi)智能最厲害的地方之一，而“知識(shí)表示與管理”也是通用人工智能系統(tǒng)的必要組成部分。

另一方面，“形式化人類(lèi)領(lǐng)域知識(shí)”也并不是“顯然可行”的事情。國(guó)際象棋方面，是在深藍(lán)成功之后才真正證明國(guó)際象棋大師的經(jīng)驗(yàn)“可以”形式化表達(dá)(深藍(lán)團(tuán)隊(duì)在這方面做了大量工作)，而圍棋盤(pán)面靜態(tài)評(píng)估甚至至今尚未找到有效形式化的方法。可以說(shuō)，針對(duì)圍棋弈棋的研究在知識(shí)表示上尚處于努力證明“可以形式化”的階段；而與此同時(shí)，“通用博弈比賽”相關(guān)的研究則已經(jīng)開(kāi)始對(duì)“統(tǒng)一化的知識(shí)表示”的初步探索。

本文由《科學(xué)世界》雜志授權(quán)轉(zhuǎn)載