本文關(guān)鍵詞：基于改進(jìn)博弈樹的黑白棋設(shè)計與實現(xiàn)，由筆耕文化傳播整理發(fā)布。

【摘要】： 計算機的人工智能(Artificial Intelligence,簡稱AI)研究一直是人類一個富于挑戰(zhàn)的實踐。讓計算機具有智能,是科研學(xué)者一直為之奮斗的課題。而在計算機AI的研究領(lǐng)域中,讓傳統(tǒng)的棋類博弈游戲具有智能,一直是人們關(guān)注和研究的內(nèi)容。棋類博弈人工智能,一般包括博弈搜索、局面評估兩個方面。頂尖的博弈智能系統(tǒng)還具備自學(xué)習(xí)的能力,在對局中通過學(xué)習(xí)不斷地提高AI。各種棋類游戲雖然玩法各異,都是基本的博弈算法是通用。其中,作為博弈游戲AI最核心的博弈樹搜索算法,是整個博弈AI的基礎(chǔ),同時也是最核心的內(nèi)容。所以,對博弈樹搜索算法的研究和設(shè)計,具有重要的現(xiàn)實意義。本論文就是通過對博弈搜索關(guān)鍵技術(shù)的分析,設(shè)計和實現(xiàn)一個基于改進(jìn)博弈樹搜索算法的黑白棋對弈系統(tǒng)。 本論文對基于改進(jìn)博弈樹的黑白棋設(shè)計與實現(xiàn)工作,主要體現(xiàn)在以下幾個方面: 一、對博弈游戲核心的博弈樹搜索算法等關(guān)鍵技術(shù)進(jìn)行了較全面的研究和分析。從基本的min-max算法、alpha-beta剪枝、到基于啟發(fā)式的優(yōu)化策略、基于期望窗口和有損剪枝的優(yōu)化策略,到使用多處理器的并行博弈計算等;盡量做到了全面而又系統(tǒng),為后面的博弈樹搜索算法的設(shè)計和改進(jìn)奠定了基礎(chǔ)。 二、以面向?qū)ο蟮脑O(shè)計思想,設(shè)計和實現(xiàn)黑白棋的人工智能對弈系統(tǒng)。在設(shè)計上,采用了完全面向?qū)ο蟮姆椒?把人工智能的各個方面抽象成人類智能對應(yīng)的推理、分析、記憶和自學(xué)習(xí)幾個方面,然后對這幾個部分分別進(jìn)行設(shè)計,改變了以往以算法為核心的形式。 三、在黑白棋博弈樹搜索算法的實現(xiàn)上,對原來的博弈樹搜索算法進(jìn)行了一定改進(jìn)。自行設(shè)計了一個基于雙置換表、淺層探測啟發(fā)和 殺手‖啟發(fā)的搜索算法,并且具備動態(tài)選擇要排序的結(jié)點進(jìn)行排序的能力。這樣大大提高了alpha-beta剪枝的效率。同時使用零窗口搜索的MTD(f)方法,一方面提高了效率,另一方面有利于以后的并行計算實現(xiàn)的擴展。 四、黑白棋的下棋規(guī)則和局面評估方面,使用了位棋盤的數(shù)據(jù)結(jié)構(gòu)的設(shè)計和基于模板匹配的局面評估方法,最大程度地提高了下棋的效率和AI。位棋盤和基于模板匹配的方法是黑白棋程序現(xiàn)階段先進(jìn)的設(shè)計方法,同時也是其它棋類系統(tǒng)設(shè)計的發(fā)展趨勢。 五、在黑白棋對弈系統(tǒng)開局庫和自學(xué)習(xí)方面:開局庫并沒有使用傳統(tǒng)的樹型結(jié)構(gòu),而是使用基于一維線性表的二分查找方法來實現(xiàn)。同時,區(qū)別于一般的系統(tǒng)的自學(xué)習(xí)能力,就是自學(xué)習(xí)除了可以提高AI之外,還可以不斷地提高下棋效率。 最后,通過測試,改進(jìn)的啟發(fā)式博弈樹搜索比原alpha-beta搜索和傳統(tǒng)的啟發(fā)搜索在效率上有了相當(dāng)?shù)奶岣�。同時經(jīng)測試,本黑白棋人工智能對弈系統(tǒng)已經(jīng)具備了較高的智能,具有一定的研究和使用意義。
【關(guān)鍵詞】：黑白棋 博弈樹搜索 模板匹配 自學(xué)習(xí)
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2010
【分類號】：TP18
【目錄】：

• 摘要5-7
• Abstract7-11
• 第一章 緒論11-16
• 1.1 計算機棋弈人工智能的發(fā)展概況11-13
• 1.1.1 馮諾依曼的博弈論和圖靈的紙上機器11
• 1.1.2 alpha-beta 剪枝的博弈搜索的出現(xiàn)11-12
• 1.1.3 基于alpha-beta 剪枝的算法發(fā)展12-13
• 1.1.4 棋局分析技術(shù)的發(fā)展13
• 1.1.5 自學(xué)習(xí)能力的引入13
• 1.2 黑白棋計算機博弈的發(fā)展概況13-14
• 1.3 本文的主要研究內(nèi)容及意義14-15
• 1.4 本文結(jié)構(gòu)15-16
• 第二章 博弈樹搜索理論與技術(shù)的分析16-29
• 2.1 博弈樹和極大-極小搜索16-18
• 2.2 局面評估——葉子結(jié)點的計算18-19
• 2.3 alpha-beta 剪枝搜索19-22
• 2.4 提高alpha-beta 剪枝的方法22-25
• 2.4.1 結(jié)點有序22-24
• 2.4.2 期望窗口24-25
• 2.5 一些其它的策略25-29
• 2.5.1 并行與串行的優(yōu)化25-27
• 2.5.2 選擇性搜索策略27-29
• 第三章 黑白棋系統(tǒng)基于面向?qū)ο蟮脑O(shè)計29-36
• 3.1 黑白棋的概述29-30
• 3.2 面向?qū)ο蟮南到y(tǒng)設(shè)計30-32
• 3.3 棋盤數(shù)據(jù)結(jié)構(gòu)的設(shè)計32-35
• 3.4 本章小結(jié)35-36
• 第四章 黑白棋博弈樹搜索的改進(jìn)設(shè)計36-47
• 4.1 基于啟發(fā)式alpha-beta 搜索的優(yōu)化設(shè)計36-40
• 4.1.1 啟發(fā)式的搜索36-37
• 4.1.2 使用0-窗口的alpha-beta 搜索37-40
• 4.2 置換表啟發(fā)40-44
• 4.2.1 置換表的設(shè)計40-42
• 4.2.2 基于雙置換表的優(yōu)化實現(xiàn)42-44
• 4.3 “殺手”啟發(fā)的實現(xiàn)44-45
• 4.4 動態(tài)選擇排序結(jié)點45-46
• 4.5 終局搜索的實現(xiàn)46
• 4.6 本章小結(jié)46-47
• 第五章 黑白棋局面評估和基于開局庫學(xué)習(xí)的實現(xiàn)47-54
• 5.1 黑白棋局面評估的實現(xiàn)47-50
• 5.1.1 基于模板匹配的局面評估的實現(xiàn)47-49
• 5.1.2 基于統(tǒng)計學(xué)計算模板分值49-50
• 5.1.3 棋局樣本的選擇50
• 5.2 開局庫的實現(xiàn)50-52
• 5.2.1 基礎(chǔ)開局庫的實現(xiàn)50-51
• 5.2.2 開局庫基于勝率下棋的改進(jìn)51-52
• 5.3 基于開局庫的自學(xué)習(xí)52
• 5.4 本章小結(jié)52-54
• 第六章 系統(tǒng)AI 的測試與分析54-58
• 6.1 改進(jìn)的博弈樹搜索效果測試54
• 6.2 系統(tǒng)AI 效果的測試54-56
• 6.3 結(jié)果分析56-58
• 結(jié)論58-60
• 參考文獻(xiàn)60-62
• 致謝62

【引證文獻(xiàn)】

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 曹森;對α-β剪枝算法的性能改進(jìn)研究[D];內(nèi)蒙古師范大學(xué);2012年

  本文關(guān)鍵詞：基于改進(jìn)博弈樹的黑白棋設(shè)計與實現(xiàn)，，由筆耕文化傳播整理發(fā)布。

本文編號：312215