爱恩斯坦棋计算机博弈关键技术研究
发布时间：2020-12-04 07:53
计算机博弈是人工智能领域的重要研究方向之一,被誉为人工智能学科的“果蝇”。爱恩斯坦棋属于完备信息博弈棋种,是一种棋局信息完全透明的博弈类型,即博弈双方在任何时候都能完全掌握当前的棋局信息。然而,它不同于其它的完备信息博弈棋种,在双方行棋过程中需通过投掷骰子来确定可走的棋子,具有随机性,这使博弈系统对棋盘局势的分析和决策带来一定的挑战。自2012年爱恩斯坦棋被列为中国大学生计算机博弈大赛项目之后,国内越来越多的人专注于研究针对爱恩斯坦棋的博弈技术。现有估值函数的研究往往是从进攻、防守和概率三个因素分析局势的优劣,将这些因素以不同权重线性相加来组成估值函数。通过这种方式构造的估值函数一般会受到设计者自身博弈水平的限制,而且很难得到一个最优的权重。此外,搜索算法的研究大多是针对Alpha-Beta搜索算法和期望极大极小搜索算法的改进,但是这些搜索算法过于依赖估值函数,估值函数的好坏决定了整个博弈系统的水平。本文以爱恩斯坦棋为研究对象,研究爱恩斯坦棋计算机博弈的关键技术。在搜索算法方面,本文引入蒙特卡洛树搜索（Monte-Carlo tree search,MCTS）算法,提出了概率启发的并行...
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：76 页
【学位级别】：硕士
【部分图文】：
图１．１论文框架??Ｆｉｇｕｒｅ?１．１?Ｆｒａｍｅｗｏｒｋ?ｏｆ?Ｔｈｅｓｉｓ??第二章爱恩斯坦棋计算机博弈技术
?第二章爱恩斯坦棋计算机博弈相关技术??的价值只可能来源于节点ｂ，便无需再访问子树ｈ和子树ｉ。同样地，在图２．５（ｂ）??中，由于节点ｃ是最大值节点，它的第一个子节点ｇ的值为６，因此节点ｃ的值??总是大于等于６。然而，因为节点ａ是最小值节点，所以它的价值只可能来源于??节点ｂ，无需再访问子树ｈ和子树ｉ。??２．４．２期望极大极小搜索算法??期望极大极小（Ｅｘｐｅｃｔｉｍｉｎｉｍａｘ）算法是极大极小算法的一个变种，用于解??决棋类博弈中出现的随机性问题，在爱恩斯坦棋中有成功的运用。该算法在博弈??树的Ｍａｘ层和Ｍｉｎ层中插入一层用于表不随机事件的Ｃｈａｎｃｅ层，用来模拟随机??事件的发生，评估随机性对节点价值计算带来的影响。?????Ｍａｘ?层???／?Ｎ—???Ｃｈａｎｃｅ?层???＾?Ｊ?／Ｖ?（ｙ?Ｍｉｎ?层??￣?Ｃｂａｎｃｅｍ??－?—???一?一????—???—?－?Ｍａｘ?层??图２．６期望极大极小搜索算法??Ｆｉｇｕｒｅ?２．６?Ｅｘｐｅｃｔｉｍｉｎｉｍａｘ?Ａｌｇｏｒｉｔｈｍ??在图２．６所示的博弈树中
ｉｅ?｛１，２，３，４，５，６１。概率节点的父节点表示此时的棋盘状态，子节点表示随??机事件发生后的结果，即一组新的棋盘状态。为更好地描述博弈树，本文将最大??值节点和最小值节点统称为最值节点（Ｍｉｎ－Ｍａｘ?Ｎｏｄｅ，?ＭＮｏｄｅ）。以图３．１（ａ）所示??的棋盘为例，引入概率节点的博弈树结构如图３．３所示。图中以菱形表示概率节??点，最值节点Ｓ有６个子概率节点，对应６个投骰子事件；概率节点有１个或多??个子最值节点，对应每个合法走法。??Ｑ?？?Ｇ）?Ｇ）??图３．３引入概率节点的博弈树??Ｆｉｇｕｒｅ?３．３?Ｇａｍｅ?Ｔｒｅｅ?ｗｉｔｈ?Ｐｒｏｂａｂｉｌｉｔｙ?Ｎｏｄｅ??从图３．１（ａ）的棋盘中可看出，当骰子投掷到的点数为１、２、３时，可以走动??２号棋子，所以最值节点Ａ、Ｂ和Ｃ与概率节点１、２和３建立连接；当骰子投??掷到的点数为３、４、５、６时，可以走动４号棋子，所以最值节点Ｄ与概率节点??３、４、５和６建立连接。概率节点与最值节点之间不再是一对多的树状结构，而??是多对多的网状结构。因此
【参考文献】：
期刊论文
[1]动态规划求解中国象棋状态总数[J]. 魏印福,李舟军. 智能系统学报. 2019(01)
[2]改进UCT算法在爱恩斯坦棋中的应用[J]. 张小川,李琴,南海,彭丽蓉. 计算机科学. 2018(12)
[3]中国象棋博弈系统实现的关键技术探索[J]. 肖秀春,刘泽伟,陈柏桃. 电子技术与软件工程. 2018(15)
[4]爱恩斯坦棋计算机博弈算法研究与改进[J]. 杨昌杰,陈柯成,刘跃元,王京. 无线互联科技. 2018(15)
[5]爱恩斯坦棋评估策略的研究[J]. 范博奇,丁濛,张芳梓. 智能计算机与应用. 2018(01)
[6]基于爱恩斯坦棋削减随机性影响的博弈算法研究[J]. 黄恩一,丁濛. 智能计算机与应用. 2017(01)
[7]深度强化学习综述[J]. 刘全,翟建伟,章宗长,钟珊,周倩,章鹏,徐进. 计算机学报. 2018(01)
[8]计算机博弈的研究与发展[J]. 王亚杰,邱虹坤,吴燕燕,李飞,杨周凤. 智能系统学报. 2016(06)
[9]AlphaGo技术原理分析及人工智能军事应用展望[J]. 陶九阳,吴琳,胡晓峰. 指挥与控制学报. 2016(02)
[10]六子棋中基于局部“路”扫描方式的博弈树生成算法[J]. 李学俊,王小龙,吴蕾,刘慧婷. 智能系统学报. 2015(02)
博士论文
[1]计算机博弈问题的复杂性、理论解及相关搜索算法研究[D]. 高强.东北大学 2016
硕士论文
[1]爱恩斯坦棋计算机博弈算法的研究与实施[D]. 李琴.重庆理工大学 2018
[2]五子棋计算机博弈系统的研究与设计[D]. 张效见.安徽大学 2017
[3]点格棋博弈中UCT算法的研究与实现[D]. 刘洋.安徽大学 2016
[4]爱恩斯坦棋计算机博弈系统的研究与实现[D]. 光洋.安徽大学 2016
[5]点格棋机器博弈系统的研究与实现[D]. 唐霜霜.安徽大学 2015
[6]并行计算在计算机博弈中的研究与应用[D]. 侯鑫磊.重庆理工大学 2015
[7]基于专家系统和蒙特卡罗方法的计算机围棋博弈的研究[D]. 周明明.南京航空航天大学 2012
[8]基于极大极小搜索算法的亚马逊棋博弈系统的研究[D]. 张柳.东北大学 2010
[9]六子棋中基于BP-TD学习的局面估值方法研究[D]. 李新星.东北大学 2009
本文编号：2897248
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：76 页
【学位级别】：硕士
【部分图文】：
图１．１论文框架??Ｆｉｇｕｒｅ?１．１?Ｆｒａｍｅｗｏｒｋ?ｏｆ?Ｔｈｅｓｉｓ??第二章爱恩斯坦棋计算机博弈技术
?第二章爱恩斯坦棋计算机博弈相关技术??的价值只可能来源于节点ｂ，便无需再访问子树ｈ和子树ｉ。同样地，在图２．５（ｂ）??中，由于节点ｃ是最大值节点，它的第一个子节点ｇ的值为６，因此节点ｃ的值??总是大于等于６。然而，因为节点ａ是最小值节点，所以它的价值只可能来源于??节点ｂ，无需再访问子树ｈ和子树ｉ。??２．４．２期望极大极小搜索算法??期望极大极小（Ｅｘｐｅｃｔｉｍｉｎｉｍａｘ）算法是极大极小算法的一个变种，用于解??决棋类博弈中出现的随机性问题，在爱恩斯坦棋中有成功的运用。该算法在博弈??树的Ｍａｘ层和Ｍｉｎ层中插入一层用于表不随机事件的Ｃｈａｎｃｅ层，用来模拟随机??事件的发生，评估随机性对节点价值计算带来的影响。?????Ｍａｘ?层???／?Ｎ—???Ｃｈａｎｃｅ?层???＾?Ｊ?／Ｖ?（ｙ?Ｍｉｎ?层??￣?Ｃｂａｎｃｅｍ??－?—???一?一????—???—?－?Ｍａｘ?层??图２．６期望极大极小搜索算法??Ｆｉｇｕｒｅ?２．６?Ｅｘｐｅｃｔｉｍｉｎｉｍａｘ?Ａｌｇｏｒｉｔｈｍ??在图２．６所示的博弈树中
ｉｅ?｛１，２，３，４，５，６１。概率节点的父节点表示此时的棋盘状态，子节点表示随??机事件发生后的结果，即一组新的棋盘状态。为更好地描述博弈树，本文将最大??值节点和最小值节点统称为最值节点（Ｍｉｎ－Ｍａｘ?Ｎｏｄｅ，?ＭＮｏｄｅ）。以图３．１（ａ）所示??的棋盘为例，引入概率节点的博弈树结构如图３．３所示。图中以菱形表示概率节??点，最值节点Ｓ有６个子概率节点，对应６个投骰子事件；概率节点有１个或多??个子最值节点，对应每个合法走法。??Ｑ?？?Ｇ）?Ｇ）??图３．３引入概率节点的博弈树??Ｆｉｇｕｒｅ?３．３?Ｇａｍｅ?Ｔｒｅｅ?ｗｉｔｈ?Ｐｒｏｂａｂｉｌｉｔｙ?Ｎｏｄｅ??从图３．１（ａ）的棋盘中可看出，当骰子投掷到的点数为１、２、３时，可以走动??２号棋子，所以最值节点Ａ、Ｂ和Ｃ与概率节点１、２和３建立连接；当骰子投??掷到的点数为３、４、５、６时，可以走动４号棋子，所以最值节点Ｄ与概率节点??３、４、５和６建立连接。概率节点与最值节点之间不再是一对多的树状结构，而??是多对多的网状结构。因此
【参考文献】：
期刊论文
[1]动态规划求解中国象棋状态总数[J]. 魏印福,李舟军. 智能系统学报. 2019(01)
[2]改进UCT算法在爱恩斯坦棋中的应用[J]. 张小川,李琴,南海,彭丽蓉. 计算机科学. 2018(12)
[3]中国象棋博弈系统实现的关键技术探索[J]. 肖秀春,刘泽伟,陈柏桃. 电子技术与软件工程. 2018(15)
[4]爱恩斯坦棋计算机博弈算法研究与改进[J]. 杨昌杰,陈柯成,刘跃元,王京. 无线互联科技. 2018(15)
[5]爱恩斯坦棋评估策略的研究[J]. 范博奇,丁濛,张芳梓. 智能计算机与应用. 2018(01)
[6]基于爱恩斯坦棋削减随机性影响的博弈算法研究[J]. 黄恩一,丁濛. 智能计算机与应用. 2017(01)
[7]深度强化学习综述[J]. 刘全,翟建伟,章宗长,钟珊,周倩,章鹏,徐进. 计算机学报. 2018(01)
[8]计算机博弈的研究与发展[J]. 王亚杰,邱虹坤,吴燕燕,李飞,杨周凤. 智能系统学报. 2016(06)
[9]AlphaGo技术原理分析及人工智能军事应用展望[J]. 陶九阳,吴琳,胡晓峰. 指挥与控制学报. 2016(02)
[10]六子棋中基于局部“路”扫描方式的博弈树生成算法[J]. 李学俊,王小龙,吴蕾,刘慧婷. 智能系统学报. 2015(02)
博士论文
[1]计算机博弈问题的复杂性、理论解及相关搜索算法研究[D]. 高强.东北大学 2016
硕士论文
[1]爱恩斯坦棋计算机博弈算法的研究与实施[D]. 李琴.重庆理工大学 2018
[2]五子棋计算机博弈系统的研究与设计[D]. 张效见.安徽大学 2017
[3]点格棋博弈中UCT算法的研究与实现[D]. 刘洋.安徽大学 2016
[4]爱恩斯坦棋计算机博弈系统的研究与实现[D]. 光洋.安徽大学 2016
[5]点格棋机器博弈系统的研究与实现[D]. 唐霜霜.安徽大学 2015
[6]并行计算在计算机博弈中的研究与应用[D]. 侯鑫磊.重庆理工大学 2015
[7]基于专家系统和蒙特卡罗方法的计算机围棋博弈的研究[D]. 周明明.南京航空航天大学 2012
[8]基于极大极小搜索算法的亚马逊棋博弈系统的研究[D]. 张柳.东北大学 2010
[9]六子棋中基于BP-TD学习的局面估值方法研究[D]. 李新星.东北大学 2009
本文编号：2897248
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2897248.html
