五子棋游戏的单机版及网络版的实现 毕业论文.doc

本 科 生 毕 业 论 文题 目：五子棋游戏的单机版及网络版的实现院 系：信息科学与技术学院 计算机科学系 专 业： 网络工程 学生姓名： xxx 学 号： xxx 指导教师： xxx 摘 要 随着IT技术的发展，很多日常生活中的游戏都被搬到了计算机里供大众娱乐，尤其是博弈类的棋类游戏，如中国象棋，围棋，五子棋等，近年来人们对人工智能技术的研究成果更使得计算机在这些博弈游戏中能战胜很多玩家。本文结合五子棋这个游戏的特点，将阐述单机版五子棋的算法设计，突出人工智能在博弈方面的应用，旨在试验人工智能里的一些搜索算法，最终确定人工智能在未来各学科里的重要应用性；最后还涉及网络版五子棋的设计实现，同时介绍一般网络游戏的架构。第一章简要介绍五子棋相关的状况。第二章概述了人工智能与五子棋相关的各种算法。第三章详细描述本设计所使用的人工智能算法。第四章讲述一般网络游戏的架构以及本设计中网络版五子棋的实现细则。第五章总结本次设计过程中的各种收获。关键词：五子棋； 人工智能； 博弈； 网络游戏AbstractWith the development of IT technology, a lot Games in daily life have been moved to the computer for public entertainment, especially the game of chess-type games, such as Chinese chess, the game of Go , gobang , etc., in recent years , artificial intelligence research makes the results that computer can overcome a lot of players in these Games. In this paper, with the characteristics of Gobang ,I will describe algorithm design on stand-alone version of Gobang ,to highlight the application of artificial intelligence in the game , and test some search algorithms of artificial intelligence , and ultimately determine the important application of artificial intelligence in the various disciplines ; Finally the paper also involves the design of implementation Gobang online version , at the same time introduces the general architecture of online Games. Chapter I briefly introduce the relevant situation of Gobang. Chapter II provides an overview of Artificial Intelligence and Gobang related algorithms. Chapter III detailed description of the design of algorithms used in artificial intelligence. Chapter IV on the general network architecture of the Games as well as the online version of the design in the implementation details.Chapter V summarized the harvest of the designing.Keywords: Gobang；Artificial Intelligence；Game；Online Game- iv -目 录第一章前言11.1五子棋的棋盘11.2五子棋的基本规则2第二章 人工智能的应用52.1人工智能的发展历史52.2人工智能研究的特点72.3人工智能的应用72.4博弈算法极大极小搜索算法9第三章 五子棋单机部分详细设计12第四章 五子棋联机部分详细设计194.1 联机网络游戏概述194.2 联机五子棋的设计20第五章 结论24参考文献29致谢30第一章 前言五子棋是我国古代的、传统的黑白棋种之一，大约在南北朝时期随围棋一起先后传入朝鲜、日本等地。五子棋在日本叫“连珠棋”，英文称之为“Gobang” 或者FIR(Five in a row的缩写) ， 亦有“连五子”，“五子连”，“串珠”.，“五目”，“五目碰”等多种称谓1。通过一系列的规则变化使连珠五子棋这一简单的游戏复杂化、规范化，而最终成为今天的职业连珠五子棋，同时也成为一种国际比赛棋。 1988年8 月8日，国际连珠联盟( RI F )由日 本、 俄罗斯、瑞典、亚美尼亚等九个成员国在瑞典宣告成立。五子棋在国内外发展速度相当快，预计在几年后，五子棋能在很多国家形成热门运动。 我国也不例外， 在很多热衷于五子棋事业的棋手的共同努力下，有望在不久的将来成为五子棋运动的中心。 随着我国经济社会的快速发展，人们生活水平不断提高，人们的生活观念发生改变，高质量的生活、现代化的生活方式成为人们追求的目标，休闲、 娱乐性体育活动作为时尚生活的一部分， 被越来越多的人所追捧。 棋类项目作为一种智力性体育项目， 可以修身养性、 益智健心， 也可以满足人们对于休闲和娱乐的需求. 一些项目如五子棋等由于项目自身的特点和生命力， 也一直被人们所喜爱， 因此得以生存和发展， 成为许多人喜爱的休闲娱乐性棋类项目。随着时代的发展、社会的进步和人民生活水平的提高， 人们对业余体育文化生活方面的需求会不断增加， 这些“ 趣味性”棋类项目 将会越来越受到关注和重视。1.1五子棋的棋盘五子棋的棋盘如图1所示，正中一点为“天元”。棋盘两端的横线称端线。棋盘左右最外边的两条纵线称边线。从两条端线和两条边线向正中发展而纵横交叉在第四条线形成的四个点称为“星”。天元和星应在棋盘上用直径约为0.5厘米的实心小圆点标出。图1 五子棋棋盘示意图以持黑方为准，棋盘上的纵轴线从左到右用英文字母AO标记。横行线从近到远用数字115标记。纵横轴上的横纵线交叉点分别用横纵线标记的名称合写成。如“天元”H8，四个“星”分别为D4，D12，L12，L4。1.2五子棋的基本规则黑白双方依次落子， 任一方先在棋盘上形成横向，竖向，斜向的连续的相同颜色的五个( 含五个以上) 棋子的一方为胜。21）连 在棋阳线和阴线的任意一条线上形成的有5 个或5 个以上的同色棋子不间隔地紧紧相连。五连:在棋盘上形成的5 个同色棋子的“ 连” 。长连:在棋盘上形成的6个或6个以上同色棋子的“ 连”。2）“四”包括“活四”和“冲四”。活四：如图2所示，在棋盘某一条阳线或阴线上有同色4子不间隔地紧紧相连，且在此4子两端延长线上各有一个无子的交叉点与此4子紧密相连。图2 活四冲四:除“ 活四” 外的，再下一着棋便可形成五连，并且存在五连的可能性的局面。白棋再下一着可形成长连的局面也视为“四”，如图3所示。图3 黑棋各种不同的冲四3）“三”指活三，包括“连三”和“跳三”。 连三:在棋盘某一条阳线或阴线上有同色三子相连，且在此三子两端延长线上有一端至少有一个，另一端至少有两个无子的交叉点与此三子紧密相连。 跳三:中间仅间隔一个无子交叉点的连三， 但两端延长线均至少有一个无子的交叉点与此三子相连。4）禁手：对局中禁止使用的着法。 黑棋禁手包括“三三”，“ 四四” 和“ 长连” ， 禁手只对黑棋而言。 三三:由于黑方走一着在无子交叉点上同时形成二个或二个以上黑方“ 活” 的局面，如图4所示。图4 三三禁手 四四:由于黑方走一着在无子交叉点上同时形成二个或二个以上黑方“ 四” 的局面。5 )先手对方必须应答的着法，其中“ 冲四“ 称为绝对先手。6 )四三指某一方同时具备两个先手，其中一个是“ 四” ，一个是“ 活三”.7 )三手可交换 是指黑棋下盘面第3 着棋后，白方在应白之前，如感觉黑方棋形不利于己方，可提出交换，即执白棋一方变为执黑棋一方，而黑方不可以不换。8 )五手两打 是指黑棋在下盘面上关键的第五手棋时， 必须下两步棋，让白 棋在这两步棋中任选一步，然后再继续对弈。一般说来，白棋肯定拿掉对白方不利的一点， 而保留对黑方较为不利的那点让黑方行棋。第二章 人工智能的应用2.1人工智能的发展历史1. 萌芽时期（1956年以前）Ø 17世纪，法国物理学家B.Pascal制成的机械加法器；Ø 在其基础上，德国数学家Leibniz制成了四则运算的计算器。Ø 1936年 英国数学家Turning提出了图灵机模型；Ø 1938年 德国工程师Zuse研制成了第一台累计数字计算机；Ø 1946年 美国诞生了第一台电子数字计算机ENIAC；Ø 1945年，奥地利学者系统论的创立Ø 1948年，美国数学家N.Wiener控制论的创立；Ø 1948年，美国数学家C.E.Shannon信息论的创立；2. 形成时期（1956-1961年） 1956年，在美国Dartmouth大学的一次历史性聚会是人工智能学科正式诞生的标志。有三个较有影响的研究团队：ü 心理学小组：A.Newell、J.Shaw和H.Simon等人于1957年编制出逻辑理论机LT，证明了数学原理中第2章的38条定理，1963年的新版LT证明了该章全部共52条定理。1960年，通用问题求解器GPS能求解10 种不同类课题的问题ü IBM研究小组：A.Samuel研究的具有自学习、自组织和自适应能力的西洋跳棋程序，1959年，该程序战胜了设计者，1962年，战胜了美国的一个州冠军。ü MIT研究小组：1959年，MCCarthy发明了人工智能主要的语言LISP。1958年开发了行动计划咨询系统。1960年Minsky的论文：走向人工智能的步骤。ü 其他：1956年N.Chomsky的文法体系、1958年Shelffridge的模式识别系统等，都对人工智能研究产生了有益的影响。3. 发展时期（1961年以后）o 符号主义学派方面： ü 1965年，J.A.Robinson的归结原理，推动了定理机器证明技术的发展：ü 1965年，E.A.Feigenbaum研制的基于领域知识和专家知识的DENDRAL程序，能根据质谱仪的数据并利用相关知识，推断出有机化合物的分子结构，达到甚至超过了化学家的水平。后来又有