人工智能α-β剪枝实现的一字棋实验报告(共12页).doc
《人工智能α-β剪枝实现的一字棋实验报告(共12页).doc》由会员分享,可在线阅读,更多相关《人工智能α-β剪枝实现的一字棋实验报告(共12页).doc(12页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上实验5:a -b剪枝实现一字棋一、实验目的 学习极大极小搜索及a -b 剪枝算法实现一字棋。二、实验原理1.游戏规则一字棋游戏(又叫三子棋或井字棋),是一款十分经典的益智小游戏。井字棋 的棋盘很简单,是一个 33 的格子,很像中国文字中的井字,所以得名井字棋。井字棋游戏的规则与五子棋十分类似,五子棋的规则是一方首先五子连成一线就胜利;井字棋是一方首先三子连成一线就胜利。 2.极小极大分析法设有九个空格,由 MAX,MIN 二人对弈,轮到谁走棋谁就往空格上放一只自己的棋子,谁先使自己的棋子构成三子成一线(同一行或列或对角线全是某人的棋子),谁就取得了胜利。 用圆圈表示
2、MAX,用叉号代表 MIN比如左图中就是 MAX 取胜的棋局。估价函数定义如下设棋局为 P,估价函数为 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. a
3、 -b剪枝算法上述的极小极大分析法,实际是先生成一棵博弈树,然后再计算其倒推值,至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了a-b 剪枝技术。 a -b 剪枝技术的基本思想或算法是,边生成博弈树边计算评估各节点的倒推值,并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点,即相当于剪去了博弈树上的一些分枝,从而节约了机器开销,提高了搜索效率。 具体的剪枝方法如下: (1) 对于一个与节点 MIN,若能估计出其倒推值的上确界 b,并且这个 b 值不大于 MIN 的父节点(一定是或节点)的估计倒推值的下确界 a,即 ab,则就不必再扩展该MIN 节点的其余子节点了(
4、因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了)。这一过程称为 a 剪枝。 (2) 对于一个或节点 MAX,若能估计出其倒推值的下确界 a,并且这个 a 值不小于 MAX 的父节点(一定是与节点)的估计倒推值的上确界 b,即 ab,则就不必再扩展该 MAX 节点的其余子节点了(因为这些节点的估值对 MAX 父节点的倒推值已无任何影响 了)。这一过程称为 b 剪枝。 从算法中看到: (1) MAX 节点(包括起始节点)的 a 值永不减少; (2) MIN 节点(包括起始节点)的 b 值永不增加。 在搜索期间,a 和 b 值的计算如下: (1) 一个 MAX 节点的 a 值等于其后继节
5、点当前最大的最终倒推值。 (2) 一个 MIN 节点的 b 值等于其后继节点当前最小的最终倒推值。4输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有,则说明有一方胜利,如果没有则继续搜索,直到有一方胜利或者搜索完整个棋盘。三、实验代码#includeusing namespace std;int num=0; /记录棋盘上棋子的个数int p,q; /判断是否平局int tmpQP33; /表示棋盘数据的临时数组,其中的元素0表示该格为空,int now33; /存储当前棋盘的状态con
6、st int depth=3; /搜索树的最大深度void Init() /初始化棋盘状态 for(int i=0;i3;i+)for(int j=0;j3;j+) nowij=0; /将初值均置为0 void PrintQP() /打印棋盘当前状态 for(int i=0;i3;i+) for(int j=0;j3;j+)coutnowijt; coutendl; void playerinput() /用户通过此函数来输入落子的位置,比如:用户输入3 1,则表示用户在第3行第1列落子。 int x,y;L1: cout请输入您的棋子位置(x y):xy; if(x0&x0&y4&nowx-
7、1y-1=0) nowx-1y-1=-1; /站在电脑一方,玩家落子置为-1 else cout非法输入!endl; /提醒输入错误 goto L1; int Checkwin() /检查是否有一方赢棋(返回 0:没有任何一方赢;1:计算机赢;-1:人赢) /该方法没有判断平局 for(int i=0;i3;i+) if(nowi0=1&nowi1=1&nowi2=1)|(now0i=1&now1i=1&now2i=1) |(now00=1&now11=1&now22=1)|(now20=1&now11=1&now02=1) /正方行连成线 return 1; if(nowi0=-1&nowi
8、1=-1&nowi2=-1)|(now0i=-1&now1i=-1&now2i=-1)|(now00=-1&now11=-1&now22=-1)|(now20=-1&now11=-1&now02=-1) /反方行连成线 return -1; return 0;int value() /评估当前棋盘状态的值(同时可以用p或q判断是否平局) p=0; q=0; for(int i=0;i3;i+) /计算机一方 将棋盘中的空格填满自己的棋子,既将棋盘数组中的0变为1 for(int j=0;j3;j+) if(nowij=0) tmpQPij=1; else tmpQPij=nowij; for(
9、int i=0;i3;i+) /计算共有多少连成3个1的行 p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3; for(int i=0;i3;i+) /计算共有多少连成3个1的列 p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3; p+=(tmpQP00+tmpQP11+tmpQP22)/3; /计算共有多少连成3个1的对角线 p+=(tmpQP20+tmpQP11+tmpQP02)/3; for(int i=0;i3;i+) /人一方 /将棋盘中的空格填满自己的棋子,既将棋盘数组中的0变为-1 for(int j=0;j3;j+) if(nowij=0) tmpQPi
10、j=-1; else tmpQPij=nowij; for(int i=0;i3;i+) /计算共有多少连成3个-1的行 q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3; for(int i=0;i3;i+) /计算共有多少连成3个1的列 q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3; q+=(tmpQP00+tmpQP11+tmpQP22)/3; /计算共有多少连成3个1的对角线 q+=(tmpQP20+tmpQP11+tmpQP02)/3; return p+q; /返回评估出的棋盘状态的值int cut(int &val,int dep,bool max)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 剪枝 实现 一字棋 实验 报告 12
限制150内