_CAR 9 //红车
#define R_HORSE 10//红马
#define R_CANON 11//红炮
#define R_BISHOP 12//红士
#define R_ELEPHANT 13//红相
#define R_PAWN 14//红兵
判断颜色:
#define IsBlack(x) (x>=B_BEGIN && x<=B_END)//判断某个棋子是不
是黑色
#define IsRed(x) (x>=R_BEGIN && x<=R_END)//判断某个棋子是不
是红色
对于着法的表示,
直接借用棋盘数组的下标来记录着法的起点和目标点。
至于是什么棋子在走,以及是否吃子、吃的是什么子,
在着法结构中并不记录。
这些信息由外部读取棋盘上起点、终点的数据获得。
着法结构定义如下,其中还包含了对着法的历史得分的记录项,
以供后面要讲到的"历史启发"所用。
typedef struct
{
short nChessID; //表明是什么棋子
CHESSMANPOS From;//起始位置
CHESSMANPOS To; //走到什么位置
int Score; //走法的分数
}CHESSMOVE;
有了对棋盘局面和着法的表示之后,
程序才能够完成以下操作:
1、 生成所有合法着法;
2、 执行着法、撤销着法;
3、 针对某一局面进行评估。
因而,棋局表示好比是整个程序(计算机下棋引擎部分)的地基,
之后所有的操作都将建立在其基础上。
2.2 着法生成
程序需要让计算机在轮到它走子的时候能够执行一步它认为对它最有利的着法,
那前提就是它要有诸多(也可能是唯一)可供选择的着法
提供所有候选着法的"清单"就是着法生成器所要完成的。
之后用搜索函数来搜索"清单",并用局面评估函数来逐一打分,
最后就可以选择出"最佳着法"并执行了。
在着法生成器中,采用的基本思想就是遍历整个棋盘(一个接一个地查看棋盘上的每个位置点),
当发现有当前下棋方的棋子时先判断它是何种类型的棋子
然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。
这里谈到的"合法着法"包括以下几点:
1、各棋子按其行子规则行子。
诸如马跳"日"字、象走"田"字、士在九宫内斜行等等(这里需要特别注意的是卒(兵)的行子规则会随其所在位置的不同而发生变化--过河后可以左右平移)。
2、行子不能越出棋盘的界限。
当然所有子都不能走到棋盘的外面,同时某些特定的子还有自己的行棋界限,
如将、士不能出九宫象不能过河。
3、行子的半路上不能有其它子阻拦(除了炮需要隔一个子才能打子之外)以及行子的目的点不能有本方的棋子(当然不能自己吃自己了)。
4、将帅不能碰面(本程序中只在生成计算机的着法时认为将帅碰面是非法的,
而对用户所走的导致将帅碰面的着法并不认为其非法
而只是产生败局罢了)。
产生了着法后要将其存入着法队列以供搜索之用,
由于搜索会搜索多层(即考虑双方你来我往好几步
这样才有利于对局面进行评估以尽可能避免"目光短浅")
所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。
因此可以将着法队列定义为二维数组m_MoveList[8][80],
其中第一个数组下标为层数第二个数组下标为每一层的全部着法数。
关于搜索层数,设定为8,实际使用的是1到7(在界面中将其限定为1-7)。
搜索层数的增加会显著提高电脑的下棋水平(当然计算机的棋力在很大程度上也依赖于局面评估)。
在配置为1.5G,512M内存的计算机上最多只能搜索4层,
再多将导致搜索时间达到令人无法容忍的地步(这里还需要特别说明的是
搜索的速度也和着法生成的效率以及局面评估的复杂度有关
因为每分析一个结点都要执行这两种操作)。
对于每一层的着法数,也就是当前下棋方针对当前局面的所有可选的合法着法,
据有关数据统计在象棋实战中一般最多情况下也就五六十种。
定义第二个数组下标为80,应当可以保证十分的安全。
着法生成为搜索部分提供了"原料",接下来的任务就交给搜索和局面评估了。
2.3 搜索算法
搜索算法对于整个下棋引擎来说都是至关重要的。
它如同程序的心脏,驱动着整个程序。
搜索算法的好坏直接影响着程序执行的效率(从某种角度上,
它影响着计算机的下棋水平。
因为,计算机必须在有限的时间内完成思考,
搜索速度快意味着在相同的时间内程序可以"看"得更远
"想"的更多)。
关于棋类对弈程序中的搜索算法,已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法(还有众多基于Alpha-Beta算法的派生、变种算法)在程序中直接借鉴了Alpha-Beta搜索算法并辅以了历史启发。
本节先介绍Alpha-Beta搜索算法:
在中国象棋里,
双方棋手获得相同的棋盘信息。
他们轮流走棋,目的就是将死对方,或者避免被将死。
由此,可以用一棵"博弈树"(图2)来表示下棋的过程--树中每一个结点代表棋盘上的一个局面,
对每一个局面(结点)根据不同的走法又产生不同的局面(生出新的结点)
如此不断直到再无可选择的走法即到达叶子结点(棋局结束)。
中国象棋的博弈树的模型大概如下图所示,
可以把其中连接结点的线段看作是着法
不同的着法自然产生不同的局面。
图 2博弈树
该树包含三种类型的结点:
1、 奇数层的中间结点(以及根结点),
表示轮到红方走棋;
2、 偶数层的中间结点
表示轮到黑方走棋;
3、 叶子结点表示棋局结束。
现在让计算机来下中国象棋,它应当选择一步对它最有利的着法(最终导致它取胜的着法)。
获得最佳着法的方法就是"试走"每一种可能的着法,
比较它们所产生的不同后果然后从中选出能够产生对自己最有利的局面的着法。
结合上面所讲的博弈树,若给每个结点都打一个分值来评价其对应的局面(这一任务由后面所讲的局面评估来完成),
那么可以通过比较该分值的大小来判断局面的优劣。
假定甲乙两方下棋,甲胜的局面是一个极大值(一个很大的正数),
那么乙胜的局面就是一个极小值(极大值的负值)
和棋的局面则是零值(或是接近零的值)。
如此,当轮到甲走棋时他会尽可能地让局面上的分值大,
相反轮到乙走棋时他会选尽可能地让局面上的分值小。
反映到博弈树上,即如果假设奇数层表示轮到甲方走棋,
偶数层表示轮到乙方走棋。
那么由于甲方希望棋盘上的分值尽可能大,
则在偶数层上会挑选分值最大的结点--偶数层的结点是甲走完一步棋之后的棋盘局面
反映了甲方对棋局形势的要求。
同样道理,由于乙方希望棋盘上的分值尽可能小,
那么在奇数层上会选择分值最小的结点。
这是"最小-最大"(Minimax)的基本思想。
这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大(最小)的结点,
在偶数层选择分值最小(最大)的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。
然而不幸的是,博弈树相当庞大(它会成指数增长),
因而搜索(限定层数以内的)整棵树是一件相当费时的工作--其时间复杂度为O(bn)。
其中b是分枝因子,即针对各种局面的合法着法的数目的平均值,
n是搜索的深度。
对于中国象棋而言,在中盘时平均着法数目大约是40种左右,
那么搜索4层需要检查250万条路线搜索5层需要检查1亿条路线
搜索6层需要检查40亿条路线!
Alpha-Beta搜索能在不影响搜索精度的前提下大幅减少工作量。
因为,如果考虑到下棋是一个你来我往的交替进行并且相互"较劲"的过程。
由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向(假定下棋双方对棋局有着同样的认知,
即你认为对你很糟糕的局面在你的对手看来则是对他很有利的局面)
那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。
所以当你看到某个局面有可能产生很糟糕的局面时(确切地说这里的"很糟糕"是与之前分析的情况相比较而言的),
你应当立刻停止对其剩余子结点的分析--不要对它再抱任何幻想了
如果你选择了它那么你必将得到那个很
上一篇:
中国象棋打谱系统-Java语言毕业设计内附详细的Java程序
下一篇:
近三年来思想工作小结(德能勤绩廉)