没有合适的资源?快使用搜索试试~ 我知道了~
六子棋计算机博弈系统的研究与实现.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 78 浏览量
2022-06-12
13:28:48
上传
评论
收藏 351KB DOC 举报
温馨提示
试读
14页
六子棋计算机博弈系统的研究与实现.doc
资源推荐
资源详情
资源评论
. . . .
六子棋计算机博弈系统的研究与实现
摘要:本文简述了目前计算机博弈技术的开展状况,通过将六子棋游戏作为计算机博弈技术的研究平台,
提出了六子棋计算机博弈的概念。通过对国外相关研究现状的综述,指出本课题研究的意义。通过借鉴国
际象棋和中国象棋计算机博弈中的成熟技术,提出了建立六子棋计算机博弈系统的关键技术。
关键词:人工智能;六子棋计算机博弈;状态表示;着法生成;棋局评估;博弈树搜索;开局库
1 引言
人工智能诞生 50 周年以来,在知识工程、模式识别、机器学习、进化计算、专家系统、
自然语言处理、数据挖掘、机器人、图象识别、人工生命、分布式人工智能等各个领域得
到了蓬勃的开展
[1]
。计算机博弈作为人工智能领域的一个重要分支,也得到了极其快速的
开展,并为人工智能带来了很多重要的方法和理论,同时也产生了广泛的社会影响和学术
影响以与大量的研究成果。博弈就是对策
[2]
,是自然界中的普遍现象,它不仅存在于游戏 、
下棋之中,而且存在于政治、经济、军事和生物竞争中,博弈的参加者可以是个人、集体
某类生物或机器,他们都力图用自己的智力去击败对手。表达计算机博弈技术的各种棋类
游戏在其博弈技术研究中已取得相当丰硕的成果,且各种棋类游戏的计算机博弈系统也日
趋完善,根本上能达到大师级水平。六子棋作为最近两年才兴起的棋类游戏,其计算机博
弈技术和算法的研究相对较少
[3]
。
2 六子棋计算机博弈的研究意义
人们常常把计算机博弈描述为人工智能的果蝇,即人类在计算机博弈的研究中衍生了
大量的研究成果,这些成果对更广泛的领域产生了重要影响。通过博弈问题来研究人工智
能典型问题,具有以下的优点
[4]
:
〔1〕博弈问题局限在一个小的有典型意义的围,研究容易深入。
〔2〕博弈问题非常集中的表达了人类的智能,已经足以为现实世界提供新的方法和新
的模型。
〔3〕专家经验容易获取。
〔4〕进展可以准确的展示和表现出来,不同方法和模型的优缺点也容易比拟。
用一棵树来表示棋局开展的种种可能性,这种树叫做博弈树。根节点表示对局的开始
状态,每一种可能的走法造成的结果作为其子节点,而对每一个这样的子节点,考虑另一
方的各种可能应对,作为下一层的子节点,这样一直找下去就得到了博弈树。它是一棵与
或树。这是一个典型的指数复杂性问题,如何在这棵树上有效的搜索,找出最正确或满意
的目标,是研究的主要问题。
由于机器速度和存储空间的限制,这种搜索只能进展到某一深度,得到一个 层的子
树。对于这一子树的叶节点进展某种评价,然后用搜索的方法找出最优解或满意解,这就
是计算机博弈的主要方法。
在博弈研究的早期阶段,人们使用这种方法研究博弈问题,主要的研究容是
[5][6]
:
〔1〕评价的效率更高,评价要花费时间和空间的代价,如何建立有效、快速的评价函
数和评价方法。
〔2〕找最正确解〔在生成的子树上〕的过程更为有效,由此开展了各种搜索法。
在五、六十年代,博弈研究是人工智能研究的带头领域,Alpha-Beta 剪枝、启发搜索
[7]
最初就是由博弈树的研究开展而来的。专家系统
[8]
的方法出现以后,研究者在产生树的过
程中引入专家知识,使得不必要的节点不再产生,并以此来改良程序的效率。博弈研究的
1 / 14
. . . .
另一个成果是在六十年代就引入了机器学习
[9]
,使机器自己不断改良自己的博弈水平:
〔1〕最简单的学习是改良评价函数的一些参数,使之更加准确和实用。
〔2〕记忆自己和别人的错误,不再犯已犯过的错误。
〔3〕记录一些常见的形状和模式,以便找出局部最好的应对。
〔4〕自己学习规那么。
这些研究对于人工智能的开展起了很大的推动作用。不完备信息博弈的研究还推动了
不准确信息、模糊信息推理和复杂环境决策的研究过程。由于博弈不能防止搜索,而搜索
对时间的要求较高,所以博弈一直是研究并行算法、并行体系结构的工具。
人们通过博弈的研究还提出了认知心理学上的很多新课题,对认知心理学产生了影响。
有些博弈项目为一些新模型与新方法的研究提供了帮助。例如,Backgammon 就对神经网
络的开展做出了贡献。
计算机博弈中指定决策和选择决策,与政治、军事、经济、日常生活中的决策有很多
类似之处,是一种典型的决策系统,所以它的研究对于建立现实社会的决策支持系统有很
强的参考价值。也因此,在国外计算机博弈研究项目经常得到军方和政府机构的支持和赞
助。
随着人工智能技术的不断开展与深入,更多学者将各种棋类游戏利用计算机程序实现
对弈,如中国象棋、五子棋、西洋跳棋、桥牌、麻将等。六子棋是继五子棋公平性问题
[10]
之后,由吴毅成教授发明,现正逐渐兴起。
六子棋作为一种新颖的棋类游戏,由于它的特殊性,每次每方下两颗棋子。直观地看,
其状态空间复杂度和博弈树的复杂度会成倍地提高,同时必须考虑两步棋的综合效用,即
综合评估,在搜索算法上必须做到“两步〞作为“一步〞处理,即综合搜索。六子棋计算机
博弈和其他棋类的计算机博弈一样,都会用到一些最根本的搜索算法、模式识别与智能方
法,并且可以采用一些开展较为成熟的计算机博弈技术。对六子棋计算机博弈的研究,不
但能促进六子棋这项运动的开展,而且更能进一步推动计算机博弈理论的开展。
在计算机日益普与和大众化的现代社会,高水平的博弈系统很容易获得可观的商业价
值,目前,世界领先的计算机围棋程序根本上都是商业产品。事实上,个人计算机软件市
场的大约 80%销售额是来自游戏软件,其中有传统的博弈游戏,而非博弈游戏中也不可缺
少人工智能与博弈的成分。
3 六子棋计算机博弈在国外的研究现状
3.1 计算机博弈研究开展简史
计算机博弈,简单的说,就是让计算机像人一样从事需要高度智能的博弈活动。研究
者们从事研究的计算机博弈项目主要有国际象棋、围棋、中国象棋、五子棋、西洋跳棋、
桥牌、麻将、Othello、Hearts、Backgammon、Scrabble 等
[11]
。六子棋是继五子棋公平性问
题之后逐渐兴起了一款棋类游戏。其中二人零和完备信息博弈的技术性和复杂性较强,是
人们研究博弈的集中点。二人零和随机性研究的一个代表是 Backgammon,并且产生了很
大影响。桥牌是研究不完备信息下的推理的好方法。高随机性的博弈项目趣味性很强,常
用于娱乐和赌博,是研究对策论和决策的好例子。
近代计算机博弈的研究是从四十年代后期开始的,国际象棋是影响最大、研究时间最
长、投入研究精力最多的博弈项目,成为计算机博弈开展的主线。
1950 年 C.Shannon 发表了两篇有关计算机博弈的奠基性文章〔Programming a Computer
for Playing Chess 和 A Chess-playing Machine〕,其中提出了“极大-极小算法〞(Minimax
Algorithm ),奠定了计算机博弈的理论根底。随后,A.Turing 完成了一个叫做 Turochamp
的国际象棋程序,但这个程序还不能在已有的计算机上运行。1956 年 Los Alamos 实验室的
2 / 14
. . . .
研究小组研制了一个真正能够在 MANIAC-I 机器上运行的程序〔不过这个程序对棋盘、棋
子、规那么都进展了简化〕。
1957 年 Bernstein 利用深度优先搜索策略,每层选七种走法展开对局树,搜索四层,他
的程序在 IBM704 机器上操作,能在标准棋盘上下出合理的着法,是第一个完整的计算机
国际象棋程序
[12]
。
1958 年,人工智能界的代表人物 H.A.Simon 预言
[13]
:“计算机将在十年赢得国际象棋比
赛的世界冠军〞。当然,这个预言过于乐观了。
1967 年 MIT 的 Greenblatt 等人在 PDP-6 机器上,利用软件工具开发的 Mac Hack VI 程
序,参加麻省国际象棋锦标赛,写下了计算机正式击败人类选手的记录
[12]
。
从 1970 年起,ACM Association for Computing Machinery 开始举办每年一度的全美计
算机国际象棋大赛。从 1974 年起,三年一度的世界计算机国际象棋大赛开始举办
[14]
。
1981 年, CRA YBL ITZ 新的超级计算机拥有特殊的集成电路, 预言可以在 1995 年击败
世界棋王。1983 年, Ken Thompson 开发了国际象棋硬件 BELL E,达到了大师水平
[15]
。
80 年代中期,美国的卡基梅隆大学开始研究世界级的国际象棋计算机程序—“深思〞
[16]
。1987 年,“深思〞首次以每秒 75 万步的思考速度露面, 它的水平相当于拥有国际等级分
为 2450 的棋手.。1988 年,“深思〞击败丹麦特级大师拉尔森。1989 年,“深思〞已经有 6 台信
息处理器, 每秒思考速度达 200 万步, 但在与世界棋王卡斯帕罗夫进展的“人机大战〞中, 以 0
比 2 败北。
1997 年,由 1 名国际特级大师, 4 名电脑专家组成的“深蓝〞小组研究开发出“更深的
蓝〞,它具有更加高级的“大脑〞,通过安装在 RS/6000S 大型计算机上的 256 个专用处理
芯片, 可以在每秒钟计算 2 亿步, 并且存储了百年来世界顶尖棋手的 10 亿套棋谱, 最后“超级
深蓝〞以 3.5 比 2.5 击败了卡斯帕罗夫,成为人工智能领域的一个里程碑
[17]
。
在其它博弈项目上,1962 年 Samuel 等人利用对策理论和启发式搜索技术编制的西洋
跳 棋 程 序 战 胜 了 美 国 的 州 冠 军 。 1979 年 H.Berliner 的 程 序 BKG9.8 以 7 比 1 战 胜 了
Backgammon 游 戏 的 世 界 冠 军 Luigi Villa 。 1980 年美 国 西 北 大 MikeReeve 的 程 序 The
MOOR 战胜了 Othello 世界冠军
[18]
。1989 年第一届计算机奥林匹克大赛在英国伦敦正式揭
幕,计算机博弈在世界上的影响日益广泛
[19]
。
3.2 计算机博弈关键技术开展现状
机器博弈被认为是人工智能领域最具挑战性的研究方向之一。国际象棋的计算机博弈
已经有了很长的历史,并且经历了一场波澜壮阔的“搏杀〞,“深蓝〞计算机的胜利也给人
类留下了难以忘怀的记忆。在国际象棋成熟技术的根底上,结合中国象棋和五子棋计算机
博弈已有的研究成果,总结出计算机博弈系统的关键技术为:棋局表示、着法生成、棋局
评估、博弈树搜索。
3.2.1 棋局状态表示
要让计算机下棋首先需要解决的是棋盘和棋局的数字表示。以中国象棋
[20]
为例,需要
对棋盘、兵种、棋子、棋盘状态和比特棋盘进展表示。棋盘上面有 9 路 10 行形成 90 个交
叉点,它很容易用 10 9 的棋盘数偶矩阵 表示与坐标的对应关系。 矩阵就是对棋
盘的数偶表示。
3 / 14
剩余13页未读,继续阅读
资源评论
智慧安全方案
- 粉丝: 3658
- 资源: 59万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 88-520告白(520气球).zip
- HTML+CSS+JS精品网页模板H126.rar
- n.cpp
- jdk-8u411-windows-x64下载安装可用
- vgg模型-图像分类算法对水果识别-不含数据集图片-含逐行注释和说明文档.zip
- KMP算法(Knuth-Morris-Pratt算法
- vgg模型-python语言pytorch框架训练识别化妆品分类-不含数据集图片-含逐行注释和说明文档.zip
- KMP算法(Knuth-Morris-Pratt算法
- shufflenet模型-基于人工智能的卷积网络训练识别狗的表情-不含数据集图片-含逐行注释和说明文档.zip
- EPIC Fantasy Town 1.0
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功