三子棋搜索树程序设计报告大学论文.doc

计算机科学与技术学院

《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:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include下/
2、把ege的lib\vc2013目录下的链接文件拷贝到C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\lib下

第2章 算法设计与流程图
2.1主控模块算法设计与流程图
设计思路：函数首先调用棋盘界面函数face()产生一个棋盘，之后函数继续读取鼠标点击位置的坐标，读取后首先判断坐标在哪一个if—else if语句内。如果函数进入人人对战，则函数在界面上显示“人人对战开始”；如果函数进入到人机对战中，则在界面出显示出“人机对战开始”和两个选项“人先手”和“机器先手”，再一次进行鼠标点击的选择。
在选择完毕之后函数进入到对战当中，如果选择的是“人先手人机对战”，则会进入到一个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(else if)语句进行匹配，如果匹配成功，就会进入到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.1 3.2 3.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主控模块第三步测试图

源代码:int main()
{
initgraph(840, 480);
face();
srand((unsigned)time(NULL));
mouse_msg msg = { 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();
return 0;
}
play(10, '#');
if (winner(array, size, 'O', '#') == 1 || winner(array, size, 'O', '#') == 0 || winner(array, size, 'O', '#') == 3)
{
main_judge('O', '#');
getch();
return 0;
}
}
else if (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)
{
node temp;
temp = play(50, 'O');
if (winner(array, size, 'O', '#') == 1 || winner(array, size, 'O', '#') == 0 || winner(array, size, 'O', '#') == 3)
{
main_judge('O', '#');
getch();
return 0;
}
MC(&temp);
if (winner(array, size, 'O', '#') == 1 || winner(array, size, 'O', '#') == 0 || winner(array, size, 'O', '#') == 3)
{
main_judge('O', '#');
getch();
return 0;
}
}
}
else if (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)
{
node temp;
temp = play(50, 'O');
if (winner(array, size, 'O', '#') == 1 || winner(array, size, 'O', '#') == 0 || winner(array, size, 'O', '#') == 3)
{
main_judge('O', '#');
getch();
return 0;
}
MC(&temp);
if (winner(array, size, 'O', '#') == 1 || winner(array, size, 'O', '#') == 0 || winner(array, size, 'O', '#') == 3)
{
main_judge('O', '#');
getch();
return 0;
}
}
}
}
}
}
}
}
getch();
return 0;
}
3.2图形界面模块程序设计编码与测试
功能：函数可以显示一个界面，左边是九宫格，右边是两个选项:人机对战、人人对战。
运行结果：如图3.4
结果分析：显示界面函数分别调用两组八次line()函数，分成4—4两组，一组构成横线，一组构成竖线，从而形成九个格子。在棋盘的最右面函数调用两次显示outtextxy()函数，显示两个选项:人人对战、人机对战。

图3.4图形界面模块测试图
程序源代码：
int face()
{
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, "人机对战");
return 0;
}
3.3人类走棋模块程序设计编码与测试
功能：在对应的位置显示棋子
测试：点击坐标为0 0的位置
运行结果：如图3.5 如图3.6
结果分析：函数根据鼠标点击位置的坐标，判断是否符合落子的条件（在棋盘内且此处不存在棋子为空），如果不符合就会继续读取下一个鼠标点击的位置，直到符合为止。

图3.5人类走棋模块测试图
源代码：node play(int radious,char symbol) {
//处理鼠标信息
mouse_msg msg = { 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循环
}
else if (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;
}
else if (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;
}
else if (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;
}
else if (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;
}
else if (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;
}

else if (msg.x >= 125 && msg.x <= 255 && msg.y >= 305 && msg.y <= 435)
{
if array[2][0] = ' ')
{
circle(190, 370, radious);
array[2][0] = symbol;
size--;
human.item = 'O';
human.row = 2;
human.line = 0;
human.child = NULL;
break;
}
else
continue;
}
else if (msg.x >= 255 && msg.x <= 385 && msg.y >= 305 && msg.y <= 435)//第三行
{
if (array[2][0] = ' ')
{
circle(320, 370, radious);
array[2][1] = symbol;
size--;
human.item = 'O';
human.row = 2;
human.line = 1;
human.child = NULL;
break;
}
else
continue;
}
else if msg.x >= 385 && msg.x <= 515 && msg.y >= 305 && msg.y <= 435)
{
if (array[2][2] = ' ')
{
circle(450, 370, radious);
array[2][2] = symbol;
size--;
human.item = 'O';
human.row = 2;
human.line = 2;
human.child = NULL;
break;
}
else
continue;
}
else if (1)
{
continue;//当下棋的位置在不允许的范围内
}
}
}
return human;
}
3.4判断输赢模块程序设计编码与测试
功能：函数在检测棋子的排列，根据棋子的排列返回三种结果（先手胜利、先手失败、平局）
测试：1先手胜利 2和棋
运行结果：如图3.6 如图3.7
分析：图3.6对角线的三个先手棋子连成一条线符合先手胜利的条件，函数返回先手胜利。图3.7函数检查此时的棋子排列符合和棋的条件，函数返回和棋。
图3.6判断输赢模块先手胜利测试图

图3.7判断输赢模块和棋测试图
源代码：
int winner(char array[3][3],int count,char people_symbol,char computer_symbol)
{
if ((array[0][0] == array[0][1] && array[0][1] == array[0][2] && array[0][2] == people_symbol) ||
(array[1][0] == array[1][1] && array[1][1] == array[1][2] && array[1][2] == people_symbol) ||
(array[2][0] == array[2][1] && array[2][1] == array[2][2] && array[2][2] == people_symbol) ||
(array[0][0] == array[1][0] && array[1][0] == array[2][0] && array[2][0] == people_symbol) ||
(array[0][1] == array[1][1] && array[1][1] == array[2][1] && array[2][1] == people_symbol) ||
(array[0][2] == array[1][2] && array[1][2] == array[2][2] && array[2][2] == people_symbol) ||
(array[0][0] == array[1][1] && array[1][1] == array[2][2] && array[2][2] == people_symbol) ||
(array[0][2] == array[1][1] && array[1][1] == array[2][0] && array[2][0] == people_symbol))
return 1;
//玩家获胜
else if ((array[0][0] == array[0][1] && array[0][1] == array[0][2] && array[0][2] == computer_symbol) ||
(array[1][0] == array[1][1] && array[1][1] == array[1][2] && array[1][2] == computer_symbol) ||
(array[2][0] == array[2][1] && array[2][1] == array[2][2] && array[2][2] == computer_symbol) ||
(array[0][0] == array[1][0] && array[1][0] == array[2][0] && array[2][0] == computer_symbol) ||
(array[0][1] == array[1][1] && array[1][1] == array[2][1] && array[2][1] == computer_symbol) ||
(array[0][2] == array[1][2] && array[1][2] == array[2][2] && array[2][2] == computer_symbol) ||
(array[0][0] == array[1][1] && array[1][1] == array[2][2] && array[2][2] == computer_symbol) ||
(array[0][2] == array[1][1] && array[1][1] == array[2][0] && array[2][0] == computer_symbol))
return 0;
//电脑获胜
else if (0 == count)//和棋
return 3;
return 2;
}
3.5电脑走棋模块程序设计编码与测试
功能：在剩余的空格中选择一个对电脑最有利的位置落子。
测试:1当人落子在row=0，line=0时，2当人有两个棋子连在一起时
运行结果：如图3.8 3.9
分析：1在人先手的人机对战中人落子在row=0，line=0时，电脑通过一定次数模拟下棋之后，再经过估值选择出最有利的点，即:row=1，line=1。
2在人先手的人机对战中人已经有两个棋子连在一条线，如果三个棋子连在一起，人就会胜利，所以电脑通过一定次数模拟下棋之后，选择出目前最有利的点，即:row=2，line=0。

图3.9电脑走棋模块测试图

图3.10电脑走棋模块测试图

源代码：

int MC(node * root)
{
using namespace std;
int index;
store * p_store_result = new store[size];//声明一个
for (index = 0; index < size; index++)
{
(p_store_result + index)->line = -1;
(p_store_result + index)->row = -1;
(p_store_result + index)->count_lose = 0;//初始化为0
(p_store_result + index)->count_win = 0;
(p_store_result + index)->count_peace = 0;
}
for (index = 0; index < 22200; index++)
{
int result;//结果
node * root_child;//初代子节点
int count = size;
assignment(temp_array, array);//复制当前的局面
result =create_node(count, root, temp_array);//创建节点，root

root_child = root->child;
//保存数据
store_array(root_child, size, result, p_store_result);//保存数
}
//选择出胜率最大的位置落子
int max_win = -1000000;
index = 0;
int special_point = 0;
for (index = 0; index < size; index++)
{
int temp = 0;
temp = 3 * (p_store_result + index)->count_win - 3 * (p_store_result + index)->count_lose + 2*(p_store_result + index)->count_peace;//函数的估值
if (temp > max_win)
{
max_win = temp;
special_point = index;
}
}
int newrow = (p_store_result + special_point)->row;
int newline = (p_st