大学计算机毕业设计论文.doc

目录摘要.3Abstract.3第1章绪言.51.1研究动机.51.2主要研究内容.5第2章 黑白棋简介.52.1黑白棋的历史.52.2黑白棋游戏规则.62.3黑白棋战术分析.6第3章 黑白棋程序概况.63.1程序流程图.63.2主要模块简介.73.3程序设计思路.7第4章 游戏主界面.84.1背景设计.84.2游戏标题.84.3游戏主菜单.8第5章 动画过渡效果.95.1百叶窗效果.105.2随机线效果.115.3随机出现过度效果.11第6章 汉字的显示与移动.126.1汉字点阵字模存储模式.126.2汉字点阵输出方法.126.3汉字移动技术.12第7章 人机对战.137.1游戏初始化.137.1.1初始化棋盘.137.1.2初始化光标.147.1.3初始化分数.147.2用户操作.157.2.1键盘扫描码.157.2.2控制光标移动.157.2.3落子判断.167.2.4判断游戏是否结束.187.3电脑战术分析.197.3.1棋盘扫描.207.3.2判断行动力.207.3.3四角优先战术.217.3.4选择最佳位置落子.22第8章 总结与展望.228.1总结.228.2前景及展望.22参考文献.23致谢.24附录1部分运行结果.25附录2 光盘内容简介.26C语言设计游戏人工智能黑白棋摘要人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。“人工智能”一词最初是在1956 年Dartmouth学会上提出的。从那以后,研究者们发展了众多理论和原理,人工智能的概念也随之扩展。人工智能是一门极富挑战性的科学，包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。例如繁重的科学和工程计算本来是要人脑来承担的, 现在计算机不但能完成这种计算, 而且能够比人脑做得更快、更准确, 因而当代人已不再把这种计算看作是“需要人类智能才能完成的复杂任务”, 可见复杂工作的定义是随着时代的发展和技术的进步而变化的, 人工智能这门科学的具体目标也自然随着时代的变化而发展。它一方面不断获得新的进展, 一方面又转向更有意义、更加困难的目标。目前能够用来研究人工智能的主要物质手段以及能够实现人工智能技术的机器就是计算机, 人工智能的发展历史是和计算机科学与技术的发展史联系在一起的。除了计算机科学以外, 人工智能还涉及信息论、控制论、自动化、仿生学、生物学、心理学、数理逻辑、语言学、医学和哲学等多门学科。本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步。本文首先详细介绍了黑白棋的游戏规则，和一些基本的战术，然后将基本战术编写成代码存储在计算机中，使计算机在与人对弈过程中，可以选择一个较为合理的位置落子。本程序主要是采用最大最小搜索的战术，就在对抗中的开局和中局使用最小搜索，而在终局时采用最大搜索。对于一般的最大最小搜索，即使每一步只有很少的下法，搜索位置的数目也会随着搜索深度呈级数增长。在大多数的中局棋形中，每步平均有十种下法，假设电脑搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置，这样极大地限制了电脑的棋力：我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度的前提下将需要搜索的结点减小一些？幸运的是，可以证明，程序不需要考虑所有的位置而找到最佳点，于是人们采用了一个方法，叫"alpha-beta剪枝"，它大为减少了检测的数目，提高电脑搜索的速度。所有的强力黑白棋程序都用到了各种各样的这种算法。文章的最后，对全文进行了总结和分析，并展望了人工智能计算机下棋在计算机领域和其他一些领域的前景与应用。关键词：人工智能 行动力 搜索 估值 最小最大算法Abstractputer 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 posed of different areas, such as machine learning, puter vision, etc., in general, artificial intelligence research a major objective is to make some machines capable of human intelligence is often needed to plete the plex task . But different times, different people of this "plex" understanding is different. For example, the heavy science and engineering is dignitaries have to bear the brain, the puter will be able to acplish 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 plete the plex task" Visibility plex 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 puters, The history of the development of artificial intelligence and puter science is with the history of the development of technology linked. In addition to puter 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 puter simulation of human brain for the next reversi. puter chess is in the field of artificial intelligence research a hot topic for many years, With puter technology and artificial intelligence technology continues to develop, the level of puter chess has been great progress.This paper details the rules of the game reversi, and some basic tactics, Then basic tactical piled code stored in the puter, so the puter 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 puter 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 puter Jili : We can not put up with the puter 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 puter 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 puter 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 puter chess in the puter field and other areas with the prospect of application.Keywords：Artificial Intelligence Action Force Search Valuation Minimum largest Algorithm第 1 章绪言1.1研究动机随着计算机处理速度的飞速提高，人们很早就提出了疑问：计算机是否会超越人类？世界国际象棋棋王卡斯帕罗夫与美国IBM公司的RS6000（深蓝）计算机系统于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）：该模块用于初始化游戏的界面，其中包括初始化棋盘、初始化各种在后面用到的结构体、数组等变量。人机对战模块（pvs.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<300;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图41 游戏主界面第 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<N;i+)for(j=0;j<480;j+=N)line(0,j+i,639,j+i);/*画出水平线*/delay(100);/*延迟100毫秒*/4.2随机线效果随机线也分为水平随机线和垂直随机线。以水平随机线为例。屏幕的高度为480个像素，在每个像素上画一条水平线，但是画线的顺序的随机的，每两条线之间延迟200毫秒。这里涉及到一个产生不重复随机数的算法，具体代码如下：void randLine1(int color)/*水平随机线*/int aWW,bWW,i,t;setcolor(color);/*设置前景色*/for(i=0;i<WW;i+) /*将数组a初始化*/ai=i;for(i=0;i<WW;i+) /*产生不重复的随机数*/t=random(WW-i); /*随机产生数组a的下标，每次随机X围缩小1*/bi=at; /*将随机产生的下标所对应的元素赋值给数组b*/at=aWW-i-1; /*将数组a后面的元素赋值给本次随机出现的元素*/ /*避免下次重复出现相同的随机数*/for(i=0;i<WW;i+)line(bi,0,bi,479);delay(200);产生不重复随机数的方法是，先将预产生随机数的X围存储到一个一维数组中，例如上面代码中随机数的X围是0-639，共640个整数，那么就定义一个长度为640的一维数组a，数组a中元素的初始值就设置为与下标相等的数。然后调用随机函数，X围是0-639，产生随机数后（假如这里产生的随机数为100），并不直接使用该数，而是将这个数作为数组的下标，将第100个元素的值取出（当然第一次随机到100这个下标时，所对应的元素也是100），存放到另一个事先定义好的数组b中，然后将数组a的最后一个元素的取出，存放到第100个元素中。然后再次调用随机函数，但这次的随机X围变成0-638，这样即使第二次产生的随机数又是100，那么100这个下标所对应的元素已经发生了改变。这样每次循环产生随机数后，都将随机X围缩小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<matsize;j+)/*显示汉字点阵的一行*/for(i=0;i<m;i+)/*显示六个字节*/for(k=0;k<8;k+)/*显示一个字节*/if(matj*m+i&(0x80>>k)/*测试二进制位是否为可显示的点*/putpixel(x+i*8+k,y+j,color);/*输出像素点*/drawmat(huan64Z,64,100,100,7);/*调用函数输出汉字*/6.3汉字移动技术使文字移动的方法是多种多样的，本文使用的是目标移动，即将被移动的目标由屏幕的一个位置移动到另一个位置。如果直接一步到位移动，没有中间过程，会使人有生硬或突然感，动感不强，为了实现良好的动感，必须根据目标的大小及移动