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

1、五子棋人工智能的分析與實(shí)現(xiàn)摘要 ：機(jī)器博弈是人工智能的一個(gè)重要研究分支，本文通過(guò)設(shè)計(jì)一個(gè)五子棋智能博奕程序，采用傳統(tǒng)的博弈樹(shù)算法，利用剪枝和極大極小樹(shù)搜索最佳位置，從而實(shí)現(xiàn)人機(jī)智能博弈。并對(duì)現(xiàn)有算法存在的問(wèn)題進(jìn)行探究改進(jìn)，最后給出程序?qū)嵗?，結(jié)果表明效果比較理想。關(guān)鍵詞 ：五子棋；人工智能；博弈；1 主要傳統(tǒng)算法1.1 博弈樹(shù)傳統(tǒng)的算法是采用博弈樹(shù)法來(lái)設(shè)計(jì)程序。以甲乙兩人下棋為例， 甲有很多種落子方式， 乙也有多種應(yīng)對(duì)走法， 如果把所有的走法列出來(lái)， 自然就構(gòu)成了一棵樹(shù)，即為搜索樹(shù)， 也稱博弈樹(shù)。 樹(shù)的根結(jié)點(diǎn)為先手的第一步走法，下面的走法構(gòu)成了樹(shù)的子結(jié)點(diǎn)， 直至棋局結(jié)束。 顯然，如果棋盤足夠大，

2、 子結(jié)點(diǎn)數(shù)會(huì)以幾何級(jí)數(shù)上升，而我們的任務(wù)是從這些子結(jié)點(diǎn)中尋找一個(gè)對(duì)己方最有利的結(jié)點(diǎn)，從而得到棋局的最佳走法。這必然是一個(gè)指數(shù)復(fù)雜度的過(guò)程，費(fèi)時(shí)低效， 無(wú)法搜索到最終結(jié)果 （除了棋局結(jié)束），通常只能達(dá)到一個(gè)有限的深度，在有限的范圍內(nèi)來(lái)判斷走法的好壞，得到一個(gè)局部最優(yōu)解。2-3因此，有必要做一些調(diào)整改進(jìn)，以提高算法的效率和質(zhì)量。1.2 極大極小算法極大極小搜索算法就是在博弈樹(shù)在尋找最優(yōu)解的一個(gè)過(guò)程，這主要是一個(gè)對(duì)各個(gè)子結(jié)點(diǎn)進(jìn)行比較取舍的過(guò)程，定義一個(gè)估值函數(shù) f(n)來(lái)分別計(jì)算各個(gè)終結(jié)點(diǎn)的分值，通過(guò)雙方的分值來(lái)對(duì)棋局形勢(shì)進(jìn)行分析判斷。還是以甲乙兩人下棋為例，甲為max，乙為 min。當(dāng)甲走棋時(shí)，自

3、然在博弈樹(shù)中尋找最大點(diǎn)的走法，輪到乙時(shí)，則尋找最小點(diǎn)的走法， 如此反復(fù)， 這就是一個(gè)極大極小搜索過(guò)程，以此來(lái)尋找對(duì)機(jī)器的最佳走法。其中估值函數(shù)通常是為了評(píng)價(jià)棋型的狀態(tài)，根據(jù)實(shí)現(xiàn)定義的一個(gè)棋局估值表，對(duì)雙方的棋局形態(tài)進(jìn)行計(jì)算，根據(jù)得到的估值來(lái)判斷應(yīng)該采用的走法。棋局估值表是根據(jù)當(dāng)前的棋局形勢(shì)，定義一個(gè)分值來(lái)反映其優(yōu)勢(shì)程度，來(lái)對(duì)整個(gè)棋局形勢(shì)進(jìn)行評(píng)價(jià)。本程序采用的估值表如下：狀態(tài)眠二假活三眠三活二沖四假活三活三活四連五分值2 4 5 8 12 15 40 90 200 一般來(lái)說(shuō)，我們采用的是 1515 的棋盤，棋盤的每一條線稱為一路，包括行、列和斜線， 4個(gè)方向，其中行列有 30路，兩條對(duì)角線共有

4、58路，整個(gè)棋盤的路數(shù)為88路?？紤]到五子棋必須要五子相連才可以獲勝，這樣對(duì)于斜線，可以減少8路，即有效的棋盤路數(shù)為72路。對(duì)于每一路來(lái)說(shuō)，第 i路的估分為 e(i)=ec(i)-ep(i)，其中ec(i)為計(jì)算機(jī)的 i路估分，ep(i)為玩家的 i路估分。棋局整個(gè)形勢(shì)的估值情況通過(guò)對(duì)各路估分的累加進(jìn)行判斷，即估值函數(shù)：1.3 剪枝剪枝算法簡(jiǎn)單來(lái)說(shuō)，就是在搜索過(guò)程中減少一定的冗余現(xiàn)象，如已經(jīng)找到極大值， 執(zhí)行該走法就可以獲勝， 則無(wú)須再往下進(jìn)行搜索比較，此過(guò)程即為剪枝。對(duì)于極大的 max結(jié)點(diǎn)，稱為 剪枝；反之為 剪枝。具體規(guī)則可以簡(jiǎn)單描述如下： 剪枝：對(duì)于極大值層結(jié)點(diǎn)的 值如果不小于它的任一祖

5、先極小值層結(jié)點(diǎn)的值，即 (后續(xù)層 )(祖先層 )， 則可中止該極大值層中這個(gè)max節(jié)點(diǎn)以下的搜索過(guò)程，這個(gè) max節(jié)點(diǎn)最終的倒推值就確定為這個(gè) 值。 剪枝：對(duì)于極小值結(jié)點(diǎn)層的 值如果不大于它任一祖先極大值層結(jié)點(diǎn)的值，即 (祖先層 )(后續(xù)層 )，則可中止對(duì)該極小值層中這個(gè)min節(jié)點(diǎn)以下結(jié)點(diǎn)的搜索，這個(gè) min節(jié)點(diǎn)最終的倒推值就確定為這個(gè) 值。2 剪枝可以進(jìn)一步進(jìn)行改進(jìn)，在走棋過(guò)程中，在中心先下的一方往往有一定的優(yōu)勢(shì)，雙方的搏斗糾纏都是在爭(zhēng)奪最佳位置，可以考慮從中心往外螺旋進(jìn)行擴(kuò)展搜索； 另外由于防守的需要， 落子的位置通常也是在彼此下子的附近，因此可以優(yōu)先考慮在這些位置進(jìn)行搜索，也就是對(duì)落子位

6、置進(jìn)行排序預(yù)先搜索，更進(jìn)一步的縮減冗余現(xiàn)象，進(jìn)而提高搜索效率和行棋質(zhì)量。52 改進(jìn)傳統(tǒng)算法傳統(tǒng)算法最大的一個(gè)缺點(diǎn)還是在于它的指數(shù)復(fù)雜度問(wèn)題，雖然通過(guò)剪枝、 優(yōu)化搜索位置等方法減少了冗余，提高了一定的搜索效率， 但都無(wú)法解決搜索深度增加帶來(lái)的呈幾何級(jí)數(shù)增加的巨大計(jì)算量問(wèn)題。4在進(jìn)一步的實(shí)驗(yàn)中發(fā)現(xiàn)， 搜索超過(guò)7層以后，程序響應(yīng)速度明顯變慢，到9層會(huì)出現(xiàn) 1-2s 的間隔期。因此，通過(guò)研究五子棋的規(guī)律和特點(diǎn)，結(jié)合實(shí)際經(jīng)驗(yàn)，可以對(duì)程序作一些預(yù)定的調(diào)整措施，從而提高算法的執(zhí)行效率和對(duì)弈能力。2.1 縮減搜索范圍對(duì)于15x15 的棋盤，每一種走法都有上百種可能，如果對(duì)每種走法都進(jìn)行計(jì)算估值，則無(wú)疑大大增加

7、了計(jì)算量， 降低了算法的效率和質(zhì)量。 根據(jù)規(guī)則和實(shí)際經(jīng)驗(yàn)，我們知道只要考慮以棋子為中心的鄰近區(qū)域皆可，比如不大于4的距離通常為該子的有效范圍， 同理我們還可以在對(duì)方的落子范圍進(jìn)行判斷估值。這樣可以縮減搜索范圍，同時(shí)提高算法的效率和走法的實(shí)用性。2.2 置換表搜索前面我們討論了利用 剪枝來(lái)處理冗余結(jié)點(diǎn)，對(duì)于已經(jīng)搜索過(guò)的結(jié)點(diǎn)，我們可以通過(guò)設(shè)置一張 hash 表記錄該結(jié)點(diǎn)，這樣在后續(xù)的搜索過(guò)程中，可以對(duì)這些點(diǎn)的記錄進(jìn)行查詢?nèi)缦惹坝羞^(guò)記錄則直接調(diào)用，免于重新搜索， 從而避免出現(xiàn)重復(fù)操作，加快搜索速度。該方法通常稱為置換表（transposition table）。2.3 建立棋譜庫(kù)該方法廣泛應(yīng)用在象棋

8、程序設(shè)計(jì)中，五子棋遠(yuǎn)比象棋簡(jiǎn)單， 該方法也更為有效實(shí)用。通過(guò)在數(shù)據(jù)庫(kù)中存儲(chǔ)一些開(kāi)局“ 定式” 手法和經(jīng)典棋局， 開(kāi)局階段， 程序使用開(kāi)局庫(kù)， 一旦發(fā)現(xiàn)相同棋局， 則直接調(diào)用該走法， 無(wú)須再次搜索， 同時(shí)建立數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)失敗案例不斷進(jìn)行調(diào)整對(duì)策。該方法可以極大的提高程序的智能化，只是增加了額外的系統(tǒng)開(kāi)銷。 另外對(duì)于棋譜的匹配和存儲(chǔ)也是關(guān)鍵問(wèn)題。4 但是由于時(shí)間和選擇語(yǔ)言的限制，建立棋譜庫(kù)沒(méi)有在程序中得到實(shí)現(xiàn)。2.4 合理設(shè)置搜索深度理論上來(lái)說(shuō)， 為了尋找最優(yōu)解， 最好是對(duì)完整博弈樹(shù)進(jìn)行完全搜索，但實(shí)際中是不可行的，無(wú)論是從時(shí)間上還是從系統(tǒng)資源上。在后面實(shí)際程序設(shè)計(jì)中，默認(rèn)為5層，當(dāng)然也可以根據(jù)不

9、同機(jī)器配置加以調(diào)整，以達(dá)到最大效率。3 實(shí)例分析在windows7操作系統(tǒng)下，利用上述算法思想，采用actionscript 編程實(shí)現(xiàn)一個(gè)實(shí)現(xiàn)人機(jī)對(duì)戰(zhàn)的五子棋程序。通過(guò)實(shí)驗(yàn)分析比較， 程序的智能化和質(zhì)量效果較為理想。當(dāng)計(jì)算機(jī)執(zhí)黑時(shí)，基本上每次都能獲勝，且步驟、時(shí)間較短；當(dāng)玩家執(zhí)黑先行，計(jì)算機(jī)獲勝比率也較高，具有很好的智能性。4 結(jié)束語(yǔ)本文介紹了一個(gè)智能五子棋的主要算法思想和實(shí)現(xiàn)技術(shù)，利用剪枝和極大極小樹(shù)搜索博弈樹(shù)，作出了一些改進(jìn)措施，尋求最佳下棋位置，從而提高了智能博弈的質(zhì)量。進(jìn)行優(yōu)化以后， 五子棋程序的智能水平和搜索效率有了明顯的提升。本文所討論的算法思想和設(shè)計(jì)過(guò)程也為其他棋類游戲(如象棋和

10、圍棋等 )提供了一定的參考價(jià)值。 此外，五子棋的國(guó)際規(guī)則較為復(fù)雜，加入了禁手判負(fù)、 三手交換等規(guī)則限制黑手先行優(yōu)勢(shì)，可以在進(jìn)一步的工作中考慮實(shí)現(xiàn)。參考文獻(xiàn) ：1 蔡自興 . 人工智能及其應(yīng)用m. 北京：清華大學(xué)出版社,1999:2-12. 2 朱全民 ,陳松喬 . 五子棋算法的研究與思考j. 計(jì)算技術(shù)與自動(dòng)化,2006(02):75-78. 3 董紅安 ,蔣秀英 . 智能五子棋博弈程序的核心算法j. 棗莊學(xué)院學(xué)報(bào) ,2005(2):61-65. 4 蔣加伏 ,陳藹祥 ,唐賢英 . 基于知識(shí)推理的博弈樹(shù)搜索算法j. 計(jì)算機(jī)工程與應(yīng)用,2004(1):74-76. 5 張海峰 ,白振興 ,張登福

11、. 五子棋中的博弈智能設(shè)計(jì)j. 現(xiàn)代電子技術(shù) ,2004,27(7): 25-27. 附錄 ：1.程序截圖游戲運(yùn)行中玩家先手勝利玩家先手失敗電腦先手勝利電腦先手失敗2.主要代碼package classes import flash.display.*; import flash.events.*; import flash.geom.*; import flash.text.textfield; /* * 五子棋*/ public class gobangdoc extends movieclip /棋盤格寬度private const gridsize:number = 20; /棋盤格數(shù)

12、private const gridnum:number = 15; /沒(méi)有棋子為 0,黑子為 1 ，白子為 2 private const nothing:uint = 0; private const black:uint = 1; private const white:uint = 2; /現(xiàn)在輪到哪一方出子private var crtside:uint = white; /玩家的棋子private var myside:uint = white; /對(duì)手的棋子private var otherside:uint; /是否可以進(jìn)行游戲private var canplay:boole

13、an = false; /記錄盤面狀態(tài)的數(shù)組private var agridstate:array = ; /記錄盤面上的棋子的數(shù)組private var achessmen:array = ; /棋子的幾種狀態(tài)public const stwo:int = 2;/眠二public const ftwo:int = 4;/假活二public const sthree:int = 5;/眠三public const two:int = 8;/活二public const sfour:int = 12;/ 沖四public const fthree:int = 15;/ 假活三public co

14、nst three:int = 40;/活三public const four:int = 90;/活四public const five:int = 200;/五連/玩家的棋形表private var aplayer:array = ; /對(duì)手的棋形表private var aopponent:array = ; /八個(gè)方向，從左上角開(kāi)始順時(shí)針private var dir:array = -1,-1,0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0; public function gobangdoc() mcgamestate.visible = false; others

15、ide = white + black - myside; /初始化盤面數(shù)組for (var i:uint=0; igridnum; i+) agridstatei = 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; mcchessboard.addeventlistener(mouseevent.mouse_down,addmychessman); btnstart.addeventlistener(mouseevent.click,btnstart_handler); btnreplay.addeventlistener(mouseevent.click,btnreplay_

16、handler); mcselectchessman.addeventlistener(mouseevent.m ouse_down ,selectchessman); /初始化棋盤private function init():void btnstart.visible = false; for(var i:int=0;iachessmen.length;i+) mcchessboard.removechild(achessmeni); for (var j:uint=0; jgridnum; j+) agridstatej = 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;

17、achessmen = ; canplay = true; /玩家添加棋子public function addmychessman(e:mouseevent):void /不能添加棋子的狀態(tài)（棋局未開(kāi)始、對(duì)方走、棋子沒(méi)有落在棋盤里）if(!canplay | crtside != myside | != mcchessboard) return; if (myside = crtside) /計(jì)算鼠標(biāo)落在哪一格var crtx:uint = math.floor(e.localx/gridsize); var crty:uint = math.floor(e.lo

18、ca ly/gridsize); /如果這一格已經(jīng)有棋子就返回if (agridstatecrtycrtx) return; /創(chuàng)建棋子var chessman:chessman; if (myside = black) chessman = new blackchessman(); else chessman = new whitechessman(); chessman.bplayer = true; agridstatecrtycrtx = myside; chessman.x = (crtx + .5) * gridsize; chessman.y = (crty + .5) * gr

19、idsize; achessmen.push(chessman); mcchessboard.addchild(chessman); checkwinner(crtx,crty,crtside); /對(duì)方走crtside = white + black - myside; /計(jì)算機(jī)走var opos:array = calculatestate(crtside); var cx:int = opos0; var cy:int = opos1; addchessman(cx,cy); checkwinner(cx,cy,crtside); crtside = myside; /計(jì)算機(jī)添加棋子pu

20、blic function addchessman(tox:int,toy:int):void if(!canplay) return; var autox:int = tox; var autoy:int = toy; var chessman:chessman; if (myside = black) chessman = new whitechessman(); else chessman = new blackchessman(); chessman.x = (autox + .5)*gridsize; chessman.y = (autoy + .5)*gridsize; agrid

21、stateautoyautox = (black + white) - myside; achessmen.push(chessman); mcchessboard.addchild(chessman); /評(píng)估棋盤上每一格的分值，返回得分最高的棋格坐標(biāo)public function calculatestate(side):array var i:int,j:int,k:int; var otherside:int = white + black - side; /填充玩家的棋形表和對(duì)手的棋形表for(i = 0;igridnum;i+) for(j = 0;jgridnum;j+) if(

22、agridstateij != nothing) aopponenti * gridnum + j = val:-1,x:j,y:i; aplayeri * gridnum + j = val:-1,x:j,y:i; else var v1 = getscore(agridstate,j,i,side); aopponenti * gridnum + j = val:v1,x:j,y:i; var v2 = getscore(agridstate,j,i,otherside); aplayeri * gridnum + j = val:v2,x:j,y:i; /取得分值最大的棋格var max

23、o:object = sortarray(aopponent); var maxp:object = sortarray(aplayer); var apos:array = 0,0; if(maxo.val -1 | str2.indexof(str)-1 | str3 .indexof(str)-1 | str4.indexof(str)-1) winner = side; if(winner) dowin(winner); /取勝后觸發(fā)的事件private function dowin(side:int):void /現(xiàn)實(shí)游戲結(jié)果說(shuō)明mcgamestate.visible = true;

24、 /關(guān)閉棋局canplay = false; /期盼設(shè)為半透明mcchessboard.alpha = .5; /根據(jù)玩家輸贏展示不同的游戲結(jié)果if(side = myside) mcgamestate.gotoandstop(win); else mcgamestate.gotoandstop(lose); /為數(shù)組排序的方法private function sortarray(arr):object var arrlen:int = arr.length; var ar:array = ; for(var j=0;j0 ? xp - 5:0; /結(jié)束位置xe = xp + 5= gridn

25、um?gridnum:xp + 5; for(var i:int=xs;i0 ? yp - 5:0; /結(jié)束位置ye = yp + 5= gridnum?gridnum:yp + 5; for(var i:int=ys;i xp ? 0 : xp - yp; ys = xp yp ? 0 : yp - xp; /結(jié)束位置xe = gridnum - ys; ye = gridnum - xs; var pos:int; for(var i:int=0;i(xe-xs0?pos-4:0,pos+5arr.length?arr.length:pos+5); return arr; / / 取得游戲

26、中的一方在指定位置左下右上兩邊5格以內(nèi)的狀態(tài)private function getyxline(aposition:array,xp:int,yp:int,side:int):array var arr:array = ; var xs:int,ys:int,xe:int,ye:int; var num:int = gridnum; var half:int = math.ceil(gridnum/2); /起始位置xs = xp + yp = num?num-1:(xp + yp); ye = xe; var pos:int; for(var i:int=0;i=num?2*num-xp-

27、yp-1:xp+yp+1);i+) if(ye - i = yp & xs + i = xp) arr.push(side); pos = i; else arr.push(apositionye - i xs + i); arr = arr.slice(pos-40?pos-4:0,pos+5arr.length?arr.length:pos+5); return arr; /評(píng)估游戲中的一方在指定位置落子后某一方向可能取得的分值private function ana lysisline(aline:array,side:int):int var otherside:int = w

28、hite + black - side; /以下注釋中* 為本方棋子， o 為對(duì)方棋子， _ 為空格/ * var five:string = (side * 11111).tostring(); / _* var four:string = 0 + (side * 1111).tostring() + 0; / _*_ var three:string = 0 + (side * 111).tostring() + 0; / _*_ var two:string = 0 + (side * 11).tostring() + 0; / _*_*_ var jtwo:string = 0 + (

29、side * 101).tostring() + 0; / *_ var lfour:string = otherside.tostring() + (side * 1111).tostring() + 0; / _* var rfour:string = 0 + (side * 1111).tostring() + otherside.tostring(); / *_* var l_four:string = (side * 10111).tostring(); / *_* var r_four:string = (side * 11101).tostring(); / o*_ var lt

30、hree:string = otherside.tostring() + (side * 111).tostring() + 0; / _*o var rthree:string = 0 + (side * 111).tostring() + otherside.tostring(); / o*_ var ltwo:string = otherside.tostring() + (side * 11).tostring() + 0; / _*o var rtwo:string = 0 + (side * 11).tostring() + otherside.tostring(); / *_o

31、var rfthree:string = (side * 111).tostring() + 0 + otherside.tostring(); / o_* var lfthree:string = otherside.tostring() + 0 + (side * 111).tostring(); var str:string = aline.join(); var res:int; if(str.indexof(five)=0) res = five; if(side = otherside) res * =2; else if(str.indexof(four)=0) res = fo

32、ur; else if(str.indexof(three)=0) res = side!=myside?three+4:three; else if(str.indexof(two)=0 | str.indexof(jtwo)=0 ) res = two; else if(str.indexof(lfour)=0 | str.indexof(rfour)=0 | str.indexof(l_four)=0 | str.indexof(r_four)=0) res = sfour; else if(str.indexof(lthree)=0 | str.indexof(rthree)=0) res = sthree; else if(str.indexof(ltwo)=0 | str.indexof(rtwo)=0) res = stwo; else if(str.indexof(lfthree)=0 | str.indexof(rfthree)=0) res = fthree; else res = 0; return res; /開(kāi)始游戲按鈕觸發(fā)的方法private function btnstart