无二致了）。因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。
可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer所提出的“历史启发”（History Heuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。
对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。 3.1.3 局面评估
前文已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助“历史启发”）， 在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。
首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点：
1、子力总和
子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值10的话，那可能马值6，卒值2等等。所以在评估局面时，首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。
2、棋子位置
棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。
3、棋子的机动性
棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以
9
下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。
4、棋子的相互关系
这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。
在程序中，估值函数最后返回的是每一方的总分的差值，而各方的总分就是上面所提到的四个因素的打分的总和。
对于子力打分和控制区域打分，只要遍历棋盘，当遇到棋子时简单地去查事先定义好的“子力价值表”和“控制区域价值表”，取出相对应的值进行累加即可。
对于机动性打分，需要求出各个子总共有多少种走法，然后根据各个子所不同的机动性价值每多一种走法就加一次相应的分数。
对棋子间相互关系的打分，要用到以下几个数据： int m_BaseValue[15]; int m_FlexValue[15];
//存放棋子基本价值 //存放棋子灵活性分值 //存放每一位置被威胁的信息
short m_AttackPos[10][9];
BYTE m_GuardPos[10][9]; //存放每一位置被保护的信息 BYTE m_FlexibilityPos[10][9];//存放每一位置上棋子的灵活性分值 int m_chessValue[10][9]; //存放每一位置上棋子的总价值
其中计算机会进行所有棋子值的判断，AttackPos和GuardPos分别记录该棋子受到的威胁和被保护的值。
当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，再根据关系表来具体考察棋子的相互关系，进行关系打分。
分析关系时，首先，对王的攻击保护应分离出来单独考虑，因为对王的保护没有任何意义，一旦王被吃掉整个游戏就结束了。
其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题： 1、攻击者子力小于被攻击者子力，攻击方将愿意换子。比如，一个车正遭受一个炮的攻击，那么任何对车的保护都将失去意义——对方肯定乐意用一个炮来换一个车。
2、多攻击/单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者子力之和，则攻击方可能以一子换两子。
3、三攻击/两保护的情况，并且攻击者子力较小的二者之和小于被攻击者子力与保
10
护者子力之和，则攻击方可能以两子换三子。
4、攻击方与保护方数量相同，并且攻击者子力小于被攻击者子力与保护者子力之和再减去保护者中最大子力，则攻击方可能以n子换n子。
当然，上述四条只是覆盖了最常见的几种情况，覆盖并不全面。而且，在程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况（之所以说没有“直接地重新考虑”，是因为搜索继续展开结点后仍会考虑这些因素，只是目前不知这样效果是否受影响——考察这两种方法在效果上的差异需要一定数量的试验数据的支持）。所以，如果今后要对引擎进行改进，提高程序的下棋水平的话，还应当在此进行研究。 3.2 悔棋和还原功能的实现
悔棋和还原是棋类软件中较为基本的功能。要实现悔棋和还原功能，首先要明确哪些信息应当被保存以供悔棋和还原所使用。
在程序中保存了如下信息： 棋局表示中所定义的棋盘数组； 各棋子的贴图位置；
这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。然而，在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此保存了全部棋子的信息。
根据所要保存的数据定义了如下基本结构类型： typedef struct {
CHESSMOVE cmChessMove; short nChessID;//被吃掉的棋子 }UNDOMOVE;
在对弈过程中，每一回合都将棋局信息（这里指前面所说的需要保存的信息）保存至走法队列，以供悔棋所用。还原功能是与悔棋功能相对应的，只有当产生了悔棋功能之后，还原功能才会被激活。一个回合的结束意味着前一次操作没有悔棋功能的产生，因此还原队列也应被清空。
在悔棋中主要完成了以下任务： 1、下棋回合数减一；
11
2、将当前局面信息保存至走法队列，以供还原所用；
3、从走法队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从 队列中剔除掉；
4、将显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队 列，以供还原所用。然后从列表框中删除它。
而在还原中所做的刚好和悔棋相反： 1、下棋回合数加一；
2、将当前局面信息保存至队列，以供悔棋所用；
3、从队列中取出最近一次悔棋前的棋局信息，恢复到当前局面，然后将其从队列中剔除；
4、从走法队列中取出最近一次存入的着法名称（两项，因为每回合会产生两步着法），将其重新显示到列表框中。然后将其从中剔除。
以上便是悔棋和还原功能所完成的具体操作，其代码分别写入悔棋和还原按钮（Button）的事件处理函数中。 3.3 着法名称显示功能的实现
每当下棋者（用户或是计算机）走一步棋，在棋盘旁边的一个列表框控件（List Box）中按照中国象棋关于着法描述的规范要求显示出该着法的名称。如：炮八进四、马二进三此类。为了获得该着法名称，我们编写了一个函数，其功能就是将被移动的棋子类型以及走法的起点坐标、终点坐标这些信息转换成中国象棋所规范的着法名称。实现此功能代码如下：
void CGradientProgressCtrl::OnPaint() {
CPaintDC dc(this); // device context for painting // TODO: Add your message handler code here
if(m_nCurrentPosition<=m_nLower || m_nCurrentPosition>=m_nUpper) {
CRect rect; GetClientRect(rect); CBrush brush;
brush.CreateSolidBrush(::GetSysColor(COLOR_3DFACE)); dc.FillRect(&rect,&brush);
12
VERIFY(brush.DeleteObject()); return;
}
CRect rectClient; GetClientRect(rectClient);
float maxWidth((float)m_nCurrentPosition/(float)m_nUpper*(float)rectClient.right); //绘制
DrawGradient(&dc,rectClient,(int)maxWidth); //显示进程条进度文字 if(m_bShowPercent) {
CString percent;
percent.Format(\ dc.SetTextColor(m_clrText); dc.SetBkMode(TRANSPARENT);
dc.DrawText(percent,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
}
//显示其他文字 if(m_bIsShowText) {
dc.SetTextColor(m_clrText); dc.SetBkMode(TRANSPARENT);
dc.DrawText(m_strShow,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
}
// Do not call CProgressCtrl::OnPaint() for painting messages
}
int CGradientProgressCtrl::SetPos(int nPos) {
//Set the Position of the Progress m_nCurrentPosition=nPos;
return (CProgressCtrl::SetPos(nPos));
}
int CGradientProgressCtrl::StepIt()
13
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库中国象棋游戏的设计与实现-毕业设计(3)在线全文阅读。
相关推荐：