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

实验5：-剪枝实现一字棋

一、实验目的

学习极大极小搜索及-剪枝算法实现一字棋。

二、实验原理

1.游戏规则

"一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字

棋"的棋盘很简单，是一个3×3的格子，很像中国文字中的"井"字，所以得名"井字棋

"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线

就胜利；"井字棋"是一方首先三子连成一线就胜利。

2.极小极大分析法

设有九个空格，由MAX，MI二人对弈，轮到谁走棋谁就往空格上放一只自己的棋

子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就

取得了胜利。

用圆圈表示MAX，用叉号代表MI○

╳

╳

╳

○○○比如左图中就是MAX取胜的棋局。

估价函数定义如下设棋局为P，估价函数为

e(P)。

(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完

全的行、列或对角线的总数)-e(那些仍为MI空着的完全的行、列或对角线的总数)

(2)若P是MAX必胜的棋局，则e(P)＝+（实际上赋了60）。

(3)若P是B必胜的棋局，则e(P)＝-（实际上赋了-20）。

比如P如下图示,则e(P)=5-4=1

需要说明的是，+赋60，-赋-20的原因是机器若赢了，

则不论玩家下一步是否会赢，都会走这步必赢棋。

○

╳3.-剪枝算法

上述的极小极大分析法，实际是先生成一棵博弈树，然后

再计算其倒推值，至使极小极大分析法效率较低。于是在极小

极大分析法的基础上提出了-剪枝技术。

-剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并

且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪

去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。

具体的剪枝方法如下：

(1)对于一个与节点MI，若能估计出其倒推值的上确界，并且这个值不大

于MI的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展

该MI节点的其余子节点了(因为这些节点的估值对MI父节点的倒推值已无任何影响

了)。这一过程称为剪枝。

(2)对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小

于MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展

该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影

响了)。这一过程称为剪枝。

从算法中看到：

(1)MAX节点(包括起始节点)的值永不减少；

(2)MI节点(包括起始节点)的值永不增加。

在搜索期间，和值的计算如下：

(1)一个MAX节点的值等于其后继节点当前最大的最终倒推值。

(2)一个MI节点的值等于其后继节点当前最小的最终倒推值。

4．输赢判断算法设计

因为每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断

是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有

一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。

三、实验代码

#include

usingnamespacestd;

intnum=0;<

return0;

}

if(val>m){<

return0;

}

gotoL5;

}

else{<

return0;

}

for(intx=0;x<3;x++){

for(inty=0;y<3;y++){

if(now[x][y]==0){

now[x][y]=1;

cut(val,dep,1);

if(Checkwin()==1){

cout<<"电脑将棋子放在:"<

PrintQP();

cout<<"电脑获胜!游戏结束."<

return0;

}

if(val>m){

m=val;

x_pos=x;y_pos=y;

}

val=-10000;

now[x][y]=0;

}

}

}

now[x_pos][y_pos]=1;

val=-10000;

m=-10000;

dep=1;

cout<<"电脑将棋子放在:"<

PrintQP();

cout<

num++;

value();

if(q==0){

cout<<"平局!"<

return0;

}

gotoL4;

}

return0;

}

intmain(){

computer();

system("pause");

return0;

}

4.主要函数

1估值函数

估价函数：intCTic_MFCDlg::evaluate(intboard[])

完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：

若是MAX的必胜局，则e=+IFIITY，这里为+60

若是MI的必胜局，则e=-IFIITY，这里为-20，这样赋值的原因是机

器若赢了，则不考虑其它因素。

其它情况，棋盘上能使CUMPUTER成三子一线的数目为e1

棋盘上能使PLAYER成三子一线的数目为e2，

e1-e2作为最终权值

参数：board:待评估棋盘

返回：评估结果

剪枝算法

AlphaBeta剪枝主函数：

intCTic_MFCDlg::AlphaBeta(intBoard[],intDepth,intturn,intAlpha,int

Beta,int*result)

完成功能：根据输入棋盘，搜索深度，及其他参数，给出一个相应的最优解，存入result

中。

参数：board:待评估棋盘

Depth:搜索深度

turn:当前是机器走(MAX结点)还是玩家走(MI结点)

Alpha:alpha值，第一次调用默认-100

Beta:beta值，第一次调用默认+100

result:输出结果

返

回：

若当

前点

为

MAX

节

点，

则返

回

alph

a

值；

若

当前

点为

MI

节

点，

则返

回beta值

３.判断胜负

intCTic_MFCDlg::isWin(intcurPos)

完成功能：根据输入棋盘，判断当前棋盘的结果，COMPUTER胜？PLAYER胜？平局？

参数：board:待评估棋盘

返回：-1表示：尚未结束

0表示：平局

1表示：PLAYER胜

2表示：COMPUTER胜

五、实验截图

六、实验总结

通过本次实验进一步对老师课堂上所讲的-剪枝有了更加深刻的了解，对它的一

般实现有了初步的认识。

搜索深度并非越深越好，局限于估值函数是根据能够成三子一线的数目决定的，所以

搜索到最后一层，如果有人胜，则出现?，如果没人胜，则三子一线数目为0，所以

毫无意义。。这也是为什么大多数情况下都是平局的原因。