從一個策略游戲談搜索算法優(yōu)化

1、.從一個策略游戲談搜索算法優(yōu)化從一個策略游戲談搜索算法優(yōu)化對于策略游戲性質(zhì)的二人博弈問題，比方黑白棋，五子棋等，一般的解答方法就是搜索；但搜索算法的原理不同，其性能就大不一樣。一般來說，假設(shè)我們對問題的本質(zhì)把握的越深，算法的設(shè)計就會相對的復(fù)雜，但是效率會高很多。下面我們就通過一個二人游戲來談這方面的體會。一.問題的提出問題：TwoFour羅馬尼亞奧林匹克,via Stroe,2002Bessie有一個新的兩人游戲：TwoFour.她有N3=N=30堆球,每堆有nballs0=nballs=4個.球的總數(shù)為2*N.玩這個游戲時,游戲者輪流執(zhí)行一個有效挪動.一個有效挪動由以下動作組成：*第一,游戲

2、者選擇不同的兩堆球.*第二,把一個球從一堆拿到另一堆.她可以這樣做的前提是運完球后第二堆的球數(shù)包括新放上的球不大于第一堆剩下的球的數(shù)目.當(dāng)沒有挪動可做時,游戲完畢.實際上,在游戲的末尾,每堆將包含恰好兩個球.游戲的勝者擁有多數(shù)球堆.平局是可能的.當(dāng)某堆有兩個球并且是由于某游戲者最近對它的的一次挪動不管移走還是放入使其變?yōu)閮蓚€球的,我們就說她擁有這堆球.看看這些例子：*假設(shè)一個游戲者從有四個球的某球堆中移走一個球,放到有一個球的某球堆中,那么它擁有了第二堆有兩個球.*假設(shè)一個游戲者從有三個球的某球堆中移走一個球,放到有零個球的某球堆中,那么它擁有了第一堆,如今這堆有兩個球.*假設(shè)一個游戲者從有三

3、個球的某球堆中移走一個球,放到有一個球的某球堆中,那么它擁有了這兩堆他們都有兩個球.擁有權(quán)可以變化.設(shè)想一個游戲者擁有兩個球的一個球堆,假設(shè)另一個游戲者選了一個有四個球的堆并把一個球移到此兩個球的堆中,那么這堆球誰也不屬于了.假設(shè),在游戲的開頭,存在有兩個球的一些球堆,那么這些堆被平分給兩個游戲者,剩余的堆那么分給游戲者2.游戲者1先挪動.你的程序必須判斷,對一個初始的游戲狀態(tài),誰將獲勝或者會否出現(xiàn)平局.你的程序?qū)⑻幚鞧1=G=1000個游戲狀態(tài).該問題要求使用不超過1.00 MB的內(nèi)存.問題名：twofour輸入格式：*行1：用空格隔開的兩個整數(shù)：N和G.*行2.G+1：每行包含空格隔開的N

4、個整數(shù)用于描繪該游戲.第一個整數(shù)是堆1的球數(shù),第二個整數(shù)是堆2的球數(shù),.行2描繪了游戲1,行3描繪了游戲2,.你的程序應(yīng)該計算每個特定游戲的勝者.輸入樣例文件twofour.in：5 40 34 12 22 22 21 12 24 43 21 0輸出格式：*行1.G：每個游戲的結(jié)果.行1給出游戲1的結(jié)果,.結(jié)果是一個整數(shù)：1代表第一個游戲者獲勝,2代表第二個獲勝,以及0代表平局.輸出樣例文件twofour.out：1 21 1二.問題的初步分析和第一種解答從問題的描繪來看，我們可以得到如下的一些根本信息：1player1總是先手的，問題也是求player1的勝負情況；player2在瓜分最初的

5、2堆的時候具有優(yōu)先權(quán)。2整個的游戲過程，就是把不均有分布的堆，逐步均勻化，直至所有的堆都是2堆，由于2N個球，放置在N堆上，這是個必然。32堆在游戲過程中會變化成1堆或者3堆；每堆的球數(shù)不超過4，允許0堆。4假設(shè)兩堆之間的球數(shù)目差1，就可以進展球的挪動，這是我們在程序中判斷可行步的根據(jù)。在上面的根本信息的根底上，我們就要決定用什么搜索算法，用廣度優(yōu)先搜索還是深度優(yōu)先搜索呢?假設(shè)用廣度優(yōu)先搜索的話，一般的方法是從根節(jié)點出發(fā)，平行的推進所有從根節(jié)點衍生出來的子節(jié)點，每個節(jié)點都要保存當(dāng)前棋局的狀態(tài),同時還要記住父節(jié)點的索引；子節(jié)點需要父節(jié)點的信息來進展衍生，而父節(jié)點需要子節(jié)點的結(jié)果來決定本節(jié)點的結(jié)果

6、。一般我們用一個隊列來實現(xiàn)這個過程；由于所有的節(jié)點都需要保存，一些廢節(jié)點也被保存了，而對于奇偶深度的節(jié)點的處理還不一樣奇偶深度，對應(yīng)player1還是player2，下面會詳細講到，節(jié)點所要保存和處理的信息都比較復(fù)雜，另外針對這個問題的廣度優(yōu)先搜索的剪枝工作也是個問題，因為廣搜的處理方式是先把子節(jié)點全部入隊列，然后從隊頭逐個再擴展，一些無用的節(jié)點就占用了珍貴的隊列空間。比方player1的任何一步挪動，只要能成功，其它方式的挪動都不需要考慮了；然而對于走法的判斷是在所有子節(jié)點入隊之后，所以其他廢節(jié)點就占用了多余的空間。綜合上面的討論，我認為本問題不太適宜使用基于廣度優(yōu)先搜索的算法。下面考慮深度

7、優(yōu)先搜索。深度優(yōu)先搜索有一個好處就是占用的空間少。先講講我們的思路，請大家注意對于player1和player2的處理的不同。1我們對所有棋局的考慮都以player1為中心，不管當(dāng)前棋局是由player1的挪動還是player2的挪動造成的.2假設(shè)相對與當(dāng)前棋局，對于player1的所有挪動中，有一種能導(dǎo)致player1成功，那么當(dāng)前節(jié)點就能導(dǎo)致player1成功，也就是不需要再擴展了,直接返回結(jié)果到上層父節(jié)點；假設(shè)對于player1的所有挪動，全都導(dǎo)致player1失敗，才能說本節(jié)點導(dǎo)致player1失敗；假設(shè)沒有走法能成功，但有一種走法能使得player1和局，那么player1會選擇和局

8、。3同樣的道理，假設(shè)相對與當(dāng)前棋局，對于player2的所有挪動中，有一種能導(dǎo)致player2成功，那么當(dāng)前節(jié)點就能導(dǎo)致player1失敗，也就是不需要再擴展了，直接返回結(jié)果到上層父節(jié)點；假設(shè)對于player2的所有挪動，全都導(dǎo)致player2失敗，才能說本節(jié)點導(dǎo)致player1成功；假設(shè)沒有走法能使得player2成功，但有一種走法能使得player2和局，那么player2會選擇和局，也就是導(dǎo)致player1和局。4由于player1先手，從初始棋局出發(fā)，逐個擴展出子節(jié)點，并遞規(guī)的調(diào)用自身來擴展子節(jié)點，直到無法再深度擴展為止。下面來看我們的第一個版本的解答。#define QMAX 30

9、typedef structint qn；/球的個數(shù)int owner；/所有者，0：沒有所有者,1：屬于player1,-1：屬于player2sq_str；/上面的數(shù)據(jù)構(gòu)造用來描繪堆的屬性。sq_str aQMAX；/用來描繪棋局狀態(tài)int n；/記錄堆的個數(shù)，全局變量int depthmax=-1；/用來記錄最深的遞規(guī)深度，以便理解堆棧內(nèi)存的使用使用下面的代碼得到輸入，當(dāng)然后面我們會討論隨機生成棋局的方式，初始的棋局在這里就準(zhǔn)備好void test1int i,j；int G,c；scanf%d%d,&n,&G；fori=0；i G；i+c=0；forj=0；j n；j+scanf%d,

10、&aj.qn；ifaj.qn=2ifc&1=0aj.owner=-1；/由player2所有else aj.owner=1；/由player1所有c+；else aj.owner=0；/無人所有depthmax=-1；c=qiuv00；printfresult：%d.depthmax=%d.n,c,depthmax；/求解棋局的函數(shù)，勝負是指player1的勝負。depth表示當(dāng)前迭代的深度，同時也表示當(dāng)前執(zhí)子的玩家，depth為偶數(shù)，表示player1執(zhí)子，depth為奇數(shù)，表示player2執(zhí)子。/返回1：成功，-1：失敗,0：和局int qiuv0int depthint i,j,k=0

11、,s,tx=0；int ret0；int fu=0；/會導(dǎo)致player1失敗的節(jié)點的個數(shù)int shen=0；/會導(dǎo)致player1成功的節(jié)點的個數(shù)sq_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1/判斷可行挪動步的標(biāo)準(zhǔn)，從第i堆到第j堆k+；/記錄子節(jié)點的個數(shù)/保存被修改的堆，方便以后恢復(fù)savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifde

12、pth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；ret0=qiudepth+1；/遞規(guī)調(diào)用/恢復(fù)被修改的棋局ai=savei；aj=savej；/請大家注意下面的不同處理，所有的勝負都是對于player1來說的ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；ifk=0/假設(shè)沒有子節(jié)點可以擴展，那么這是個終局fo

13、ri=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；else/否那么是擴展了子節(jié)點的ifdepth&1=0iffu=kreturn-1；/所有的走法都導(dǎo)致輸else return 0；/至少有一種走發(fā)可以保證平局elseifshen=kreturn 1；/player2所有的走法都導(dǎo)致player1成功else return 0；/player2會選擇平局三.初步的優(yōu)化和剪枝好了程序很簡單，應(yīng)該很容易理解，但是效率也很低！下面我們來逐步分析優(yōu)化，看看問題在哪里。首先我們發(fā)現(xiàn)，同層擴展出的各棋局的狀態(tài)只和各堆的狀態(tài)有關(guān)

14、，而和各堆的排列沒有關(guān)系，所以在同一層我們就可以進展剪枝，把那些本質(zhì)上是一樣的子節(jié)點剪掉?？紤]所有的走法一共有8種：4-2-1,1,4-1,4-0,3-1,3-0,2-1,1-0,括號里的數(shù)表示2堆的歸屬情況。新的程序如下：int qiuv1int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；sq_str savei,savej；sq_str tt82；/一共有8種不同的挪動方式int re8；/8種挪動方式帶來的結(jié)果int ti=0；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=

15、0；j n；j+ifai.qn-aj.qn 1k+；fors=0；s ti；s+ifai.owner=tts0.owner&ai.qn=tts0.qn&aj.owner=tts1.owner&aj.qn=tts1.qnbreak；ifs！=tiret0=res；ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；continue；elsettti0=ai；ttti1=aj；savei=ai；savej=aj；ai.qn-；aj.q

16、n+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；ret0=qiudepth+1；reti=ret0；ti+；ai=savei；aj=savej；ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；if

17、k=0fori=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；elseifdepth&1=0iffu=kreturn-1；/所有的走法都導(dǎo)致輸else return 0；/至少有一種走發(fā)可以保證平局elseifshen=kreturn 1；/player2所有的走法都導(dǎo)致player1成功else return 0；/player2會選擇平局四、進一步的優(yōu)化和剪枝經(jīng)過上面的優(yōu)化，程序的性能有所提升，但是還不夠快，問題出在哪里呢?我們知道深度優(yōu)先搜索的一大缺點就是對已有的計算結(jié)果沒有繼承，造成了大量的計算浪費；qiuv

18、1已經(jīng)做了一點工作，但還不夠；我們需要記錄所有的已經(jīng)訪問過的棋局和相應(yīng)的結(jié)果，方便在后續(xù)的搜索中進展剪枝。這就需要對以往結(jié)果的記錄。定義如下數(shù)據(jù)構(gòu)造：#define STAMAX 11000 unsigned char x_staSTAMAX8；/player1的2就在2，player2的2在5,局勢的結(jié)果放在7,depth的奇偶性放在6里int x_inx=0；/x_sta中的下一個空位置我們知道棋局只和堆本身有關(guān)，而和堆的排列順序無關(guān)，進一步，兩個一樣的堆也是無區(qū)別的，這樣我們只需要記錄一個棋局中0堆的個數(shù)，1堆的個數(shù),21堆的個數(shù)，2-1堆的個數(shù),3堆的個數(shù)，4堆的個數(shù)，以及當(dāng)前棋局對應(yīng)

19、的執(zhí)子方，這種棋局的結(jié)果。由于最多也就30堆，所以1個字節(jié)足以存放相關(guān)的信息。算算上面的空間才不到90KB，離1MB尚遠。還有一個問題，那就是棋局的對偶性，棋局A的對偶棋局，就是把depth的奇偶性取反，把相應(yīng)的2堆的歸屬性取反，相應(yīng)的棋局結(jié)果自然取反。這個很容易理解，相當(dāng)與player2和player1交換位置，下對方的棋。這樣我們每求得一個棋局，實際上是得到了兩個棋局的結(jié)果。好了還是看看新程序吧.int qiuv2int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；int old_xinx；unsigned char x7；sq

20、_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1k+；memsetx,0,7；savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；fors=0；s n；s+ifas.qn！=2xas

21、.qn+；elseifas.owner=1x2+；else x5+；x6=depth&1；/開場搜索以前保存的結(jié)果fors=0；s x_inx；s+ifmemcmpx,x_stas,7=0break；ifs！=x_inx/找到了！ai=savei；aj=savej；ret0=charx_stas7；ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；continue；elsememcpyx_stax_inx,x,7；/每找到，把當(dāng)

22、前棋局添加進去old_xinx=x_inx；/記錄自己的位置，后面好吧結(jié)果填進去，因為下面的遞規(guī)會參加新的內(nèi)容到存儲隊列x_inx+；ret0=qiuv1depth+1；x_staold_xinx7=ret0；ai=savei；aj=savej；/把對偶的情況放進去memcpyx_stax_inx,x_staold_xinx,8；x_stax_inx2=x_staold_xinx5；x_stax_inx5=x_staold_xinx2；x_stax_inx6=！x_staold_xinx6；x_stax_inx7=-x_staold_xinx7；x_inx+；ifdepth&1=0/playe

23、r1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；ifk=0fori=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；elseifdepth&1=0iffu=kreturn-1；/所有的走法都導(dǎo)致輸else return 0；/至少有一種走發(fā)可以保證平局elseifshen=kreturn 1；/player2所有的走法都導(dǎo)致player1成功else return 0；/player2

24、會選擇平局好了，這下我們的程序有了質(zhì)的飛躍，速度進步很多，比v1版本進步了幾個數(shù)量級！很開心-。五.HASH函數(shù)的應(yīng)用但是當(dāng)我們加大測試強度，把堆的數(shù)量推到頂，到達30之后，我們的程序還是不夠快，對有的棋局，幾乎半分鐘內(nèi)都解不出來，這是不能承受的。那好吧，看來我們還需要進一步優(yōu)化。還有什么地方值得優(yōu)化呢?就是下面這個地方！/開場搜索以前保存的結(jié)果fors=0；s x_inx；s+ifmemcmpx,x_stas,7=0break；通過測試發(fā)現(xiàn)，對于30堆的情況，我們的存儲會有超過10000的情況，一般也會超過5000！對于這么大的存儲空間，假設(shè)向上面那樣每次都進展線性匹配，效率是很低下的，這也

25、就是為什么在堆變多之后，我們的程序變慢的原因。好了問題找到了，那么如何解決呢?還是有方法的，那就是hash表！通過hash表就可以一步定位到我們需要的位置，只要hash函數(shù)設(shè)置的好，就可以盡量減少碰撞的產(chǎn)生；即使有了碰撞也不怕，搞個拉鏈鏈接起來就可以了，經(jīng)過測試新的程序，使用hash表，最多也就產(chǎn)生兩三次碰撞，一般都能一擊中的！#define STAMAX 0x4000 typedef structunsigned char x_sta8；/player1的2就在2，player2的2在5,局勢的結(jié)果放在7,depth的奇偶性放在6里unsigned short pr；/低14bit是索引，高

26、2bit：00空工程,01低14bit表示下一個的位置，10沒有下一個了X_sta；/hash表X_sta hashSTAMAX；/占用160KB空間，實際測試，可以處理的堆數(shù)達35堆的情況/返回14bit的HASH值，我自己構(gòu)造的hash函數(shù)unsigned short cal_hashunsigned char*in,int lenunsigned short x1=0；int i；fori=0；i len；i+x1=x1*11+ini0x3d；returnx1&0x3fff；int qiuv3int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；in

27、t shen=0；int old_xinx；unsigned char x8；/把結(jié)果也含進來了unsigned short s_indx；int nexti；int find；sq_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1k+；memsetx,0,8；savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；

28、else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；fors=0；s n；s+ifas.qn！=2xas.qn+；elseifas.owner=1x2+；else x5+；x6=depth&1；find=0；s_indx=cal_hashx,7；/計算hash值作為索引nexti=s_indx；switchhashs_indx.pr 14/查看高兩bit屬性值case 0：/空項，直接填入memcpyhashnexti.x_sta,x,8；hashnexti.pr=0x8000；old_xinx=nexti；x_in

29、x+；break；case 1：/碰撞，那就順著鏈條往下查找吧doifmemcmpx,hashnexti.x_sta,7=0find=1；break；nexti=hashnexti.pr&0x3fff；whilehashnexti.pr 14！=2；/這里直接滑入case2，因為到這里處理是一樣的了case 2：/和最后一個進展比較ifmemcmpx,hashnexti.x_sta,7=0find=1；iffind=1/找到了一模一樣的ai=savei；aj=savej；ret0=charhashnexti.x_sta7；ifdepth&1=0/player1的局勢ifret0=1return

30、 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；continue；/否那么就是沒有找到，那么就只能拉拉鏈了，找一個空地方塞進去fors=0；s STAMAX；s+ifhashs.pr 14=0break；ifs=STAMAX/hash表滿了！printferror hashtable full！；return-2；memcpyhashs.x_sta,x,8；hashs.pr=0x8000；/這幾行就是在接拉鏈old_xinx=s；hashnexti.pr=s|0x4000；x_inx+；break

31、；default：printferror in pr！；break；ret0=qiuv1depth+1；hashold_xinx.x_sta7=ret0；ai=savei；aj=savej；/把對偶的情況放進去find=x2；x2=x5；x5=find；find=0；x6=！x6；x7=-ret0；s_indx=cal_hashx,7；/查找對偶情況，假設(shè)對偶情況已經(jīng)在里面了，就不用添加了，否那么就需要添加nexti=s_indx；switchhashs_indx.pr 14case 0：x_inx+；memcpyhashnexti.x_sta,x,8；hashnexti.pr=0x8000；break；case 1：doifmemcmpx,hashnexti.x_sta,7=0find=1；break；nexti=hashnexti.pr&0x3fff；whilehashnexti.pr 14！=2；case 2：/和最后一個進展比較ifmemcmpx,hashnexti.x_sta,7=0find=1；iffind=0/否那么就是沒有找到fors=0；s STAMAX；s+ifhashs.pr 14=0break；ifs=STAMAXprintferror hashtable full！；return-2；memcpyhashs.x_sta,x,8；hashs.pr