没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
11页
随着人工智能的火热,机器游戏变得越来越熟悉。机器博弈是人工智能领域最具挑战性的研究方向之一。亚马逊国际象棋是机器游戏领域的一个重点研究方向,由于其本身动作空间可能概率的复杂性,第一步便超过2000个动作,因此常被用来研究与机器博弈相关的算法。本文针对亚马逊国际象棋环境,对比分析了不同算法在效率上的优缺点,主要对蒙特卡洛博弈算法及其并行优化进行介绍和总结,在此基础上,对关于亚马逊棋蒙特卡洛博弈算法并行优化的研究前景进行了展望。 主要内容为关于亚马逊棋的蒙特卡洛博弈算法的并行优化综述,对相关内容进行了调研和总结,首先是引言部分,简要介绍亚马逊棋的相关知识,其次介绍应用于亚马逊棋的相关博弈算法,如:极大化极小法(MiniMax)、Negamax算法、PVS算法和Alpha-Beta等搜索算法。适用于研究计算机领域、人工智能领域的用户下载研究使用,该文章为原创,严禁盗用抄袭,如有发现,将追究侵权责任,同时涉及学术不端问题。 此前将该文档借与他人浏览,所发布本文档目的在于:避免被学术不端者盗用。
资源推荐
资源详情
资源评论
关于亚马逊棋蒙特卡洛博弈算法并行优化的综述
摘要
亚马逊国际象棋是机器游戏领域的一个重点研究方向,由于其本身动作空间
可能概率的复杂性,第一步便超过 2000 个动作,因此常被用来研究与机器博弈
相关的算法。本文针对亚马逊国际象棋环境,对比分析了不同算法在效率上的优
缺点,主要对蒙特卡洛博弈算法及其并行优化进行介绍和总结,在此基础上,对
关于亚马逊棋蒙特卡洛博弈算法并行优化的研究前景进行了展望。
关键词:计算机博弈论、亚马逊棋、人工智能、蒙特卡洛搜索树
一、 引言
随着人工智能的火热,机器游戏变得越来越熟悉。机器博弈是人工智能领域
最具挑战性的研究方向之一。亚马逊象棋机游戏就是让电脑玩亚马逊象棋[1]。
由于亚马逊象棋的复杂性介于象棋和围棋之间,亚马逊象棋很少用于人与人之间
的博弈,而是经常用于以亚马逊象棋为载体,进行计算机博弈算法的研究[2]。
目前已经出现了多种搜索算法来解决亚马逊棋的博弈问题,随着机器学习和人工
智能的出现,强化学习也开始应用于亚马逊棋人机博弈问题的解决。本文主要是
针对亚马逊棋中的蒙特卡洛博弈算法及其并行优化进行介绍,同时简要介绍其他
算法,并将不同算法进行对比,得出各自优缺点及特点。
本文的主要结构如下:第二部分主要介绍亚马逊棋及其相关的常见博弈算法,
并对不同博弈算法进行对比研究和分析,总结出不同算法的优缺点。第三部分主
要针对亚马逊棋中最经典的蒙特卡洛博弈算法进行介绍,重点介绍蒙特卡洛博弈
算法及其并行优化策略。最后,对本文内容进行概括总结,并对关于亚马逊棋的
蒙特卡洛博弈算法及其并行优化的研究前景进行展望。
二、 亚马逊棋及其常见博弈算法
亚马逊象棋是阿根廷人 Zamkauskas 发明的一种特殊国际象棋,是一种与国
际象棋规则相似的封闭式游戏[3]。如图 1 所示,亚马逊有一个 10 x 10 的棋盘,
每边有四块棋子[4]。当一方移动时,它必须移动其四个部分中的任何一个,并
且每个移动都分两步完成。第一步是移动碎片。第二步是放置箭头并设置箭头。
在上一步中,箭头从移动片段的当前位置释放。箭头设置规则与国际象棋的移动
规则相同,设置后不能进行移动。当任何一方的四块棋子无法再移动时,该方被
判定为负数,游戏结束。
图 1 亚马逊棋的初始棋盘
由于亚马逊棋是一类最优策略选择类问题,因此可以用常用的最优化问题解
决算法来求解,如蒙特卡洛算法、模拟退火法和遗传算法等,也可以使用常见的
人机博弈算法,如极大化极小算法(MiniMax)、Negamax 算法、PVS 算法和 Alpha-
Beta 等搜索算法。
MiniMax 算法的核心思想是最小化最大情况,即:决策使得最差的情况出现
概率最小。该算法一般用于零和博弈游戏中,通过递归形式来最小化对手的最大
收益情况。通过树形结构的形式,每个节点的子节点和父节点都是对方玩家,所
有的节点被分为极大值节点(我方)和极小值节点(对方)。该算法的最大缺点
就是容易造成数据冗余,增加计算量和算法复杂度,冗余一般会出现两种情况:
极大值冗余和极小值冗余。
Negamax 算法是 MiniMax 算法的优化[5],Negamax 算法的思路是:在博弈
树中,我方要选择评价值最大的节点,对方要选择评价值最小的节点(评价值越
小,越不利于一边,这样棋的实力才能提高)。为了统一搜索过程中对最大值和
最小值的判断,评估功能需要对博弈双方敏感,算法采用取双方负值的形式消除
差异,使代码形式美观简洁。
在搜索 Negamax 算法的过程中,存在一定数量的数据冗余。以亚马逊象棋
为例:假设现在轮到 A 了,在游戏树搜索过程中,A 发现在招式序列中有一招
可以挡住 B 的全部,也就是有一步就能赢得胜利。此步骤是 A 最有价值的节点,
其余节点不必继续搜索。此过程可以放弃大量不影响结果的冗余节点。
图 2 是两层游戏树的片段。假设叶节点 E、F 和 G 估计分别为 9、8 和
5,则很容易知道节点 B 的值为 8。如果节点 G 的值为 5,则节点 C 的估计值
最多为 5,这小于其同级节点 B 的估计值,因此根节点 A 的值必须为 8。可以看
出,节点 G 的兄弟节点根本不用搜索,节点 H 相当于从游戏树上剪下来。这是
Alpha 修剪,该方式可以解决上文提到的极大值冗余问题。
图 2 Alpha 修剪示例
当图 2 中的框节点采用最小值时,圆形节点采用最大值。假设节点 E、F
和 G 的估计值分别为 9、8 和 15,则很容易知道节点 B 的值为 9。节点 G
的值为 15,节点 C 的估计值至少为 15,这大于其同级节点 B 的估计值,因
此根节点 A 的值必须为 9。可以看出,节点 G 的兄弟节点不必搜索,这相当于
从游戏树中切下了节点 H,这是 Beta 修剪,该方式可以解决上文提到的极小值
冗余问题。
剩余10页未读,继续阅读
资源评论
Joker_CSDNID
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功