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

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

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

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

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

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

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

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

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