《五子棋毕业论文--人工智能课题》由会员分享，可在线阅读，更多相关《五子棋毕业论文--人工智能课题（26页珍藏版）》请在金锄头文库上搜索。
1、五子棋毕业论文五子棋毕业论文-人工智能课题人工智能课题本文由 Ackarlix 贡献doc 文档可能在 WAP 端浏览体验不佳。建议您优先选择 TXT，或下载源文件到本机查看。本科毕业论文(设计)题 目五子棋 AI 算法和网络通信的研究 学生姓名 学 系 年 专 号 别 级 业 计算机科学系 2004 计算机科学与技术指导教师 职 称 讲师 2008-4-01完成日期五子棋 AI 算法和网络通信的研究摘要: 摘要:本系统将利用五子棋游戏作为研究对象,通过设计出一个能够实现两种不 同对战模式的五子棋游戏.并对所涉及到的相关技术进行初步的探讨,将重点放 在人机对奕中 AI 算法研究方面. 游戏中提
2、供两种选择模式:人机对战和人人对战.在人机对战中玩家通过 选择不同的 AI 等级和电脑一决高下.在人人对战中双方可以进行下棋,悔棋但1要通过对方的同意.同时还可以实现在线聊天.AI 的不同等级是以不同的搜索 深度确定的.本系统以深度为 2,3,4 分别为初级,中级,高级.网络对战中则 使用 Socket 实现点对点通信. 关键字: 算法, 关键字:五子棋 ,博奕 AI 算法,网络通信Research the AIof Renju and the CommunicationSummary:This system will use Renju as research objects, passin
3、g to design a Renju game that can provide two kinds of dissimilarities to the play mode. to involve to of the related technique carry on the study of the first step, play more attention in the AI calculate way research aspect. It provide two kinds of choice modes in the game:Persons machine to the w
4、ar and the everyone to war.The player passes to choose the different AI grade and computer in persons machine the rightness the war a definitely superiority.Both parties can carry on play chess in the everyone the rightness the war, the regrets chess but want to pass the approval of the other party.
5、Can also carry out on-line chat in the meantime.AI different grade with search the depth assurance differently.This system takes depth as 2, 3, 4 is an entry-level respectively, medium class, high class.The network orders correspondence towards then using the Socket realization to order in the war t
6、o. Key word: Renju ,AI,networks目录引言4 第一章 引言 1.1 问题背景4 1.2 五子棋简介5 详细设计过程5 第二章 详细设计过程 2.1.概要介绍.5 2.1.1 本程序介绍5 2.1.2 本程序优点5 2.2 用软件工程方法学指导开发过程522.2.1 问题定义6 2.2.2 可行性研究7 2.2.3需求分析8 2.2.4 总体设计.9 2.2.5 详细设计10 2.2.6 编码和单元测试10 2.3 用户界面10 2.4 系统解析11 2.4.1 界面部分11 2.4.1.1 CFiveChessView 的属性.11 2.4.1.2 CFiveChe
7、ssView 的函数.12 2.4.2 通信部分14 2.4.3 其他部分15 2.4.3.1 CMatch 棋盘类.16 2.4.3.2 CMessg消息类.17 2.4.3.3 CComputer电脑类18 2.5. 人机对战中的 AI 算法18 2.5.1 极大极小树.19 2.5.2 深度优先搜索(DFS)19 2.5.3 剪枝方法.20 2.5.4 静态估值函数.21 2.5.5 AI 算法的分析和改进.21 2.5.5.1 算法分析.22 2.5.5.2 算法改进.24 运行测试25 第三章 运行测试 3.1 网络部分25 3.2 人机部分25 总结部分27 第四章 总结部分 4.
8、1 系统总结29 4.2 不足说明29 4.3 致谢28 参考文献.29 参考文献第一章 引言1.1 问题背景计算机运算速度一直遵循着摩尔定律在飞速的发展,随着这些技术的快速 发展,使得大规模的运算得以在很短的时间内实现.正是基于这些技术,近年来 各式各样的棋类游戏软件也纷纷出现在了电脑荧屏上,使得那些喜爱下棋,又常 常苦于没有对手的棋迷们能随时过足棋瘾. 所以如果能设计一款兼有人工智能和 网络联机的五子棋软件则对五子棋棋迷们来说无疑是个“福音“ .在人机智能方 面其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝“便是最具说服力的代表; 其 它像围棋的“手淡“,象棋的“将族“等也以其优秀的人工智
9、能深受棋迷喜爱;3本系统将重点放在人工智能方面, 采用不同的策略将人工中的智能分为不同 的等级.选择五子棋游戏作为本设计的课题,是因为该游戏的规则简单,所涉及 的方向比较少.这样才能将问题的重点放在人工智能解决上,而非规则的解决, 有更多的精力放在高效算法和通信过程的优化.希望能通过本次系统的设计,整 合所学的知识,实现从理论到实践上的升华.1.2 五子棋简介下面就五子棋的背景和规则做一些简单的介绍. 五子棋是起源于中国古代的传统黑白棋种之一.现代五子棋日文称之为“连 珠“,英译为“Renju“,英文称之为“Gobang“或“FIR“(Five in a Row 的缩写), 亦有“连五子“,“
10、五子连“,“串珠“,“五目“,“五目碰“,“五格“等多种称谓. 五子棋不仅能增强思维能力, 提高智力, 而且富含哲理, 有助于修身养性. 五子棋既有现代休闲的明显特征“短,平,快“,又有古典哲学的高深学问“阴阳 易理“;它既有简单易学的特性,为人民群众所喜闻乐见,又有深奥的技巧和高 水平的国际性比赛;它的棋文化源渊流长,具有东方的神秘和西方的直观;既有 “场“的概念,亦有“点“的连接.它是中西文化的交流点,是古今哲理的结晶. 五子棋的规则如下:棋盘:采用同围棋盘一样的 15 路或 19 路线的棋盘,为 了减小问题的规模,本系统将采用 15 路线的棋盘.下法:两人分别执黑白两色 棋子,轮流在棋盘
11、上选择一个无子的交叉点落子.无子的交叉点又被称为空点. 输赢判断:黑,白双方有一方的 5 个棋子在横,竖或斜方向上连接成一线即为该 方赢.第二章 详细设计过程2.1 概要介绍2.1.1 本程序介绍游戏中提供两种选择模式:人机对战和人人对战.在人机对战中玩家通过选 择不同的等级和电脑一决高下,可以向后悔棋.在人人对战中双方通过选择一方 作为服务器,通过弹出对话框设置本地应用程序监听端口,而另外一方则作为客 户端,通过连接服务器选项,在弹出的对话框中设置要连接的服务器的 IP 地址 和端口号.当双方都提示连接成功后,两方才可以进行下棋.如要悔棋则需要通4过对方的同意.同时还可以实现在线聊天.AI
12、的不同等级是以不同的搜索深度 确定的.本系统以深度为 2,3,4 分别为初级,中级,高级.网络对战中则使用 Socket 实现点对点通信.2.1.2 本程序特点五子棋游戏程序由于规则简单操作简便等特点, 自然就成为程序员对人工智 能研究的首选对象.所以网络上关于这类的程序很多,但是由于主要都是采用搜 索穷举技术作为解决方案,这将使得问题的规模变的很庞大如当搜索深度为 3 时 , 每 走 一 步 电 脑 在 将 最 坏 的 情 况 下 需 要 搜 索 的 点 将 达 到 225*225*225=11390625 个.即使采用的剪枝技术,其某些点的响应的时间也是 让人无法忍受的, 如开局时, 因为
13、这个时候每个点都是空的, 没有可以剪枝的点, 必须遍历真个盘面,所以很耗时间,大约需要 30 多秒的时间,这个显然是不可 接受的.为了程序设计和玩家的忍受时间的需要.不得不减小深度,所以绝大部 分都采用深度为 2 的检索,很明显深度越低系统的智力也相对的降低,需要代价 的. 本程序的一个主要特点是,采用了高效的优化方法,使得在相同的搜索规模 中所花费的计算时间大幅度的减小.响应时间明显得到提高.即使搜索深度达到 4 的时候,其响应时间在绝大部分的情况下还是可以接受的.2.2 用软件工程方法学指导开发过程 软件工程方法学指导开发过程在小规模的程序开发中,很多人都不太注意用软件工程的方法学设计系统, 包括我本人,在开发一些小功能程序时总是随心所欲的添加需求:有时为了类与 类之间的通信需要,往类中添加不相关的变量,直接修改变量的属
