毕业论文--基于MTD(f)算法的计算机围棋吃子算法研究.doc

毕业设计（论文）题目 基于MTD（f）算法的计算机围棋吃子算法研究 系 别 专 业 名 称 班 级 学 号 学 生 姓 名 指 导 教 师 年 月毕业设计（论文）任务书I、毕业设计(论文)题目：基于算法的计算机围棋吃子算法研究II、毕业设计(论文)使用的原始资料(数据)及设计技术要求：本课题利用算法进行计算机围棋吃子算法的研究，要求实现根据不同的输入棋形，计算黑棋（或白棋）如何将对方棋子或棋块捕获的功能。课题设计主要知识、技术点包括：1掌握Windows API编程方法；2掌握Visual Studio平台下MFC编程方法；3利用机器学习相关知识，产生捕获棋步的候选着点并对其进行排序的方法； 4、通过算法对候选着点依次进行搜索，寻找出正确的捕获棋步的方法； 5翻译英文文献。III、毕业设计(论文)工作内容及完成时间：第01-03周：收集和消化资料、可行性分析、英文资料翻译、开题报告的撰写。第04-11周：系统框架设计、各模块实现细节设计、编码调试。第12-15周：分析结果，改进和完善设计，整理论文思路。第16-18周：撰写毕业论文，准备答辩。 、主 要参考资料：1 孙鑫.VC+ 深入详解M.北京：电子工业出版社，20062 陈志行. 电脑围棋小洞天M. 广州：中山大学出版社, 2000.3 Microsoft Corporation MSDN Library Visual Studio 6.0M. 20004 曾凡锋. MFC编程技巧与范例详解M. 北京: 清华大学出版社, 2008.5 Stanley B. C+ PrimerM. 人民邮电出版社, 2010.6 Lei Yu, Jingao Liu. Improved Winning Probability Model in Go Based on Strong Group Quantization and Multi-level Species Compete-Die Out Algorithms. Proc. of 2010 the 2nd International Conference on Future Computer and Communication (ICFCC 2010). 学生（签名）： 填写日期： 指导教师（签名）： 助理指导教师(并指出所负责的部分 系主任（签名）： 学士学位论文原创性声明本人声明，所呈交的论文是本人在导师的指导下独立完成的研究成果。除了文中特别加以标注引用的内容外，本论文不包含法律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式表明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期：学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权南昌航空大学科技学院可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。作者签名： 日期： 导师签名： 日期：基于MTD（f）算法的计算机围棋吃子算法研究 学生姓名： 班级： 指导老师： 摘要：博弈是人工智能的重要研究主题，人工智能的发展在很大程度上得益于博弈研究的发展。作为博弈研究的主要内容之一，棋类博弈得到了满意的解决，但到目前为止计算机围棋仍是人工智能领域中的一大难题。虽然人们不断地研究，但计算机围棋的水平仍然很低，甚至还达不到低段位职业棋手的水平。作为探究人脑工作机制的前沿性尖端学科，认知科学已经引起了全世界科学家的广泛关注。由于在视觉表现形式上具有抽象、复杂的特性，计算机围棋正在成为认知科学研究的重要方向和工具。同时，开发出与人类棋手水平相当的围棋程序也有助于人类认知能力的理解。所以计算机围棋研究具有重要的理论意义和实用价值。目前，围棋程序通常依靠alpha-beta（）剪枝算法进行搜索，使用启发式围棋规则进行走法排序，以此来解决吃子问题；但程序解决问题的速度和准确度依然不高。本论文的研究内容主要是：基于算法的计算机围棋吃子算法研究。在该问题的研究过程当中，首先，对棋块的气划分等级。根据分级结果，可以判断棋块的安全程度，确定捕获目标，产生候选着点并对其排序。通过算法对候选点依次进行搜索，寻找出正确的捕获棋步。实验结果表明其效果较好，可以应用于计算机围棋实战中,并为下一步的厚势价值量化算法研究做准备。关键字： 计算机围棋，吃子问题，MTD（f）算法 指导老师签名：Based on the MTD(f) algorithm of capturing problems in goStudent name: Class:Supervisor:Abstract:Game is one of the important subjects of Artificial Intelligence (AI) and AIs development contributes to the development of the study of game greatly. As one of the main subjects of game, the board game has been studied thoroughly, But, so far, computer go is one of the difficult problems. Although scientists have made study of computer go for many years, at present the level of computer go is very low, even can not reach low dan professional players level.As an exploratory subject focusing on the working of human brain, cognitive science has aroused wide attention from all around the world. Computer Go has become an important tool in cognitive scientific research due to its visual abstractness and complexity. At the same time, it is helpful to comprehend the human cognition that develop the Computer Go programes, whose level is equal to humans. Therefore, the study of Computer go is important both in theory and in practice.So far, go programs often depend on alpha-beta（）pruning algorithm to search, using heuristic go rules for takes a way sort, in order to solve the capturing problems in go; But programs to solve the problem of speed and accuracy is still is not high.This paper studies the content is mainly: Based on the MTD(f) algorithm of capturing problems in go. In the research of the problem in the process, first, Set levels for the groups liberties. According to the levels, the groups safeness can be judged, the target can be fixed and the candidate moves can be generated and sorted. Search the candidate moves in sequence by MTD(f) algorithm to find the best capture move. The result shows the method has good effect and can be applied in the real game of computer Go，prepare for influence value quantization algorithm.Key words: computer Go, capturing problem, MTD(f) algorithm Signature of Supervisor:2目录第一章 绪论11.1 研究背景11.1.1围棋简介11.1.2 计算机围棋的研究现状121.2 研究意义131.3研究内容141.3.1围棋系统软件基本功能的程序实现141.3.2系统软件功能模块图151.3.3系统流程图161.3.4系统界面和功能17第二章 吃子问题求解模型的构造202.1 确定捕获对象和捕获方法202.1.1 简单吃子法202.1.2 捕获对象的确定242.1.3 气的分级262.1.4 候选点的产生302.2 搜索算法与走法排序322.2.1 MTD(f) 搜索算法322.2.2 Hash表的迭代与走法排序322.2.3 考虑对手最强的反抗路径332.2.4 Alpha-Beta搜索算法352.2.5 MTD(f)搜索算法与Alpha-Beta搜索算法对比36第三章 总结38参 考 文 献39致谢. .41第一章 绪论1.1 研究背景近来随着计算机的快速发展，各种各样的电脑游戏层出不穷，使得我们能有更多的娱乐项目，而棋类游戏能起到锻炼人的思维和修身养性的作用，而且棋类游戏水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝” M Muller. Decomposition Search: A Combinatorial Games Approach to Game Tree Search, with Applications to Solving Go Endgames. In: Proceedings IJCAI99. 1999,1:578-583.便是最具说服力的代表；其它像围棋的“手淡”、象棋的“将族”等 K. Chen, Z. Chen. Static analysis of life and death in the game of Go. Information Sciences, 1999. 113-134.也以其优秀的人工智能深受棋迷喜爱。计算机围棋是计算机博弈研究的一个重要分支，是当前人工智能研究的热点之一，一直以来吸引着大量的研究人员，产生了较大的社会影响和学术影响。由于围棋变化复杂、棋理深奥，是一种高智能的活动，因而围棋的计算机博弈设计难度较大，同时计算机围棋热点问题的研究为人工智能带来了崭新的方法和理论。计算机围棋的研究和实现需要多门学科的知识交叉，至少会涉及到围棋、计算机、数学、生物、逻辑学、军事学、教育、心理学乃至哲学等领域，因此其发展具有重要的研究价值和应用价值。对电脑程式设计师而言，围棋已证实是项艰巨的挑战，因为这个游戏的复杂度高深莫测。这种棋戏是在九乘九或十九乘十九格结的交叉点上，放置黑棋与白棋，以占领地域并且包围对手为目标。特別是在大棋盘上，每一手的可能棋步都非常多，对弈当中平均每手可能的位置有200种，相较之下西