首先了解數據的結構:
妳必須先看看MantisChessDef.h裏有什麽，否則妳會迷路的。
和棋盤坐標:
棋盤的尺寸是9x10。為了便於編程，規定板的每壹邊都有壹個元素的邊界。
這樣棋盤大小(包括邊界)就變成了11x12。棋盤的x軸是右，y軸是下。
黑色永遠在最上面，標準出發時左上角的黑車坐標是(1，1)。
這種情況由以下三個變量表示:
靜態點g點棋子[32]；//國際象棋坐標
static int g _ iChessmanMap[11][12]；//國際象棋位置狀態
靜態int g _ iSide//輪到誰去了？
智能部分幾個函數的前三個參數就是這個東西，應該很好理解吧？
-
搜索功能:
首先，經常有朋友問我原理，但是我公開源代碼是給妳參考的，不是給任何教程看的，所以我不想說那些理論上的東西。
基本原理是α -β搜索，很多人工智能教材中都有提到。沒看過的話，去找本書啃壹啃。
這些書中的文字雖然大多晦澀難懂，但畢竟是清晰的。
如果妳沒有書，請發揮主觀作用，自己去找。別問我要，因為我也沒有。
這裏我只分析搜索功能:
了解α -β搜索然後看這個博弈樹，看看怎麽編程。
明確壹下，我們用壹個整數來表示情況。
數字越大，形勢對棋手越有利，0表示雙方實力相當。
1a(1)┬2a(-1)┬3a(-1)
│ └ 3b( 1)
└ 2b(-5) ┬ 3c( 2)
├ 3d(-4)
└ 3e( 5)
分析這棵樹，有這樣壹個特點:父節點的值= -MAX(子節點的值)。
我們也知道1，每個節點對應壹種情況。2.底部節點的值為“估計值”。
所以我們可以寫偽代碼:
偽代碼:搜索壹個節點下的分支，得到這個節點的值。
參數:情況、搜索深度
返回值:節點的值。
Int搜索(情況，int深度)
{
如果(深度！=0)//不是底部節點。
{
枚舉所有子節點(列出所有方式)；
Int count=子節點的數量；
int max value =-∞；
for(int I = 0；我& lt數數；I++)//遍歷所有節點。
{
計算子節點情況；
Maxvalue=max(maxvalue，search(子節點情況，深度-1))；
}
return-max value；
}
Else //是底層節點。
{
返回估計值；
}
}
這是搜索算法的框架，它使用遞歸。
尾數棋的智能功能都在MantisChessThink.cpp中，其中搜索就是搜索，和上面的搜索差不多。我來抄壹下，做個評論:
int Search(int tmap[11][12]，POINT tmanposition[32]，int & amptside，int man，POINT point，int upmax，int depth)
{
//前三個參數是情況。
//man和point是行走方法，用來計算這個節點的情況。這裏把計算情況放在函數的開頭，和上面的偽代碼不太壹樣。
//upmax:up-上層，max-maximum value，這是α-β剪枝用的，後面再說。
//depth:搜索深度
int ate，cur，maxvalue，curvalue，xs，ys；
int計數；
//# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
ate = 32
//移動棋子:
xs=tmanposition[man]。x；ys=tmanposition[man]。y；//原始坐標
if(SideOfMan[tmap[point . x][point . y]]= =！Tside) //目標點有對方的棋子。
{
ate = tmap[point . x][point . y]；//記錄吃掉的棋子
if(ate==0 || ate==16)
{
返回9999；
}
tman位置[ate]。x = 0；//目標點的棋子被吃掉。
}
tmap[point . x][point . y]= man；//這兩行是:
tmap[xs][ys]= 32；//地圖上的移動
tman position[man]= point；
tside=！tside
//####################################################################################
深度-；
if(深度& gt0) //不是底部節點。
{
智力棋子[125]；
POINT target POINT[125]；
If (enumlist (tmap，tmanposition，tside，chesman，targetpoint，count))//枚舉所有子節點(列出所有路由)。
{
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//這是剪枝(不是α-β剪枝)。原理是在正式搜索之前先用淺層搜索得到誤差大的值。
//然後根據這些值對子節點進行排序，只保留最好的S_WIDTH節點進行正式搜索。
//顯然，這種修剪有壹定的風險。
if(深度& gt= 2 & amp& ampcount & gtS_WIDTH+2)
{
int value[125]；
cur = 0；
max value =-10000；
while(cur & lt；計數)
{
curvalue=Search(tmap，tmanposition，tside，chessman[cur]，targetpoint[cur]，-10000，depth-2)；
value[cur]= curvalue；
if(曲線值& gtmax value)max value = curvalue；
cur++；
}
* Mantis _ quick sort(值，棋子，目標點，0，計數-1)；//排序
count = S _ WIDTH//修剪
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
max value =-10000；
cur = 0；
while(cur & lt；計數)
{
curvalue=Search(tmap，tmanposition，tside，chessman[cur]，targetpoint[cur]，maxvalue，depth)；
if(曲線值& gtmax value)max value = curvalue；
if(曲線值& gt=-up max)goto _ end sub；//α-β剪枝，符合剪枝條件的會被剪掉。這裏用的是goto語句，不要模仿我。
cur++；
}
}
else maxvalue = 9800
}
Else //是底層節點。
{
maxvalue=Value(tmap，tmanposition，tside)；//估價
}
_ENDSUB:
//回到之前還原父節點的情況。
//####################################################################################
男人的位置。x = xs//這兩行是:
男人的位置。y = ys//面部恢復
tmap[xs][ys]= man；//在地圖上恢復
如果(吃了！=32)
{
tman position[ate]= point；
tmap[point . x][point . y]= ate；
}
else tmap[point . x][point . y]= 32；
tside=！tside
//####################################################################################
return-max value；
}
上面的代碼使用了α -β剪枝，從壹個例子可以看出:
還是這個博弈樹，從上到下遍歷。
1a(1)┳2a(-1)┳3a(-1)
┃ ┗ 3b( 1)
┗ 2b(-5) ┯ 3c( 2)
├ 3d(-4)
└ 3e( 5)
2a遍歷後Upmax=-1，3c遍歷後返回2b，發現3c = 2 >；-upmax，那就不用擔心3d和3e了，因為不管它們的值是多少，2b =-max (3c，3d，3e)
換句話說，2b是可以安全切斷的。這就是α -β剪枝。
從上面的代碼來看，我的尾數棋算法和標準的α -β剪枝搜索沒什麽區別，只是增加了排序和剪枝。
我在網上找到的。呵呵，我同意。
0|評論
2012-4-14 23:25 lee xye | 6級
即使給出這種直接的源代碼，估計我也看不懂。
0|評論