本科毕业设计论文三子棋搜索树程序设计报告.docx
《本科毕业设计论文三子棋搜索树程序设计报告.docx》由会员分享，可在线阅读，更多相关《本科毕业设计论文三子棋搜索树程序设计报告.docx（70页珍藏版）》请在冰点文库上搜索。
本科毕业设计论文三子棋搜索树程序设计报告
计算机科学与技术学院
《C高级语言程序设计》课程设计报告
（2016/2017学年第1学期）
学生姓名：
肖磊
学生专业：
物联网工程
学生班级：
物联网工程152002
学生学号：
201520050228
指导教师：
张荣国
2016年 12 月 26 日
计算机科学与技术学院
课程设计任务书
课程设计名称
C高级语言程序设计课程设计
课程设计题目
三子棋搜索算法树的实现
学生姓名
肖磊
专业班级
物联网152002
学号
201520050228
课程设计任务内容
[问题描述]
针对三子棋，应用C语言程序设计的基本理论和方法，从对问题的分析研究开始，到编程调试结束的整个过程进行分析和设计，具体包括以下几点。
[基本要求]
（1）了解程序设计的方法和步骤，对三子棋进行分析研究。
（2）系统的工作可以进行：
人类走棋功能、电脑走棋、判断两方输赢、棋盘界面函数（选择先后手、选择人人对战、人机对战）、搜索树的实现等。
（3）画流程图：
将主函数和每个功能模块的函数的流程图分别画出来；
（4）编写程序代码,对每个模块实现的功能进行详细的说明,对程序中使用的变量予以说明,对程序中主要语句的功能予以说明；
（5）提交课程设计报告。
[测试要求]
（1）设计的程序能够方便地运行，达到设计的目的；
（2）用户界面友好，功能明确，操作方便。
指导教师：
张荣国
时间：
2016年12月1日
第1章设计过程总结与分析
1．1关于三子棋问题的描述…………………………....….…1
1．2关于三子棋问题的分析………………………….………1
1．3程序运行环境…………………………………..……..….1
第2章算法设计与流程图
2.1主控模块的算法设计与流程图...........................2
2.2图形界面模块算法设计与流程图.........................4
2.3人类走棋模块算法设计与流程图.........................5
2.4判断输赢模块算法设计与流程图.........................5
2.5电脑走棋模块算法设计与流程图.........................6
第3章程序设计编码与测试
3.1主控模块程序设计编码与测试...........................12
3.2图形界面模块程序设计编码与测试......................17
3.3人类走棋模块程序设计编码与测试......................19
3.4判断输赢模块程序设计编码与测试......................25
3.5电脑走棋模块程序设计编码与测试......................28
第4章设计过程总结与分析
4.1三子棋设计过程中的总结与分析.......................32
附录：
程序流程图及程序代码
5.1程序流程图..............................................33
5.2程序源码..........................................。
.....42
第1章设计过程总结与分析
1.1关于三子棋问题的描述
“三子棋”游戏（又叫“井字棋”），是一款十分经典的益智小游戏，想必很多玩家都有玩过。
“三子棋”的棋盘很简单，是一个3×3的格子，很像中国文字中的“井”字，所以得名“井字棋”。
“三子棋”游戏的规则与“五子棋”十分类似，“五子棋”的规则是一方首先五子连成一线就胜利；“三子棋”是一方首先三子连成一线就胜利。
游戏时一方是电脑，另一方是玩家。
所以，这类游戏在开始时有两种方式：
一种是玩家先走；另一种是电脑先走。
1.2关于三子棋问题的分析
这是一道人工智能的题目，关键是找出电脑的思维。
而电脑的思维必是一个算法。
本题用的蒙特卡洛算法。
进行一定次数的随机模拟的下棋，之后选择出最有利的一点为落子点。
正是因为电脑有思维，电脑能赢就赢，同时也要干扰玩家赢（力求和局）
1.3程序运行环境
程序是在vs2013的环境下运行的，并且需要配置ege文件。
配置ege文件：
1.把ege的include目录下的头文件拷贝到C:
\ProgramFiles（x86）\MicrosoftVisualStudio12.0\VC\include下/
2、把ege的lib\vc2013目录下的链接文件拷贝到C:
\ProgramFiles（x86）\MicrosoftVisualStudio12.0\VC\lib下
第2章算法设计与流程图
2.1主控模块算法设计与流程图
设计思路：
函数首先调用棋盘界面函数face（）产生一个棋盘，之后函数继续读取鼠标点击位置的坐标，读取后首先判断坐标在哪一个if—elseif语句内。
如果函数进入人人对战，则函数在界面上显示“人人对战开始”；如果函数进入到人机对战中，则在界面出显示出“人机对战开始”和两个选项“人先手”和“机器先手”，再一次进行鼠标点击的选择。
在选择完毕之后函数进入到对战当中，如果选择的是“人先手人机对战”，则会进入到一个while
（1）的无限循环当中
首先调用人类走棋play（）函数，之后调用判断胜负的winner（）函数，。
如果判断胜负winner（）函数返回先手胜利
（1），先手失败（0），平局（3），则跳出while循环。
如果判断胜负winner（）函数没有返回上述的数值，函数就会在调用电脑下棋函数。
之后在一次执行while循环，直到判断出胜负或者和棋为止。
图2.1主控模块流程图
2.2图形界面模块算法设计与流程图
设计思路：
函数分别调用八次划线函数line（），分别画出四条竖线和四条横线，交织出九宫格。
之后函数调用输出函数，在棋盘界面显示“人机对战”和“人人对战”。
图2.2图形界面模块流程图
2.3人类走棋模块算法设计与流程图
设计思路：
函数读取鼠标点击位置的坐标，读取后首先判断，：
坐标是否在棋盘内，不是继续读取下一个坐标是进入到下一项的判断。
坐标处是否有棋子，如果坐标处有棋子，返回到读取坐标处；如果没有，在相应的位置显示一个棋子。
图2.3人类走棋模块流程图
2.4判断输赢模块算法设计与流程图
设计思路：
函数列出了先手和后手胜利的八种情况。
首先，函数检查先手是否符合胜利的条件，之后函数在检查后手是否符合胜利的条件，最后函数判断是否符合平局条件
图2.4判断输赢模块流程图
2.5电脑走棋模块算法设计与流程图
设计思路：
函数首先设置蒙特卡洛相应的模拟次数，作为for循环的判断条件。
在for循环中函数调用复制当前局面assignment（）函数，之后调用创建节点create-node（）函数，最后调用保存函数。
在跳出for循环之后，函数给每一个结果的进行估值，胜利获得三分，失败获得三分，平局获得两分。
在保存函数的结构数组中挑选出一个估值最大的点，传递给play_chess（）函数中，在界面上显示一个棋子
图2.5电脑走棋模块流程图
子函数:
复制当前局面函数的算法设计与流程图
设计思路:
函数根据一个for的嵌套循环把现在的局面复制到另一个测试的二维数组当中
图2.6复制当前局面函数流程图
子函数:
创造节点函数的算法设计与流程图
设计思路:
函数接受一个节点和二维数组作为参数，之后随机的产生随机数作为函数的横纵坐标赋值（此时函数为while
（1）的无限循环，如果产生的坐标成功则跳出循环，不成功则进行再一次赋值）。
之后函数使用new创建一个节点，并未为该节点进行赋值（包括父节点，子节点，row、line等）和更新测试局面，只有调用判断输赢的winner（）函数，如果此时判断输赢函数返回胜利失败和平局的结果则函数结束退出。
如果判断输赢函数没有返回结果则进行函数的递归，知道出现结果为止。
图2.7创造节函数流程图
子函数:
保存函数的算法设计与流程图
设计思路:
函数接受winner（）函数的结果作为参数，然后设置两个for的嵌套循环搜索测试棋局局面，把测试棋局局面中为空的位置坐标分别保存到电脑走棋MC（）函数中动态分配的结构数组中。
之后使用一个for循环把判断输赢winner（）函数的结果保存到匹配的结构数组中。
图2.8保存函数流程图
子函数：
落子函数的算法设计与流程图
设计思路：
函数根据传入的坐标row和line从第一个if（elseif）语句进行匹配，如果匹配成功，就会进入到if语句中，并且更新棋局局面和在对应的位置显示棋子，最后跳出函数。
图2.9落子函数流程图
第3章程序设计编码与测试
3.1主控模块程序设计编码与测试
功能：
调用其他函数完成博弈运算。
测试：
人先手的人机对战中，先手第一次落子在row=1.line=1处，电脑落子第一次在row=0.line=0，先手第二次落子在row=0.line=2处，电脑落子第二次在row=2.line=0，先手第一次落子在row=0.line=1处，电脑落子第三次在row=1.line=0。
电脑胜利，
运行结果：
如图3.13.23.3
分析：
人先手落子在点row=1.line=1，电脑经过设定次数的模拟之后选择此时最有可能胜利的点row=0.line=0，人第二次落子在row=0.line=2，如果人再一次落在在row=2.line=0点处人就会获的胜利，所以电脑第二步落子在row=2.line=0，阻止人胜利，人第三次落子在row=0.line=1，电脑只需落子在row=1.line=0处，就可以取得胜利，所以在经过一定次数的模拟和估值时候电脑落子在点row=0.line=1处取得胜利。
图3.1主控模块第一步测试图
图3.2主控模块第二步测试图
图3.3主控模块第三步测试图
源代码:
intmain（）
{
initgraph（840,480）;
face（）;
srand（（unsigned）time（NULL））;
mouse_msgmsg={0};
for（;is_run（）;delay_fps（60））
{
while（mousemsg（））
{
msg=getmouse（）;
}
if（（int）msg.is_down（））//如果鼠标点下才会进入if语句
{
if（msg.x>=599&&msg.x<=712&&msg.y>=100&&msg.y<=127）//人人对战
{
outtextxy（600,250,"人人对战开始"）;
play（50,'O'）;
if（winner（array,size,'O','#'）==1||winner（array,size,'O','#'）==0||winner（array,size,'O','#'）==3）
{
main_judge（'O','#'）;
getch（）;
return0;
}
play（10,'#'）;
if（winner（array,size,'O','#'）==1||winner（array,size,'O','#'）==0||winner（array,size,'O','#'）==3）
{
main_judge（'O','#'）;
getch（）;
return0;
}
}
elseif（msg.x>=600&&msg.x<=713&&msg.y>=199&&msg.y<=227）//人机对战
{
outtextxy（600,250,"人机对战开始"）;
outtextxy（600,300,"选择人先手"）;
outtextxy（600,350,"选择电脑先手"）;
for（;is_run（）;delay_fps（60））
{
while（mousemsg（））
{
msg=getmouse（）;
}
if（（int）msg.is_down（））//如果鼠标点下才会进入if语句
{
if（msg.x>=599&&msg.x<=739&&msg.y>=299&&msg.y<=326）//选择人先手
{
outtextxy（600,400,"人机对战人先手开始"）;
while
（1）
{
nodetemp;
temp=play（50,'O'）;
if（winner（array,size,'O','#'）==1||winner（array,size,'O','#'）==0||winner（array,size,'O','#'）==3）
{
main_judge（'O','#'）;
getch（）;
return0;
}
MC（&temp）;
if（winner（array,size,'O','#'）==1||winner（array,size,'O','#'）==0||winner（array,size,'O','#'）==3）
{
main_judge（'O','#'）;
getch（）;
return0;
}
}
}
elseif（msg.x>=599&&msg.x<=763&&msg.y>=350&&msg.y<=377）//选择电脑先手
{
outtextxy（600,400,"人机对战电脑先手开始"）;
array[1][1]='#';
size--;
circle（320,240,10）;
while
（1）
{
nodetemp;
temp=play（50,'O'）;
if（winner（array,size,'O','#'）==1||winner（array,size,'O','#'）==0||winner（array,size,'O','#'）==3）
{
main_judge（'O','#'）;
getch（）;
return0;
}
MC（&temp）;
if（winner（array,size,'O','#'）==1||winner（array,size,'O','#'）==0||winner（array,size,'O','#'）==3）
{
main_judge（'O','#'）;
getch（）;
return0;
}
}
}
}
}
}
}
}
getch（）;
return0;
}
3.2图形界面模块程序设计编码与测试
功能：
函数可以显示一个界面，左边是九宫格，右边是两个选项:
人机对战、人人对战。
运行结果：
如图3.4
结果分析：
显示界面函数分别调用两组八次line（）函数，分成4—4两组，一组构成横线，一组构成竖线，从而形成九个格子。
在棋盘的最右面函数调用两次显示outtextxy（）函数，显示两个选项:
人人对战、人机对战。
图3.4图形界面模块测试图
程序源代码：
intface（）
{
setcolor（GREEN）;//设置画图颜色
line（125,45,515,45）;//行
line（125,175,515,175）;
line（125,305,515,305）;
line（125,435,515,435）;
line（255,45,255,435）;//竖
line（125,45,125,435）;
line（385,45,385,435）;
line（515,45,515,435）;
setfont（28,0,"宋体"）//
outtextxy（600,100,"人人对战"）;
outtextxy（600,200,"人机对战"）;
return0;
}
3.3人类走棋模块程序设计编码与测试
功能：
在对应的位置显示棋子
测试：
点击坐标为00的位置
运行结果：
如图3.5如图3.6
结果分析：
函数根据鼠标点击位置的坐标，判断是否符合落子的条件（在棋盘内且此处不存在棋子为空），如果不符合就会继续读取下一个鼠标点击的位置，直到符合为止。
图3.5人类走棋模块测试图
源代码：
nodeplay（intradious,charsymbol）{
//处理鼠标信息
mouse_msgmsg={0};
for（;is_run（）;delay_fps（60））
{
while（mousemsg（））
{
msg=getmouse（）;
}
if（msg.x>=125&&msg.x<=255&&msg.y>=45&&msg.y<=175）
{
if（array[0][0]=''）//判断是否可以落子
{
array[0][0]=symbol;
circle（190,110,radious）;
size--;
human.item='O';
human.line=0;
human.row=0;
human.child=NULL;
break;//跳出for循环，执行下一条语句
}
else
continue;//继续执行for循环
}
elseif（msg.x>=255&&msg.x<=385&&msg.y>=45&&msg.y<=175）//第一行
{
if（array[0][1]=''）
{
circle（320,110,radious）;
array[0][1]=symbol;
size--;
human.item='O';
human.row=0;
human.line=1;
human.child=NULL;
break;
}
else
continue;
}
elseif（msg.x>=385&&msg.x<=515&&msg.y>=45&&msg.y<=175）
{
if（array[0][2]=''）
{
circle（450,110,radious）;
array[0][2]=symbol;
size--;
human.item='O';
human.row=0;
human.line=2;
human.child=NULL;
break;
}
else
continue;
}
elseif（msg.x>=125&&msg.x<=255&&msg.y>=175&&msg.y<=305）
{
if（array[1][0]=''）
{
circle（190,240,radious）;
array[1][0]=symbol;
size--;
human.item='O';
human.row=1;
human.line=0;
human.child=NULL;
break;
}
else
continue;
}
elseif（msg.x>=255&&msg.x<=385&&msg.y>=175&&msg.y<=305）//第二行
{
if（array[1][1]=''）
{
circle（320,240,radious）;
array[1][1]=symbol;
size--;
human.item='O';
human.row=1;
human.line=1;
human.child=NULL;
break;
}
else
continue;
}
elseif（msg.x>=385&&msg.x<=515&&msg.y>=175&&msg.y<=305）
{
if（array[1][2]=''）
{
circle（450,240,radious）;
array[1][2]=symbol;
size--;
human.item='O';
human.row=1;
human.line=2;
human.child=NULL;
break;
}
else
continue;
}
elseif（
升级会员 