計(jì)算機(jī)圍棋中的算法研究.pdf

1、博弈是人工智能的重要研究主題，人工智能的發(fā)展在很大程度上得益于博弈研究的發(fā)展。作為博弈研究的主要內(nèi)容之一，棋類(lèi)博弈得到了滿意的解決，唯一的例外的是圍棋，目前最優(yōu)秀的圍棋程序的水平還不及人類(lèi)初級(jí)棋手。由于圍棋的搜索空間太大、計(jì)算機(jī)難于處理模糊概念且難于設(shè)計(jì)學(xué)習(xí)算法，造成了計(jì)算機(jī)圍棋程序的棋力難于提高。圍棋是檢驗(yàn)人工智能發(fā)展水平的良好環(huán)境，如何提高圍棋程序的棋力是人工智能領(lǐng)域的一大難題。同時(shí)，開(kāi)發(fā)出與人類(lèi)棋手水平相當(dāng)?shù)膰宄绦蛞灿兄趯?duì)人類(lèi)

2、認(rèn)知能力的理解。所以計(jì)算機(jī)圍棋研究具有重要的理論意義和實(shí)用價(jià)值。 我們首先介紹了國(guó)內(nèi)外計(jì)算機(jī)圍棋研究現(xiàn)狀，包括基礎(chǔ)算法、搜索算法和學(xué)習(xí)算法三方面并介紹了部分計(jì)算機(jī)圍棋程序，認(rèn)為計(jì)算機(jī)圍棋的搜索算法主要有minmax算法、alphabeta算法、failsoft算法、negmax算法、negscout算法和mtdf算法等等，涉及到的學(xué)習(xí)算法和理論基礎(chǔ)主要有組合博弈理論、數(shù)學(xué)形態(tài)學(xué)、蒙特卡羅算法、模糊學(xué)習(xí)、分治法、強(qiáng)化學(xué)習(xí)算法、遺傳

3、算法、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、貝葉斯模式分類(lèi)、基于解釋的泛化和并行算法等等，指出了目前研究中存在的主要不足主要表現(xiàn)為局面表示法欠完善、中盤(pán)策略欠完整以及學(xué)習(xí)算法欠成熟。 然后，我們簡(jiǎn)述了本研究的相關(guān)理論基礎(chǔ)，包括數(shù)學(xué)形態(tài)學(xué)、有限狀態(tài)機(jī)、線性模型、感知機(jī)與遺傳算法。 接著，我們闡明了本研究提出的棋手思維模型、基礎(chǔ)算法、搜索算法、學(xué)習(xí)算法及相應(yīng)實(shí)驗(yàn)結(jié)果。具體說(shuō)來(lái)，我們完成的主要工作與創(chuàng)新點(diǎn)包括以下幾個(gè)方面： 一、提出了

4、一個(gè)完整的棋手思維模型。這是在提出了領(lǐng)土領(lǐng)海和領(lǐng)空等地域概念、提出了局面的層次表示法、歸納并分類(lèi)了大量圍棋術(shù)語(yǔ)、提取了目標(biāo)概念、建立了目標(biāo)圖、總結(jié)了若干目標(biāo)選擇原則和走步屬性并分析了棋風(fēng)概念的基礎(chǔ)上完成的。這個(gè)模型的特點(diǎn)在于它的完整性和圍棋術(shù)語(yǔ)的分類(lèi)、目標(biāo)選擇原則與走步屬性的全面性。二、設(shè)計(jì)了基于數(shù)學(xué)形態(tài)學(xué)的局面層次表示法、棋群聚類(lèi)算法和地域劃分算法。這些有統(tǒng)一理論基礎(chǔ)的算法計(jì)算簡(jiǎn)單，實(shí)驗(yàn)結(jié)果表明其效果良好。利用已有的數(shù)學(xué)形態(tài)學(xué)理論可以

5、設(shè)計(jì)更多有意義的啟發(fā)式策略。 三、設(shè)計(jì)了PEMIS模式編碼方法。它基于模式的鄰近特征、行列特征和輪廓特征進(jìn)行編碼，其突出優(yōu)點(diǎn)是與模式的黑白對(duì)稱(chēng)性、旋轉(zhuǎn)與翻轉(zhuǎn)對(duì)稱(chēng)性以及平移對(duì)稱(chēng)性均無(wú)關(guān)，實(shí)驗(yàn)結(jié)果表明這種模式編碼方法性能良好。在基礎(chǔ)算法方面，我們還設(shè)計(jì)了一種走步增量算法。 四、設(shè)計(jì)了復(fù)合目標(biāo)搜索算法。我們認(rèn)為復(fù)合目標(biāo)可看作是由“與”或“或”關(guān)系構(gòu)成的單一目標(biāo)的二維向量。復(fù)合目標(biāo)搜索算法的優(yōu)點(diǎn)是其調(diào)用的基本函數(shù)可由單一目標(biāo)搜索

6、算法的基本函數(shù)合成。我們還比較了經(jīng)典搜索算法的性能。 五、設(shè)計(jì)了PEMIS模式庫(kù)與定式庫(kù)學(xué)習(xí)算法。實(shí)驗(yàn)結(jié)果表明了其有效性，最終學(xué)習(xí)到的模式庫(kù)與定式庫(kù)占用的空間比較小。另外，還設(shè)計(jì)了ZOBRIST定式庫(kù)學(xué)習(xí)算法，實(shí)驗(yàn)結(jié)果也表明了其有效性。在學(xué)習(xí)算法方面，我們還設(shè)計(jì)了棋形與氣術(shù)語(yǔ)的示教學(xué)習(xí)算法和棋風(fēng)模型的遺傳學(xué)習(xí)算法。 六、開(kāi)發(fā)了以此棋手思維模型為核心的計(jì)算機(jī)圍棋程序ShoutGo，實(shí)現(xiàn)了上述各算法。ShoutGo認(rèn)為棋手擁

7、有模式庫(kù)和定式庫(kù)，有各自的棋風(fēng)；棋手在完成棋群聚類(lèi)和地域劃分后，在目標(biāo)選擇原則的指引下以對(duì)方最后所下之子為焦點(diǎn)進(jìn)行目標(biāo)猜測(cè)，同樣在目標(biāo)選擇原則及棋風(fēng)的指引下生成特定目標(biāo)，繼而以目標(biāo)為導(dǎo)向在各自的模式庫(kù)和定式庫(kù)推薦走步的作用下進(jìn)行搜索發(fā)現(xiàn)走步，再根據(jù)走步屬性選取特定走步，如果目標(biāo)不成功或無(wú)可行走步，則重新進(jìn)行地域劃分或根據(jù)其它決策原則生成其它目標(biāo)，直到發(fā)現(xiàn)合適走步；在這一過(guò)程中，模式庫(kù)和定式庫(kù)影響了走步的推薦，棋風(fēng)影響了目標(biāo)之間的跳轉(zhuǎn)。

8、 最后，我們探討了棋手思維模型的評(píng)價(jià)、走步增量算法與走步掃描算法的關(guān)系、數(shù)學(xué)形態(tài)學(xué)方法在基礎(chǔ)算法中的應(yīng)用、劫與共活現(xiàn)象對(duì)搜索的影響、搜索樹(shù)特點(diǎn)與心理因素的關(guān)系、搜索時(shí)間估計(jì)、局面評(píng)價(jià)函數(shù)、目標(biāo)搜索的可學(xué)習(xí)性以及棋風(fēng)建模等問(wèn)題，并探討了機(jī)器學(xué)習(xí)方法在計(jì)算機(jī)圍棋中的應(yīng)用可能性，提出了進(jìn)一步的研究計(jì)劃。 計(jì)算機(jī)圍棋研究作為人工智能領(lǐng)域的一個(gè)分支，與心理學(xué)有著天然聯(lián)系。我們?cè)谘芯窟^(guò)程中，特別強(qiáng)調(diào)以人類(lèi)棋手為本的原則，力求棋手思維模