人工智能上机实习题.docx
《人工智能上机实习题.docx》由会员分享，可在线阅读，更多相关《人工智能上机实习题.docx（67页珍藏版）》请在冰点文库上搜索。
人工智能上机实习题
人工智能上机实习题
一．概述
1．实习名称
该实习是一个Windows环境下的可以进行人机对弈的五子棋程序，程序的名称是快乐五子棋。
2．运行环境和编程语言版本
运行环境：
MicrosoftWindows98或者MicrosoftWindowsNT。
编程语言：
MicrosoftVisualC++6.0企业版
3．程序文件目录清单及文件说明
整个五子棋程序所有文件放在Five目录下。
Five.h五子棋类的头文件
Five.cpp五子棋类的实现文件
以上两个文件是VisualC++自动生成的
Fivedlg.h五子棋程序主窗体类的头文件，所有的程序控制和大部份的数据结构都在这里定义和实现
Fivedlg.cpp五子棋程序主窗体类的实现文件，是整个程序的核心
Queue.h优先队列的头文件
Queue.cpp优先队列的实现文件
Node.h优先队列的节点类头文件
Node.cpp优先队列的节点类的实现文件
Settings.h五子棋设置类的头文件
Settings.cpp五子棋设置类的实现文件
设置类是一个对话框，主要负责对五子棋的人工智能部份的参数的控制。
StdAfx.cppMFC类必需的文件，由Microsoft提供
StdAfx.h同上
Five.dsp五子棋程序的工程文件，可以通过打开它来打开整个工程
Res子目录存放本程序的资源，如图标，位图等。
另外还有一些文件是VC自已生成的，与我们这个具体的程序是没有关系的，所以在里就不再特别说明了。
4．程序使用说明
本五子棋程序界面亲切友好，玩家可以很容易上手。
下面是一些基本的使用说明。
程序的主界面是一个大的对话框，它里面又分为三个部份。
左边是一排按钮，分别是“开始新游戏”，“设定”，“认输”，“确定这样走”，“我不走这步了”，“关于本程序”，“退出”。
单击“设定”后又会弹出一个对话框，里面可以对先后手，难度以及电脑的棋风进行设定。
“认输”按钮只有在游戏开始以后才可以用。
玩家每走一步，需要进行确定，即走完一步后点击“确定这样走”，若发现走错了，只需点击“我不走这步了”，即可重新下子，同样，这两个按钮也只有在游戏开始后才可以使用。
“关于”是作者的简介和程序的简介。
“退出”是退出游戏，在游戏进行时不可用。
窗体的中间部份是一个16＊16的棋盘。
玩家和电脑在这里面对弈。
窗体的右部有一幅对联：
“观棋不语真君子，起手无回大丈夫。
”对联的下面是几个标签，对当前的设定和棋局的状态进行必要的说明。
另外，对于每走一步棋，该程序都会自动记录走的步数，并会直接在棋子上显示出来，以方便玩家查找下过的棋。
在主窗体的右下角，有两个计时器，一个是玩家的思考的用时，另一个是电脑方下棋的用时。
二．程序的数据结构说明
本程序用到的数据结构如下，我们分别作出说明：
1．程序的设置类（SETTINGS）
该类对五子棋的一些参数作出设定，主要有先手方，难度，电脑棋风，和棋盘在位置参数。
下面是该类的数据的说明：
inttype;//电脑的棋风，1---进攻2—平稳3---防守
SETTINGS（CWnd*pParent=NULL）;//标准的构造函数
boolPcfirst;//先手变量true—电脑先走false---玩家先走
intAI;//难度，即算法的搜索深度
intSIZE;//棋盘格的大小
intXROW;//棋盘行数
intYCOL;//棋盘列数
intXSTART;//棋盘左上角的相对横坐标
intYSTART;//棋盘左上角的相对纵坐标
2．优先队列（CQueue）
优先队列用来暂时存放一个结点展开以后的子结点。
主要是在程序中实行贪心算法时用到的数据结构。
下面是该数据结构的具体的操作。
Public:
CQueue（）;//构造函数
~CQueue（）;//析构函数
voidDeQueue（）;//出队
voidEnQueue（Nodep,longScore）;//入队
NodeGetHead（）;//取队首节点位置
boolIsEmpty（）;//判队空
longGetHeadScore（）;//取队首节点数值
intQcount（）;//返回队中的节点数
voidDeltail（int）;//按指定要求删除队尾的元素
private:
structQnode//优先队列的节点类
{
Nodep;//棋盘节点类
longScore;//该手的分值
Qnode*Next;//下一节点的指针
}*Head;//指向队首的指针
intcount;//优先队列的节点的个数
};
3．棋子节点类（Node）
棋子节点类包括了一个棋子的全部信息，颜色，绝对位置，相对位置，顺序，下子方等等。
它是本程序的核心数据结构。
下面是该类的成员：
intorder;//下子顺序
intvisit;//下子方1---computer-1---player0---none
intcolor;//颜色
intx;//该棋子的实际横坐标
inty;//该棋子的实际纵坐标
intindexx;//棋子的相对横坐标
intindexy;//棋子的相对纵坐标
Node（Node&）;//拷贝构造函数
Node（）;//构造函数
structMaxIMin{//用于α-β剪枝的结构
longMax;
longMin;
};
三．程序的使用说明
该程序使用简便，但我们还是给出它的使用说明。
程序开始，就会出现一个大的对话框，我们前面已经介绍过了。
在棋局开始之前，可以对棋局的一些参数进行设定。
在难度设定一栏，有易，中，难三个档可以选择。
其实它的是分别对应程序中搜索算法不同的搜索深度的。
其中易是对应一层搜索，中对应两层搜索，难对应四层搜索。
在难度设定为难的时候，程序运行得比较慢，因为要展开的结点数比较多。
在棋风设定一栏，也有三项，分别是进攻型，平稳型和防守型。
三种风格的不同之处在于它们允许搜索算法进行搜索的范围不同。
其中进攻型是在每一颗棋子周围三格以内进行搜索，在第一层展开的时候对优先队列后面一半的元素进行删除，并且把搜索深度加一。
而平稳型是在每一颗棋子周围两格以内进行搜索。
防守型与平稳型相似，只是多了一个第一层剪枝的工作。
在设置好了之后，就可以开始游戏了。
单击开始新游戏就可以开始了。
玩家每下一步棋，就要进行一次确认，即点击”确定这样走”，如果发现在未确认之前走错了，可以单击”我不走这步了”，单击以后可以重新走这一步棋。
本程序没有回棋的功能，其实也是不需要的，只要看看棋盘右边的那两句话就知道了。
另外，在主窗体的下面还有一些状态可以看。
比如说现在下的是第几步了，当前的设置状态是什么，双方用时多少都可以看得到。
若在游戏进行时玩家想认输，可以单”认输”按钮，这样可以立刻认输，并且没有返回的机会！
四．程序主要算法的分析
本程序运用了α-β剪枝法对五子棋的当前状态进行搜索，找出一步比较优的棋作为下一步的着法。
下面我们就来具体说明整个算法的基本思想和实现。
α-β剪枝法是一种对搏弈树进行搜索的有效的算法。
它是对Min-Max算法的改进。
我们知道Min-Max算法的基本思想是从根结点开始展开，形成整棵搜索树之后，从最底层开始从下往上逐层计算各点的权值，最后确定根节点的权值，从而确定下一步的取向。
但是Min-Max算法有一个缺点，就是要先把整棵搜索树展开，再进行计算。
这样要计算的结点数就会很多，当层数增加的时候就会使程序难以执行。
但是我们发现，其实并不是所有的结点都需要计算权值的。
另外，先展开整棵搜索树再计算权值的做法效率显然太低了。
而α-β剪枝法就是针对Min-Max算法的这些缺点进行改进的。
它采取一种边展开，边计算，边剪枝的方法，使得要展开计算的节点大大减少，提高了程序运行的效率，在同等的搜索深度下程序的运行时间要大大短于不剪枝的程序。
下面我们对α-β剪枝法作一些具体的说明。
在算法中，我们采用有界深度优先策略进行搜索，这样当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值。
我们在搜索树上有Min和Max两种类型的结点，所以剪枝的类型也有两种，一种是在Max层进行的，称为α剪枝。
另一种是在Min层进行的，称为β剪枝。
α剪枝的过程是这样的，假设一个Max节点A它的一个孩子为B，这个B又有一个孩子为C，当C的权值确定以后，程序把C的权值与B现有的权值进行比较，又注意到B是Min层的结点，如果发现C的权值比B的权要值小，则把C的权值赋给B，然后程序把B的权值与A的权值进行比较，当发现B的权值小于A的权值的时候，则把B从C开始的孩子全部剪掉。
以上过程称为α剪枝。
为什么可以这样剪枝呢？
我们注意到，当发现B的权值小于A的权值的时候，因为B是Min层的结点，无论怎么样计算，B的权值都不会比当剪的权值大，所以再去计算B的孩子的权值是没有意义的。
如果剪枝发生在Min层，原理也是差不多，但这时称为β剪枝。
在我的程序里，通过一个MaxMin的数据结构来实现了剪枝，整个程序是一个不断递归的过程。
深度优先搜索不用递归是很难实现的。
下面是搜索算法的程序片断：
//用于Max-Min搜索的递归函数。
输入：
M决定对那种棋子进行估值，true为白子，//false为黑子；depth为深度控制；MaxMin为用于α-β剪枝的结构。
longCFiveDlg:
:
absearch（boolM,intdepth,MaxIMinMaxMin）
{
CQueueOpen;//优先队列，用于储存可下的位置和价值。
MaxIMinMM=MaxMin;//用于α-β剪枝的结构。
Nodep;//临时位置。
，Count为计数器。
longtemp;//temp为临时变量
longResult;//Result为返回的节点价值
intCount=0;//Count这里起指示的作用。
指示当前取出
//的元素是不是队头元素。
//在判断必杀棋型的时候，只需要判断优先队//列中的队头元即可
intOver;//指示棋局是否结束
if（depth==0）returnh（）;//最底层递归返回棋局状态的函数值。
//循环把可能下的位置和价值放入优先队列,
//这样做的目的是为了在搜索时能够先展开
for（inti=0;i<=15;i++）//价值较高的节点
{
p.indexx=i;
for（intj=0;j<=15;j++）
{
p.indexy=j;
if（CanPut（chess[i][j]））{
Put（p,M）;
Count++;
Over=IsOver（p）;//若结局这直接返回。
if（Over==1）
{
Remove（p）;
return1000000000;
}
elseif（Over==-1）
{
Remove（p）;
return-1000000000;
}
inttemp=NodeScore（p,M）;//取位置p的价值。
Open.EnQueue（p,temp）;//将位置p和价值放入优先//队列Open中。
Remove（p）;//清除刚才下的棋子。
}
}
}
if（M==false&&dlg_settings.type==1&&Top==3）
Open.Deltail（Count*2/5）;
if（dlg_settings.type==2&&Top==3）Open.Deltail（Count/5）;
Count=0;
while（!
Open.IsEmpty（））
{
p=Open.GetHead（）;//取队头节点的位置。
if（（Count==0）&&M）//若队头节点的位置的棋型必杀，则//向上返回。
{
if（Open.GetHeadScore（）>1000000）
returnOpen.GetHeadScore（）;
}elseif（（Count==0）&&!
M）
{
if（Open.GetHeadScore（）<-1000000）
returnOpen.GetHeadScore（）;
}
Open.DeQueue（）;//删队头节点。
Put（p,M）;
temp=absearch（!
M,depth-1,MM）;//向下一层搜索。
Remove（p）;//拿起位置p的棋子
if（Count==0）{
Result=temp;//第一次时赋值给Result。
Count=1;
}
//以下程序段根据M进行α-β剪枝，并给Result赋值，就是根//据我们上面说的原理进行的
if（M）{
if（temp>Result）Result=temp;
if（MaxMin.Min!
=Default）//极大层，进行α剪枝
if（Result>=MaxMin.Min）
returnResult;
if（MM.Max!
=Default）
{
if（Result>MM.Max）MM.Max=Result;
}else
MM.Max=Result;
}else{
if（tempif（MaxMin.Max!
=Default）//极小层，进行β剪枝
if（Result<=MaxMin.Max）
returnResult;
if（MM.Min!
=Default）
{
if（Result}elseMM.Min=Result;
}
}
returnResult;
}
在α-β剪枝法中，有一个用于估计每个节点权值的评分函数h，它是实现程序人工智能的关键，其实，不同的人工智能程序的搜索算法都是差不多的，但h函数的不同使它们能各实现各种各样的智能化的功能。
我们这里的h函数，也是根据人下五子棋的经验，总结出来的。
但是由于本人五子棋棋力很弱，所以h函数定义得不是很好，导致本程序的棋力一般。
下面是h函数的具体的定义：
我们把五子棋中几种最常见的棋型用一个数组来表示，数组中的每一个元素代表一种棋型。
这个数组的定义如下：
unsignedtype[15]={//用数组来存储五个格子内同色棋子的不同排列.
//二进制数排列
//在NodeType（）函数里判断
0x0001,//00001
0x0009,//01001
0x0005,//00101
0x0003,//00011
0x0015,//10101
0x0019,//11001
0x0013,//10011
0x000d,//01101
0x000b,//01011
0x0007,//00111
0x001b,//11011
0x0017,//10111
0x001d,//11101
0x000f,//01111
0x001f//11111
};
其中每一项都代表一种棋型。
我们在对某一种棋局状态评分的时候，对棋盘进行搜索，分别对每一格计算双方的棋型价值，并对棋盘上的棋型价值进行求和，所得的值为整个状态的价值。
h（）对当前的棋盘的状态进行评价，目的是判断刚下的一手棋是否值得，以确定搜索的方向。
longCFiveDlg:
:
h（）//估值函数。
输出：
棋盘价值。
{
longweight=0;//价值变量。
//循环搜索棋盘
for（inti=0;i<=15;i++）
{
for（intj=0;j<=15;j++）
{
//若该位置为空格时，加上电脑方的棋型价值，减去玩家方棋型价值。
if（chess[i][j].visit==0）{
weight+=NodeScore（chess[i][j],true）;
weight-=NodeScore（chess[i][j],false）;
}elseif（chess[i][j].visit==1）//若为电脑方，加上其价值
weight+=NodeScore（chess[i][j],true）;
elseweight-=NodeScore（chess[i][j],false）;//若为玩家方，减去其价值
}
}
returnweight;
}
//该函数是一个辅助函数，用于判断位置p处的棋子属于何种棋型（type[15]数组中的某一种）。
intCFiveDlg:
:
NodeType（Nodep,boolM,intx,inty）
//输入：
p为位置参数。
//M为何种棋子。
//x和y为方向控制参数，（x，y）为（1，1）时由左上向右下搜索；为（1，0）时由左向右搜索；为（0，1）时由上向下搜索；为（1，-1）时由右上向左下搜索。
//注意：
以下以（1，1）为例阐述各语句，其余雷同。
{
intValue,blank,count,sign1=0,sign2=0,type1=-1,type2=-1;
//Value为1时下白子,为-1时下黑子；blank为空格数控制；count为搜索的格子数；sign1和sign2都表示棋型两端是否有异色子，其值为0时表示两端空白，为15时表示一端有异色子，为30时表示两端都有异色子；type表示何种棋型。
unsignedresult1=0,result2=0;
//result1和result2都为用来和type[15]数组比较的中间变量。
Nodetemp_p;
//temp_p为临时位置的中间变量。
if（M）Value=1;
elseValue=-1;
//以下程序段找到左上的搜索始点。
blank=1;
count=0;
//当左上为本色子时继续向左上搜索，允许有一个空格。
while（（chess[p.indexx-count*x][p.indexy-count*y].visit==Value）||（（blank>0）&&（chess[p.indexx-count*x][p.indexy-count*y].visit==0）&&（chess[p.indexx-（count+1）*x][p.indexy-（count+1）*y].visit==Value）））
{
if（chess[p.indexx-count*x][p.indexy-count*y].visit==0）blank--;
count++;
if（p.indexx-count*x<0||p.indexy-count*y<0||p.indexy-count*y>15||p.indexx-count*x>15）break;
}
if（p.indexx-count*x<0||p.indexy-count*y<0||p.indexx-count*y>15||p.indexy-count*y>15||chess[p.indexx-count*x][p.indexy-count*y].visit==-Value）sign1+=15;//如果端点有异色子，sign1增加15。
temp_p.indexx=p.indexx-count*x;//设置左上端点。
temp_p.indexy=p.indexy-count*y;
//以下程序段由temp_p向右下搜索五格，把棋型所表示的二进制数放入result1中。
if（temp_p.indexy+y>=0&&temp_p.indexy+y<=15&&temp_p.indexx+x>=0&&temp_p.indexx+x<=15&&chess[temp_p.indexx+x][temp_p.indexy+y].visit==Value）
{
count=1;
while（count<=5）
{
if（temp_p.indexx+count*x<0||temp_p.indexx+count*x>15||temp_p.indexy+count*y<0||temp_p.indexy+count*y>15）break;
if（（chess[temp_p.indexx+count*x][temp_p.indexy+count*y].visit==-Value）||（chess[temp_p.indexx+count*x][temp_p.indexy+count*y].visit==5））
//如果五格之内有益色子或到了棋盘边缘，sign1增加15，并跳出。
{
sign1+=15;
break;
}
if（chess[temp_p.indexx+count*x][temp_p.indexy+count*y].visit==Value）result1+=（1<<（count-1））;//将表示棋型的二进制数列存入result1。
count++;
}
}
//以下程序段找到右下的搜索始点。
（同向上数第二个程序段相反方向）
blank=1;
count=1;
while（p.indexx+（count+1）*x>=0&&p.indexx+（count+1）*x<
升级会员 