五子棋計(jì)算機(jī)博弈系統(tǒng)的研究與設(shè)計(jì).pdf

1、計(jì)算機(jī)博弈是人工智能領(lǐng)域最具挑戰(zhàn)的研究分支之一。它是研究人腦思維的載體，是計(jì)算機(jī)技術(shù)與博弈論相結(jié)合的產(chǎn)物，是人工智能領(lǐng)域的“試驗(yàn)田”，被譽(yù)為人工智能的“果蠅”。因此，有關(guān)計(jì)算機(jī)博弈的理論與實(shí)踐研究，將可以促進(jìn)人工智能的發(fā)展。在計(jì)算機(jī)博弈中，棋類(lèi)博弈是其研究熱點(diǎn)之一，因?yàn)槿藗兿嘈糯嬖谟谄孱?lèi)博弈中的智能信息或許可以應(yīng)用到人類(lèi)智能活動(dòng)中。
　　五子棋博弈是棋類(lèi)博弈中至關(guān)重要的組成部分，其普及程度僅次于國(guó)際象棋。它具有聚集博弈典型意義、容

2、易深入研究、博弈結(jié)果直觀反應(yīng)機(jī)器智能程度等優(yōu)點(diǎn)。因此可以把五子棋博弈作為計(jì)算機(jī)博弈的典型代表之一，對(duì)其進(jìn)行深入研究，從而促使計(jì)算機(jī)博弈理論和實(shí)踐研究的發(fā)展，進(jìn)而推動(dòng)人工智能事業(yè)不斷地前進(jìn)。
　　本文以五子棋為載體對(duì)計(jì)算機(jī)博弈相關(guān)理論與技術(shù)進(jìn)行了分析與研究。針對(duì)傳統(tǒng)Alpha-Beta剪枝算法搜索效率較低以及博弈水平不高的問(wèn)題，提出了一種基于連續(xù)沖四搜索的Alpha-Beta剪枝算法以及基于搜索限定的Alpha-Beta剪枝算法;針

3、對(duì)傳統(tǒng)基于棋型估值函數(shù)的參數(shù)主要由經(jīng)驗(yàn)獲得并通過(guò)手工進(jìn)行調(diào)整，存在人為不確定性的問(wèn)題，提出了一種新的自適應(yīng)慣性權(quán)重混沌粒子群算法(CPSO-NAIW)，并把它首次應(yīng)用到五子棋估值函數(shù)參數(shù)優(yōu)化問(wèn)題中。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)Alpha-Beta剪枝算法有效地提高了搜索效率和博弈水平;采用本文提出的CPSO-NAIW算法優(yōu)化后參數(shù)的五子棋博弈系統(tǒng)的博弈水平得到了很大提升。
　　本文首先介紹了計(jì)算機(jī)博弈相關(guān)概念與技術(shù)，然后分析了五子

4、棋博弈組成要素并利用事件對(duì)策論對(duì)其進(jìn)行數(shù)學(xué)建模，研究了五子棋博弈中的搜索算法以及估值函數(shù)，最后對(duì)系統(tǒng)進(jìn)行了設(shè)計(jì)與實(shí)現(xiàn)。
　　本文核心技術(shù)與創(chuàng)新點(diǎn)如下:
　　(1)提出了一種基于連續(xù)沖四搜索的Alpha-Beta剪枝算法。根據(jù)五子棋博弈的特點(diǎn)，在Alpha-Beta剪枝算法中引入連續(xù)沖四搜索這種強(qiáng)有力的進(jìn)攻手段，并采用搜索范圍限定以及對(duì)連續(xù)沖四成功進(jìn)行保存，當(dāng)下次遇到相同局面時(shí)，優(yōu)先對(duì)存儲(chǔ)的連續(xù)沖四著法進(jìn)行搜索的連續(xù)沖四啟發(fā)方

5、法，以減少無(wú)用和重復(fù)搜索。該算法提高了搜索效率和博弈水平。
　　(2)提出了一種基于搜索限定的Alpha-Beta剪枝算法。根據(jù)五子棋落子比較集中和脫離戰(zhàn)場(chǎng)思想，對(duì)棋盤(pán)搜索區(qū)域進(jìn)行劃分，并根據(jù)不同搜索區(qū)域落子對(duì)局面的影響程度采用不同的搜索深度，以減少無(wú)用搜索。該算法在不影響博弈水平的情況下，提高了搜索效率。
　　(3)提出了一種新的自適應(yīng)慣性權(quán)重混沌粒子群算法(CPSO-NAIW)。該算法從慣性權(quán)重的調(diào)整以及如何擺脫局部極值

6、兩個(gè)方面入手來(lái)改善粒子群算法(Particle Swarm Optimization，PSO)的性能。首先采用粒子相對(duì)于群體極值位置的距離對(duì)權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整，把權(quán)重的變化與粒子的位置狀態(tài)信息關(guān)聯(lián)起來(lái)的方法，減少了算法陷入局部極值的概率，然后在算法陷入局部極值時(shí)，對(duì)群體極值位置進(jìn)行混沌優(yōu)化，以使粒子搜索局部極值外的新鄰域和新路徑，增強(qiáng)了算法跳出局部極值的可能，最后把CPSO-NAIW算法首次應(yīng)用到五子棋估值函數(shù)的參數(shù)優(yōu)化問(wèn)題中，以解決傳統(tǒng)

7、估值參數(shù)僅通過(guò)手工調(diào)整，存在人為不確定的問(wèn)題。采用該算法優(yōu)化后參數(shù)的五子棋博弈系統(tǒng)的博弈水平有顯著提升。
　　本文以五子棋為載體對(duì)計(jì)算機(jī)博弈中至關(guān)重要的搜索算法以及估值函數(shù)進(jìn)行了相關(guān)研究與改進(jìn)。在搜索算法方面，提出了一種基于連續(xù)沖四搜索的Alpha-Beta剪枝算法以及基于搜索限定的Alpha-Beta剪枝算法。在估值函數(shù)方面，提出了一種CPSO-NAIW算法，并把它首次應(yīng)用到估值函數(shù)的參數(shù)優(yōu)化問(wèn)題中。實(shí)驗(yàn)結(jié)果表明，兩種改進(jìn)的Al