計算機圍棋中的算法研究.pdf

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

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

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

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

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

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

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

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