算法合集之人工智能在圍棋程序中的應(yīng)用

1、百度文庫(kù)-讓每個(gè)人平等地提升自我人工智能在闈棋程序中的應(yīng)用亞旦大學(xué)附屬中學(xué)施遙【關(guān)鍵字】圍棋，搜索，模式匹配，博弈樹(shù)【摘要】圍棋程序的編制被稱作人工智能的“試金石”，是人工智能技術(shù)的一大難題。本文介紹了人工智能在圍棋程序中的應(yīng)用與發(fā)展，對(duì)比了闈棋與國(guó)際象棋博弈算法的差 別和狂雜度，從而分析圍棋算法的難點(diǎn)，討論各種博弈算法（氣位理論、模式匹配與博弈樹(shù)） 在圍棋程序中的融合運(yùn)用。并給出了闈棋死活程序的算法實(shí)例（附程序），以供參考【正文】目錄一、概述二、圍棋的復(fù)雜性三、博弈（棋類）算法及其在象棋與闈棋中的對(duì)比四、圍棋算法五、圍棋棋形識(shí)別六、圍棋死活的算法與實(shí)現(xiàn)七、展望一、概述1、圍棋簡(jiǎn)介圍棋相傳為堯

2、所創(chuàng)，縱橫一十九道，天元是為太極，太極生兩儀，為黑白子；兩儀生四 象，為四個(gè)角。弈旨（漢班固）云：“棋有白黑，陰陽(yáng)分也，駢羅列布，效天文也?！?可知圍棋本是仿效天文而制，逐漸演變?yōu)椴┺挠螒颉?、計(jì)算機(jī)與圍棋計(jì)算機(jī)運(yùn)用于棋類方面幾乎與計(jì)算機(jī)的誕生的歷史一樣長(zhǎng)。這方面內(nèi)容主要屬于人工智 能技術(shù)。人工智能作為一門(mén)科學(xué)首先是在五十年代提出的，隨即便運(yùn)用于棋類。由于技術(shù)的進(jìn)步，計(jì)算機(jī)速度的提高、算法的不斷發(fā)展，目前電腦國(guó)際象棋的水平已極 高，然而圍棋水平卻徘徊不前。就圍棋而言，人弈棋憑的是經(jīng)驗(yàn)，即“棋感”。人類的優(yōu)勢(shì)是模糊判斷、靈敏的直覺(jué)， 高手往往會(huì)有靈機(jī)一動(dòng)而弈出妙手。當(dāng)然事物有其兩面性，即人的情感

3、、直覺(jué)有時(shí)也會(huì)誤導(dǎo) 自己形成錯(cuò)誤，而棋手的心態(tài)也是至關(guān)重要的一環(huán)，“成也蕭何，敗也蕭何”，直覺(jué)既是人類 的法寶，亦是敗因（當(dāng)然是指敗給人了）。計(jì)算機(jī)的優(yōu)勢(shì)是計(jì)算速度快，劣勢(shì)是不擅模糊判斷、不能根據(jù)經(jīng)驗(yàn)選點(diǎn)導(dǎo)致搜索量過(guò)大。 計(jì)算機(jī)不為情緒所困，不為直覺(jué)所惑，故地域廣狹、大小之分能較為準(zhǔn)確，其耗時(shí)亦少，然 而計(jì)算機(jī)畢竟沒(méi)有棋感，不知道哪步好、哪步不好，只有一點(diǎn)點(diǎn)地去試，要么費(fèi)時(shí)甚巨（也 未必有用），要么草草了事，結(jié)果也可想而知。二、圍棋的復(fù)雜性圍棋全局與其死活問(wèn)題其更雜性都大致可歸納為如下三點(diǎn)：1、模糊性“闈棋”之名自是取自用地之意，倘若是雙方落子一開(kāi)始便是緊緊相貼的，那么可想而 之行棋的速度（即

4、占領(lǐng)地盤(pán)的速度）是極慢的，故而布局、中盤(pán)以至大官子階段，雙方只是 圍出一個(gè)大概的輪廓，甚而連輪廓都不明顯。黑白勢(shì)力難分，形狀犬牙差互。這對(duì)于計(jì)算機(jī) 處理形成了極大的困難。2、反復(fù)性象棋中棋子一旦被吃，則永遠(yuǎn)從棋盤(pán)上提去，而在圍棋棋盤(pán)上，被吃的地方仍可重新落 子，甚而將對(duì)方反吃回來(lái)，如此一來(lái)，搜索的難度便大大增加。如“倒脫靴”之形，送子后 再吃子，一塊空可以幾易其主。所以“死子”不死，“活子”有時(shí)倒是堪虞。所以在計(jì)算機(jī) 處理中不可以簡(jiǎn)單確定一塊棋子的死活和對(duì)周圍的影響。3、靈活性象棋的靈活，至多體現(xiàn)在兌子上，所謂“寧棄一子，不失一先”，也僅是一子而己，若 是兩子、三子呢？恐怕在雙方實(shí)力相當(dāng)?shù)那闆r

5、下必?cái)o(wú)疑。而且在象棋算法中多有將各種棋 子折合為一定的價(jià)值相加的做法，如，在國(guó)際象棋中以一個(gè)兵為單位，一個(gè)馬約可等于三個(gè) 半兵，一個(gè)車約可等于五個(gè)半兵，等等，最多再根據(jù)棋子所處位置加以一定的折算。而圍棋的炎活遠(yuǎn)勝于此，有時(shí)棄去十來(lái)個(gè)子以取勢(shì)，棄去二、三十目的角地以轉(zhuǎn)換。再 者，圍棋棋子的價(jià)值是難以估量的，其價(jià)值不完全在其本身，而常于在周圍的配置，有些影 響甚而可斜跨整個(gè)棋盤(pán)。三、博弈（棋類）算法及其在象棋與圍棋中的對(duì)比一九九七年，IBM的電腦“深藍(lán)”一舉戰(zhàn)勝卡斯帕羅夫，震驚世界。其實(shí)電腦國(guó)際象棋 的水平早在七、八十年代已擠身世界高手之林，而中國(guó)象棋軟件也已幾乎具有大師水準(zhǔn)，非 一般愛(ài)好者能望

6、其項(xiàng)背。唯獨(dú)I制棋舉步維艱，連業(yè)余下手都勝券難握，更莫論一等一的高手， 究其原因不外是闈棋之博大精深、縱橫變換繁狂，棋手多靠經(jīng)驗(yàn)而計(jì)算機(jī)則無(wú)此功能。目前，棋類博弈算法主要有兩大類：模式匹配和使用博弈樹(shù)。這在國(guó)際象棋中的運(yùn)用可 以追溯到五、六十年代，且而十分成功。圍棋和象棋一樣是博弈游戲，看似僅有黑白兩種棋子，簡(jiǎn)單不過(guò)。實(shí)則比起兵種繁多的 象棋卻更雜得多。電腦圍棋起源于六十年代。兩位博士 Zobrist和Ryder在論文中均涉及了圍棋程序，前 者的算法基于模式識(shí)別：而后者的算法基于搜索，即使用博弈樹(shù)。這兩種在國(guó)際象棋中效果 不錯(cuò)的算法在圍棋中的表現(xiàn)卻極差，竟然連僅有幾盤(pán)棋經(jīng)驗(yàn)的人都贏不了。我們不

7、妨來(lái)考慮一下上述兩種算法。首先，我們來(lái)看模式匹配。象棋中因?yàn)槠遄觽€(gè)數(shù)少、種類多，那么就較易分別與歸納（實(shí) 際上也是困難的，但比闈棋容易實(shí)現(xiàn)得多）。而在用棋中，顯然將所有的模式都存儲(chǔ)起來(lái)是 不可能的。那么只有模糊匹配。但這似乎也很難辦。圍棋中有“愚形”這個(gè)名詞，一般指的 是效率差的形狀。那么怎樣是效率差呢？就是浪費(fèi)子力，在不必要的地方落子，哪怕只是一 個(gè)子。而模糊的匹配在一子之差時(shí)究竟如何判斷？是好形還是愚形？這就陷入了矛盾的境地。 況且，根據(jù)實(shí)際情況，還有“愚形之妙手”（出自口本古局），實(shí)難判斷。其次是搜索的算法。搜索的代價(jià)是極大的，據(jù)估計(jì)，國(guó)際象棋搜索7個(gè)回合約有500 億至600億種選擇（

8、當(dāng)然是在博弈樹(shù)剪枝后），這個(gè)數(shù)字盡管也十分龐大，但以目前的技術(shù) 水平還是可以承受的：然而在圍棋中，我們稍微計(jì)算一下便知道：假設(shè)每步大約有只有一百 個(gè)可行點(diǎn)（已經(jīng)非常少了），那么14步（即7個(gè)回合）以內(nèi)的變化則約有1028種，當(dāng)然這 只是保守的估計(jì)，已足以駭人了。可見(jiàn)在全局使用搜索算法是不可行的。因此當(dāng)前的做法一 般是在局部明確目標(biāo)（如做活、殺棋、突闈、切斷等）的情況下，才使用博弈樹(shù)進(jìn)行搜索。 四、圍棋算法目前，世界上流行的圍棋軟件主要是由以下三種算法組成的：1、使每個(gè)棋子周圍產(chǎn)生某種影響，這種影響隨著距離的增加而減少，用一定的公式計(jì)算 疊加這種影響，以判斷形勢(shì)和估計(jì)著點(diǎn)的價(jià)值。這與圍棋的棋理相

9、通，即對(duì)于每個(gè)棋子可估 算其“勢(shì)力”。此中就有著名的“氣位”理論。2、建立模式庫(kù)，貯存了大量模式（定式、棋形等），以供匹配。這其實(shí)涉及到圍棋的許多 棋諺與棋理。如“二子頭必扳”、“鎮(zhèn)以飛應(yīng)”、“斷從一邊長(zhǎng)”、三子正中、點(diǎn)方等等。這些 都是根據(jù)圍棋的具體情況而設(shè)計(jì)的o3、對(duì)目標(biāo)明確的局部，用人工智能中的搜索法探求其結(jié)果。一般來(lái)說(shuō)，現(xiàn)在還沒(méi)有找到突破性的算法，只有在以上三種算法中細(xì)細(xì)加工。五、圍棋棋形識(shí)別圍棋中棋力的高下大凡憑一個(gè)棋手的感覺(jué)與經(jīng)驗(yàn)，而這感覺(jué)正是棋手水平的主要體現(xiàn)。 而對(duì)棋的感覺(jué)其實(shí)就是人對(duì)于棋本身（即棋形）的主觀認(rèn)識(shí)。這是一個(gè)識(shí)別過(guò)程。識(shí)別能力的高低是智能的一大特征。識(shí)別能力由低到

10、高分為三個(gè)層次，儀器水平：物理 識(shí)別；動(dòng)物水平：模糊識(shí)別；人類水平：情感識(shí)別。物理識(shí)別是對(duì)接受到的信息實(shí)現(xiàn)物理、化學(xué)和生物學(xué)的量化認(rèn)識(shí)。這不需要經(jīng)驗(yàn)與智能, 所以是最低層次的識(shí)別。模糊識(shí)別是在大量更雜的信息中識(shí)別出有用的部分，即對(duì)接收的信息與以往的記憶和經(jīng) 驗(yàn)進(jìn)行關(guān)聯(lián)認(rèn)識(shí)，剔除無(wú)關(guān)的信息。情感識(shí)別是最高級(jí)的識(shí)別。它是完全的感性識(shí)別?？梢哉f(shuō)闈棋中既有模糊識(shí)別，亦有情感識(shí)別。即對(duì)于一個(gè)新棋形，將之與經(jīng)驗(yàn)中的棋形 比較，綜合周邊情況，作出判斷。其決策帶有明顯的個(gè)人情感傾向，這與每個(gè)人的理解有關(guān)， 很多是沒(méi)有定論的，因此即便九段高手之間的棋也是截然不同的，很難說(shuō)孰優(yōu)孰劣。而在計(jì)算機(jī)中，對(duì)于棋形卻難以模

11、糊判斷，因?yàn)檫@既不是聲音，也不是圖象，一子之差， 優(yōu)劣迥異。一般來(lái)說(shuō)，目前計(jì)算機(jī)對(duì)于圍棋棋形只能作簡(jiǎn)單的識(shí)別，用以減少搜索，其實(shí)這也就是 賦予了計(jì)算機(jī)一定的“經(jīng)驗(yàn)”。六、圍棋死活的算法與實(shí)現(xiàn)死活是闈棋中的一個(gè)典型問(wèn)題，可以說(shuō)也是圍棋算法的一個(gè)縮影。它需要融合上述的三 種算法。目前，死活軟件已達(dá)到較高的水平，但主要因?yàn)檫@只是一個(gè)局部問(wèn)題，與全局千絲 萬(wàn)縷的關(guān)系卻是極難把握。注：為了敘述簡(jiǎn)便起見(jiàn)，下文中黑方總為攻擊方，白方總為欲做活的一方，在本節(jié)中僅以白方為 例來(lái)設(shè)計(jì)算法。本節(jié)中的各算法均已簡(jiǎn)化，目的只是說(shuō)明方法。由于時(shí)間關(guān)系和水平所限，本節(jié)算法不免有所疏漏，望不吝指正。對(duì)于圍棋死活問(wèn)題，首先我們

12、不妨看看人下棋的思路：先看有多少眼位，是否已活？如不活:計(jì)算缺多少眼位，能否補(bǔ)上？在做眼（或破眼） 的過(guò)程中，人總是先以第一感為線索來(lái)計(jì)算，那么人的第一感是從何而來(lái)呢？其實(shí)就是長(zhǎng)期 對(duì)棋型認(rèn)識(shí)的經(jīng)驗(yàn)，經(jīng)驗(yàn)豐富者強(qiáng)、經(jīng)驗(yàn)欠缺者弱。因?yàn)樵谒阑钪杏性S多常見(jiàn)的棋型，前人 也曾總結(jié)過(guò)一些棋諺，如“殺棋用扳”、“二一多妙手”等，還有如夾、點(diǎn)、跨等手段經(jīng)常構(gòu) 成殺棋；而有些著點(diǎn)卻無(wú)需考慮。因?yàn)樗阑钍且粋€(gè)局部目標(biāo)明確的問(wèn)題，故而以搜索為主。 因此一個(gè)圍棋死活軟件的優(yōu)劣關(guān)鍵在于對(duì)于搜索的優(yōu)化、剪枝上。我對(duì)于圍棋死活問(wèn)題的算法有兩大部分組成：靜態(tài)眼位判斷搜索程序的主線是搜索，然而靜態(tài)眼位判斷穿插于其間。1、靜態(tài)眼

13、位判斷勢(shì)力劃分前面提到了，闈棋黑白雙方的界限是模糊的，很難精確劃分，而不能精確劃分的話，則 在計(jì)算機(jī)中難以處理。為此，采用氣位理論的的方法來(lái)近似計(jì)算“勢(shì)力”。勢(shì)力劃分貫穿于整個(gè)靜態(tài)眼位判斷，作用很大。一個(gè)棋子對(duì)于周圍有一定的影響，稱之為“勢(shì)力”，一個(gè)子的周圍稱為氣位。氣位如下 劃分：1、相鄰位為1級(jí)氣位；2、尖位為級(jí)氣位，扳位為2級(jí)氣位（即右圖中處若是扳位，則須改為“2”）；3、關(guān)位為2級(jí)氣位;4、小飛位為級(jí)氣位。各級(jí)別氣位所受影響如下表：氣位級(jí)別1級(jí)級(jí)2級(jí)級(jí)影響的絕對(duì)值6532黑棋的影響為正值，白棋為負(fù)值。當(dāng)然，以上的各位置與原來(lái)位置之間不可有棋子隔斷，否則（無(wú)論黑白）勢(shì)力即為其所 阻隔。另

14、外要補(bǔ)充的是，每一點(diǎn)所受某種顏色棋子的影響只受離其最近（影響最大）的該色棋 子的影響。如此一來(lái)，半敞開(kāi)的區(qū)域便可為勢(shì)力所封閉，一此處于重重包圍的棋子由于周闈對(duì)方勢(shì) 力太盛，自己的勢(shì)力值反而為對(duì)方所顛倒，自然成為死子（但不是絕對(duì)的，如“倒脫靴”便 是死棋再生的例子）。本文講的只是一個(gè)基本方法，在真正操作時(shí)可以根據(jù)不同情況有一定的變化，對(duì)于優(yōu)秀 的圍棋軟件來(lái)說(shuō)，影響力也未必是線性疊加的。白方（做活方）眼位的確定首先，我們知道每塊棋子至少要兩個(gè)真眼才能做活。真眼與假眼的區(qū)別如右圖：在角上A點(diǎn)為己方占領(lǐng)為真眼，反之為假眼；在邊上AB兩點(diǎn)要俱為己方占領(lǐng)方為真眼；在 中央ABCD中己方須至少占領(lǐng)三點(diǎn)才能成

15、其為真眼，反之為假眼，當(dāng)然倘是己方已占領(lǐng)了其 中兩點(diǎn)，而另兩點(diǎn)無(wú)子，亦是真眼，因?yàn)檫@兩點(diǎn)見(jiàn)合（即兩點(diǎn)必得其一）?，F(xiàn)在我們來(lái)考慮何為“占領(lǐng)”？ “占領(lǐng)”的含意對(duì)于黑白雙方是不同的。對(duì)于白方：占領(lǐng)未必在該點(diǎn)要有白子，只需在該點(diǎn)的白方勢(shì)力極強(qiáng)即可，因?yàn)槿绱撕诜?即使在此落子也必為白方所吃，最終仍為白方占據(jù)。對(duì)于黑方：占領(lǐng)即在該點(diǎn)是黑子，沒(méi)有黑子的地方即使勢(shì)力再?gòu)?qiáng)，一旦白方落子于該處， 黑方也無(wú)可奈何。第二我們要明確，眼位未必非真即假，非假即真。如下圖：圖中白方在A位先行補(bǔ)一手可成真眼，反之黑方先行即成假眼。我們不妨稱之為半只 眼。一目眼位的判斷一目眼位判斷較為簡(jiǎn)單，只需如上所述計(jì)算即可，分三種類型：

16、真眼、假眼（可不計(jì)）、 白方先手真眼。二目以上（包括二目）五目以下（包括五目）空的判斷二目以上的眼位由于形狀更雜難以簡(jiǎn)單判斷。盡管形狀復(fù):雜，然而形狀數(shù)量有限（大約 基本型十幾種，經(jīng)旋轉(zhuǎn)、翻轉(zhuǎn)后為三、四十種），可以做成棋型庫(kù)進(jìn)行匹配，有五種類型： 白方先行一個(gè)真眼、總為一個(gè)真眼、白方先行兩個(gè)（兩個(gè)以上）真眼、總為兩個(gè)（兩個(gè)以上） 真眼及無(wú)真眼（可不計(jì)）。五目以上（不包括五目，下同）空的判斷五目以上的空，形狀極多，不可勝舉，故很難將之做成模式庫(kù)。但值得注意的是，五目以上的空（形狀完整）幾乎都可以成為兩個(gè)真眼。因此在判斷的 時(shí)候，我們暫先不妨將之判為兩個(gè)（兩個(gè)以上）真眼。死活的判斷有了以上眼位的確

17、定，我們便可以切入關(guān)鍵了。靜態(tài)眼位判斷的主要目的是判斷死活的 類型，即白先活，白先死與白后活。白先活，即白棋先行可以做活，后行則死。此種狀態(tài)的條件是以下之一：一個(gè)真眼與半只眼；三個(gè)半只眼。白先死，即白方即使先行也死。條件是以下之一：一個(gè)或無(wú)真眼，無(wú)半只眼；兩個(gè)或兩個(gè)以下的半只眼，無(wú)真眼。白后活，即白方即使后行也是活棋。條件是以下之一：兩個(gè)或兩個(gè)以上真眼：一個(gè)真眼與兩個(gè)或兩個(gè)以上半只眼；四個(gè)或四個(gè)以上半只眼。簡(jiǎn)單地說(shuō)，以一個(gè)真眼折合兩個(gè)半只眼。若少于三個(gè)半只眼，為白先死；等于三個(gè)半只 眼為白先活；大于三個(gè)半只眼為白后活。2、搜索（博弈樹(shù)）搜索算法是主線，但不如靜態(tài)眼位判斷來(lái)得復(fù)雜。博弈樹(shù)的奇數(shù)層

18、為白方（計(jì)算機(jī)），偶數(shù)層為黑方。如下圖：對(duì)于每個(gè)結(jié)點(diǎn)，以在此狀態(tài)下白活的可能性作為估價(jià)函數(shù)。對(duì)于奇數(shù)層白棋的選點(diǎn)，我們可以作如下限制：1、不走在黑棋包圍圈的外側(cè)；2、此子不能被黑棋一手提掉，且同被吃掉的一塊棋子個(gè)數(shù)小于四個(gè)（因?yàn)樗膫€(gè)或四個(gè) 以上棋子被提，可能是“倒脫靴”的妙手）。對(duì)于偶數(shù)層黑棋的選點(diǎn)，則限制在黑棋包圍圈及其內(nèi)部。在枚舉了白棋選點(diǎn)后，生成某一狀態(tài)，此狀態(tài)倘若是“白后活”，立即返回此狀態(tài)白活 （白活可能性為1）;否則，查找此狀態(tài)下是否有黑棋下某一手后，白呈“白先死”，則此結(jié) 點(diǎn)不用繼續(xù)擴(kuò)展，返回此狀態(tài)白死（白活可能性為0）。若不在上述兩種狀況之列，則擴(kuò)展下一層（黑棋），根據(jù)下一層的

19、狀態(tài)中白活可能性的 大小來(lái)給此結(jié)點(diǎn)估價(jià)。在枚舉子黑棋的選點(diǎn)后，對(duì)于每一黑棋選點(diǎn)，可生成一種狀態(tài)。此狀態(tài)下，若是“白先 活”，則立該返回白活（白活可能性為1）;否則，查找此狀態(tài)下是否有白棋下某一手后，白 呈“白后活”，則此結(jié)點(diǎn)不用繼續(xù)擴(kuò)展，返回此狀態(tài)白活（白活可能性為1）。如非上述兩種 狀況，則繼續(xù)擴(kuò)展結(jié)點(diǎn)，根據(jù)下一層的狀態(tài)中白死可能性的大小來(lái)給此結(jié)點(diǎn)估價(jià)。最后程序根據(jù)白話的可能性，選擇該值最大的落點(diǎn)落子。當(dāng)然在博弈樹(shù)中應(yīng)當(dāng)使用 B剪枝，在白棋層中將白活可能性小的結(jié)點(diǎn)剔除，不予擴(kuò)展；在黑棋層中，將白棋活可能性 大的結(jié)點(diǎn)剔除，不予擴(kuò)展。關(guān)于博弈樹(shù)的一些具體問(wèn)題可以參照有關(guān)資料。七、展望除了上述的方

20、法外，在人工智能領(lǐng)域還存在著這樣一些可行方案： 人工神經(jīng)網(wǎng)絡(luò)由于近年來(lái)人工神經(jīng)網(wǎng)絡(luò)的發(fā)展，也為闈棋程序找到了又一條道路，即增加人工神經(jīng)網(wǎng) 絡(luò)的部分，使軟件其具有一定的學(xué)習(xí)、記憶和聯(lián)想功能，將之與高手對(duì)弈，以吸收一定的“知 識(shí)”，培養(yǎng)棋感。美國(guó)Footland的MFGO就做了一些這方面的有益嘗試，但目前可能還不完 善?！岸嗝骈澠濉钡脑O(shè)計(jì)者、美國(guó)惠普電腦公司的工程師大衛(wèi)佛特蘭德所說(shuō)：“強(qiáng)力檢索對(duì) 圍棋全無(wú)作用，你得創(chuàng)造出一個(gè)像人一樣精明的程序來(lái)誠(chéng)然，圍棋是如此之復(fù)雜，僅靠 機(jī)械地教電腦如何下棋是遠(yuǎn)遠(yuǎn)不夠的，所以應(yīng)該使用人工神經(jīng)網(wǎng)絡(luò)令電腦“聰明”起來(lái)，讓 它主動(dòng)學(xué)習(xí)。但這方面的技術(shù)還并沒(méi)有達(dá)到很高的程度，故而目前也僅是一種設(shè)想。 專家系統(tǒng)專家系統(tǒng)已廣泛地運(yùn)用到