人工智能α-β剪枝实现的一字棋实验报告

实验：-枝实现一字棋一、实验的学习极大极小搜索与-实现一字棋。二、实验理"一字棋"游三子棋"或"井字棋"益智小游戏。"井字棋"的棋盘很简单，是一个3×3的格子，很像中国文字中的井"字，所以得名"井字棋"井字棋"游戏的规则与"五子棋十分类似五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。设有九个空格MAX二人对弈到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成三子成一线(同一行或列或对角线全是某人的子)，谁就取得了胜利。eq\o\ac(○,棋)eq\o\ac(○,)╳○○○

用圆圈表示MAX，用叉号代表MIN比如左图中就是MAX取胜的棋局。╳

╳

估价函数定义如下设棋局为P估价函数为e(P)。(1)若P对任何一方来说都不是获胜的位置些仍为MAX空着的完全的行、列或对角线的总数-e(那些仍为MIN空着的完全的行、列或对角线的总数)(2)若P是MAX必胜的棋局，则e(P)＝+（实际上赋了60(3)若P是B必胜的棋局，则e(P)＝-（实际上赋了-20如P如以下图示,则e(P)=5-4=1eq\o\ac(○,比)╳

需要说明的是20的原因是机器若赢了不论玩家下一步是否会赢会走这步必赢棋。上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，

...至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了枝技术。-枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值评估出的倒推值围扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界个值不大于MIN的父节点(定是或节点估计倒推值的下确界则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界这个值不小于MAX的父节点定是与节)的估计倒推值的上确界则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为枝。从算法中看到：(1)MAX节点(包括起始节点)的永不减少；(2)MIN节点(包括起始节点)的永不增加。在搜索期间，的计算如下：(1)一个MAX节点的等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的等于其后继节点当前最小的最终倒推值。．输因为每次导致输赢的只会是当前放置的棋子,赢算法中只需从当前点开始扫描判断是否已经形成三子于这个子的八个方向判断是否已经形成三子果有说明有一方胜利果没有则继续搜索到有一方胜利或者搜索完整个棋盘三、实验码/

...行

或判/

...个个个1变3个个/

...

记如如/

...val您棋游/

...平平您平

/

...您游平/

...4.要函数1估值估价函数：intCTic_MFCDlg::evaluate(intboard[])完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是MAX的必胜局，则e=+INFINITY，这里为+60若是MIN的必胜局，则e=-INFINITY，这里为20，这样赋值的原因是机器若赢了，则不考虑其它因素。其它情况，棋盘上能使CUMPUTER成三子一线的数目为e1棋盘上能使PLAYER成三子一线的数目为e2，e1-e2作为最终权值参数：board:待评估棋盘返回：

评估结果/

...AlphaBeta剪枝主函数：intCTic_MFCDlg::AlphaBeta(intBoard[],intDepth,intturn,intAlpha,intBeta,int*result)完成功能：根据输入棋盘，搜索深度，与其他参数，给出一个相应的最优解，存入result中。参数：board:待评估棋盘Depth:搜索深度turn:当前是机器走(MAX结点)还是玩家走(MIN结点)Alpha:alpha值，第一次调用默认-100Beta:beta值，第一次调用默认+100result:输出结果返回：若当前点为MAX节点，则返回alpha值；/

...若当前点为MIN节点，则返回beta值３.判断intCTic_MFCDlg::isWin(intcurPos)完成功能据输入棋盘断当前棋盘的结果？PLAYER胜？平局？参数：board:待评估棋盘返回：-1表示：尚未完毕0表示：平局1表示：PLAYER胜2表示：COMPUTER胜五、实验图/

...六、实验结通过本次实验进一步对老师课堂