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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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