毕业论文论文 - 中国象棋人机对弈

更新时间:2024-04-21 06:42:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

四川大学本科毕业论文中国象棋人机对弈

本科生毕业论文(设计)

题 目 中国象棋人机对弈 学 院 专 业

学生姓名 学 号 年级 指导教师

教务处制表

四川大学本科毕业论文中国象棋人机对弈

中国象棋人机对弈

[摘要]文章主要是研究中国象棋的人机对弈,包括象棋的界面和引擎部分。界面主要是方便人与电脑进行交互的可视化界面。界面包括棋盘区、菜单项和功能按钮区。主要实现棋子的移动、悔棋、记录棋谱、难度选择等选项功能。引擎部分主要包括,棋子棋盘的表示即数据结构,走法的生成,局面优劣的评估即评估函数,搜索算法及其优化和改进。界面的设计是采用MFC的框架来实现界面部分,MFC是微软公司提供的一个类库,以C++类的形式封装了Windows的API,并且包含一个应用程序框架,以减少应用程序开发人员的工作量,其中包含大量的Windows句柄封装类和很多Windows控件和组件的封装类。象棋对弈其实是一种博弈。双人对弈,轮流走步;信息完备,双方得到的信息都是一样的;零和,即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利或无利的棋。如果轮到自己落子的时候,一定会选择使局面分数最高的着法,如果轮到对手落子,他一定会选择使你得分最低的局面。这就是我们经常听到的极大极小值搜索,而对局面进行估分的函数就是评估函数。

[主题词]博弈树;极大极小值搜索;alpha-beta剪枝;评估函数

Chinese chess computer game

四川大学本科毕业论文中国象棋人机对弈

Network Engineering

[Abstract]This paper mainly explores the Chinese chess computer game,it includes user interface and game engine.UI is a visual interface which helps human to communicate with computer.UI includes the board area,the menu and commonly used buttons.Its functions include pieces move,undoing,saving game record,choosing level and so on.The game engine mainly includes

the

form

of

pieces

and

board,that

is

data

structure,movegeneraion,evaluationfunction,searchalgorithm.The UI is implemented through MFC.MFC is a class library provided by Microsoft.It encapsulates a Windows API in the form of c++class,and includes a application framework,and reduces the workload of programmers.Chinese chess is a zero-sum game.Two people play,take turns to move piece;Information is the same to the both sides.There is no favorable or bad situation for both parties.If it is your turn,you will choose the favorable situation,in the same way,the opponent will choose the bad situation for you.This thought is called minimaxalgorithm,the function for estimating is called evaluation function.

[Key Words]Game Tree;Minimax Search;Alpha-Beta Pruning;Evaluation Function

目录

1. 综述 ...................................................................................................................................................... 1

四川大学本科毕业论文中国象棋人机对弈

1.1选题的意义 .................................................................................................................................. 1 1.2国内外研究现状概述 ............................................................................................................. 1 1.3主要研究内容 ............................................................................................................................. 2

2. 数据结构 ........................................................................................................................................... 4

2.1棋盘的表示 .................................................................................................................................. 4 2.2棋子的表示 .................................................................................................................................. 5

3. 棋子的走法 ..................................................................................................................................... 7 4. 评估函数 ........................................................................................................................................... 8 5. 搜索算法 ......................................................................................................................................... 10

5.1极大极小值搜索算法 ........................................................................................................... 10 5.2 alpha-beta剪枝算法 ........................................................................................................ 12 5.3 alpha-beta剪枝算法的改进 ....................................................................................... 13

6. 界面的实现 ................................................................................................................................... 15

6.1棋盘区........................................................................................................................................... 15 6.2菜单项的设计 ........................................................................................................................... 16 6.3常用按钮的设计 ..................................................................................................................... 17

7.开局库 ..................................................................................................................................................... 18 8.系统的实现 ......................................................................................................................................... 19 9.总结........................................................................................................................................................... 26 参考文献 ..................................................................................................................................................... 27 声明 ................................................................................................................................................................ 28 致谢 ................................................................................................................................................................ 29

四川大学本科毕业论文中国象棋人机对弈

四川大学本科毕业论文中国象棋人机对弈

1. 综述

1.1选题的意义

中国象棋在中国拥有悠久的历史,这个游戏需要两个人进行对弈。由于中国象棋用具简单、趣味性强,成为流行极为广泛、老少皆宜的棋艺活动。中国象棋是一种古老的文化,它集文化、科学、艺术、竞技于一体,有利于开发人的智慧,锻炼人的思维,培养人的毅力,增强人的竞争意识。随着电脑技术及互联网的发展,人们下棋没有了地域限制,人们甚至可以跟电脑对战,于是就产生了人是否能够战胜电脑的疑问。

从很早开始,人们就开始进行棋类博弈的游戏了,而在人工智能领域,机器博弈始终是一个重要的组成部分。人们对人工智能的窥探是从棋类博弈游戏开始的,人们在博弈游戏中,对战双方通过对游戏规则的掌握、丰富的经验和知识,使游戏的局面有利于自己,这就是人类的思维过程,于是棋类博弈就成了人工智能的实验品。

对机器博弈的研究取得的成果不仅仅只用在棋类游戏上,而且也已广泛应用于军事、政治、经济等多个领域,给人类带来了极大的社会效益。

1.2国内外研究现状概述

机器棋类博弈的研究最早是从国际象棋开始的,1950年美国著名数学家香农积几十年的研究,找到了编制国际象棋程序的原则方法。他提出以数的函数评价局面的优劣。函数的主题是通常一般实力的棋手都能考虑到的一些因素,诸如:棋子实力重叠兵孤立兵、落后兵的弱点以及车的通路和其他子力的活动性等等。香农还提出用简化的估计方法剔除次要的变化。他是计算机国际象棋理论的奠基人。

在数学家和计算机专家的共同努力下,20世纪50年代末终于试制出世界上第 1台公开与棋手对弈的电子计算机。

1974年,在瑞典的斯德哥尔摩举行了计算机国际象棋的第1届世界冠军赛,8个国家的13种弈棋程序按积分循环制进行比赛,结果苏联的“卡伊赛”程序获得冠军。

最出名的是1997 年,卡内基梅隆大学的“深蓝”小组研究开发出“更深的蓝”,挑战人类大师。最后在全世界目光的关注下,“超级深蓝”击败了棋王卡斯帕罗夫。成为人工智能历史上里程碑式的事件,也标志着机器博弈的重大成功。

和国际象棋相比,中国象棋机器博弈起步比较晚,八十年代才开始。1981年张耀腾发表的《人造智慧在电脑象棋上的应用》,是第一篇研究中国象棋机器博弈的文章。他在他的毕业论文中以残局做实验,提出审局函数为静态子力值,棋子位置值,棋子灵活度值,

1

四川大学本科毕业论文中国象棋人机对弈

威胁与保护等四项之和。1982年廖嘉成发表的《利用计算机象棋的实验》就进了一步,包括开局、中局、残局。

台湾大学的许舜钦教授被称为中国计算机象棋之父。在他1991年的两篇论文中,总结并介绍了到当时为止几乎所有的搜索算法,他在文中详细阐述了许多算法的不足之处并且解释了人们对这些算法的误解。这些研究成果为以后计算机象棋的发展做好了铺垫,至今仍在指导着人们进行计算机象棋的研究和实验工作。

到了九十年代,中国象棋计算机博弈开始发展起来,人们研究出了各种博弈软件。比较有代表性的有台湾的吴身润的《中国象棋》、光谱公司出品的《将族Ⅲ》、晟业编制的《象棋水浒战》等等。

1.3主要研究内容

文章主要是研究中国象棋的人机对弈,包括象棋的界面和引擎部分。界面主要是方便人与电脑进行交互的可视化界面。界面包括棋盘区、菜单项和功能按钮区。主要实现棋子的移动、悔棋、记录棋谱、难度选择等选项功能。引擎部分主要包括,棋子棋盘的表示即数据结构,走法的生成,局面优劣的评估即评估函数,搜索算法及其优化和改进。

主界面分为三部分:菜单栏,棋盘区,常用按钮。菜单栏在最上面,有四个主菜单:游戏,难度,让子,棋谱。游戏菜单包括“我先走”、“电脑先走”、“音效”、“退出”。不论选择我先走还是电脑先走,棋盘区的棋子都会回到初始位置。选择音效会有声音效果,取消音效为静音。难度菜单包括“傻瓜”、“菜鸟”、“新手”、“入门”、“业余”、“专业”、“大师”,总共设有七个难度,选择任何一个难度不会影响棋盘区的布局,只会改变当前电脑的策略。让子菜单包括“让单马”、“让双马”、“让九子”、“被让单马”、“被让双马”、“被让九子”,选择任何一个选项也会让棋盘区的棋子回到让子的初始状态。棋谱菜单包括保存棋谱和读取棋谱,保存棋谱是保存从初始状态到当前局面的过程。读取棋谱,读取出保存的棋谱并使棋盘区的棋子回到初始状态,棋盘下方的常用按钮替代为“上一步”“下一步”,可以通过这两个按钮演示棋局。棋盘区是显示棋盘的区域,占据了整个界面的正中。常用按钮区在棋盘区的下面,有三个按钮:悔棋、保存、复盘,悔棋是当人该下子的时候回到上一步,保存是保存当前棋盘的格局,复盘是恢复保存的棋盘格局,人可以接着回复的格局继续对弈。

文章设计是采用MFC的框架来实现界面部分,主要用到的MFC类有,CWnd:窗口,它是大多数“看得见的东西”的父类(Windows里几乎所有看得见的东西都是一个窗口,大窗口里有许多小窗口)。CDC设备文本。无论是显示器还是打印机,都是画图给用户看。这图就抽象为CDC。CDC与其他GDI(图形设备接口)一起,完成文字和图形、图像的显示工作。CDialog对话框类,CPen类,CBrush类等等。

2

四川大学本科毕业论文中国象棋人机对弈

象棋对弈其实是一种零和博弈。双人对弈,轮流走步;信息完备,双方得到的信息都是一样的;零和,即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利或无利的棋。所以内核代码的思路要用到博弈算法。对每一个局面所有可能的着法进行考虑,每一步着法会形成新的局面,这样就形成了一颗博弈树。机器博弈就是要从这颗博弈树中找到最优的分支,即要用到搜索算法对整棵树进行搜索。而中国象棋的博弈树是一个庞大的集合,如果一毫微秒走一步,也要需要10的一百多次方年才能搜索出必赢的第一步,所以博弈树是不可能穷举的。人在思索下棋的时候也不可能对棋局所有的可能计算完全,人往往是凭自己的经验、知识对棋面的好坏进行评估。通过这种思路我们可以给每个局面打一个分数来表示棋局对自己的有利程度。如果轮到自己落子的时候,一定会选择使局面分数最高的着法,如果轮到对手落子,他一定会选择使你得分最低的局面。这就是我们经常听到的极大极小值搜索,而对局面进行估分的函数就是评估函数。

极大极小值搜索就是在轮到自己落子的时候选择分数最大的局面,轮到对手落子的时候选择得分最小的局面,这样就使得搜索可以进行,而由于估分的存在我们就可以在搜索进行到可以接受的时间范围内时结束它。

3

四川大学本科毕业论文中国象棋人机对弈

2. 数据结构

2.1棋盘的表示

任何程序都是由数据结构和算法构成的。对中国象棋的计算机游戏编程,首先是要思

考用什么样的数据结构来记录棋盘和棋子。下图是一个中国象棋的棋盘:

图2-1 中国象棋棋盘

可以明显地看出,中国象棋的棋盘是由10*9根横竖直线相交的交叉点构成的。那么我

们很容易地想到了用一个10*9的数组board[10][9]来表示棋盘,棋盘的定义如下: int board[10][9]={ 1,1,1,1,1,1,1,1,1, 0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,1,0, 1,0,1,0,1,0,1,0,1, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,

4

四川大学本科毕业论文中国象棋人机对弈

1,0,1,0,1,0,1,0,1, 0,1,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1 };

在这里我们用0表示某个位置上没有棋子,用1来表示某个位置上有棋子,棋子的具我们还可以用一个一维数组来表示这个棋盘,棋盘从左到右再从上到下我们可以用一体表示方法我们在下一小节将会讨论。

个一维数组board[90]来表示棋盘,一维数组的定义为: intboard[90]={

1,1,1,1,1,1,1,1,1, 0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,1,0, 1,0,1,0,1,0,1,0,1, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 1,0,1,0,1,0,1,0,1, 0,1,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1 };

也就是说数组的第一个位置代表左上角的车,而数组的最后一个位置代表的事右下角的车。用一维数组来表示棋盘有什么好处呢,首先一维数组比二维数组少了一个维度,可以用一个下标就能表示一个点,这对于找寻一个点的位置是十分方便的,其次只需通过下标的求余和求整计算就可以轻易得到某个点的横纵坐标。

还有一种更高效的办法,就是用一个256长度的一维数组来表示棋盘,它主要是利用了与运算和右移运算来实现求横纵坐标的,我们这里不再进行阐述。

2.2棋子的表示

上一小节为了阐述方便,我们简单地把有棋子标记为1,在实际的操作过程中,这样

是远远不够的,因为我们知道不同的棋子作用是不同的,所以我们需要用新的不同的数字来代表不同的棋子。

我们可以按照棋盘上从左到右的顺序,用1来表示车、2表示马等等,可以总结为下

5

四川大学本科毕业论文中国象棋人机对弈

边的对应图:

车 马 象 士 将 炮 卒 车 马 相 仕 帅 炮 兵 1 2 3 4 5 6 7

这样我们就得出了一个简单的对应关系,我们通过数字的不同就可以判断棋子的不同种类,但是这样不能区别红黑双方的棋子,于是我们做一个小小的改进:

车 马 相 仕 帅 炮 兵 1 2 3 4 5 6 7 车 马 象 士 将 炮 卒 8 9 10 11 12 13 14

那同一方的同类的棋子有没有差别呢?我们知道,如果马被封在了角落里它的作用可能还不及一个过河兵,如果马在卧槽的位置上那么它的威胁是十分大的,关于棋子的效力我们将在评估函数一节中讨论,所以即使是同一方相同的棋子也需要用不同的数字来表示,于是就形成了下边的对应:

车 马 相 仕 帅 仕 相 马 车 炮 炮 兵 兵 兵 兵 兵 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 车 马 象 士 帅 士 象 马 车 炮 炮 卒 卒 卒 卒 卒

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

我们依然用0来表示棋盘上的位置上没有棋子。当电脑在下棋的时候,它会挨着搜索

棋盘上有哪些棋子,然后来判断棋子的移动,这样到了中后期,棋盘上的棋子很少的时候这样的做法效率是很低的。于是我们就想到通过某一个棋子可以直接知道它是否还在棋盘上,如果在棋盘上能知道它在棋盘上的位置。我们可以定义一个长度为32的一维数组来建立一个棋子到棋盘的映射,来记录棋子的信息。如果我们用的是一维数组来表示棋盘,那么这个映射数组的值当为-1时我们可以知道棋子已经不再棋盘上了,我们可以用相应的整数来表示棋子在棋盘上的坐标。

6

四川大学本科毕业论文中国象棋人机对弈

3. 棋子的走法

没有规矩不成方圆,任何棋类游戏都有它落子的规矩。对于简单的五子棋来说,下棋双方轮流下棋,只要是棋盘上有空位的地方都可以落子。相比于五子棋来说,象棋的规则就相对要复杂一些,像马走日、象走田、将不能出九宫格、士划斜线,还要考虑撇马脚、堵象眼等各种情况。对于中国象棋电脑游戏,电脑对于人落子合理性的判断要相对简单一些,只需判断起始点的棋子的规则时候能够走到终点。由于中国象棋的电脑思索过程是基于搜索的,所以电脑必须判断出棋子所有合法的落点。

根据棋子的走法,如车可以在横竖直线上走任意步,兵每次只能移动一步,这样我们可以得出棋子可能走到的点,我们还需要考虑棋子是否走出了棋盘,这种着法是不合理的。我们还需要考虑规则的合理性,车在走任意步的时候起始点和终点之间没有棋子的阻隔,兵永远不能后退,兵在过河后才能左右移动,马脚时候被撇住,象的中心是否被堵住。还要考虑当落子的终点上有对方的棋子话就形成了吃子。另外,对于炮来说,炮的移动和吃子的规则是分开的,需要分开来考虑。

如果每次搜索都要一个棋子一个棋子地去考虑它们所有的落子位置,这样搜索的效率会大大降低。通常我们会使用一种模板法的方法来简化棋子落子的选择,这种方法是利用空间去换取时间来提高效率。模板法是将在某个位置上的棋子的所有可能的落点记录下来,例如某个位置上的棋子是一个马,根据马的行子规则我们可以记录下马所有可能达到的位置,存储起来作为模板,当我们搜索棋子与棋盘的映射数组时,如果我们知道了马正好在这个位置上,我们就可以直接得出马可能的几个落子位置,再检查马脚是否被撇,就可以很快地知道棋子的落点。

棋子走法的生成是在搜索的每层必须要用到的,能够简化走法生成的步骤缩短走法生成的时间将会大大提高搜索算法的时间,从而提高电脑下棋的速度。

7

四川大学本科毕业论文中国象棋人机对弈

4. 评估函数

对于中国象棋来说,当一方的将帅被吃掉的时候棋局也就结束了,被吃掉的一方输掉了比赛,当双方都无论如何无法吃掉对方的将帅的时候就为和局。电脑是通过搜索的办法来寻找下棋的策略的,如果电脑搜索到对方的将帅被吃的时候,那么返回的第一步就是电脑必赢的第一步,然而根据现在的硬件设备很多地方都证明了这需要上亿万年的时间,也就是说要需找出必赢的第一步棋几乎是不可能的,这样也使得人机对弈失去了意义。于是我们就考虑怎样才能让搜索的时间控制在可以接受的范围内,假设我们只搜索到第N层,当到了第N层的时候我们就需要判断出哪一个局面对下棋的一方是最有利的。对于人来说局面是否有利是凭自己的经验感觉、掌握的知识等来判断的,但是电脑它不能像人一样真正地思考,它需要我们给它制定一些规则来判断局面的好坏,这个告诉电脑棋局形势好坏的函数就是评估函数。评估函数会以下棋的一方为主体给棋局进行打分,让电脑一目了然地知道哪个棋局对它有利,从而返回最佳的落子策略。

那怎么来判断一个局面的好坏呢,首先想到的就是棋子本身的价值。通常我们会觉得车的价值比一个兵的价值大,这样我们就可以用一个分数来表示它们作用的大小。有一个词叫弃车保帅,如果将帅都被吃掉了,那么游戏也就以失败告终了,所以将帅看似能力很小但我们要给它一个无穷的值来表示它的重要性,在计算机中我们用一个相对来说非常大的数字来表示将帅的值。对于炮和马的价值差别是很模糊的,很少有人会在下象棋的第一步就用自己这一方的炮去换掉对方的马,当然这里面包含有转换先手的原因,而马的吃子的效果不用考虑到局面棋子的多少,相对来说比较灵活。这里我们认为马的作用稍高于炮。我们可以得出一个棋子与分数的简单对应:

车 马 象 士

炮 兵

700 320150 150 10000 300 100

这是一种最简单的判断局面好坏的方法,利用这种方法加上高效的搜索算法也可以写出一个具有相当棋力的象棋程序。

棋子除了它本身的价值还有它所处位置的影响,前面的内容我们就说到了如果一个被封在死角的马的作用不及一个卧槽马的作用,甚至不如一个在对方九宫格附近的过河兵的作用。所以我们在考虑棋子本身价值的同时我们还需要考虑它的位置附加值。我们可以做出所有棋子位置附加值的映射作为模板存储起来,给一个棋子在不同的位置打一个分数,当评估局面的好坏时,也把位置附加值加权在内。像兵过河过后的附加值比没过河要大,兵进一步靠近对方的九宫格附加值更大,当兵被逼到对方的底线时附加值又会相应地减少。对于将帅来说位于最起始的位置时附加值是最大的。

我们知道下围棋的时候最讲究的就是形和势,所谓的形就是棋子与棋子之间的相互作用。像一些必杀的棋,炮与炮的组合双重炮,炮与马的组合马后炮,这些都是由自己一方

8

四川大学本科毕业论文中国象棋人机对弈

的棋子形成的强有力的杀招,当棋子的移动可以构成某些固定的形的时候,我们也应该给这样形加分。除了这些杀招外,还有一些非常强硬的组合,像连环马、担子炮、霸王車,根据不同的形加上相应的附加值。古文中有“夫六国与秦皆诸侯,其势弱于秦”,所谓的势就是保护与被威胁的情况。当一方的某个棋子在下一步将会被对方吃掉的时候,如一方的马在对方的炮的吃子位置上,我们就认为被威胁的一方势要弱一些,就应该给主动威胁的一方加上相应的分数,而给被威胁的一方减去相应的分数。我们还需要考虑到,在中国象棋中经常存在连环吃的情况,如果你吃了对方的一个子,对方马上也能吃掉你的那个子,也就是说某一方的一个棋子虽然在对方一个棋子吃子的威胁下,但是被威胁的那个棋子又在己方的某一个棋子的保护之下,这种局面处于动态稳定,我们不予加分。如果对子的两颗棋子本身价值及位置附加值等相差甚远,我们又需要另外作考虑。

上面介绍了一些常用的判断局势的依据,依据这些依据可以写出十分强大的象棋程序,但是如果和顶尖棋手较量还有一定的差距。就像完全展开博弈树一样,这是一个理想的状态。对于评估函数,如果它能像人一样或者比人的思维更强,它能考虑到各种各样的情况,计算到各种各样的因素,换句话说它是一个完美的评估函数,那么我们就不再需要搜索算法。我们只需要凭借评估函数就能知道要走的棋是哪一步。但是这样的评估函数我们都知道至少现在是不可能的,但是人们也在朝着这个方向努力,神经网络评估函数就是想实现这个目标。庞大的象棋程序会吸纳成千上万的优秀棋局作为计算机的参考,并且计算机还具有一定的学习修正能力。这需要用到更深奥的知识,如现在的加强学习法,自适应遗传算法等。

9

四川大学本科毕业论文中国象棋人机对弈

5. 搜索算法

5.1极大极小值搜索算法

中国象棋是一种零和博弈游戏,所谓零和即一方的收益必然意味着另一方的损失,博弈双方的收益和损失相加总和永远为零。博弈双方轮流下棋,都选择对自己最有利即对对手最坏的情况,这样交替就形成了一颗博弈树。为了阐述方便,我们假设后边都是一个叫Max的一方即将下棋,而他的对手叫做Min,而评估函数计算出的分数都是相对于Max的得分。当Max下棋的时候他一定会选择对自己最有利的着法,即得分最高的局面,我们称为Max点,而轮到Min下棋的时候,他一定会选择对Max来说最坏的局面,即得分最低的局面,我们称为Min点。这个轮流思考的过程我们用搜索算法表达出来就是极大极小值搜索算法。

图5.1 一颗博弈树

如图5.1是一颗分支为3,深度为2的博弈树。正方形的点代表它是一个极大值点,它选择它的后继者中值最大的局面。圆形的点代表它是一个极小值点,它选择它的后继者中值最小的局面。例如点p(1),它是一个极小值点,在它的后继者中p(1,2)的值最小,所以它的值就为3。对于根节点p来说,它是一个极大值点,它的后继者中p(1)的值最大,所以它的值就为3。

下边是极大极小值的一段伪代码。 intMaxmin(int depth) {

10

四川大学本科毕业论文中国象棋人机对弈

}

If (0==depth)

return Evalute();

if (Max节点) { }

if (Min节点) { }

return value;

for (生成每一个可能的走法) { }

执行走法;

flag=Maxmin(depth-1); 撤销走法; If (flag

value=flag;

for (生成每一个可能的走法) { }

执行走法;

flag=Maxmin(depth-1); 撤销走法; If (flag>value)

value=flag;

//返回评估函数的值

通过观察可以看出,极大值点和极小指点的处理有很多相似之处,产生了很多冗余的代码,为了使代码简洁方便管理,可以做一个小小的处理。我们让Maxmin()函数每次都返回负值,然后在采用极大值点的比较方法flag>value来判断value是否赋值。这样就可以大大地简化代码,伪代码如下:

intMaxmin(int depth) {

If (0==depth)

return Evalute();

for (生成每一个可能的走法)

11

//返回评估函数的值

四川大学本科毕业论文中国象棋人机对弈

}

{ }

执行走法;

flag=-Maxmin(depth-1); 撤销走法; if (flag>value)

value=flag;

这样做没有改变程序的效率,只是使得代码整洁易懂。这种做法也叫做负极大值算法。可能有人会问这样不是改变了返回值,程序的正确性怎样保证。其实要做修正的不仅仅是这里,在评估函数中,当下棋的是Max点时返回负的估值,当下棋的是Min点时依旧返回原来的估值。这样就保证了经过处理的返回值保持不变,这里还需要向评估函数传递一个参数,用来表明当前下棋的是谁。

5.2alpha-beta剪枝算法

上一小节中我们已经讨论过,将一颗博弈树完全展开几乎是不可能的,要找到必胜的第一步也是不可能的。但是如果越靠近博弈树的末端我们可以认为越接近最终局面,也就是说我们希望尽可能的搜索更深的层次,但是搜索的深度和时间的花费是成正比的,我们必须提高搜索算法的效率才能节约更多的时间。这样我们就会想到每次搜索的过程中是不是有很多其实不需要搜索的分支浪费了很多时间。到底哪些分支不需要搜索了,哪些分支需要减掉呢,我们来看下边的分析。

图5.2

12

四川大学本科毕业论文中国象棋人机对弈

如图5.2,我们采用的是从上到下从左到右的深度优先搜索,p(1,1)的值v(1,1)=3,由于p(1)是一个极小值点,它的取值是它所有继承者中值最小的那个点,于是我们可以得到v(1)<=3。再看点p(1,2),当我们搜索到它的第二个子节点时我们通过上述的方法可以得到v(1,2)>=5,也就是说点p(1,2)的值绝对不会比5小。我们再看点p(1),它的值绝对不会比3大,所以它不会取它第二个子节点p(1,2)的值,那么p(1,2)剩余的子节点就不用搜索了。这时就发生了alpha剪枝。

同样地,由于根节点p的值取的是它的子节点中最大的值,由于p(1)=3,那么可以得出p的值v>=3。而p(2)的第一个子节点的值可以推出p(2)的值v(2)<=1,所以p(2)节点剩下的子节点都用搜索了,这样就发生了beta剪枝。下边是融合了alpha-beta剪枝算法的极大值极小值算法的伪代码:

IntMaxmin(intdepth,intalpha,int beta) {

If (0==depth)

return Evalute();

}

传递参数的时候之所以要调换beta和alpha的值,是因为要迎合负极大值算法。应用alpha-beta算法可以省去很多冗余的分支,节省很多时间。在alpha-beta剪枝算法中我们希望剪枝发生越早越好,这就和节点的顺序有关,事实上根据这个思想alpha-beta剪枝算法可以进一步改进。相应的改进方法有静态启发和迭代深化等。

for (生成每一个可能的走法) { }

Return alpha;

执行走法;

flag=-Maxmin(depth-1,-beta,-alpha); 撤销走法; if (flag>alpha)

alpha=flag; break;

if (alpha>=beta)

//返回评估函数的值

5.3 alpha-beta剪枝算法的改进

上面已经说过alpha-beta剪枝算法非常依赖于棋子走法的搜索顺序,如果每次运气都

13

四川大学本科毕业论文中国象棋人机对弈

非常不好,总是先搜索到最坏的走法,那么剪枝永远不可能发生,那么结合了alpha-beta剪枝算法的极大极小值搜索算法就相当于简单的极大值极小值搜索算法。如果每次都搜索到最好的走法,那么alpha-beta算法的效率就接近于数学理论值,搜索的有效分支因子就相当于实际分支因子的平方根。由于在简单的alpha-beta算法中,博弈树中的走法是随机的,alpha-beta算法虽然能达到一定的剪枝效果,但是它还有很大的提升空间。

我们可以尽可能早地去搜索我们认为比较好的走法,也就是可以产生剪枝的走法。我们把之前产生了剪枝的走法记录下来,当遇到下次需要这个走法的时候它也有可能产生剪枝,我们就优先搜索这个走法。我们还可以保存同样的分支,当搜索到同样的分支的时候,前一个分支的走法发生的剪枝也可能使得后一个分支发生剪枝,于是我们可以借鉴先前的走法,优先搜索先前的走法。

当我们使用alpha-beta剪枝算法时,我们常常传递一个无穷大的值beta和一个无穷小的值alpha到函数里面去。我们搜索的时候alpha和beta的值就像一个窗口,凡是不再这个窗口范围的值都被排除,发生了剪枝。我们知道,如果alpha和beta的差值越小越容易发生剪枝,于是我们起初传递的无穷大和无穷小效率不高。我们可以根据上一次的搜索找到一个估计值N,并且找到alpha和beta距离N的波动范围e,于是我们可以传递一个更小的alpha-beta范围为[N-e,N+e]。这样做可能会返回不正确的最大值最小值,但是却大大提高了效率。当返回值不再预测的范围之内时,需要重新进行搜索,这种消耗的时间和提升的效率比起来是值得的。

中国象棋每个局面平均有几十个走法,但是开局和残局区别是非常大的,开局的时候所有的棋子都在,而残局的时候可能就只有个十几个棋子。通常我们搜索的深度根据难度选择的不同会设定一个固定值,这样开局搜索的时间相对来说就会很长,为了照顾开局的搜索时间而设定的搜索深度在残局的时候只需要很短的时间进行搜索,这样就没能够充分的利用时间。于是我们就可以想到在棋局进行的过程中根据实际的情况可以慢慢地增加搜索的深度,这样就可以使得时间得到充分地利用。而在开局的时候我们可以利用开局库和一些定式,比如要尽早出马等,来节约一些搜索的时间。

在前边介绍评估函数的时候我们就说到一个现象,如果我们设定的搜索程度是n层,那么当搜索到n层的时候程序就不会继续搜索了,而这个时候下棋的一方可以吃掉对方的一个棋子,比如说车可以吃掉一个炮,程序就可能认为这是一个巨大的优势从而选择了这个走法。但是这个时候会产生一种情况,那就是当车吃掉炮的时候对方的某一个棋子可能吃掉这个车,这就相当于下棋的一方用车去换了对方一个炮,这是相当不理智的。这种现象被称为水平效应。要规避这种现象有好几种方法。当搜索到设定深度的时候来判断局面时候相对静止,如果不是则继续搜索到相对静止的局面。这个所谓的相对静止的局面就是除了吃子、将军等引起局面非常大的变化的走法。如果父节点和子节点的估值相差过大,也可以选择继续往下搜索。

14

四川大学本科毕业论文中国象棋人机对弈

6. 界面的实现

6.1棋盘区

前边已经介绍过界面的实现用的是微软MFC类库,用的系统开发环境VC++6.0。首先建立一个MFC工程,将不需要菜单栏工具栏去掉,运行一下我们就得到了一个Windows应用程序的基本框架,这是MFC特别方便的地方。

我们首先考虑棋盘区的设计。棋盘区需要一副背景图,下边是在网上找的一副图。

图6.1

位图是一副资源,它有一个ID号为IDB_GROUND。这里需要用到一个类CBitmap,需要把位图资源和一个CBitmap变量关联起来。CBitmap类封装了Windows图形设备接口中的位图,并且提供了操纵位图的成员函数。

CBitmapm_Bitmap_Background;

m_Bitmap_Background.LoadBitmap(IDB_GROUND);

然后再把CBitmap变量和CDC句柄关联起来。CDC类定义的是设备上下文对象的类。CDC对象提供处理器显示器或打印机等设备上下文的函数。通过CDC对象的成员函数进行所有的绘图。

m_Dc_Background.SelectObject(m_Bitmap_Background);

接着用CDC的函数把它画到客户区。所要用到的函数是BitBlt()。

画完背景过后就需要画棋盘了,画棋盘首先要用到画笔,这需要用到一个类CPen,它用来在CD上完成绘制线条的任务。初始化时系统自动提供了一个默认的黑色画笔,如果对这个默认的画笔不满意,可以自己创建画笔来替换它。自定义画笔需要使用CPen类的构造函数,创建自己的CPen类对象。画棋盘需要用到CDC类的几个成员函数Moveto()、Lineto(),Moveto()是将画笔移到起始点,Lineto()是从起始点画一条直线到终点。棋盘

15

四川大学本科毕业论文中国象棋人机对弈

画好过后就是在棋盘上边摆放棋子了,棋子也用位图表示,使用和画背景相同的办法把棋子画到棋盘上。

还有一点值得注意,当窗口移动、遮挡、大小变化的时候都会进行窗口重绘,重绘擦出先前所画的东西,所以我们必须在Ondraw()函数中进行处理,应用程序窗口的客户区进行绘图的所有代码都必须写在这个函数中。

棋盘区画好过后就需要做一些消息响应处理。消息就是指Windows发出的一个通知,告诉应用程序某个事情发生了,在我们这个程序中就是点击鼠标、改变窗口尺寸等。消息本身是作为一个记录传递给应用程序的,这个记录中包含了消息的类型以及其它的信息。我们程序中常常相应的鼠标点击消息,它相对应的结构体就包含了单机鼠标的消息号、单机鼠标时的坐标。当轮到人下棋的时候鼠标左键点击客户区,响应函数会判断在该位置上是否有己方的棋子,只有当己方棋子存在的时候才会发生动作,将该棋子选中,相应地我们还可以给这个选中动作关联一个声音文件。当我们继续点击鼠标左键时,如果依然是己方棋子程序会重新选中这个棋子,如果是空位或者是对方棋子,响应函数会判断按照规则是否可以走到这个位置上或者形成吃子,如果可以的话就会把选中的棋子画到这个位置上,清楚起始位置和终点位置上原来的棋子。当轮到电脑下棋的时候,它是不会响应我们的鼠标点击事件的。

棋盘区还有一个功能,就是在实现读取棋谱的菜单项时,会在棋盘的下方画上两个图片按钮“上一步”、“下一步”,这两个图片按钮会响应鼠标左键点击事件从而来演示棋谱。

6.2菜单项的设计

菜单栏在客户区的上方,主要是实现一些基本的操作和功能。在MFC菜单也是当做一种资源管理的,利用MFC设计菜单非常便捷。我们从左到右一个个介绍每个菜单的选项和功能。

首先是“游戏”菜单,它包括“我先走”、“电脑先走”、“音效”、“退出”四个子菜单。每个子菜单的功能一目了然,“我先走”是代表由人执红棋,“电脑先走”是代表电脑执红棋,“音效”选中时会伴有各种操作棋子的声音,“退出”代表退出游戏,如果你正在棋局中点击“退出”,它会提醒你正在游戏中是否退出程序。当重新选择选择先手的时候,棋盘区的棋子都会回到初始位置。

第二个菜单是“难度”菜单,它包括七个等级“傻瓜”、“菜鸟”、“新手”、“入门”、“业余”、“专业”、“大师”。从前边的章节中我们知道,搜索算法搜索的程度越深,越接近最终局面,我们认为这样得出的走法越高明,这样使用的时间也越多,于是我们通过搜索算法搜索的深度来控制程序的难度、计算机的等级选择。选择任何一个难度都不会改变棋盘区的布局,只会改变当前电脑的策略,也就是说在下棋的过程中可以改变计算机的难度等

16

四川大学本科毕业论文中国象棋人机对弈

级。

第三个菜单是“让子”菜单,包括“让单马”、“让双马”、“让九子”、“被让单马”、“被让双马”、“被让九子”。这个菜单栏的实现相对来说是比较简单的,只需在棋盘上撤掉相应的棋子就行了,当然相应的数据也要作初始化处理。让子菜单中菜单项的选择也会终止当前的棋局。

接下来是“棋谱”菜单栏,它包括“保存棋谱”和“读取棋谱”。保存棋谱是保存从初始状态到当前局面的过程。读取棋谱是读取出保存的棋谱并在棋盘区进行演示。这里需要用到C++对文件的操作。我们在编写程序的时候最密不可分的就是对文件进行相应的操作,我们可以将数据保存到文件,也可以从文件中读取数据。

6.3常用按钮的设计

在棋盘区的右边空白部分将实现一些常用按钮,称为常用按钮区。常用的按钮有三个,悔棋、保存、复盘。三个按钮的实现思路都是采用图片的方式,准备三个位图分别写上对应的功能名称,再把三个位图画到客户区。三个按钮的响应通过判断鼠标左键点击时鼠标的坐标来判断,如果鼠标左击时坐标位于某个按钮内则响应这个按钮。

悔棋是轮到人下棋的时候才有效,它的功能是分别撤销电脑和人的一步棋。保存时保存当前棋盘的格局,它与保存棋谱是不同的。复盘是从保存的棋局状态中选择一个恢复到棋盘去,可以接着当前的棋局继续进行对弈,它与读取棋谱是不同的。这里也要用到C++的文件操作。

17

四川大学本科毕业论文中国象棋人机对弈

7.开局库

上面我们已经多次提到过开局库,开局库就像人的经验一样,在一些固定的棋局中人可能思索的过程很简单,他会根据以往的经验迅速的做出判断。而开局的时候由于局面比较简单,这个时候可以套用一定定式。我们知道开局的时候电脑搜索的时间会更多但是搜索的层数又不是很多,套用开局库可以减少很多时间,也能使得开局很稳定。

我们可以给程序添加开局库组件,包括与开局有关的数据库。一个理想中的开局库会考虑到几乎所有的开局和变化。古人云“靡不有初,鲜克有终”,要想在一盘棋中取得优势并且最终获得胜利,在开局阶段就打下良好的基础这是必不可少的。开局一般是在前十回合左右,双方在这个时候基本上都不会与对方的棋子相接触,更多的是着重布局,抢占地盘,布好阵型,相互制约,蓄势待发。像我们最简单了解地就是要尽快出马出车。

开局库可以说是集结了很多盘棋的经验,它可以使你不会在同一样的招式下吃亏,如果你被某一个招数打败过,你经过研究思考过后是不会再上第二次当的。纯机器搜索的象棋程序是没有结合了很多盘棋的经验的象棋程序强大的。

开局库也有它的局限性,不灵活的开局库会被固定的招式套住,我们知道只有在残局的时候才可能出现必赢的杀招,在棋局开始的时候一切都是变幻莫测的,也就是说任何招数都是可以破解的,所以使用开局库的定式容易被对手抓住利用给你设下圈套。所以在使用开局库的时候一方面除了要不断完善开局库,还要配合机器搜索等各种手段使得象棋程序更加强大。

开局库存储在相应的数据库中,并不断地更新和维护,在开局的时候程序从数据库中进行匹配和调用。

18

四川大学本科毕业论文中国象棋人机对弈

8.系统的实现

由于程序借用了MFC框架编程,MFC为我们提供了五个类,CAboutDlg、CApp、CDoc、CView、CFrame。我们这里把所有的功能用各个函数实现封装在CView类里。

DrawChessboard(CDC*pDC)函数主要用来画棋盘,画棋盘就是一系列画直线的操作,下面是这个函数的代码:

voidCChessView::DrawChessbord(CDC *pDC) {

CPen chessbord1,chessbord2,chessbord3; chessbord1.CreatePen(0,1,RGB(0,0,0)); chessbord2.CreatePen(0,3,RGB(0,0,0)); chessbord3.CreatePen(0,5,RGB(0,0,0)); inti,k;

for (i=0;i<2;i++) {

pDC->SelectObject(&chessbord1); for (k=1;k<5;k++) { }

for (k=1;k<8;k++) { }

pDC->MoveTo(50+60*3,50+i*7*60); pDC->LineTo(50+60*5,50+2*60+i*7*60); pDC->MoveTo(50+60*3,50+2*60+i*7*60); pDC->LineTo(50+60*5,50+i*7*60); if (0==i)

19

pDC->MoveTo(50,50+k*60+i*4*60); pDC->LineTo(50+60*8,50+k*60+i*4*60);

pDC->MoveTo(50+60*k,50+i*5*60); pDC->LineTo(50+60*k,50+4*60+i*5*60);

四川大学本科毕业论文中国象棋人机对弈

}

{ }

if (1==i) { }

pDC->SelectObject(&chessbord2); DrawStar(1,2+i*5,pDC); DrawStar(7,2+i*5,pDC); DrawStar(0,3+i*3,pDC); DrawStar(2,3+i*3,pDC); DrawStar(4,3+i*3,pDC); DrawStar(6,3+i*3,pDC); DrawStar(8,3+i*3,pDC);

pDC->SelectObject(&chessbord3); pDC->MoveTo(50-10,50-10); pDC->LineTo(50-10,50+10+60*9); pDC->MoveTo(50-10,50-10); pDC->LineTo(50+60*8+10,50-10); pDC->MoveTo(50+8*60+10,50-10); pDC->LineTo(50+8*60+10,50+60*9+10); pDC->MoveTo(50-10,50+10+9*60); pDC->LineTo(50+8*60+10,50+10+60*9); pDC->SelectObject(&chessbord2); pDC->MoveTo(50,50); pDC->LineTo(50,50+60*9); pDC->MoveTo(50,50); pDC->LineTo(50+60*8,50); pDC->MoveTo(50+8*60,50); pDC->LineTo(50+8*60,50+60*9); pDC->MoveTo(50,50+9*60); pDC->LineTo(50+8*60,50+60*9);

chessbord1.DeleteObject(); chessbord2.DeleteObject(); chessbord3.DeleteObject();

20

四川大学本科毕业论文中国象棋人机对弈

}

其中DrawStar(intx,inty,CDC*pDC)函数是用来画棋盘上星的,它也是一系列画直线的操作,这里不再列出它的具体实现。

DrawChess(CDC*pDC)函数是用来画棋子的,也就是初始化棋盘棋子布局的,由于棋子是用一个个位图来表示的,所以这是一系列画位图的重复操作,在这个函数里还会对一些变量进行初始化。由于重复代码量繁多,这里列出部分代码:

voidCChessView::DrawChess(CDC *pDC) {

21

inti; m_Start=-1; m_End=-1; m_Back_Start=-1; m_CStart=-1; m_CEnd=-1; m_Back_End=-1; m_Dc_Mask.DeleteDC();

m_Dc_Mask.CreateCompatibleDC(pDC); m_Dc_Mask.SelectObject(m_Mask); for (i=0;i<90;i++) { }

if (0==m_First) {

pDC->BitBlt(20+4*60,20,56,56,&m_Dc_Mask,0,0,MERGEPAINT); pDC->BitBlt(20+4*60,20,56,56,&m_Dc[1],0,0,SRCAND); m_Dc[i].CreateCompatibleDC(pDC); m_Dc[i].SelectObject(m_Bitmap[i]); m_Position[i]=0; m_PB[j]=-1; m_Dc[i].DeleteDC(); for (int j=0;j<33;j++) for (i=1;i<=32;i++) for (i=1;i<=32;i++)

四川大学本科毕业论文中国象棋人机对弈

pDC->BitBlt(20,20,56,56,&m_Dc_Mask,0,0,MERGEPAINT); pDC->BitBlt(20,20,56,56,&m_Dc[2],0,0,SRCAND);

OnDraw(CDC*pDC)函数是程序界面生成或者变化时会被调用的,由于程序界面的变化会导致窗口的重绘,所以必须在这个函数中设置代码重新绘制窗口之前现实的内容。所以这个函数会反复地调用DrawChessboard()函数,并根据各个变量记录的信息绘制棋子。

以上几个函数是界面实现的几个主要函数,它们加上其它的一些小的辅助函数共同绘制出了象棋程序的界面。由于微软的MFC提供了很方便的资源管理器,可以在图形界面的情形下编辑菜单,菜单生成的绝大部分代码是系统为我们写好的,我们只需实现它们的响应就可以了,所以这里就不详细阐述。

Value(int turn)函数是评估函数,它会在搜索的末端被调用,返回当前局面的一个估分。程序中采用最简单的估分方法,以棋子的价值和作为估分的依据。代码如下:

intCChessView::value(int turn) {

inti,j; i=0; j=0;

for (int k=1;k<=32;k++)

if (m_PB[k]!=-1)

switch (k) { case 1:

i+=100000; break; i+=989; break; i+=989; break; i+=439; break; i+=439;

22

case 2:

case 3:

case 4:

case 5:

四川大学本科毕业论文中国象棋人机对弈

break; case 6:

i+=442; break; case 7:

i+=442; break; case 8:

i+=226; break; case 9:

i+=226; break; case 10:

i+=210; break; case 11:

i+=210; break; case 12:

i+=55; break; case 13:

i+=55; break; case 14:

i+=55; break; case 15:

i+=55; break; case 16:

i+=55;

break;

case 17:

23

四川大学本科毕业论文中国象棋人机对弈

j+=100000; break; case 18:

j+=989; break; case 19:

j+=989; break; case 20:

j+=439; break; case 21:

j+=439; break; case 22:

j+=442; break; case 23:

j+=442; break; case 24:

j+=226; break; case 25:

j+=226; break; case 26:

j+=210; break; case 27:

j+=210; break; case 28:

j+=55;

break;

24

四川大学本科毕业论文中国象棋人机对弈

}

case 29: }

j+=55; break; j+=55; break; j+=55; break; j+=55; break;

case 30:

case 31:

case 32:

if (m_First==1 && turn==0)

return (i-j); return (i-j); return(j-i); return (j-i);

if (m_First==0 && turn==1) if (m_First==1 && turn==1) if (m_First==0 && turn==0)

JudgeBing()函数是走法生成时调用来判断起始点到终点是否合理,这个函数是针对“兵”的,其它棋子也类同。

Max(intstep,intturn,intalpha,int beta)函数是运用了alpha-beta算法的极大极小值搜索算法,它其中包含了走法生成的过程,初步生成的起点和终点要调用上述的Judge系列函数判断合理性,当step等于0时调用评估函数。

上面的函数实现了程序的大部分功能,程序经过检验可以正常运行。

25

四川大学本科毕业论文中国象棋人机对弈

9.总结

经过对整个中国象棋计算机游戏的设计构思以及到代码的实现,的确让我学习到很多的东西。在吸取别人的经验之上,结合自己的理解实现了一个可以人机对弈的中国象棋程序。在最开始谈到的象棋棋盘的数据结构,还有很多可以精益求精的方法。我们可以用32个字节来表示32个棋子的位置,可以用每个字节的高四位来表示棋子的横坐标,用低四位来表示棋子的纵坐标,如果棋子被吃掉了我们可以用棋盘外的数据来表示。这样可以省下很多的空间,虽然对于现在的计算机来说这可能是没必要的,但是这可以使得我们追求思维的精致,体味到科学的严谨。

而在象棋程序中最重要的就是搜索算法。极大值极小值算法是给解决计算机的思考模式提供了方法,但是它的效率时不高的。而alpha-beta算法进一步拓宽了这条计算机思索的道路,但它的能力也是有限的,所以我们会用到各种各样的改进来提高计算机的效率,这就是算法的精妙之处。

中国象棋的界面设计借用了MFC框架编程,利用MFC编写Windows应用程序是十分方便的。现在国内已经有了统一地象棋界面,标准的接口,这样有助于各种象棋程序进行交流比赛,而象棋巫师为这一标准的制定作出了努力。

最后也说到了开局库,要想建立一个非常理想的开局库,也就是包含了所有应对走法的开局库是有一定难度的,只有我们不断研究使得开局库更加完善。

中国象棋的计算机研究相对于国际象棋来说会晚很多,但是有越来越多的人投入到了中国象棋的研究之中,即使中国象棋的计算机实现现在还不是很成熟,但是在众多爱好者的共同努力之下,它一定会迅速地发展,它的理论也会得到完善。

26

四川大学本科毕业论文中国象棋人机对弈

参考文献

[1]陆汝钤.人工智能(上册)[M].北京:科学出版社,2002年6月第1版. [2]黄文奇,宋恩民.关于象棋的不败算法[N].华中科技大学学报,2003年5月. [3]王小春.PC游戏编程(人机博弈)[M].重庆:重庆大学出版社,2002.

[4]徐心和,王骄.向中国象棋冠军发起挑战——广泛深入开展计算机博弈研究[A].中国人工智能学会第十一届全国学术年会论文集[C].北京:北京邮电大学出版社,2000年9月.

[5]肖齐英,王正志.博弈树搜索与静态估值函数[J].计算机应用研究,1997,4:74-76. [6]网冠科技.Visual C++.NET小游戏开发时尚编程百例[M] .西安:机械工业出版社,2004. [7]胡达.C++ Builder程序设计范例——中国象棋[M],北京:清华大学出版,2002年1月第5版. [8]危春波.中国象棋系统的研究与实现[D].云南:昆明理工大学,北京:中国书籍出版社,2000年07月. [9]陈建春.Visual C++ 高级编程技术——开发实例剖析[M].西安:电子工业出版社,1999. [10]涂光平等.Visual C++.NET基础教程与上机指导[M].北京:清华大学出版社,2005. [11]伍红兵.Visual C++ 编程深入引导 [M].长春:中国水利水电出版社,2002. [12]陈文伟.智能决策技术[M].北京:人民邮电出版社,1998.

[13]张赜.计算机中国象棋博弈中二次估值方法及其优化的研究[D].辽宁:东北大学,2006. [14]Michael Bowling, Johannes Furnkranz,and Thore Graepel. Machine Learning andgames. Machine Learning, 2006, 63:211-215.

[15]DF Beal, MC Smith. Learning Piece Values Using Temporal Differences. Journal of The International Computer Chess Association, 1997.

[16]马占欣,李亚,陆玉昌.用遗传算法解决博弈问题.河南科学, 2007, 25(2): 273-277. [17]王骄,王涛,罗艳红,等.中国象棋计算机博弈系统评估函数的自适应遗传算法实现.东北大学 学报,2005,126(10):949-952.

27

四川大学本科毕业论文中国象棋人机对弈

声 明

学位论文作者(签名)

论文指导教师(签名) _______________

28

四川大学本科毕业论文中国象棋人机对弈

致谢

29

本文来源:https://www.bwwdw.com/article/ou5p.html

Top