本文關(guān)鍵詞：基于搜索算法的人工智能在五子棋博弈中的應(yīng)用研究，由筆耕文化傳播整理發(fā)布。

【摘要】： 本文以計算機五子棋博弈系統(tǒng)作為研究課題,在對大量的相關(guān)文獻(xiàn)進(jìn)行分析研究的基礎(chǔ)上,按照人工智能和計算機博弈的一般原理設(shè)計了一個五子棋博弈系統(tǒng)的基本模型,并作了簡單的實現(xiàn)和驗證,所做的工作包括三個方面: 第一研究了五子棋在計算機中的表示問題,討論了計算機中存貯棋局和識別下棋次序,局勢狀態(tài)變化及局勢特征、走法產(chǎn)生等方法。 第二研究了博弈樹的極小極大搜索技術(shù)及在此基礎(chǔ)上的Alpha-Beta剪枝過程和剪枝優(yōu)化問題。實現(xiàn)將候選的后繼節(jié)點按位置鄰近順序排序,使剪枝過程得到優(yōu)化。 第三根據(jù)五子棋的特點,提取棋局局勢的若干特征,對這些特征賦加權(quán)分,并對整個棋局進(jìn)行特征統(tǒng)計,采用線性函數(shù)求得棋局的總估計分值,從而提高了五子棋程序?qū)牡乃胶湍芰Α?在上述工作的基礎(chǔ)上,本文的創(chuàng)新性研究主要包括以下兩個方面:第一對五子棋博弈的專業(yè)知識進(jìn)行了認(rèn)真的整理,針對五子棋博弈規(guī)則簡單、局勢判斷清楚的特點,對五子棋常見的開局、定式及其后的對局做了細(xì)致的統(tǒng)計分析,闡明了五子棋對弈中黑白雙方優(yōu)劣勢并非均衡的規(guī)律,這一規(guī)律作為一個指導(dǎo)原則在設(shè)計五子棋博弈系統(tǒng)時起到重要作用。 第二通過線性函數(shù)獲得的總估計值,實現(xiàn)了算法的優(yōu)化和加強,主要有以下兩個方面:在執(zhí)行常規(guī)的Alpha-Beta搜索和NegaScout算法之前,使用置換表搜索避免相同局面的節(jié)點的搜索。通過使用威脅空間搜索,讓計算機對某一局面找出全部的致勝威脅次序,避免了對靜態(tài)估值函數(shù)的調(diào)用,只有計算機對當(dāng)前局面無法找到致勝威脅次序時,才執(zhí)行對靜態(tài)估值函數(shù)的調(diào)用,由于五子棋博弈中,黑方先行者占有很強的優(yōu)勢,大多數(shù)局面往往都能找到致勝威脅次序,所以采用威脅空間搜索,結(jié)果表明,可以極大的提高程序的表現(xiàn)和對弈水平。
【關(guān)鍵詞】：搜索算法 人工智能 五子棋 博弈
【學(xué)位授予單位】：中國石油大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2007
【分類號】：TP18
【目錄】：

• 中文摘要4-6
• 英文摘要6-10
• 第1章 緒論10-19
• 1.1 課題來源10-11
• 1.2 博弈簡史11-13
• 1.3 研究計算機博弈的意義13-15
• 1.4 計算機博弈過程15-17
• 1.5 計算機五子棋基本知識介紹17
• 1.6 本文解決的問題17-19
• 第2章 狀態(tài)空間表示與走法產(chǎn)生19-25
• 2.1 棋盤局勢狀態(tài)表示19-21
• 2.2 棋盤中下棋的順序表示21
• 2.3 狀態(tài)的變化21
• 2.4 特征的表示21-23
• 2.5 走法產(chǎn)生23-24
• 2.6 小結(jié)24-25
• 第3章 博弈樹的搜索技術(shù)25-40
• 3.1 極小極大樹搜索算法25-29
• 3.2 Alpha-Beta 剪枝過程29-33
• 3.3 Alpha-Beta 剪枝存在的問題及優(yōu)化33-35
• 3.4 NegaScout 搜索35-39
• 3.5 小結(jié)39-40
• 第4章 靜態(tài)估值函數(shù)40-45
• 4.1 棋盤局勢特征40-42
• 4.2 估值42-44
• 4.3 靜態(tài)估值函數(shù)的不足及實踐結(jié)果44
• 4.4 小結(jié)44-45
• 第5章 搜索算法的優(yōu)化與增強45-70
• 5.1 置換表（Transposition Table）的搜索45-55
• 5.1.1 哈希表（Hash Table）47-50
• 5.1.2 應(yīng)用置換表的其它問題50-54
• 5.1.3 Zobrist 哈希技術(shù)54-55
• 5.2 威脅空間搜索（Threat Space Search）55-68
• 5.2.1 專業(yè)術(shù)語和“威脅次序”56-58
• 5.2.2 人類專業(yè)棋手的分析58-60
• 5.2.3 計算機程序的策略60
• 5.2.4 人與計算機60-62
• 5.2.5 威脅空間搜索62-67
• 5.2.6 算法優(yōu)化后效果的檢驗67-68
• 5.2.7 威脅空間搜索的不足68
• 5.3 小結(jié)68-70
• 第6章 結(jié)論70-71
• 參考文獻(xiàn)71-73
• 致謝73-74
• 個人簡歷及在學(xué)期間的研究成果74

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前2條

1 肖齊英,王正志;博弈樹搜索與靜態(tài)估值函數(shù)[J];計算機應(yīng)用研究;1997年04期

2 王魯明,戴汝為;在計算機圍棋中形象思維的研究[J];自動化學(xué)報;1997年04期

  本文關(guān)鍵詞：基于搜索算法的人工智能在五子棋博弈中的應(yīng)用研究，，由筆耕文化傳播整理發(fā)布。

本文編號：334237