计算机五子棋博奕系统的研究与实现

论文题目: 计算机五子棋博奕系统的研究与实现

论文类型: 硕士论文

论文专业: 计算机软件与理论

作者: 董红安

导师: 刘弘

关键词: 人工智能,博奕,五子棋,搜索算法,威胁空间搜索

文献来源: 山东师范大学

发表年度: 2005

论文摘要: 人工智能是近年来很活跃的研究领域之一。计算机博弈是人工智能研究的一个重要分支,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响。国内外对博弈的研究已经较为广泛,特别是IBM的国际象棋程序“深蓝”,已经达到了人类的世界冠军水平。“深蓝”的研究成果,特别是基于剪枝的极大极小树搜索技术为设计其它的计算机棋类博奕系统提供了良好的参照。但是不同的棋类博奕,其规则的千差万别赋予了每一种棋类博奕特殊的专业知识。这就必然要求设计一个具体的棋类博奕系统时应该深入研究它的基本原理和内在规律。本文以计算机五子棋博奕系统做为研究课题,在对大量的相关文献进行分析研究的基础上,首先按照人工智能和计算机博奕的一般原理设计了一个五子棋博奕系统的基本模型,所做的工作包括三个方面:第一研究了五子棋在计算机中的表示问题,讨论了计算机中存贮棋局和识别下棋次序,局势状态变化及局势特征、走法产生等方法。第二研究了博弈树的极小极大搜索技术及在此基础上的Alpha-Beta剪枝过程和剪枝优化问题。实现将候选的后继节点按位置邻近顺序排序,使剪枝过程得到优化。此外还研究了Alpha-Beta剪枝的改进算法NegaScout算法,此算法首先采用一小的有限Alpha-Beta窗口,以确定实际估计值的范围,再在这个较小的范围中搜索实际的估计值。由于在较小的范围中搜索,效率能得以提高。第三根据五子棋的特点,提取棋局局势的若干特征,对这些特征赋加权分,并对整个棋局进行特征统计,采用一个线性函数求得棋局的总估计分值。实践中,采用极小极大搜索加此静态估值技术的初版程序,达到了比初学者强的水平,一些比较熟练的业余人员时常也会负于此程序。在上述工作的基础上,本文的创新性研究主要包括以下两个方面:第一对五子棋博奕的专业知识进行了认真的整理,针对五子棋博奕规则简单、局势判断清楚的特点,对五子棋常见的开局、定式及其后的对局做了细致的统计分析,阐明了五子棋对奕中黑白双方优劣势并非均衡的规律,这一规律作为一个指导原则在设计五子棋博奕系统时起到重要作用。第二针对初版程序中存在的缺点和不足,通过查找原因,实现了算法的优化和加强。初版程序在运行时其搜索速度和对奕表现不能让人满意。其主要原因有两个:使用常规的Alpha-Beta搜索和NegaScout算法不能避免相同局面的重复节点的搜索,从而影响搜索速度;采用固定的估值法,估值的不准确使其“智力”较低,而且固定的赋值方式使其不能在对奕过程中提高棋力。解决的方法有两个:在执行常

论文目录:

中文摘要

Abstract (英文摘要)

第一章 绪论

1.1 选题背景

1.2 计算机博弈研究简史

1.3 计算机博弈的研究意义

1.4 计算机博奕的过程

1.5 五子棋发展简史与基本知识介绍

1.6 课题主要工作

第二章 五子棋博奕的理论研究

2.1 五子棋博奕的不同形式

2.2 五子棋博奕黑白双方优劣势的分析

2.3 策略的选择

第三章棋盘状态空间表示与走法产生

3.1 棋盘局势状态表示

3.2 棋盘中下棋的顺序表示

3.3 状态的变化

3.4 特征的表示

3.5 走法的产生

第四章 博弈树的搜索技术

4.1 极大极小树搜索算法

4.2 Alpha-Beta 剪枝过程

4.3 Alpha-Beta 剪枝存在的问题及优化

4.4 NegeScout 搜索

第五章 静态估值函数

5.1 棋盘局势特征

5.2 估值

5.3 静态估值函数的不足及实践效果

第六章 搜索算法的优化与增强

6.1 置换表的搜索

6.1.1 哈希表

6.1.2 应用置换表的其它问题

6.1.3 Zobrist 技术

6.2 威胁空间搜索

6.2.1 专业术语和“威胁次序”

6.2.2 人类专业棋手的分析

6.2.3 计算机程序的策略

6.2.4 人与计算机

6.2.5 威胁空间搜索

6.2.6 算法优化后效果的检验

参考文献

致谢

在读期间发表的论文和科研成果

发布时间: 2006-08-08

参考文献

• [1].五子棋人工智能算法设计与实现[D]. 刘瑞.华南理工大学2012
• [2].基于人工智能的五子棋专家系统研究和设计[D]. 刘阳.电子科技大学2015
• [3].移动应用中人工智能的研究与应用[D]. 耿芒芒.北京邮电大学2016
• [4].面向课堂协作学习的分组专家系统研究[D]. 孙键.上海师范大学2009
• [5].人工智能在搜索引擎资源获取中的应用[D]. 车志军.浙江大学2006
• [6].基于云服务器的高性能与高稳定性围棋搜索服务的研究[D]. 郭力森.北京邮电大学2016
• [7].五子棋对弈平台的设计与实现[D]. 罗文浩.西安电子科技大学2015
• [8].参数化创意大数据背景下的计算设计[D]. 张琦岳.中央美术学院2016
• [9].基于本体的玉米病虫害防治语义检索系统的研究[D]. 刘春辰.吉林大学2008
• [10].基于人工智能的幼儿地震安全教育游戏设计开发研究[D]. 张冬梅.云南师范大学2017

相关论文

• [1].棋牌游戏平台服务端的设计与实现[D]. 吴兆定.上海交通大学2007
• [2].具有自学习功能的计算机象棋博弈系统的研究与实现[D]. 王一非.哈尔滨工程大学2007
• [3].基于逻辑推理和机器学习的围棋死活知识的发掘系统[D]. 宗武.北京科技大学2005
• [4].计算机国际象棋博弈系统的研究与实现[D]. 万翼.西南交通大学2006
• [5].计算机中国象棋博弈中的二次估值方法及其优化的研究[D]. 张赜.东北大学2006
• [6].围棋博弈专家系统的研究与实现[D]. 高欣.北京工业大学2002
• [7].计算机围棋博弈系统的若干问题研究[D]. 谷蓉.清华大学2003
• [8].机器自学习博弈策略研究与实现[D]. 莫建文.广西师范大学2002

标签：人工智能论文;  博奕论文;  五子棋论文;  搜索算法论文;  威胁空间搜索论文;