五子棋算法.doc

五子棋算法 五子棋算法問題描述：人們通常喜愛的五子棋。某方將結(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)術蒙騙。實驗證明，下棋時幾