论文天下|会计论文|管理论文|计算机论文|医药学论文|经济学论文|法学论文|社会学论文|文学论文|教育论文|理科论文|工科论文|艺术论文|哲学论文|文化论文|外语论文|格式论文
论文天下
计算机应用论文  计算机理论论文  计算机网络论文  电子商务论文  软件工程论文  操作系统论文  通信技术论文   
五子棋人工智能算法实现研究

五子棋人工智能算法实现研究

五子棋是一种两人对弈的纯策略型棋类游戏,是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为&ldqu;连珠&rdqu;,英译为&ldqu;Renju&rdqu;,英文称之为&ldqu;Gbang&rdqu;或&ldqu;FIR&rdqu;(Five in a R的缩写),亦有&ldqu;连五子&rdqu;、&ldqu;五子连&rdqu;、&ldqu;串珠&rdqu;、&ldqu;五目&rdqu;、&ldqu;五目碰&rdqu;等多种称谓[1]。因其规则简单,变化多端,容易上手,而广受大众喜爱。五子棋游戏不仅能增强思维能力,提高智力,而且富含哲理,有助于修身养性。五子棋游戏规则比较简单,棋盘通常采用类似围棋盘的15路或19路的棋盘,两人分别执黑白两色棋子,轮流在棋盘上选择一个无子的交叉点落子,无子的交叉点又被称为空点或合法点,当黑白一方有五个棋子在横、竖或斜方向上连接成一线即为该方赢。
  人工智能(Artifiial Intelligene,AI),是计算机科学的一个分支,是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的综合性的技术科学。该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等,而博弈是人工智能研究的一个重要分支。它不仅存在于游戏、下棋之中,也存在于政治、经济、军事和生物竞争中。与其他棋类游戏相比,五子棋游戏每一层棋局搜索节点数量庞大,规则简单,更便于深入研究博弈算法。本文以五子棋游戏为研究对象,采用Alpha-Beta剪枝和最大最小树原理,优化了博弈树搜索过程,通过控制搜索深度,实现了初级和高级的人机对弈。此外,本文还对优化五子棋智能算法的思路做出了初步探讨。
  一、 五子棋传统算法
  1.人机博弈传统算法。
  解决博弈问题的传统算法是搜索树法,也叫博弈树法。以甲乙两人对弈五子棋为例,假定现在该甲走棋且甲有若干种走法,而对甲的任一走法,乙也可以有与之对应的不同的多种走法,然后又轮到甲走棋,而对乙的走法甲又有若干种方法应对,如此反复。显然,可以从当前棋局状态(根节点)出发,找出所有可能的乙的走法(子节点),再从每个子节点出发找出甲对应于每个乙的走法的所有应对(子子节点),直到出现一方赢局。由此构成的树,就称为博弈树。对于19*19的棋盘而言,显然这是一个典型的指数复杂度问题,其计算量之大是目前所有的计算机都无法承受的。因此,用搜索树法来解决人机博弈时,通常只能搜索到一个非常有限的深度,并根据此有限深度的形势来判断每种走法的优劣,从而选择较优位置下子。
  2. 极小极大值算法(inax 算法)。
  极小极大算法[3]是考虑双方对弈本文由论文联盟.Ll.收集整理若干步之后, 从可能的走法中选一步相对好的来走。若最大(AX)节点为己方下的棋,此时选择估值最大的点走。最小(IN)节点为对方下的棋,此时选择估值最小的点行走。因此IN节点的父节点(AX节点)所赋的倒推值等于端节点估值中的最大值。另一方面,AX节点的父节点(IN节点)所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值,直至起始节点的后继节点也被赋以倒推值为止,即从下往上逐层交替使用极小极大的选值方法。但当搜索深度增加时,搜索节点快速大幅增加,时间和内存空间消耗太大,且利用先前信息的效率较低。于是人们在极小极大的基础上提出了α-β剪枝技术。
  3. α-β剪枝算法。
  α-β剪枝算法[2]是在极大极小算法的基础上,当甲向下搜索节点时发现走第一个子节点就可以赢了,则剩下的节点就不需要再搜索,甲的值就是第一个子节点的值。即可以将甲的其余后继节点抛弃,此过程称为剪枝。如果甲所在的层是AX 节点的层,则称此剪枝为α剪枝,否则成为β剪枝。如图1左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值,方形框节点代表计算机走,圆形框节点代表人走。A节点表示计算机走,由于A是极大值点,根据极小极大搜索原理它要从B和当中选最大的值。假设目前已经通过估值得出B为18,当搜索节点时,因为是该人走,所以根据极小极大搜索原理要从D、E、F中选取最小的值。此时如果估出D为16,那么的值必小于或等于16。又因为已经得出B的值为18,说明节点A的值为ax(B,)=18,也就是说无须求出节点的其他子节点如E、F的值就可以得出父节点A的值。这种将节点D 的后继兄弟节点剪去的方法称为Alpha剪枝。

未完...点击下方链接下载完整文档

五子棋人工智能算法实现研究

五子棋人工智能算法实现研究 五子棋是一种两人对弈的纯策略型棋类游戏,是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为连珠,英译为Renju,英文称之为Gbang或FIR(Five in a R的缩写),亦有连五子、五子连、串珠、五目、五目碰等多种称谓[1]。
  • 上一篇:计算机游戏中的人工智能技术
  • 下一篇:计算机人工智能识别技术应用瓶颈分析
  • 面向对象数据库理论设想
    基于人工智能的银行信贷风险决策
    光纤光缆和通信电缆技术发展与思
    研究生阶段计算机网络理论课程教
    浅谈行为引导教学方法在《计算机
    浅谈对程序开发中异常的理解和认
    渐开线圆柱齿轮几何参数计算的计
    刍议防火墙的合理使用(1)
    企业电子商务系统的规划与设计研
    基于GP算法的知识发现系统
    有关计算机软件数据接口的应用研
    大芯数OPGW在浙江电网的应用
    青年教师在医学微生物学留学生教
    浅谈Intranet在现代企业中的应用
    电子政务人员培训的问题与建议(1
    人工智能导论课程的兴趣教学法
    房租VS人工智能
    研究生人工智能课程教学探索
    人工智能和人机大战简史
    基于人工智能的计算机辅助教学
    “人工智能”比人做得更好:人
    开启新人机交互时代小i机器人
    浅析人工智能在中小学信息技术
    人工智能宇宙飞船可取代人类执
    基于人工智能的计算机辅助教学
    | 设为首页 | 加入收藏 | 联系我们 | 论文发表

    Copyright 2006-2020 © 论文天下 All rights reserved 本站所有内容均由SPider自动索引,如有侵权请联系QQ:2486851删除