改进UCT算法在爱恩斯坦棋中的应用

doi:10.11896／j.issn.1002-137X.2018.12.032

计算机科学 ›› 2018, Vol. 45 ›› Issue (12): 196-200.doi: 10.11896／j.issn.1002-137X.2018.12.032

改进UCT算法在爱恩斯坦棋中的应用

张小川¹, 李琴¹, 南海¹, 彭丽蓉²

(重庆理工大学计算机科学与工程学院重庆400054)¹
(重庆工业职业技术学院科研处重庆401120)²

收稿日期:2017-11-20 出版日期:2018-12-15 发布日期:2019-02-25
作者简介:张小川(1965-),男,教授,主要研究方向为人工智能、机器博弈、软件工程等,E-mail:zxc@cqut.edu.cn;李琴(1992-),女,硕士生,主要研究方向为人工智能、机器博弈等,E-mail:654704323@qq.com(通信作者);南海(1982－),男,讲师,主要研究方向为人工智能、机器博弈、图像数字水印等,E-mail:cqu.nn@163.com;彭丽蓉(1983-),女,副教授,主要研究方向为计算机网络等。
基金资助:
本文受国家自然科学基金-青年科学基金项目(61502065),重庆市基础科学与前沿技术研究计划项目(cstc2015jcyjA40041),重庆市重庆理工大学研究生创新基金(YCX2016238)资助。

Application of Improved UCT Algorithm in EinStein Würfelt Nicht! Computer Game

ZHANG Xiao-chuan¹, LI Qin¹, NAN Hai¹, PENG Li-rong²

(College of Computer Science and Engineering,Chongqing University of Technology,Chongqing 400054,China)¹
(Scientific Research Department,Chongqing Industry Polytechnic College,Chongqing 401120,China)²

Received:2017-11-20 Online:2018-12-15 Published:2019-02-25

摘要/Abstract

摘要： UCT(Upper Confidence Bound Apply to Tree)算法是蒙特卡罗搜索算法的延展,因其鲁棒性强而受到广泛关注,且被应用于计算机博弈系统。爱恩斯坦棋是近年国内博弈大赛引进的新棋种,在竞赛中投骰子所引发的随机性和娱乐性吸引了广大学者的目光。从全局优化着法角度出发,在爱恩斯坦棋博弈系统中引入UCT算法。首先,针对当前计算机多核现状,利用并行计算方法进一步优化UCT算法;其次,针对UCT算法的最优着法需求,引入当前估值因子(WINK)和次优节点平衡因子(UCTK),以此辅助增加估值的精确度,决策胜率与着法的优先关系,提高算法的收敛效率;最后,构造了爱恩斯坦棋博弈系统,通过与基于极大极小算法、α-β算法以及蒙特卡罗算法的爱恩斯坦棋博弈系统进行机-机对弈,其胜率提高了25%,并在全国计算机博弈大赛中获冠军,这进一步验证了改进算法的有效性。

关键词: UCT算法, 爱恩斯坦棋, 并行计算, 平衡优化

Abstract: UCT (Upper Confidence Bound Apply to Tree) algorithm,as the extension of Monte Carlo search algorithm,is widely concerned and applied to computer game system because of its strong robustness.EinStein würfelt nicht! game is a new kind of game introduced in the domestic game competition in recent years,and the randomness and entertainment of throwing the dice in the competition attracts the participation of the majority of scholars.From the perspective of global optimization method,UCT algorithm was introduced to apply in EinStein würfelt nicht! game system.Firstly,the UCT algorithm is further optimized by using the parallel computing method based on the current state of multi-core computer.Secondly,the current winning factor (WINK) and the optimal node selection factor (UCTK) are introduced to optimize the optimal relationship between the decision winning percentage and the move.Finally,a complete EinStein würfelt nicht! game system is constructed.The winning percentage is improved by 25% by computer-computer game with the game system based on the Minimax algorithm,α-β algorithm and Monte Carlo algorithm,and it has won the champion in the National Computer Game Contest,which further validates the effectiveness of the algorithm.

Key words: Balance optimization, EinStein würfelt nicht! game, Parallel computing, UCT algorithm

中图分类号:

TP391

张小川, 李琴, 南海, 彭丽蓉. 改进UCT算法在爱恩斯坦棋中的应用[J]. 计算机科学, 2018, 45(12): 196-200. https://doi.org/10.11896／j.issn.1002-137X.2018.12.032

ZHANG Xiao-chuan, LI Qin, NAN Hai, PENG Li-rong. Application of Improved UCT Algorithm in EinStein Würfelt Nicht! Computer Game[J]. Computer Science, 2018, 45(12): 196-200. https://doi.org/10.11896／j.issn.1002-137X.2018.12.032

参考文献

[1]WANG Y J,QIU H K,WU Y Y,et al.Research and development of computer games[J].CAAI Transantions on Intelligent Systems,2016,11(2):788-798.(in Chinese)
王亚杰,邱虹坤,吴燕燕,等.计算机博弈的研究与发展[J].智能系统学报,2016,11(6):788-798.
[2]LORENTZ R J.An MCTS Program to Play Einstein Würfeltnicht![M]∥Advances in Computer Games.Springer Berlin Heidelberg,2011:52-59.
[3]GULATI V.Gaming algorithms applied to EinStein würfeltnicht![D].Los Angeles:California State University,Northri-dge,2013.
[4]LI XJ,GUANG Y,ZHANG Y W.An Offensive and Defensive EXpect Minimax Algorithm in EinStein Würfelt Nicht![C]∥Control and Decision Conference.IEEE,2015:5814-5817.
[5]ALTHÖFER I,VOIGT R.EinStein würfelt nicht[M]∥Spiele,Rätsel,Zahlen.Springer Berlin Heidelberg,2014:41-47.
[6]LI Z Y,LI S Q,GU L,et al.Eenstein Chess Algorithm Design and Analysis[J].Information Technology and Informatization,2014(1):111-114.(in Chinese)
李占宇,李淑琴,顾磊,等.爱恩斯坦棋算法设计与分析[J].信息技术与信息化,2014(1):111-114.
[7]ZHOU W M,LI S Q.The Research os Static Algorithms inWTN Chess[J].Computer Knowledge and Technology,2014(5):161-165.(in Chinese)
周文敏,李淑琴.爱恩斯坦棋静态攻防策略的研究[J].电脑知识与技术,2014(5):161-165.
[8]RUI X X,WANG Y L.Application of UVT-RAVE algorithm in multi-player games with imperfect imformation[J].Computer Engineering and Design,2012,33(3):1136-1139.(in Chinese)
芮雄星,王一莉.UCT.RAVE算法在多人非完备信息博弈中的应用[J].计算机工程与设计,2012,33(3):1136-1139.
[9]ZHANG J,WANG X,WU S,et al.Modified UCT Algorithm with Risk Dominance Methods in Imperfect Information Game[C]∥Applied Mechanics and Materials.Trans Tech Publications,2014:367-376.
[10]ZHANG J J,WANG X.Study of the risk analysis of machine game and its estimation method.
[J].High Technology Letters,2013,23(9):965-972.(in Chinese)
张加佳,王轩.机器博弈风险分析及其估算方法的研究[J].高技术通讯,2013,23(9):965-972.
[11]TOM D,MÜLLER M.A Study of UCT and Its Enhancements in an Artificial Game[M]∥Advances in Computer Games.Spinger Berlin Heidelberg,2009:55-64.
[12]WANG Y,HUANG S,XIONG R,et al.A framework for multi-session RGBD SLAM in low dynamic workspace environment[J].CAAI Transactions on Intelligence Technology,2016,1(1):90-103.
[13]ZHOU Y,DENG L,XIE Y.Analysis of a Game Playing Algorithm for Five-in-a-Row[J].Modern Computer,2017(10):8-10.(in Chinese)
周洋,邓莉,谢煜.一种五子棋博弈算法的分析[J].现代计算机,2017(10):8-10.
[14]ZHU L M.Strategy research on artificial intelligence heuristicsearch[J].Electronic Design Engineering,2013,21(16):61-64.(in Chinese)
朱龙梅.浅论人工智能启发式搜索策略的研究[J].电子设计工程,2013,21(16):61-64.
[15]BAUDRY G,MACHARIS C,VALLÉE T.Range-based Multi-Actor Multi-Criteria Analysis:A combined method of Multi-Actor Multi-Criteria Analysis and Monte Carlo simulation to support participatory decision making under uncertainty[J].European Journal of Operational Research,2018,264(1):257-269.
[16]WANG Y J,WANG X Y,QIU H K,et al.A Case Design ofProgram Design Course based on Enstein[J].Computer Education,2012(18):75-77.(in Chinese)
王亚杰,王晓岩,邱虹坤,等.基于爱恩斯坦棋的程序设计课程教学案例设计[J].计算机教育,2012(18):75-77.
[17]ZHANG J J,WANG X,YAO L,et al.Modified UCT Algorithm with Risk Dominance Methods in Imperfect Information Game[C]∥International Conference on Intelligent Manufacturing and Computational Technology.Hong Kong:AMM Press,2013:367-376.
[18]LI X J,WANG X L,WU L,et al.Game tree generation algorithm based on local-road scanning method for connect 6[J].CAAI Transactions on Intelligent Systems,2015,10(2):267-272.(in Chinese)
李学俊,王小龙,吴蕾,等.六子棋中基于局部“路”扫描方式的博弈树生成算法[J].智能系统学报,2015(2):267-272.
[19]GUO X Y,LI C,MEI Q Z.Deep Learning Applied to Game[J].ACTA Automatica Sinica,2016,42(5):676-684.(in Chinese)
郭潇逍,李程,梅俏竹.深度学习在游戏中的应用[J].自动化学报,2016,42(5):676-684.

相关文章 15

[1]	姜洋洋, 宋丽华, 邢长友, 张国敏, 曾庆伟. 蜜罐博弈中信念驱动的攻防策略优化机制 Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game 计算机科学, 2022, 49(9): 333-339. https://doi.org/10.11896/jsjkx.220400011
[2]	陈鑫, 李芳, 丁海昕, 孙唯哲, 刘鑫, 陈德训, 叶跃进, 何香. 面向国产异构众核架构的CFD非结构网格计算并行优化方法 Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture 计算机科学, 2022, 49(6): 99-107. https://doi.org/10.11896/jsjkx.210400157
[3]	傅天豪, 田鸿运, 金煜阳, 杨章, 翟季冬, 武林平, 徐小文. 一种面向构件化并行应用程序的性能骨架分析方法 Performance Skeleton Analysis Method Towards Component-based Parallel Applications 计算机科学, 2021, 48(6): 1-9. https://doi.org/10.11896/jsjkx.201200115
[4]	何亚茹, 庞建民, 徐金龙, 朱雨, 陶小涵. 基于神威平台的Floyd并行算法的实现和优化 Implementation and Optimization of Floyd Parallel Algorithm Based on Sunway Platform 计算机科学, 2021, 48(6): 34-40. https://doi.org/10.11896/jsjkx.201100051
[5]	冯凯, 马鑫玉. (n,k)-冒泡排序网络的子网络可靠性 Subnetwork Reliability of (n,k)-bubble-sort Networks 计算机科学, 2021, 48(4): 43-48. https://doi.org/10.11896/jsjkx.201100139
[6]	胡蓉, 阳王东, 王昊天, 罗辉章, 李肯立. 基于GPU加速的并行WMD算法 Parallel WMD Algorithm Based on GPU Acceleration 计算机科学, 2021, 48(12): 24-28. https://doi.org/10.11896/jsjkx.210600213
[7]	马梦宇, 吴烨, 陈荦, 伍江江, 李军, 景宁. 显示导向型的大规模地理矢量实时可视化技术 Display-oriented Data Visualization Technique for Large-scale Geographic Vector Data 计算机科学, 2020, 47(9): 117-122. https://doi.org/10.11896/jsjkx.190800121
[8]	陈国良, 张玉杰. 并行计算学科发展历程 Development of Parallel Computing Subject 计算机科学, 2020, 47(8): 1-4. https://doi.org/10.11896/jsjkx.200600027
[9]	阳王东, 王昊天, 张宇峰, 林圣乐, 蔡沁耘. 异构混合并行计算综述 Survey of Heterogeneous Hybrid Parallel Computing 计算机科学, 2020, 47(8): 5-16. https://doi.org/10.11896/jsjkx.200600045
[10]	冯凯, 李婧. k元n方体的子网络可靠性研究 Study on Subnetwork Reliability of k-ary n-cubes 计算机科学, 2020, 47(7): 31-36. https://doi.org/10.11896/jsjkx.190700170
[11]	杨宗霖, 李天瑞, 刘胜久, 殷成凤, 贾真, 珠杰. 基于Spark Streaming的流式并行文本校对 Streaming Parallel Text Proofreading Based on Spark Streaming 计算机科学, 2020, 47(4): 36-41. https://doi.org/10.11896/jsjkx.190300070
[12]	邓定胜. 一种改进的DBSCAN算法在Spark平台上的应用 Application of Improved DBSCAN Algorithm on Spark Platform 计算机科学, 2020, 47(11A): 425-429. https://doi.org/10.11896/jsjkx.190700071
[13]	徐传福,王曦,刘舒,陈世钊,林玉. 基于Python的大规模高性能LBM多相流模拟 Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python 计算机科学, 2020, 47(1): 17-23. https://doi.org/10.11896/jsjkx.190500009
[14]	徐磊, 陈荣亮, 蔡小川. 基于非结构化网格的高可扩展并行有限体积格子 Scalable Parallel Finite Volume Lattice Boltzmann Method Based on Unstructured Grid 计算机科学, 2019, 46(8): 84-88. https://doi.org/10.11896/j.issn.1002-137X.2019.08.013
[15]	舒娜,刘波,林伟伟,李鹏飞. 分布式机器学习平台与算法综述 Survey of Distributed Machine Learning Platforms and Algorithms 计算机科学, 2019, 46(3): 9-18. https://doi.org/10.11896/j.issn.1002-137X.2019.03.002

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

改进UCT算法在爱恩斯坦棋中的应用

Application of Improved UCT Algorithm in EinStein Würfelt Nicht! Computer Game

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0