五子棋人工智能的分析與實現(xiàn)

五子棋人工智能的分析與實現(xiàn)五子棋人工智能的分析與實現(xiàn)五子棋人工智能的分析與實現(xiàn)資料僅供參考文件編號：2022年4月五子棋人工智能的分析與實現(xiàn)版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：五子棋人工智能的分析與實現(xiàn)摘要：機器博弈是人工智能的一個重要研究分支，本文通過設(shè)計一個五子棋智能博奕程序，采用傳統(tǒng)的博弈樹算法，利用剪枝和極大極小樹搜索最佳位置，從而實現(xiàn)人機智能博弈。并對現(xiàn)有算法存在的問題進(jìn)行探究改進(jìn)，最后給出程序?qū)嵗?，結(jié)果表明效果比較理想。關(guān)鍵詞：五子棋；人工智能；博弈；1主要傳統(tǒng)算法博弈樹傳統(tǒng)的算法是采用博弈樹法來設(shè)計程序。以甲乙兩人下棋為例，甲有很多種落子方式，乙也有多種應(yīng)對走法，如果把所有的走法列出來，自然就構(gòu)成了一棵樹，即為搜索樹，也稱博弈樹。樹的根結(jié)點為先手的第一步走法，下面的走法構(gòu)成了樹的子結(jié)點，直至棋局結(jié)束。顯然，如果棋盤足夠大，子結(jié)點數(shù)會以幾何級數(shù)上升，而我們的任務(wù)是從這些子結(jié)點中尋找一個對己方最有利的結(jié)點，從而得到棋局的最佳走法。這必然是一個指數(shù)復(fù)雜度的過程，費時低效，無法搜索到最終結(jié)果（除了棋局結(jié)束），通常只能達(dá)到一個有限的深度，在有限的范圍內(nèi)來判斷走法的好壞，得到一個局部最優(yōu)解。[2-3]因此，有必要做一些調(diào)整改進(jìn)，以提高算法的效率和質(zhì)量。極大極小算法極大極小搜索算法就是在博弈樹在尋找最優(yōu)解的一個過程，這主要是一個對各個子結(jié)點進(jìn)行比較取舍的過程，定義一個估值函數(shù)F(n)來分別計算各個終結(jié)點的分值，通過雙方的分值來對棋局形勢進(jìn)行分析判斷。還是以甲乙兩人下棋為例，甲為max，乙為min。當(dāng)甲走棋時，自然在博弈樹中尋找最大點的走法，輪到乙時，則尋找最小點的走法，如此反復(fù)，這就是一個極大極小搜索過程，以此來尋找對機器的最佳走法。其中估值函數(shù)通常是為了評價棋型的狀態(tài)，根據(jù)實現(xiàn)定義的一個棋局估值表，對雙方的棋局形態(tài)進(jìn)行計算，根據(jù)得到的估值來判斷應(yīng)該采用的走法。棋局估值表是根據(jù)當(dāng)前的棋局形勢，定義一個分值來反映其優(yōu)勢程度，來對整個棋局形勢進(jìn)行評價。本程序采用的估值表如下：狀態(tài)眠二假活三眠三活二沖四假活三活三活四連五分值245812154090200一般來說，我們采用的是15×15的棋盤，棋盤的每一條線稱為一路，包括行、列和斜線，4個方向，其中行列有30路，兩條對角線共有58路，整個棋盤的路數(shù)為88路。考慮到五子棋必須要五子相連才可以獲勝，這樣對于斜線，可以減少8路，即有效的棋盤路數(shù)為72路。對于每一路來說，第i路的估分為E(i)=Ec(i)-Ep(i)，其中Ec(i)為計算機的i路估分，Ep(i)為玩家的i路估分。棋局整個形勢的估值情況通過對各路估分的累加進(jìn)行判斷，即估值函數(shù)：αβ剪枝αβ剪枝算法簡單來說，就是在搜索過程中減少一定的冗余現(xiàn)象，如已經(jīng)找到極大值，執(zhí)行該走法就可以獲勝，則無須再往下進(jìn)行搜索比較，此過程即為剪枝。對于極大的MAX結(jié)點，稱為α剪枝；反之為β剪枝。具體規(guī)則可以簡單描述如下：α剪枝：對于極大值層結(jié)點的α值如果不小于它的任一祖先極小值層結(jié)點的β值，即α(后續(xù)層)≥β(祖先層)，則可中止該極大值層中這個MAX節(jié)點以下的搜索過程，這個MAX節(jié)點最終的倒推值就確定為這個α值。β剪枝：對于極小值結(jié)點層的β值如果不大于它任一祖先極大值層結(jié)點的α值，即α(祖先層)≥β(后續(xù)層)，則可中止對該極小值層中這個MIN節(jié)點以下結(jié)點的搜索，這個MIN節(jié)點最終的倒推值就確定為這個β值。[2]αβ剪枝可以進(jìn)一步進(jìn)行改進(jìn)，在走棋過程中，在中心先下的一方往往有一定的優(yōu)勢，雙方的搏斗糾纏都是在爭奪最佳位置，可以考慮從中心往外螺旋進(jìn)行擴(kuò)展搜索；另外由于防守的需要，落子的位置通常也是在彼此下子的附近，因此可以優(yōu)先考慮在這些位置進(jìn)行搜索，也就是對落子位置進(jìn)行排序預(yù)先搜索，更進(jìn)一步的縮減冗余現(xiàn)象，進(jìn)而提高搜索效率和行棋質(zhì)量。[5]2改進(jìn)傳統(tǒng)算法傳統(tǒng)算法最大的一個缺點還是在于它的指數(shù)復(fù)雜度問題，雖然通過剪枝、優(yōu)化搜索位置等方法減少了冗余，提高了一定的搜索效率，但都無法解決搜索深度增加帶來的呈幾何級數(shù)增加的巨大計算量問題。[4]在進(jìn)一步的實驗中發(fā)現(xiàn)，搜索超過7層以后，程序響應(yīng)速度明顯變慢，到9層會出現(xiàn)1-2s的間隔期。因此，通過研究五子棋的規(guī)律和特點，結(jié)合實際經(jīng)驗，可以對程序作一些預(yù)定的調(diào)整措施，從而提高算法的執(zhí)行效率和對弈能力?？s減搜索范圍對于15x15的棋盤，每一種走法都有上百種可能，如果對每種走法都進(jìn)行計算估值，則無疑大大增加了計算量，降低了算法的效率和質(zhì)量。根據(jù)規(guī)則和實際經(jīng)驗，我們知道只要考慮以棋子為中心的鄰近區(qū)域皆可，比如不大于4的距離通常為該子的有效范圍，同理我們還可以在對方的落子范圍進(jìn)行判斷估值。這樣可以縮減搜索范圍，同時提高算法的效率和走法的實用性。置換表搜索前面我們討論了利用αβ剪枝來處理冗余結(jié)點，對于已經(jīng)搜索過的結(jié)點，我們可以通過設(shè)置一張Hash表記錄該結(jié)點，這樣在后續(xù)的搜索過程中，可以對這些點的記錄進(jìn)行查詢?nèi)缦惹坝羞^記錄則直接調(diào)用，免于重新搜索，從而避免出現(xiàn)重復(fù)操作，加快搜索速度。該方法通常稱為置換表（TranspositionTable）。建立棋譜庫該方法廣泛應(yīng)用在象棋程序設(shè)計中，五子棋遠(yuǎn)比象棋簡單，該方法也更為有效實用。通過在數(shù)據(jù)庫中存儲一些開局“定式”手法和經(jīng)典棋局，開局階段，程序使用開局庫，一旦發(fā)現(xiàn)相同棋局，則直接調(diào)用該走法，無須再次搜索，同時建立數(shù)據(jù)庫來存儲失敗案例不斷進(jìn)行調(diào)整對策。該方法可以極大的提高程序的智能化，只是增加了額外的系統(tǒng)開銷。另外對于棋譜的匹配和存儲也是關(guān)鍵問題。[4]但是由于時間和選擇語言的限制，建立棋譜庫沒有在程序中得到實現(xiàn)。合理設(shè)置搜索深度理論上來說，為了尋找最優(yōu)解，最好是對完整博弈樹進(jìn)行完全搜索，但實際中是不可行的，無論是從時間上還是從系統(tǒng)資源上。在后面實際程序設(shè)計中，默認(rèn)為5層，當(dāng)然也可以根據(jù)不同機器配置加以調(diào)整，以達(dá)到最大效率。3實例分析在Windows7操作系統(tǒng)下，利用上述算法思想，采用ActionScript編程實現(xiàn)一個實現(xiàn)人機對戰(zhàn)的五子棋程序。通過實驗分析比較，程序的智能化和質(zhì)量效果較為理想。當(dāng)計算機執(zhí)黑時，基本上每次都能獲勝，且步驟、時間較短；當(dāng)玩家執(zhí)黑先行，計算機獲勝比率也較高，具有很好的智能性。4結(jié)束語本文介紹了一個智能五子棋的主要算法思想和實現(xiàn)技術(shù)，利用剪枝和極大極小樹搜索博弈樹，作出了一些改進(jìn)措施，尋求最佳下棋位置，從而提高了智能博弈的質(zhì)量。進(jìn)行優(yōu)化以后，五子棋程序的智能水平和搜索效率有了明顯的提升。本文所討論的算法思想和設(shè)計過程也為其他棋類游戲(如象棋和圍棋等)提供了一定的參考價值。此外，五子棋的國際規(guī)則較為復(fù)雜，加入了禁手判負(fù)、三手交換等規(guī)則限制黑手先行優(yōu)勢，可以在進(jìn)一步的工作中考慮實現(xiàn)。參考文獻(xiàn)：[1]蔡自興.人工智能及其應(yīng)用[M].北京：清華大學(xué)出版社,1999:2-12.[2]朱全民,陳松喬.五子棋算法的研究與思考[J].計算技術(shù)與自動化,2006(02):75-78.[3]董紅安,蔣秀英.智能五子棋博弈程序的核心算法[J].棗莊學(xué)院學(xué)報,2005(2):61-65.[4]蔣加伏,陳藹祥,唐賢英.基于知識推理的博弈樹搜索算法[J].計算機工程與應(yīng)用,2004(1):74-76.[5]張海峰,白振興,張登福.五子棋中的博弈智能設(shè)計[J].現(xiàn)代電子技術(shù),2004,27(7):25-27.附錄：程序截圖游戲運行中玩家先手勝利玩家先手失敗電腦先手勝利電腦先手失敗主要代碼packageClasses{ import.*; import.*; import.*; import /* *五子棋 */ publicclassGobangDocextendsMovieClip{ *gridsize; =(crty+.5)*gridsize; (chessman); (chessman); checkWinner(crtx,crty,crtSide); *gridsize; =(autoy+.5)*gridsize; aGridState[autoy][autox]=(BLACK+WHITE)-mySide; (chessman); (chessman); } oString(); varwinner:int=0; varstr1:String=getXLine(aGridState,xp,yp,side).join(""); varstr2:String=getYLine(aGridState,xp,yp,side).join(""); varstr3:String=getXYLine(aGridState,xp,yp,side).join(""); varstr4:String=getYXLine(aGridState,xp,yp,side).join(""); if(str)>-1||(str)>-1||(str)>-1||(str)>-1) winner=side; if(winner){ doWin(winner); } } ; oString(); oString()+"0"; oString()+"0"; oString()+"0"; oString()+"0"; oString()+"0"; oString()+(); oString(); oString(); oString()+"0"; oString()+(); oString()+"0"; oString()+(); oString()+"0"+(); oString(); varstr:String=(""); varres:int; if(five)>=0){ res=FIVE; if(side==otherSide) res*=2; } elseif(four)>=0) res=FOUR; elseif(three)>=0) res=side!=mySideTHREE+4:THREE; elseif(two)>=0||(jtwo)>=0) res=TWO; elseif(lfour)>=0||(rfour)>=0||(l_four)>=0||(r_four)>=0) res=SFOUR; elseif(lthree)>=0||(rthree)>=0) res=STHREE; elseif(ltwo)>=0||(rtwo)>=0) res=STWO; elseif(lfthree)>=0||(rfthree)>=0) res=FTHREE; else res=0; returnres; } ; publicclassChessmanextendsMovieClip{ privatevar