黑车小游戏
首先了解数据的结构:
你必须先看看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|评论