内容发布更新时间 : 2024/5/18 8:14:10星期一 下面是文章的全部内容请认真阅读。

步数。利用保存在*BK_Black,*BK_White的两个数组中记录的下棋轨迹。很容易能够实现这个功能。如黑白子向后悔棋一步应该写成Rollback（1，1）。

? void Init(CFiveChessView * view)---------初始化该类

该类实现的是初始化过程，也许你很疑惑。为什么不把他放到构造函数中去呢？起初我也是这么认为的，后来在CFiveChessView类中定义棋盘成员时发现CMatch m_match(this)是不能实现的。这里有两种方法可以解决这个问题，如声明一个棋盘类指针，然后在CFiveChessView中去初始化也就是动态申请一个棋盘变量用this做参数；当然还有一种方法就是另外再写个函数如init(CFiveChessView * view)然后在CFiveChessView中调用，同样也可以实现，明显前者会结构更符合。采用了后者是因为当初在解决这个问题时还没想到这种解决方法。

? BOOL CanDown(int x,int y,int who)--------判断该点是否可合法

这个函数根据传入进来的参数，判断该点是否合法。若是则修改该点棋盘上该点的值。当初只是根据直觉把修改棋盘值功能也合并到这个函数中去，现在想想似乎有些不妥，至少在结构上是如此。破坏了模块间的耦合度，也就是做了不该由该函数完成的动作。理想的函数只做一件事，也即是只要判断改点是否合法，然后在返回布尔变量。修改的步骤应该由其他操作完成。但是由于时间所限，目前只要完成基本功能后，修改后将影响到其他部分的代码修改，所以将更加完善的部分放到后期完成。

? BOOL IsWin(int who,int pos[5][2])--------判断是否已经赢了

该功能判断是否who已经形成了五连子了，若是则将其记录到pos[5][2]中去，便于在棋盘上标示出来，同时返回判断的结果。因为该函数实现的思路是逐个的遍历每个棋盘点进行判断。明显这个是很没必要的，当棋盘很大时候是很费时间的需要优化。我们可以做个简单的证明；假设当前棋盘没有形成五连子，那么我们往棋盘下一个子，若会形成五连子的则该点一定在这五连子中。其他的子由于在上面的假设中不会形成五连子所以也不可能形成。 这样一来我们只要判断该点的四个方向就足够了。这也是一个良好编程的思维。同样由于时间有限，只能将更完善的修改放到后期去。

? void Clear()-------清空棋盘

这个函数是将chessboard二元数组全部值修改0，表明棋盘全部置空。

2.4.3.2 CMessg------消息类

16

1.消息类的数据成员：

CString m_strText; // 用于发送聊天信息的字符变量

BOOL m_restart; // 用于表识对方是否发送重新开始请求 BOOL m_restartconfirm; // 发出重新开始请求是否得到对方的确认 BOOL m_rollback; / /标识对方是否发送了悔棋的请求

BOOL m_rollbackconfirm; //发出的悔棋请求是否得到了对方确认 BOOL m_fail; // 发出认输请求

BOOL m_failconfirm; // 发出认输确认回复 BOOL m_dogfail; // 发出和棋请求 BOOL m_dogfailconfirm; //发出和棋确认回复 int m_turn; //当前轮到哪方下棋了 int m_x; //对方下的棋子的横坐标 int m_y; //对方下的棋子的纵坐标

2.消息类的成员函数：

? void Init()--------初始化函数

在该函数中将全部的值置为不可用状态。

? virtual void Serialize(CArchive& ar)------序列化函数

Cobject类拥有序列化虚函数，消息类派生自该类，根据C++继承性质子类就可以重写该函数。从传递进来的Carchive 的类型进入相应的函数部分。当它是load类型时将数据写入ar中也就是相当于接收到了对方发过来的消息；当它是store类型时该函数就将值读入ar中，实现了向对方发送数据的功能。

2.4.3.3 Ccomputer-----电脑类

1. 消息类的数据成员：

int m_step; //表示当前电脑走了几步 int m_grade; //表示电脑的等级

int x,y; //电脑给出的最佳位置 2. 消息类的成员函数：

? OptimizeLayChess_MaxMin4(chessboard[][LW],depth,

*px,py,Alpha, Beta);

OptimizeLayChess_MaxMin_2_1(chessboard[][LW],d

epth,*px,*py, Alpha, Beta);

LayChess_MaxMin2(chessboard[][LW], depth,

*px,i*py, Alpha, Beta);

以上三个函数分别对应电脑中的高级，中级，初级智能。

第一个采用了动态优化功能深度为4；第二用也采用了动态优化，深度为3；第三个只用了剪枝。关于他们详细的介绍参看算法分析部分。

? Repair(chessboard[][LW],*px,*py);

17

由于AI算法中本身存在的问题(详细见4.2节 不足说明),所以需要进行必要的修补.这个函数遵循的原则是:己五必填,活四看对方,若对方不可能形成连五,同样必填.不是活四也不是死四的话,若对方可形成连五,必堵! ? Int Count_135(chessboard[][LW],i*p_135,*p_315,

i,j,who); int Count_90(chessboard[][LW],i*p_90, *p_270, i,

j, who);

int Count_45(chessboard[][LW], *p_45, *p_225, i, j, who);

int Count_0(chessboard[][LW],*p_0,*p_180, i,j, who);

这组函数是用于计算i,j点的各个方向上连续的who类型的棋子数,并且将每个方向上的被”阻碍”的类型. ? GetScorce(int total,int edge1,int edge2);

Get_0_Scorce(chessboard[][LW],Eva_Tab ScoTab,i,j); Get_45_Scorce(chessboard[][LW],Eva_TabScoTab,i,; Get_90_Scorce(chessboard[][LW], ScoTab, i, j); Get_135_Scorce(chessboard[][LW], ScoTab, i,ij); evaluate(int chessboard[][LW]);

这几个函数是分别用于计算，一个棋子在四个方向上的值。就是对应水平上，45度，90度，135度调用GetScorce计算。

2.5 人机对战中AI算法

人工智能(Artificial Intelligence) ，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式作出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

在该部分我们尽量去模拟人类在下棋中思考的方式，找出一种合乎逻辑的规则。

根据我们平常下棋的经验，当放入一个棋子时总是尽量的往利于己方的位置也既是“攻”；同时要提防对方使其不能得逞也既是“防”；我们可以用计算机模拟这个过程。假设我们在棋盘中放入一个己方棋子，然后考虑对方最可能下的棋子位置，也就是最有利于对方的点。（我们假设只进行两次的探索），再逐个的比较每个可下棋的点，最后得出最有利于我方的点。这就是本个系统中所采用的一个思路。对于人说用手工去比较计算是不现实的。当考虑的深度加深的话甚至无法在有效的时间内实现的。我们正是利用计算机快速的计算机能力进行这样的笨重检索，就能够在很短的时间内计算完。下面对AI算法中所涉及的几个重要概念作下介绍。

18

2.5.1 极大极小树

目前绝大部分的博弈类游戏中的人工算法都采用这种方法。假设己方为MAX点，对方则为MIN点。如果当层的节点为奇数时那么就为MAX层，同样为偶数时就为MIN层。当在MAX层时，该层的值就应该为下一个MIN层中的最大一个的值。当在MIN层是，该层的值就应该为它子层MAX的最小的一个。通俗的说就是当轮到我方时，我们就应该选择一个最有利于我们的点，预测对方可能下的最有利他方的点（相对我方来说就是最坏的点）。这样反复计算下去就能够得到根节点的最大值，这个点也就是我们最佳下棋点。在计算这个点时可以很明显的看出这是一个不断递归的过程，到达叶子节点时根据相关的计算规则算出该值然后向上一层不断的返回。下图中矩形代表极大层，椭圆代表极小层。

60 10 5 60 10 40 20 5 15 60

图 2.7 极大极小树

2.5.2 深度优先搜索（DFS）

在图论中有两个很重要的遍历的方法，一个是深度优先搜索（DFS）,另外一个是广度优先搜索(BFS).这两个方法的主要区别在于下一个节点的选择。DFS首先选择它的连接节点，若它的下个节点已经全部被遍历过或者不存在的话。则向上返回到上一个节点，在遍其他的未被访问过的点。很容易想到这要用到堆栈结构，使用一个递归来实现。而BFS则是逐个的遍历它的联接接点，将已经访问过的点放入队列中。然后再依次取出继续这个过程。

A B F C 图2.8

D

E DFS遍历过程如下：

19

首先从A点出发访问它的领接点B，因为B的领接点C,F均未被访问过，所以B点选择C（当然也可以选择F点）作为下一个要访问的点，C点的领接点是D,F选择下个节点D，而D的邻接点只有一个E且未被访问过，就将E作为了它下个节点。这时因为E已经没有可访问的邻点，所以向上一层返回到D，发现D也已经没有可访问的点了，继续向上层返回到C，由于C的邻节点F未被访问过，那么就访问F。所以整个过程的遍历结果为：A-->B?C?D?E?F。

BFS的的遍历过程为：A?B?E?C?F?D。

2.5.3 剪枝方法

在上面中提到当预测的深度达到3的时候，最坏情况下225*225*225=11390625个，这在目前的一些常规平均的机器性能下也需要40多秒的时间，这是不能够容忍的。那么是否有很好的改进技术，去除哪些不必要的节点，并且在剪去了这些点后不影响结果呢？答案是肯定的，这种方法就是Alpha---Beta剪枝。

下面通过图来说明，矩形代表极大层，椭圆代表极小层。

A: 40 B:40 C:<=30 D:20 40 50 E:30 ？ ? F:20 H:>=25 I:25

图 2.9 Alpha—Beta剪枝

? ?

从上图可以看出，由于C节点的值肯定不大于30而B节点的值为40大于C节点，那么目前为止可以很肯定的说A节点值一定不小于40。 所以C点的其他子节点无须去访问也不会对结果的值有影响。这个就是α剪枝。

在I节点的值确定为25后，我们就可以断定H节点一定不小于25,而F点的值为20，那么就可以很确定的说D的值为20。这个就是β剪枝。

下面给出完整的定义：

α剪枝:若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值 ,即α(先辈层)≥β(后继层) ,则可终止该最小值层中这个 Min 节点的搜索过程。这个 Min 节点最终的倒推值就确定为β值。

β剪枝:若任一极小值层节点的α值大于或等于它任一先辈极大值层节点的β值 ,即α(后继层)≥β(先辈层) ,则可终止该最大值层中这个 Max 节点的搜索

20