大学计算机毕业论文

目录

摘要......................................................................3

Abstract..................................................................3

第1章 绪言...............................................................5

1.1研究动机...........................................................5

1.2主要研究内容.......................................................5

第2章 黑白棋简介.........................................................5

2.1黑白棋的历史.......................................................5

2.2黑白棋游戏规则.....................................................6

2.3黑白棋战术分析.....................................................6

第3章 黑白棋程序概况.....................................................6

3.1程序流程图.........................................................6

3.2主要模块简介.......................................................7

3.3程序设计思路.......................................................7

第4章 游戏主界面.........................................................8

4.1背景设计...........................................................8

4.2游戏标题..........................................................8

4.3游戏主菜单........................................................8

第5章 动画过渡效果......................................................9

5.1百叶窗效果.......................................................10

5.2随机线效果........................................................11

5.3随机出现过度效果..................................................11

第6章 汉字的显示与移动..................................................12

6.1汉字点阵字模存储模式..............................................12

6.2汉字点阵输出方法..................................................12

6.3汉字移动技术......................................................12

第7章 人机对战..........................................................13

7.1游戏初始化........................................................13

7.1.1初始化棋盘...................................................13

7.1.2初始化光标...................................................14

7.1.3初始化分数...................................................14

7.2用户操作..........................................................15

7.2.1键盘扫描码...................................................15

7.2.2控制光标移动.................................................15

7.2.3落子判断.....................................................16

7.2.4判断游戏是否结束.............................................18

7.3电脑战术分析......................................................19

7.3.1棋盘扫描.....................................................20

7.3.2判断行动力...................................................20

7.3.3四角优先战术.................................................21

7.3.4选择最佳位置落子.............................................22

第8章 总结与展望.........................................................22

8.1总结..............................................................22

8.2前景及展望........................................................22

参考文献.................................................................23

致谢.....................................................................24

附录1 部分运行结果.......................................................25

附录2 光盘内容简介.......................................................26

C 语言设计游戏

——人工智能黑白棋

摘要

人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。“人工智能”一词最初是在1956 年Dartmouth 学会上提出的。从那以后, 研究者们发展了众多理论和原理, 人工智能的概念也随之扩展。

人工智能是一门极富挑战性的科学，包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。例如繁重的科学和工程计算本来是要人脑来承担的, 现在计算机不但能完成这种计算, 而且能够比人脑做得更快、更准确, 因而当代人已不再把这种计算看作是“需要人类智能才能完成的复杂任务”, 可见复杂工作的定义是随着时代的发展和技术的进步而变化的, 人工智能这门科学的具体目标也自然随着时代的变化而发展。它一方面不断获得新的进展, 一方面又转向更有意义、更加困难的目标。目前能够用来研究人工智能的主要物质手段以及能够实现人工智能技术的机器就是计算机, 人工智能的发展历史是和计算机科学与技术的发展史联系在一起的。除了计算机科学以外, 人工智能还涉及信息论、控制论、自动化、仿生学、生物学、心理学、数理逻辑、语言学、医学和哲学等多门学科。

本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步。

本文首先详细介绍了黑白棋的游戏规则，和一些基本的战术，然后将基本战术编写成代码存储在计算机中，使计算机在与人对弈过程中，可以选择一个较为合理的位置落子。

本程序主要是采用最大最小搜索的战术，就在对抗中的开局和中局使用最小搜索，而在终局时采用最大搜索。对于一般的最大最小搜索，即使每一步只有很少的下法，搜索位置的数目也会随着搜索深度呈级数增长。在大多数的中局棋形中，每步平均有十种下法，假设电脑搜索九步(程序术语称为搜索深度为九) ，就要搜索十亿个位置，这样极大地限制了电脑的棋力：我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度的前提下将需要搜索的结点减小一些？幸运的是，可以证明，程序不需要考虑所有的位置而找到最佳点，于是人们采用了一个方法，叫"alpha-beta 剪枝" ，它大为减少了检测的数目，提高电脑搜索的速度。所有的强力黑白棋程序都用到了各种各样的这种算法。

文章的最后，对全文进行了总结和分析，并展望了人工智能计算机下棋在计算机领域和其他一些领域的前景与应用。

关键词：人工智能 行动力 搜索 估值 最小最大算法

Abstract

Computer artificial intelligence is a branch of science that attempts to understand the real smart, and

produce a new energy to human intelligence similar to the way intelligent response machinery, research in the field, including robotics, speech recognition, image recognition, natural language processing and expert systems. "Artificial Intelligence" is the first word in 1956, Dartmouth made by the Institute. Since then, researchers have developed many theories and principles, the concept of artificial intelligence have also expanded.

Artificial intelligence is a very challenging science, including a very wide range of scientific, which is composed of different areas, such as machine learning, computer vision, etc., in general, artificial intelligence research a major objective is to make some machines capable of human intelligence is often needed to complete the complex task . But different times, different people of this "complex" understanding is different. For example, the heavy science and engineering is dignitaries have to bear the brain, the computer will be able to accomplish this, Moreover than the human brain can do faster and more accurate. so contemporary people are no longer such terms as "human intelligence needed to complete the complex task" Visibility complex work is defined as the development of the times and technological advances and changes, the science of artificial intelligence that the specific objectives naturally as times change and development. While achieve new progress, it has to be more meaningful, more difficult goal. At present AI can be used to study the material means and artificial intelligence technology to achieve the machinery, including computers, The history of the development of artificial intelligence and computer science is with the history of the development of technology linked. In addition to computer science, artificial intelligence but also information theory, control theory, automation, bionics, biology, psychology, mathematical logic, linguistics, medicine and philosophy and other subjects.

This research is the use of computer simulation of human brain for the next reversi. Computer chess is in the field of artificial intelligence research a hot topic for many years, With computer technology and artificial intelligence technology continues to develop, the level of computer chess has been great progress.

This paper details the rules of the game reversi, and some basic tactics, Then basic tactical compiled code stored in the computer, so the computer in the course of one game, choose a more reasonable position of Lao Zi.

The procedure is based on the maximum and minimum search tactics, in the beginning of the confrontation and the use of the smallest Search Bureau, and the final use of the largest search. For the average maximum and minimum search, even if only a small step in the dismount, Search location will be the number of search depth with the series level was increased. In most of the middle-game, every step, an average of 10 dismount, Assuming further nine computer search (search procedure, technically known as the depth of 9), it is necessary to search 1 billion location (10 to nine), This greatly limits the computer Jili : We can not put up with the computer players will move next year. Search nodes to reduce the simplest way is to reduce the search depth, but greatly affected the players in the computer Qili. Whether there are ways to reduce the search in depth under the premise of the need to search nodes decreased? Fortunately, it proved that the procedure need not consider all the best position to find, so people used a method called "alpha-beta pruning", which greatly reduced the number of detection, improve computer search of speed. All powerful reversi procedures used in a wide range of this algorithm. (The same for other types of board games, such as chess and checkers). In order to search nine step, a good search process only 100,000 to 1 million location, and not useless billions of times before.

The final article, the full text of the summary and analysis Prospects of artificial intelligence and

computer chess in the computer field and other areas with the prospect of application.

Keywords ：Artificial Intelligence Action Force Search V aluation Minimum largest Algorithm 第 1 章 绪言

1.1研究动机

随着计算机处理速度的飞速提高，人们很早就提出了疑问：计算机是否会超越人类？世界国际象棋棋王卡斯帕罗夫与美国IBM 公司的RS ／6000（深蓝）计算机系统于1997年5月11日进行了六局“人机大战”，结果“深蓝”以3.5比2.5的总比分获胜。比赛结束了给人们留下了深刻的思考；下棋要获胜要求选手要有很强的思维能力、记忆能力、丰富的下棋经验，还得及时做出反应，迅速进行有效的处理，否则一着出错满皆输，这显然是个“智能”问题。尽管开发“深蓝”计算机的IBM 专家也认为它离智能计算机还相差甚远，但它以高速的并行的计算能力（2r108步／秒棋的计算速度）。实现了人类智力的计算机上的部分模拟。那么计算机已经超过了人类吗？看完本文，相信你会对计算机棋手的智能有所了解。

1.2主要研究内容

本文将对计算机棋手下黑白棋做一个全面综述，介绍计算机对黑白棋战术分析的全过程，包括对图形和动画的处理、彩色菜单的制作、汉字点阵输出、过度效果制作、对棋盘搜索的算法、对棋局做出正确的估计、并生成最佳走法，并将介绍其中各个流程的研究状况及实用技术。本文的重点放在计算机对当前棋局的分析，并做出最佳的选择。 介绍搜索算法，棋类游戏不可能一步就决出胜负，象棋中不可能第一步就将对方将死；而对某个棋局的判断也不可能完全精确，在黑白棋中，初局时棋子多并不一定最终取得胜利，因为对手可能在后面的博弈过程中将局面扭转。想想人类下棋时，一般会假设我走这步，那么对手会怎样回应，如果对手回应了某一步，我再走哪一步，如果对手回应了另外某一步，我又该怎么走；然后再假设我走另外的某一步，如此反复下去。这个过程叫做搜索。

第 2 章 黑白棋简介

2.1黑白棋的历史

黑白棋是19世纪末英国人发明的。直到上个世纪70年代一个日本人将其发展，借用莎士比亚名剧奥赛罗（othello) 为这个游戏重新命名，也就是现在大家玩的黑白棋。为何借用莎士比亚名剧呢？是因为奥赛罗是莎士比亚一个名剧的男主角。他是一个黑

人，妻子是白人，因受小人挑拨，怀疑妻子不忠一直情海翻波，最终亲手把妻子杀死。后来真相大白，奥赛罗懊悔不已，自杀而死。黑白棋就是借用这个黑人白人斗争的故事而命名。

2.2黑白棋游戏规则

黑白棋(Reversi、Othello) ，也叫苹果棋，翻转棋，是一个经典的策略性游戏。它使用8x8的棋盘, 由两人执黑子和白子轮流下棋，最后子多方为胜方。轮到一方下棋时，必须把棋下在与对方棋子相邻的空位上，要求所下的棋子和原有的已方棋子夹住对方的至少一个棋子(横竖斜夹均可) ，然后把被夹住的子变成己方的颜色(也叫吃子) 。下棋过程中，任何棋子既不会从棋盘上拿走，也不会从一个格子移到另一个格子。

黑白棋规则简单，但是变化复杂，是典型的易学难精(a minute to learn, a lifetime to master),它看似简单, 实际奥妙无穷。

2.3黑白棋战术分析

从黑白棋的游戏规则上看，应该尽量使自己的棋子多于对手的，很容易就得到了一个战术，就是每步棋都落在能吃掉对手棋子最多的位置，但是经过几局后，你就会发现这并不是一个好的方法。

那么黑白棋的正确战术应该是怎样的呢？一般说来，下棋过程中，你必须尽量削减对手的行动力，同时增加自己的行动力，这种策略我们称之为行动力原则(或行动力战术) 。当一方达到或接近这个目标时，我们就称该棋手控制了棋局。另外，这个战术的目的是迫使对方下坏棋，如果对方虽然可选位置很少，但每一步却总有好棋，那战术目的就没有达成。记住，你必须让对方完全无好棋可下。

黑白棋规则规定只能在对方棋子相邻的空位下棋，这就可以推出另一个原则。对方棋子边上的空位越多，你下棋的选择也就越多，换句话说，你的行动力就越强；相反，如果你棋子边上的空位越少，对方可下的位置也就越少。我们把相邻位置上有空位的子称为外子，反之称为内子，连在一起的外子称为前线或墙。下棋时要尽量减少自己的外子。

第三章 黑白棋程序概况

3.1程序流程图

黑白棋程序流程图

3.2主要模块简介

主菜单模块（mainFace.h ）：该模块用于显示游戏开始前的主界面，其中包括初始化背景、汉字点阵显示游戏标题“欢乐五子棋”、彩色菜单的移动和执行。

过度效果模块（effect.h ）：该模块存储了几种过度效果，用于在界面之间切换时使用。

汉字字库模块（word.h ）：该模块存储了本程序用到的所有汉字的点阵字模。

初始化游戏界面模块（playFace.h ）：该模块用于初始化游戏的界面，其中包括初始化棋盘、初始化各种在后面用到的结构体、数组等变量。

人机对战模块（pvsCom.h ）：该模块是黑白棋实现人工智能的主要部分，其中包括计算机对棋盘的搜索、对当前局面的估值、并做出正确的反应，也是本程序的核心模块。

3.3程序设计思路

从程序表面看，这是一个二维平面图，所以数据用二维数组来表示，数组两个下标可以表示棋盘上的位置，数组元素的值代表棋格上的状态，共有三种情况，分别是0代表空格，1代表白棋，2代表黑棋。这样程序的主要工作是接收棋手按键操作，棋手用Up 、Down 、Left 、Right 控制光标移动，回车键表示落子。如果无棋可走则显示停步信息。一旦接收到回车键或空格键，说明棋手落子，先判断是否是有效位置，也就是说已

经有棋子的位置不能重叠落子，然后再判断该位置能否吃掉对方的棋子（根据黑白棋的游戏规则，只能将棋子落子能吃掉对方棋子的位置上），如果条件满足则在该位置落子，落子时执行这样几个步骤，先调用画棋子函数，将棋盘的相应位置上画上棋子，再调用吃棋子函数，将对手的棋子变成自己颜色的棋子，然后根据吃掉对手棋子的个数，给自己加上相应的分数和给对手减去相应的分数，再将数组中的相应元素赋值，标志该位置已经落子，最后将落子的权限交给对手。

当轮到计算机落子时，计算机先对棋盘进行扫面，找出所有能落子的位置，在从找出的位置中选择一个合理的进行落子，在选择时本程序采用的是最大最小算法，在棋局的开局和中局采用最小战术，而在终局的时候采用最大战术，同时采用的战术还有四角优先，削弱行动力战术，这些将在第7章中详细介绍。

如果想退出游戏，可以按Esc 键。

第 4 章 游戏主界面

4.1背景设计

为了增加程序的视觉效果，在屏幕上随机位置画出300个不同颜色的点，实现主界面背景模拟星空的效果。主要技术为画点函数与随机函数的配合使用，代码如下：

void showStar(void)/*星空效果*/

{

int i;

for(i=0;i

{

putpixel(random(640),random(480),random(15));

}

}

4.2游戏标题

在屏幕中上方以64*64的点阵字模显示了“欢乐五子棋”五个字，先用灰色显示这五个汉字，作为底色，然后将坐标向左上方偏移两个像素，重新输出，其中“黑”字用黑色，“白”字用白色，其余字用黄色显示，以实现阴影字的效果。关于汉字点阵的输出将在第六章中详细介绍。

4.3游戏主菜单

本程序的主界面采用的是彩色移动菜单，菜单共有4项分别为：人机对战、人人对战、游戏说明、退出游戏。

实现菜单移动的技术与4.2中的标题相似，先将4个菜单以灰色为底色的阴影显示在屏幕上，然后利用改变文字的前景色，来实现菜单视觉上的移动。再使用了一个变量

sele 来记录程序内部的当前菜单，当sele 的值为1，表示当前菜单为人机对战、2为人人对战、3为游戏说明、4为退出游戏。

当程序执行时，菜单的默认当前选项为人机对战（即sele 的初值为1），显示效果为人机对战的前景色用粉色，其余选项前景色用深灰色。当接收到键盘扫描码（关于键盘扫描码的接收将在第七章介绍）UP 键或DOWN 键时，相应改变sele 的值，同时将原当前菜单的前景色用深灰色覆盖，再将当前菜单的前景色用粉色表示。这样不断的按UP 或DOWN 时，就会实现菜单不断移动的效果。

当按下回车键或是空格键时，表示要执行当前菜单，则将sele 的值作为参数传给执行菜单的函数即可。

进入游戏后的主界面的效果如图

4-1

图4–1 游戏主界面

第 5 章 动画过渡效果

为了增加游戏换面切换的视觉效果，为本程序设计了以下几个用户画面切换的过渡效果。为了下文描述方便，先了解一下屏幕的设计情况，本程序是在C 语言的图形模式下编写的，在程序开始时，已经将屏幕设置为分辨率为640*480像素，颜色为16色。下面程序将用到的宏定义：

#define N 40 /*百叶窗的每个叶片的宽度*/

#define WW 640 /*屏幕的宽度*/

#define HH 480 /*屏幕的高度*/

#define wait delay(60000);delay(60000) /*延迟一段时间*/

4.1百叶窗效果

百叶窗效果分为水平百叶窗和垂直百叶窗。以水平百叶窗为例。

在高度能被40整除的位置上画水平线，然后延迟100毫秒，再在高度能除以40余1的位置上画水平线，再延迟100毫秒。不断循环直到屏幕全部被覆盖为止。代码如下：

void effectWindow1(int color)/*水平百叶窗*/

{

int i,j;

setcolor(color);/*设置前景色*/

for(i=0;i

{

for(j=0;j

{

line(0,j+i,639,j+i);/*画出水平线*/

delay(100);/*延迟100毫秒*/

}

}

}

4.2随机线效果

随机线也分为水平随机线和垂直随机线。以水平随机线为例。

屏幕的高度为480个像素，在每个像素上画一条水平线，但是画线的顺序的随机的，每两条线之间延迟200毫秒。这里涉及到一个产生不重复随机数的算法，具体代码如下：

void randLine1(int color) /*水平随机线*/

{

int a[WW],b[WW],i,t;

setcolor(color); /*设置前景色*/

for(i=0;i

a[i]=i;

for(i=0;i

{

t=random(WW-i); /*随机产生数组a 的下标，每次随机范围缩小1*/

b[i]=a[t]; /*将随机产生的下标所对应的元素赋值给数组b*/

a[t]=a[WW-i-1]; /*将数组a 后面的元素赋值给本次随机出现的元素*/ /*避免下次重复出现相同的随机数*/

}

for(i=0;i

{

line(b[i],0,b[i],479);

delay(200);

}

}

产生不重复随机数的方法是，先将预产生随机数的范围存储到一个一维数组中，例如上面代码中随机数的范围是0-639，共640个整数，那么就定义一个长度为640的一维数组a ，数组a 中元素的初始值就设置为与下标相等的数。然后调用随机函数，范围是0-639，产生随机数后（假如这里产生的随机数为100），并不直接使用该数，而是将这个数作为数组的下标，将第100个元素的值取出（当然第一次随机到100这个下标时，所对应的元素也是100），存放到另一个事先定义好的数组b 中，然后将数组a 的最后一个元素的取出，存放到第100个元素中。然后再次调用随机函数，但这次的随机范围变成0-638，这样即使第二次产生的随机数又是100，那么100这个下标所对应的元素已经发生了改变。这样每次循环产生随机数后，都将随机范围缩小1，就可以实现产生不重复的随机数了。

4.3随机出现的过渡效果

实际上，每次换面切换的时候，调用的过渡效果也是随机的，并且过渡效果所使用的颜色也是随机产生的，以避免视觉上的疲劳。代码如下：

void effect(void) /*随机出现不同的过渡效果*/

{

switch(random(4)) /*switch语句的参数为0到3之间的随机数*/

{

case 0:effectWindow1(random(15)+1); /*调用水平百叶窗，颜色随机*/ wait; /*延迟一段时间*/

effectWindow1(0); /*再次调用水平百叶窗，颜色黑色*/

break;

case 1:effectWindow2(random(15)+1);

wait;

effectWindow2(0);

break;

case 2:randLine1(random(15)+1);

wait;

randLine1(0);

break;

case 3:randLine2(random(15)+1);

wait;

randLine2(0);

break;

}

}

第 6 章 汉字的显示与移动

6.1汉字点阵字模存储模式

在汉字操作系统中的汉字是以点阵形式存储的，以16*16点阵为例，每个汉字由16*16=256个点组成，占用16*2=32个字节单元。字节的每一位表示一个点的属性（1表示亮点，0表示暗点）。连续的两个字节组成该汉字点阵。

6.2汉字点阵输出方法

在C 语言的图形模式下，可以对点阵进行扫描，然后配合画点函数，将汉字输出在屏幕上。

首先利用汉字点阵字模工具，计算欲输出汉字的字模。例如想输出“欢”字，字体为宋体，点阵大小为16*16，使用点阵字模工具计算其字模为：

char huan16S[]={

/* 以下是 '欢' 的 16点阵宋体 字模，32 byte */

0x00,0x80,0x00,0x80,0xFC,0x80,0x05,0xFE,

0x85,0x04,0x4A,0x48,0x28,0x40,0x10,0x40,

0x18,0x40,0x18,0x60,0x24,0xA0,0x24,0x90,

0x41,0x18,0x86,0x0E,0x38,0x04,0x00,0x00,

};

再调用汉字点阵输出函数将其显示在屏幕的指定位置上，汉字点阵和调用语句如下： void drawmat(char *mat,int matsize,int x,int y,int color)/*汉字点阵*/ /**mat是字模名，matsize 是字模大小，x,y 是汉字显示的坐标，color 是颜色*/ {

int i,j,k,m;

m=(matsize-1)/8+1;

for(j=0;j

for(i=0;i

for(k=0;k

if(mat[j*m+i]&(0x80>>k))/*测试二进制位是否为可显示的点*/

putpixel(x+i*8+k,y+j,color); /*输出像素点*/

}

drawmat(huan64Z,64,100,100,7);/*调用函数输出汉字*/

6.3汉字移动技术

使文字移动的方法是多种多样的，本文使用的是目标移动，即将被移动的目标由屏幕的一个位置移动到另一个位置。如果直接一步到位移动，没有中间过程，会使人有生硬或突然感，动感不强，为了实现良好的动感，必须根据目标的大小及移动距离的长短

分成苦干步来实现，每动一步先用底色覆盖原来的目标，再将移动目标复现在政一位置，这样依次到目的地，由于人眼具有视觉暂留的生理现象，人的肉眼见此移动过程具有真实感。很多资料中又将这种动画设计方法叫做中间化。用此法还可以进行平移、变形、旋转等动画设计。

第 7 章 人机对战

7.1游戏初始化

在介绍各种模块初始化前，先了解一下必要的变量。

struct HB

{

int a[8][8];/* 0表示无棋子、1表示黑子、2表示白子 */

int read;/* 8表示该黑子下棋、 15表示该白子下棋*/

int x,y;/* 表示当前光标的位置 */

int s1,s2;/* s1表示白棋分数，s2表示黑棋分数 */

}hb;

#define SIZE 8/*定义棋盘大小*/

程序将用二维数组a 来记录棋盘发生的所有变化。

7.1.1初始化棋盘

这里的初始化棋盘包括两部分内容：一部分是在屏幕上打印出棋盘，使用户可以根据棋盘的格子落子；另一部分是指初始化记录棋盘变化的二维数组。那么先来看一下如何在屏幕上显示一个8*8的棋盘，代码如下：

void drawQP(void)/*画棋盘函数*/

{

int i,j;

for(i=0;i

{

for(j=0;j

{

putpixel(60+j,60+i,3);/*棋盘距离边框60个像素*/

putpixel(420-j,420-i,3);

putpixel(60+i,60+j,3);

putpixel(420-i,420-j,3);

delay(100);/*延迟100毫秒，使打印棋盘的时候具有动画效果*/

}

}

}

下面对二维数组进行初始化，由于黑白棋的游戏规则是在开局前每人就有两颗棋子在棋盘的中央，那么初始化的工作除了将二维数组清零外，还需要将中间的四个元素分

别赋值1和2，并调用打印棋子的函数，将棋盘中间的位置打印上四个棋子，代码如下：

for(i=0;i

for(j=0;j

hb.a[i][j]=0;

hb.a[3][3] = 2; /* 初始化开始的四个棋子 */

hb.a[4][4] = 2;

hb.a[4][3] = 1;

hb.a[3][4] = 1;

drawQZ(getX(3),getY(3),15);

drawQZ(getX(4),getY(4),15);

drawQZ(getX(4),getY(3),8);

drawQZ(getX(3),getY(4),8);

其中getX(int)和getY(int)这两个函数的作用是计算出数组下标在屏幕上所对应的位置。drawQZ(int,int,int)函数的作用是在屏幕上打印棋子，前两个参数为打印棋子的坐标，第三个参数为打印棋子的颜色。

7.1.2初始化光标

当棋盘初始化工作完成后，就需要为用户初始化一个光标，以便用户可以选择自己想要的位置落子，打印光标的代码如下：

void dispMouse(int x,int y,int color)/*显示光标函数*/

{

setcolor(color);/*设置前景色*/

line(x-21,y-21,x-12,y-21);/*画线段函数，四个参数分别为线段的两个端点*/ line(x-21,y-21,x-21,y-12);

line(x-21,y+20,x-21,y+12);

line(x-21,y+20,x-12,y+20);

line(x+20,y-21,x+20,y-12);

line(x+20,y-21,x+12,y-21);

line(x+20,y+20,x+12,y+20);

line(x+20,y+20,x+20,y+12);

}

该函数共有三个参数，其中x 和y 表示准备打印的光标的位置，而color 为光标的颜色。本程序将开局光标定位在与数组a[2][2]相对应的位置上，代码如下：

hb.x = 2;

hb.y = 2;

dispMouse(getX(hb.x),getY(hb.y),15);

7.1.3初始化分数

初始化工作的最后一步便是为用户和计算机初始化分数。黑白棋的积分规则很简单，棋盘上自己棋子的个数便是自己的分数。由于开局前每人已经有两个棋子，所以这里初始化分数应为2，代码如下：

hb.s1=2;

hb.s2=2;/* 初始化分数 */

分数有了就要在屏幕上显示出来，下面是打印分数的函数，代码如下：

void printScore(void) /* 显示分数 */

{

char str1[5],str2[5];

sprintf(str1,"%d",hb.s1);/*将整型转换成字符串，以便打印分数*/

sprintf(str2,"%d",hb.s2);

settextstyle(0,0,2);

setcolor(6);

setfillstyle(SOLID_FILL,7);

bar(525,200,570,250);

bar(525,240,570,310);

outtextxy(530,208,str1);/*文本输出函数*/

outtextxy(530,248,str2);

}

在游戏的过程中，每落子一次便调用打印分数的函数一次，这样用户可以随时了解自己得分情况，以便选择合理的战术进行游戏。

7.2用户操作

7.2.1键盘扫描码

在计算机中，当按下键盘上的任意一个键子后，将返回一个16位的二进制数，它包括两种不同的值。当按下“普通键”（例如：A 、d 、&、4等）时，它的低8位数存放该字符的ASCII 码。对于“特殊键”（例如：方向键、Ctrl 、Alt 等），低8位为0，但高8位存放的该键子的扫描码。

既然可以用扫描码来表示一些特殊键，那么如何获得键盘的扫描码呢？可以调用C 语言函数库中的一个函数bioskey(0)。该函数的作用就是从键盘接收扫描码。

7.2.2控制光标移动

通过接收键盘扫描码，程序可以得知用户按了那些键子，在通过对这些按键扫描码的分析，如果是方向键的扫描码，程序就会认为是用户移动了光标，。代码如下：

#define UP 0x4800/*定义四个方向键的扫描码*/

#define DOWN 0x5000

#define LEFT 0x4b00

#define RIGHT 0x4d00

if(key==UP||key==DOWN||key==RIGHT||key==LEFT)

{

dispMouse(getX(hb.x),getY(hb.y),0);/*用黑色覆盖掉当前的光标*/

if(key == UP && hb.y > 0)/*根据不同的方向，改变相应的坐标*/

hb.y--;

else if(key == DOWN && hb.y

hb.y++;

else if(key == LEFT && hb.x > 0)

hb.x--;

else if(key == RIGHT && hb.x

hb.x++;

dispMouse(getX(hb.x),getY(hb.y),15);/*打印改变位置后的光标*/

}

该函数首先判断用户按的键子是否为四个方向键中的任意一个，在用背景色覆盖掉当前的光标，然后在具体判断接收到的扫描码是属于那个方向键的，

7.2.3判断落子

当程序检测到接收的键盘扫描码为空格或回车时，则程序就认为用户执行了落子的操作，但根据黑白棋的游戏规则，并非所有空的格子都可以落子。只有在能吃掉对方棋子的位置上才可以落子。这样就需要程序具有判断某个位置是否能够落子的功能。

要判断能否吃掉对方的棋子，就要利用记录棋盘变化的二维数组。当光标移动到某个位置上时（假如光标的坐标为[3][3]），用户按了回车或空格，首先判断a[3][3]元素的值，如果该值为0，则表示该位置未落子，做进一步的判断，如果值不为0，则表示该位置已经落子（值为1表示黑子，2表示白子），这时程序不做任何反应，让用户继续移动光标。

现在要讨论的是值为0时所做的进一步判断。请看游戏开局时的情况，如图：7-1

图7-1 游戏开局

图7-1为游戏开局时的状态，用户持黑棋，计算机持白棋，双方都未落子, 黑棋先走，此时用户可以有4种选择（白色圆圈标出），但除了上图所标出4个可落子的位置外，如果用户在其他位置按下回车或空格的话，程序是不错任何反应的。那么程序如何做到这点的呢。假如用户在上图显示光标的位置落子，程序会以a[2][2]元素为中心，分别向八个不同的方向（上、下、左、右、左上、右上、左下、右下）判断，以上和右下为例，先判断上方与a[2][2]相邻的a[1][2]元素，由于a[1][2]位置未落子，所以值为0，表示该方向不能吃掉对方棋子，返回值为0。再来看右下方的判断，先判断a[3][3]元素，该位置有白子，值为2，满足条件，继续向右下方判断a[4][4]的值，仍然为2，继续判断a[5][5]，值为0，同样也不能吃掉对方的棋子，所以也返回0值。以此类推，当判断完八个方向后，返回值都为0，则表示该位置无法吃掉对方棋子，程序则认为用户在该位置按下的空格或回车键无效。此时程序不做任何处理，等待用户移动光标后落子在做判断。

如果用户将光标移动到图7-1中“2”的位置上，再按回车时，程序仍然重新扫描八个方向，此时程序会发现在做右方判断时，由于能吃掉对手一个棋子，所以返回值为1。表示该位置为有效的落子位置，判断落子的代码如下：

int judge1(int x,int y,int color,int op)/* 判断方向左斜上 */

{

int i=1;

if(hb.a[x-1][y-1]==0 || x==0 || y==0 || hb.a[x-1][y-1]==color)

/*去掉几种明显错误，当左上方相邻的位置是空或者是自己的棋子时，则该方向 无效，或则当前位置已经是最上边或最左边时，也表示该方向无效。满足上边 任何一个条件，都无需在继续判断，直接返回0值*/

return 0;

while(hb.a[x-i][y-i]!=0&&hb.a[x-i][y-i]!=color&&x-i>=0&&y-i>=0)

{

if(op==1)

{

drawQZ(getX(x-i),getY(y-i),hb.read);

hb.a[x-i][y-i] = color;

}

i++;

}

if(x-i>=0&&y-i>=0)

return (hb.a[x-i][y-i]==color)?i-1:0;

else

return 0;

}

像上面这样的函数共有8个，分别判断8个不同的方向。由于篇幅关系，这里只给出了一个判断左上方的函数，其它方向的判断与此雷同（其余函数名为judge2„judge8）。给出的函数功能是做左上方的判断，共四个参数，其中x 和y 为要判断落子点的坐标，color 为要判断棋子的颜色，而op 表示要执行的操作，0表示仅判断该位置是否能够落子，1则表示吃掉对手的棋子，及对数组a 中的相应元素重新赋值，表示该位置已经是自己的棋子，并用调用画棋子函数将吃掉对手棋子改变成自己颜色的棋子。 这8个函数是最基本的扫描棋盘操作，下面将要介绍的行动力判断，预测对手行动等都将用到这8个函数。

为了每次判断落子的操作能够变得简单，这里又编写了一个函数judgeEnter()，该函数的功能就是调用上面的8个函数，然后将8个函数的返回值累加起来作为该函数的返回值，这样当需要判断能否落子时，只需调用该函数即可，如果返回值为0，则表示该位置无效，不能落子。否则将返回能吃掉对手棋子的个数，代码如下：

int judgeEnter(int x,int y,int color)/* 判断x ，y 位置能吃掉对方棋子个数，返回0则表示不能落子，color 表示棋子颜色 */

{

int n=0;/*变量n 记录吃掉对手棋子的个数*/

if(hb.a[x][y]) return 0; /*如果该位置有棋子，则直接返回0*/

n += judge1(x,y,color,0); /*分别调用8个函数，并累加函数返回值*/

n += judge2(x,y,color,0);

n += judge3(x,y,color,0);

n += judge4(x,y,color,0);

n += judge5(x,y,color,0);

n += judge6(x,y,color,0);

n += judge7(x,y,color,0);

n += judge8(x,y,color,0);

return n;

}

有了上面这个函数，很容易就可以实现对落子的判断了，请看下面的代码：

if((key==ENTER||key==SPACE)&&hb.a[hb.x][hb.y]==0)

/*如果用户按了回车或空格，并且该位置为空*/

{

i = hb.x;j=hb.y;

if(ch = judgeEnter(hb.x,hb.y,1)) /*调用判断落子函数*/

{

drawLast(hb.x,hb.y,1); /*调用吃掉对手棋子的函数*/

hb.read = 15; /*将落子的权限交给计算机*/

hb.a[i][j] = 1; /*将该位置所对应的数组元素赋值为1*/

hb.s1+=ch+1; /*为自己加上相应的分数*/

hb.s2-=ch; /*给对手减去相应的分数*/

}

}

7.2.4判断游戏是否结束

下面介绍如何判断游戏结束，我们先来看一下黑白棋游戏的结束规则：当双方都没有行动力的时候，则为游戏结束。那么要判断游戏是否已经结束，就需要用到一个检测行动力的方法。那么如何检测自己的行动力呢？这里仍然是利用上面介绍过的8个判断落子的函数，代码如下：

int moveTimes(int color)/* 检测行动力,color 代表棋子颜色 */

{

int i,j;

int n=0; /*n为统计共有多少个位置可以走*/

for(i=0;i

{

for(j=0;j

{

if (hb.a[i][j]==0&(judge1(i,j,color,0)||

judge2(i,j,color,0)||judge3(i,j,color,0)||

judge4(i,j,color,0)||judge5(i,j,color,0)||

judge6(i,j,color,0)||judge7(i,j,color,0)||

judge8(i,j,color,0)))

n++;/*如果该位置能落子，则n++*/

}

}

return n;

}

上面这段代码的功能为检测行动力，如果返回值为0，则表示自己已经没有位置可走了，只能将落子的权限交给对手，然后对手再调用该函数检测行动力，如果返回值也为0，则表示双方已经都没有行动力了，则游戏结束。当游戏结束后，程序根据双方得分情况，判断是哪一方获胜或者是和棋，然后给出相应的提示信息，代码如下：

int judgeGameover(void)

/* 如果黑棋胜出返回1，白棋胜出返回2，胜负未分返回0, 平手返回3 */

{

if(moveTimes(1)==0&&moveTimes(2)==0)

/* 如果双方都没有行动力了，则游戏结束 */

if(hb.s1>hb.s2)

return 1;

else if(hb.s1

return 2;

else

return 3;

return 0;

}

由于每落子一次都有可能使游戏的结束，所以在每次落子后都会调用上面这个函数，来检测游戏是否已经结束。

7.3电脑战术分析

在这一节中将介绍计算机是如何对棋盘进行分析，然后选择一个合理的位置进行下棋的。

7.3.1棋盘扫描

想要计算机能够与人对弈黑白棋，对棋盘的扫描是最基本的操作。前面已经介绍了与棋盘一一对应的是一个二维数组a ，那么要想对棋盘进行扫描，实际上就是对这个二维数组进行扫描，这样对棋盘的扫描工作就比较简单了，实际上只要使用一个两层循环便可实现对二维数组的扫描。这个循环在7.2.4节中已经出现过来，这里就不再累述。

7.3.2判断行动力

在2.3节黑白棋战术分析中已经提到，黑白棋的正确战术应该是尽量削弱对手的行动力，让对手全无好棋可下，同时增加自己的行动力。那么如何能让计算机懂得这个道理呢？这就要求计算机具有“思考”的能力。首先计算机调用检测行动力的函数moveTimes()，检测自己的行动力，也就是将当前棋盘所有能落子的位置找出来，然后在对这些位置逐步进行分析。分析的过程就是先假设计算机在某个位置上落子，然后马上再次调用检测行动力函数，不过这次是检测对手的行动力。意思就是如果计算机在这里落子，看看对手的行动力如何，如果对手的行动力太大，对手有很多位置可以选择，那么就不应该在这里落子。如此对所有能落子的位置进行检测，找出一个能让对手行动力变得最小的位置落子，代码如下：

min = 100;/*先假设对手的行动力为一个不能达到的最大值*/

for(i=0;i

{

for(j=0;j

{

if(judgeEnter(i,j,2))/* 判断该位置是否能够落子 */

{

hb.a[i][j] = 2;/* 假设计算机在该位置落子 */

if(min>(max=moveTimes(1)))

/*检测对手的行动力，并与上次假设的结果进行判断*/

{

x = i; /*记录能令对手行动力变得最小的落子位置*/

y = j;

min = max;

}

hb.a[i][j] = 0;/* 取消假设 */

}

}

}

if(min!=100)/*判断min 的值是否发生了变化*/

{

ch = judgeEnter(x,y,2); /*计算x ，y 位置能吃掉对手棋子的个数*/

drawLast(x,y,2); /*将对手的棋子吃掉*/

hb.a[x][y] = 2; /*对落子点与数组对应的元素赋值*/

hb.read=8; /*将落子权限交给用户*/

hb.s1-=ch; /*给用户减去相应的分数*/

hb.s2+=ch+1; /*为自己加上相应的分数*/

}

7.3.3四角优先战术

黑白棋有几个很重要的点，那就是棋盘上的四个角，因为四角上的棋子是绝对不会被吃掉的。在游戏过程中绝不能轻易的让对手进角。不让对手进角的最简单的办法就是不在与四角相邻的位置落子。这里将四角的坐标和与四角相邻的坐标分别放到两个数组中：

int aa[4][2]={{0,0},{0,7},{7,0},{7,7}};/* 四角坐标 */

int bb[12][2]={{0,1},{1,0},{1,1},{0,6},{6,0},{1,6},

{1,7},{7,1},{6,1},{6,6},{6,7},{7,6}};/*存储与四角相邻坐标*/

既然四角为不会被吃掉的稳定角，对棋局的胜负起着很重要的作用，所以在不让对手进角的同时自己却要努力进角。有了这个战术，计算机在每次扫描棋盘的前首先对四角进行判断，如果四角能够落子，则优先在四角落子，此为四角优先战术，代码如下：

ch = 0;/* 先假设四角都不能落子 */

for(i=0;i

{

x = aa[i][0];

y = aa[i][1];

if(ch = judgeEnter(x,y,2)) /* 判断四角能否落子，如果能罗则退出循环 */ break;

}

if(ch)/* 如果四个角能落子 */

{

drawLast(x,y,2);/*吃掉对手棋子*/

hb.a[x][y] = 2;

hb.read=8;

hb.s1-=ch;

hb.s2+=ch+1;

}

上面这段代码功能是努力让计算机进角，那么如果四角都不能进，则需对棋盘进行扫描，扫描时首先取消对与四角相邻位置的判断，但并非盲目的取消，如果某个角已经被计算机所占据，那么与这个角相邻的位置就不会被取消，代码如下：

for(i=0;i

{

for(j=0;j

{

if(i==0&&j==1&&hb.a[0][0]==0)continue;

/*尽量不在四个角的相邻位置下棋 */

else if(i==1&&j==0&&hb.a[0][0]==0)continue;

else if(i==1&&j==1&&hb.a[0][0]==0)continue;

else if(i==0&&j==6&&hb.a[0][7]==0)continue;

else if(i==6&&j==0&&hb.a[0][7]==0)continue;

else if(i==1&&j==6&&hb.a[0][7]==0)continue;

else if(i==7&&j==1&&hb.a[7][0]==0)continue;

else if(i==1&&j==7&&hb.a[7][0]==0)continue;

else if(i==6&&j==1&&hb.a[7][0]==0)continue;

else if(i==7&&j==6&&hb.a[7][7]==0)continue;

else if(i==6&&j==7&&hb.a[7][7]==0)continue;

else if(i==6&&j==6&&hb.a[7][7]==0)continue;

}

}

当扫描到与四角相邻的位置时，并且该角并未落子，则结束本次循环判断下个位置的坐标。

7.3.4选择最佳位置落子

使用了一些战术，使计算机能够了解当前棋局的情况，最终的目的让计算机能够选择一个合理的位置落子。在本程序里在棋局的不同时期，所采用的选择方法也是不同的，在程序开局时，尽量少吃对手的棋子，而在中期时则以削弱对手行动力为准，后期采用最大吃法，以能吃掉对手最多棋子为准。在游戏的整个过程又加入了四角优先战术，能进角则先进角。

第 8 章 总结与展望

8.1总结

计算机下棋是近年来人工智能领域的一个研究热点，许多新的技术层出不穷，世界级的棋类大师被计算机打败的例子屡见不鲜，随着人工智能在计算机中的广泛应用，人们对计算机的棋力提出了更高的要求。本文对搜索棋盘、判断行动力、估值、选择位置落子进行了介绍和讨论，并提出了在对弈过程中采用四角优先的战术，使计算机具有更高的棋力。本篇论文及黑白棋程序源代码已经在铁岭市数学与计算机学会的网站上发布，受到了大家的认可和好评(关于网站请看附录２) 。

学校并未开设过与人工智能相关的课程，但由于作者对此非常感兴趣，在论文选题时毅然选择了这个挑战非常大的关于人工智能的题目，由于作者自学能力有限，现在的黑白棋程序还处于初级阶段，但我会坚持不懈的努力，将黑白棋程序不断完善。

8.2前景及展望

人工智能下棋技术经过十余年的发展，取得了很多非常优秀的研究成果。但无论是什么样的算法，计算机运算的速度都是一个不可回避的问题，深蓝虽然战胜了世界国际象棋棋王卡斯帕罗夫，为了提高深蓝的下棋速度，所耗费的资源也是非常大的。那么提高算法的精确度，避免无谓的搜索是计算机下棋技术下一个需要解决的问题。

就像绪论中提到的那样，人工智能技术在不断的发展、不断前进，那么是否会有一天计算机的智慧超越人类？那时人类会处于怎样的地位？会像电影里演的那样电脑控制了地球，而人类成为奴隶吗？这一切都不得而知，答案就由未来几十年的计算机工程师来揭开。

参考文献

1. 中国黑白棋联盟 . http://www.othello.cn/index.htm

2. 黑白棋世界 . http://blacwet.diy.myrice.com/

3.[美]罗伯茨(Roberts,E.S.) . The Art and Science of C . 机械工业出版社 . 2005年3月

4.[美]Harvey M.Deitel/Paul J.Deitel . C How to Program . 清华大学出版社 . 2006年01月

5.[美]Charles N. Fischer/Richard J. LeBlanc,Jr . Crafting a Compiler with C . 2005年7月

6. 谭浩强 . C程序设计 . 清华大学出版社 . 1999年12月

7. 郭翠英 . C语言课程设计案例精编 . 中国水利水电出版 . 2004年3月

8. 曾春平，朱小谷，晏海华 . C语言程序设计教程 . 北京希望电子出版社 . 2005年3月

致 谢

两年的本科求学生涯使作者完成了学士论文课题的研究工作和本文的撰写工作，在这段期间得到了很多人的关怀和帮助，没有他们的关怀和帮助很难想象能顺利完成学业。

首先要感谢的是我的指导老师蔡莉副教授，两年来的学习中，蔡老师给了我很多帮助，我所取得的每一点进步都包含了蔡老师的心血，这一切学生当永志不忘。每当遇到挫折，是导师对事业的执着追求和敬业精神深深鼓舞着我。蔡老师严谨求实、谦逊和蔼、平易近人、处处为学生着想，令学生敬佩。老师深厚的学术功底、敏锐的洞察力、严谨的治学作风和精益求精的工作精神，给学生留下了很深刻的印象，并将永远激励和鞭策学生在未来的工作和科研中发奋努力，以不负导师的教诲和培养。在此期间，蔡老师对我的生活给予了很大的关心和帮助，借此表示衷心的感谢。在即将完成学业的时刻，我谨向我的导师蔡莉副教授表示衷心的感谢和崇高的敬意。

感谢所有曾经关心和帮助过我的人们。

由于我的水平有限，论文难免出现差错和遗漏，敬请老师批评指正。

附录 部分运行结果

附录 图1 与计算机对弈中

附录1 图2 计算机获得胜利

附录2 光盘内容简介

在随论文附属的光盘中有如下内容：论文的Word 版、黑白棋程序源代码、黑白棋程序可执行文件。

此外还有我在完成本论文的研究和撰写的时间里，同时为铁岭市数学与计算机学会制作的一套完成的ASP 动态网站。其中包括站内新闻、新书推荐、下载专区、站内图片、学术文章、教师频道、家长频道、学生频道、名师博客、留言板、论坛等模块。

能够完成这次网站的制作，主要感谢的两个人是计算机学院的蒋海风主任和我的导师蔡莉老师。是这两位老师给我提供的这次机会，使我在很短的时间里，掌握了很多ASP 动态网页技术，例如：制作一个学会论坛，为学会的每位教师制作博客，制作动态的下拉菜单等等。两位老师多年从事教育事业，对教育事业呕心沥血和一丝不苟的敬业精神令学生景仰。两位老师对学生的关怀的帮助，学生将永志不忘。

现在学会网站已经投入运行，并且得到了很好反响。我的毕业设计撰写完成后，已经上传到了学会网站上，可以从网站上下载到黑白棋程序的源代码。

学会的网址：http://www.tlcbxx.com/tl

再次感谢两位老师对我的栽培！

同时可以在以下网站下载到我的毕业设计： http://www.tlcbxx.com http://liaobei.com/xueke http://liaobei.com/benke