五子棋算法.doc_第1頁
五子棋算法.doc_第2頁
五子棋算法.doc_第3頁
全文預覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

五子棋算法 五子棋算法問題描述:人們通常喜愛的五子棋。某方將結(jié)果連成五子即獲勝。問題規(guī)模:15x15棋盤。算法:博弈樹,極大極小算法+Alpha-Beta剪枝法棋。數(shù)據(jù)結(jié)構(gòu)描述如下。棋盤類:棋盤為一個M*N的矩陣TblMN(定義LEDGE為左邊界,REDGE為右邊界,TEDGE為上邊界,BEDGE為下邊界)。每個棋盤矩陣有兩個評估矩陣CpuPriMN4和UserPriMN4,矩陣的第三維分別記錄了該點(0水平、1垂直、2左上右下、3左下-右上)的棋子數(shù)。若該點上棋子為USER下的,則UserPri中有值,CpuPri中值為0,反之亦然。該點無子時,兩個評估矩陣上該點評估值均為0.CpuSum:CpuPri矩陣的所有元素之和。UserSum:UserPri矩陣的所有元素之和。tag:tag=CpuSum/UserSum,CPU戰(zhàn)術選擇標記。當tag大于1時CPU進攻,小于1時CPU防守。Depth:深度。標記該棋盤位于博弈圖的層次。Father:該棋盤的前驅(qū)。Child:該棋盤的孩子棋盤鏈。nextBro:兄弟節(jié)點。Node:一個點類,標記該棋盤下子的點。算法描述如下。一、由于存在對抗性,CPU分為進攻和防守兩種方式。Tag1時進攻,tag1時防守。Tag的實際含義是對敵我的一個評估,當我方比敵方有利時選擇進攻,當敵方比我方有利時選擇防守。二、對任意一棋盤生成博弈圖的算法。算法2-1當CPU接到一張已落子n個的棋盤時:1、計算此棋盤的CpuSum值和UserSum值,并得出tag值決定進攻還是防守。此標志在本次生成整個博弈樹時都不變,也就是決定了進攻或防守后,選擇時都依據(jù)此標志。2、以CPU身份在棋盤的每個未落子的點上分別下一步棋,生成M*N-n個已落子n+1個的棋盤,分別計算評估值,并生成博弈樹第一層;3、再以USER身份在每個棋盤(已落子n+1個)每個未落子的點上再下一步棋生成M*N-n-1個棋盤,分別計算評估值并加入博弈樹第二層。4、回到步驟2,依次類推,CPU的身份不斷在CPU和USER之間變化,直到生成樹的深度大于給定深度MAX_DEP時為止,停止建圖。5、此時,將葉子節(jié)點的CpuSum和UserSum計算出來。6、若決定進攻,則極大極小過程如下:1)若某步為CPU走(depth值為偶數(shù)),則應當選擇CpuSum最大的一個棋盤,即CPU選擇了對CPU最有利的一步。(極大過程)2)若某步為USER走(depth值為奇數(shù)),則應當選擇CpuSum最小的一個棋盤(即相當于此時用戶防守),此時相當于USER選擇了對CPU最不利的一步。(極小過程)7、若決定防守,則極大極小過程如下:1)若某步為CPU走(depth值為偶數(shù)),則應當選擇UserSum最小的一個棋盤,即CPU選擇了對USER最不利的一步。(極大過程)2)若某步為USER走(depth值為奇數(shù)),則應當選擇UserSum最大的一個棋盤(即相當于此時用戶進攻),此時相當于USER選擇了對USER最有利的一步。(極小過程)8、按照6、7的選擇算法,從下至上,得到第1層的(M*N-n)個棋盤的CpuSum值和UserSum值。注:向上傳遞時,同時傳遞CpuSum和UserSum值,不論如何挑選。但棋盤并不向上傳遞。9、在第0層決定如何走下一步,方法同6(1)或7(1),取決于CPU是防守還是進攻。此時將最適合的棋局的棋盤(位于博弈樹第1層)返回,即完成了原棋局下一步的選擇過程。10、刪除該圖,算法結(jié)束。三、剪枝一個已經(jīng)落子n的棋盤按照上面的算法向前預測k步會產(chǎn)生(M*N-n)!/(M*N-n-k)!)個棋盤。例如,最大生成深度為3時,若一個15x15的棋盤已經(jīng)由用戶走了1步,那么CPU在預測下一步時會產(chǎn)生224*223*222=11089344個棋盤。若每個棋盤大小為8k(15*15+15*15*2*2=2025個int),則空間大小為86635.5MB=86.6GB,同時會有極大的耗時,這是用戶無法接受的。 由于向前預測時會進行大量計算,同時產(chǎn)生巨大的數(shù)據(jù),所以必須進行剪枝。 首先使用書上給出的Alpha-Beta剪枝計算,取得了一定的效果,但仍有很大的空間消耗。為了追求更高的速度,經(jīng)過自己分析,采用了一個變形的Alpha-Beta剪枝法。剪枝算法如下:算法3-1在生成一個棋盤的子棋盤前,將該圖的CpuSum值和UserSum值計算出來,用2-1-6和2-1-7類似的判別方法,(此處以CPU進攻為例),當其子棋盤CpuSum值小于該棋盤的CpuSum值時則舍棄不加入博弈樹,否則加入博弈樹。其他情況同理。算法分析:該剪枝算法不能保證得到最優(yōu)解(類貪心算法),但有更快的速度和更小的空間占用,而且也在短時間內(nèi)有更大概率搜到Threat-Space。其弱點在于容易被對手用一定的戰(zhàn)術蒙騙。實驗證明,下棋時幾

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論