象棋软件如何开发的？

MantisChessDef.h里的东西一定要先看一下， 否则会摸不到头脑的。

还有棋盘坐标：

象棋棋盘大小9x10,为了便于编程，规定棋盘每条边留有一个元素的边界。

这样棋盘大小（包括边界）变成11x12。棋盘x坐标轴向右，y轴向下。

黑棋永远在上方，在标准开局时左上角的黑车坐标是（1，1）。

局面用这三个变量表示:

static POINT g_pointChessman[32]//棋子坐标

static int g_iChessmanMap[11][12]//棋位状态

static int g_iSide//轮到哪方走

智能部分有几个函数的前三个参数就是这个东西, 应该不难理解吧?

---------------------------------------------------------------------------------------

search函数:

先说明一下， 经常有朋友问我要原理, 但我公开源代码是给大家一个参考， 而不是什么教程，所以我不想说那些理论的东西芦拦。

基本原理是α-β搜索， 很多人工智能的教科书上都有讲到， 没看过的的赶快去找一本来啃一啃；

虽然这些书上的文字大多晦涩难懂，但毕竟讲得明明白白。

没有书的朋友请发挥一下主观能动性， 去找一找，不要来问我要， 因为我也没有。

我在这里只分析一下search函数:

弄懂α-β搜索后来看看这个博弈树， 看怎么编程实现它。

先规定一下， 我们用一个整数表示局面的好坏.

这个数越大说明局面对 "走棋方" 越有利，陪改胡0表示双方实力相等。

1a( 1) ┬ 2a(-1) ┬ 3a(-1)

│ └ 3b( 1)

└ 2b(-5) ┬ 3c( 2)

├ 3d(-4)

└ 3e( 5)

分析一下这棵树，有这么个特点: 父结点的值 = -MAX(子结点的值)

我们还知道1、每个结点对应一个局面。2、底层的结点的值是"估"出来的。

于是我们可以写出伪代码了:

伪代码: 搜索一个结点下的分支， 得到这个结点的值。

参数: 局面，搜索深度

返回值:结点的值

int search(局面，int depth)

{

if(depth!=0)//不是底层结点

{

枚举出所有子结点(列出所有走法)

int count=子结点数；

int maxvalue= -∞

for(int i=0i<counti++)//遍历所有结点

{

算出子结点局面

maxvalue=max(maxvalue，search(子结点局面,depth-1))

}

return -maxvalue

}

else //是底层结点

{

return 估计值

}

}

这就是搜索算法的框架， 用到了递归。

MantisChess的智能部分函数都在MantisChessThink.cpp里， 其中search是搜索， 跟上面的这个search差不多，我把它copy出来注释一下：

int Search(int tmap[11][12],POINT tmanposition[32],int &tside,int man, POINT point,int upmax,int depth)

{

//前面的三个参数就是局面。

//man 和point 是走法，用来计算本结点的局面。 这里是把计算局面放在函数的开头，跟上面的伪代码不太一样。

//upmax: up - 上一层， max - 最大值， 这是α-β的剪枝用到的东西， 后面再讲。

//depth: 搜索深度

int ate,cur,maxvalue,curvalue,xs,ys

int count

//#####################这一段是计算本结点的局面#########################################

ate=32

//移动棋子:

xs=tmanposition[man].xys=tmanposition[man].y//原坐标

if (SideOfMan[tmap[point.x][point.y]]==!tside) /歼卖/目标点有对方的棋子

{

ate=tmap[point.x][point.y]//记录下被吃掉的棋子

if(ate==0 || ate==16)

{

return 9999

}

tmanposition[ate].x=0//目标点的棋子被吃掉

}

tmap[point.x][point.y]=man//这两行是:

tmap[xs][ys]=32//在map上的移动

tmanposition[man]=point

tside=!tside

//####################################################################################

depth--

if(depth>0) //不是底层结点

{

int chessman[125]

POINT targetpoint[125]

if(EnumList(tmap,tmanposition,tside,chessman,targetpoint,count)) //枚举出所有子结点(列出所有走法)

{

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

//这里是剪枝(不是α-β剪枝), 原理是在正式搜索之前先用较浅的搜索来得到误差较大的值

//然后根据这些值来对子结点排序， 只保留最好的S_WIDTH个结点进行正式搜索。

//显然，这个剪枝有一定的风险

if(depth>=2 &&count>S_WIDTH+2)

{

int value[125]

cur=0

maxvalue=-10000

while(cur<count)

{

curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],-10000,depth-2)

value[cur]=curvalue

if(curvalue>maxvalue)maxvalue=curvalue

cur ++

}

::Mantis_QuickSort(value,chessman,targetpoint,0,count-1)//排序

count=S_WIDTH//剪枝

}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

maxvalue=-10000

cur=0

while(cur<count)

{

curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],maxvalue,depth)

if(curvalue>maxvalue)maxvalue=curvalue

if(curvalue>=-upmax)goto _ENDSUB//α-β剪枝, 符合剪枝条件的就Cut掉。 这里用了goto语句了， 千万别学我。

cur ++

}

}

else maxvalue=9800

}

else //是底层结点

{

maxvalue=Value(tmap,tmanposition,tside)//估值

}

_ENDSUB:

//返回之前要恢复父结点的局面

//####################################################################################

tmanposition[man].x=xs//这两行是:

tmanposition[man].y=ys//在face上的恢复

tmap[xs][ys]=man//在map上的恢复

if(ate!=32)

{

tmanposition[ate]=point

tmap[point.x][point.y]=ate

}

else tmap[point.x][point.y]=32

tside=!tside

//####################################################################################

return -maxvalue

}

上面的代码用到了α-β剪枝, 举个例子就明白了:

还是这个博弈树，从上往下遍历。

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)<2a 一定成立,

也就是说2b可以安全地剪掉。这就是α-β剪枝。

从上面的代码来看我的MantisChess算法与标准的α-β剪枝搜索并没有什么不同， 只不过加了排序和剪枝而已。

先观察当前局面，列出所有可能的走法，然后对裤巧每种走法进行分析。

分析时，会深入若干步，看这种下法究竟如何。

判断局面的时候，会根据多种因素评分：比没纯困如为每一个棋子赋予不同的权重，车为20，马为10，炮为10，之类；为不同的位置也赋予不同的权重，比如，车在中央为50，在角落为10，在靠近对方九宫的地方为80；同一个棋子在不同的进程也可能有不同的值，比如马，到了残局阶段就会增加价值；兵过河以后会增加价值；如果能够导致杀棋的下法，价值会最大。如果能造成对方拥塞、丢子等分值降低的下法，也会为己方增值。

如果你按照套路开局，它还有开局库可以随便挑；如果你不按照套路开局，它有强大的计算力。

软件的枯念优势是计算的全面和较深入。能够把人对象棋棋理的认识反应出来，所以很厉害。

（围棋软件暂时还没有那么厉害，是因为围棋的变化和棋理更复杂。最高水平的围棋棋手都谦虚的说自己只了解了围棋的7％ ）