人工智能課程大作業(yè)

1、人工智能課程大作業(yè)作業(yè)題目 摘要：機器博弈是人工智能的一個重要研究分支，本文通過設(shè)計一個五子棋智能博奕程序，采用傳統(tǒng)的博弈樹算法，利用剪枝和極大極小樹搜索最佳位置，從而實現(xiàn)人機智能博弈。并對現(xiàn)有算法存在的問題進行探究改進，最后給出展示，結(jié)果表明效果比較理想。關(guān)鍵詞：人工智能；五子棋；博弈本組成員： 本人分工：-剪枝實現(xiàn)1 引言人工智能1是一門綜合新型的新興邊緣科學(xué)，與生物工程、空間技術(shù)并列為三大尖端技術(shù)，而機器博弈卻是其一個重要的研究分支。它研究如何利用計算機去實現(xiàn)那些過去只能靠人的智力去完成的工作，博弈為人工智能提供了一個很好的應(yīng)用場所。博弈過程可以采用與或樹進行知識表達，這種表達形式稱為博

2、弈樹。剪枝技術(shù)是博弈樹搜索中最常采用的策略。2 算法原理與系統(tǒng)設(shè)計根據(jù)五子棋游戲規(guī)則，此次五子棋游戲我們采用基于極大極小值分析法的剪枝算法來實現(xiàn)計算機走棋。剪枝技術(shù)是博弈樹搜索中最常采用的策略，剪枝搜索由極大極小值分析法演變而來2。極大極小分析法其基本思想或算法是：(1) 設(shè)博弈的雙方中一方為MAX，另一方為MIN。然后為其中的一方(例如MAX)尋找一個最優(yōu)行動方案。(2) 為了找到當(dāng)前的最優(yōu)行動方案，需要對各個可能的方案所產(chǎn)生的后果進行比較,具體地說，就是要考慮每一方案實施后對方可能采取的所有行動，并計算可能的得分。(3) 為計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈

3、樹端節(jié)點的得分。此時估算出來的得分稱為靜態(tài)估值。(4) 當(dāng)端節(jié)點的估值計算出來后，再推算出父節(jié)點的得分，推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父節(jié)點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點，選其子節(jié)點中一個最小的得分作為父節(jié)點的得分，這是為了立足于最壞的情況。這樣計算出的父節(jié)點的得分稱為倒推值。(5) 如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動方案。上述的極小極大分析法，實際是先生成一棵博弈樹，然后再計算其倒推值，至使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上提出了-剪枝技術(shù)。-剪枝技術(shù)的基本思想或算法是，邊生

4、成博弈樹邊計算評估各節(jié)點的倒推值，并且根據(jù)評估出的倒推值范圍，及時停止擴展那些已無必要再擴展的子節(jié)點，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機器開銷，提高了搜索效率。具體的剪枝方法如下：(1) 對于一個與節(jié)點MIN，若能估計出其倒推值的上確界，并且這個值不大于 MIN的父節(jié)點(一定是或節(jié)點)的估計倒推值的下確界，即，則就不必再擴展該 MIN節(jié)點的其余子節(jié)點了(因為這些節(jié)點的估值對MIN父節(jié)點的倒推值已無任何影響了)。這一過程稱為剪枝。(2) 對于一個或節(jié)點MAX，若能估計出其倒推值的下確界，并且這個值不小于 MAX的父節(jié)點(一定是與節(jié)點)的估計倒推值的上確界，即，則就不必再擴展該MAX節(jié)

5、點的其余子節(jié)點了(因為這些節(jié)點的估值對MAX父節(jié)點的倒推值已無任何影響了)。這一過程稱為剪枝。圖2.1 系統(tǒng)流程圖圖2.2 系統(tǒng)結(jié)構(gòu)圖3 系統(tǒng)實現(xiàn)首先構(gòu)造棋型估分，對五子棋當(dāng)前局勢的分析，對每步進行估分；然后應(yīng)用博弈樹，提高AI智能，考慮層數(shù)，提高AI智能，接下來應(yīng)用-剪枝，提高AI速度，經(jīng)過-剪枝，可以極大的減少搜索的數(shù)量，從而提高了的AI速度，極大的減少了搜索層數(shù)對AI速度的影響。4 實驗或測試結(jié)果實驗方案及結(jié)果：.檢測雙三或三活三 .判斷剩余空間是否能成五子 .剪枝5 結(jié)論通過對AI的學(xué)習(xí)，了解了極大極小值分析法的原理，以及這種博弈樹的不足，當(dāng)搜索層數(shù)過多時，計算量太大，嚴重影響了計算機下棋的速度，我們采用剪枝技術(shù)來解決這一問題，減掉不必要的枝，從而極大地減少了搜索層數(shù)對計算時間的影響。雖然對極大極小分析法做了時間方面的改進，但仍有不足。由于AI是有一定的失誤率存在，所以，要想提高計算機走棋的精準度，增加搜索層數(shù)是很有必要的，而搜索層數(shù)對計算速度的影響又是不可避免的，并且影響很大，僅僅依靠對博弈樹進行剪枝是不夠的，還需進一步優(yōu)化。希望能在后續(xù)的課程學(xué)習(xí)中能進一步優(yōu)化五子棋，提升AI的精準度，在增加搜索層數(shù)的同時，極大的減少對計算