αβ剪枝实现的一字棋实验报告

《αβ剪枝实现的一字棋实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能大作业——极大极小算法和a-b剪枝实现一字棋学院：班级：姓名：学号：辅导老师：日期：11目录一、实验目的3二、实验环境3三、实验原理33.1游戏规则33.2极小极大分析法33.3a-b剪枝算法43.4输赢判断算法设计5四、数据结构54.1程序流程54.2主要成员函数54.2.1估值函数54.2.2Alpha-Beta剪枝算法64.2.3判断胜负64.2.4鼠标左键响应64.2.5Draw系列函数64.2.6COMPUTERorPLAYER先走7五、实验内容75.1基本功能简介75.2流程图.85.2.1估价函数85.2.2Alpha

2、-Beta剪枝9六、实验小结10七、实验源代码1011一、实验目的(1)学习极大极小搜索及a-b剪枝。(2)利用学到的算法实现一字棋。二、实验环境(1)硬件环境：网络环境中的微型计算机。(2)软件环境：Windows操作系统，MicrosoftVisualC++语言。三、实验原理3.1游戏规则"一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋"的棋盘很简单，是一个3×3的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；

3、"井字棋"是一方首先三子连成一线就胜利。井字棋（英文名Tic-Tac-Toe）井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。3.2极小极大分析法设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。用圆圈表示MAX，用叉号代表MIN。比如左图中就是MAX取胜的棋局。11估价函数定义如下：设棋局为P，估价

4、函数为e(P)。(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)(2)若P是MAX必胜的棋局，则e(P)＝+¥（实际上赋了60）。(3)若P是B必胜的棋局，则e(P)＝-¥（实际上赋了-20）。比如P如下图示,则e(P)=5-4=1需要说明的是，+¥赋60，-¥赋-20的原因是机器若赢了，则不论玩家下一步是否会赢，都会走这步必赢棋。3.3a-b剪枝算法上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分

5、析法效率较低。于是在极小极大分析法的基础上提出了a-b剪枝技术。a-b剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界b，并且这个b值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界a，即a³b，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为

6、a剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界a，并且这个a值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界b，即a³b，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为b剪枝。从算法中看到：(1)MAX节点(包括起始节点)的a值永不减少；(2)MIN节点(包括起始节点)的b值永不增加。在搜索期间，a和b值的计算如下：(1)一个MAX节点的a值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的b值等于其后继节点当前最小的最终倒推值。113.4输

7、赢判断算法设计因为每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。四、数据结构4.1程序流程4.2主要成员函数4.2.1估值函数估价函数：intCTic_MFCDlg::evaluate(intboard[])完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是MAX的必胜局，则e=+INFINITY，这里为+6011若是MIN的必胜局，则e=-INFINITY，这

8、里为-20，这样赋值的原因是机器若赢了，则不考虑其它因素。其它情况，棋盘上能使CUMPUTER成三子一线的数目为e1棋盘上能使PLAYER成三子一线的数目为e2，e1-e2作为最