Computer Science ›› 2018, Vol. 45 ›› Issue (12): 196-200.doi: 10.11896/j.issn.1002-137X.2018.12.032

• Artificial Intelligence • Previous Articles     Next Articles

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

ZHANG Xiao-chuan1, LI Qin1, NAN Hai1, PENG Li-rong2   

  1. (College of Computer Science and Engineering,Chongqing University of Technology,Chongqing 400054,China)1
    (Scientific Research Department,Chongqing Industry Polytechnic College,Chongqing 401120,China)2
  • Received:2017-11-20 Online:2018-12-15 Published:2019-02-25

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

CLC Number: 

  • TP391
[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.
[1] JIANG Yang-yang, SONG Li-hua, XING Chang-you, ZHANG Guo-min, ZENG Qing-wei. Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game [J]. Computer Science, 2022, 49(9): 333-339.
[2] CHEN Xin, LI Fang, DING Hai-xin, SUN Wei-ze, LIU Xin, CHEN De-xun, YE Yue-jin, HE Xiang. Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture [J]. Computer Science, 2022, 49(6): 99-107.
[3] FU Tian-hao, TIAN Hong-yun, JIN Yu-yang, YANG Zhang, ZHAI Ji-dong, WU Lin-ping, XU Xiao-wen. Performance Skeleton Analysis Method Towards Component-based Parallel Applications [J]. Computer Science, 2021, 48(6): 1-9.
[4] HE Ya-ru, PANG Jian-min, XU Jin-long, ZHU Yu, TAO Xiao-han. Implementation and Optimization of Floyd Parallel Algorithm Based on Sunway Platform [J]. Computer Science, 2021, 48(6): 34-40.
[5] LI Fan, YAN Xing, ZHANG Xiao-yu. Optimization of GPU-based Eigenface Algorithm [J]. Computer Science, 2021, 48(4): 197-204.
[6] HU Rong, YANG Wang-dong, WANG Hao-tian, LUO Hui-zhang, LI Ken-li. Parallel WMD Algorithm Based on GPU Acceleration [J]. Computer Science, 2021, 48(12): 24-28.
[7] MA Meng-yu, WU Ye, CHEN Luo, WU Jiang-jiang, LI Jun, JING Ning. Display-oriented Data Visualization Technique for Large-scale Geographic Vector Data [J]. Computer Science, 2020, 47(9): 117-122.
[8] CHEN Guo-liang, ZHANG Yu-jie, . Development of Parallel Computing Subject [J]. Computer Science, 2020, 47(8): 1-4.
[9] YANG Wang-dong, WANG Hao-tian, ZHANG Yu-feng, LIN Sheng-le, CAI Qin-yun. Survey of Heterogeneous Hybrid Parallel Computing [J]. Computer Science, 2020, 47(8): 5-16.
[10] YANG Zong-lin, LI Tian-rui, LIU Sheng-jiu, YIN Cheng-feng, JIA Zhen, ZHU Jie. Streaming Parallel Text Proofreading Based on Spark Streaming [J]. Computer Science, 2020, 47(4): 36-41.
[11] DENG Ding-sheng. Application of Improved DBSCAN Algorithm on Spark Platform [J]. Computer Science, 2020, 47(11A): 425-429.
[12] XU Chuan-fu,WANG Xi,LIU Shu,CHEN Shi-zhao,LIN Yu. Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python [J]. Computer Science, 2020, 47(1): 17-23.
[13] XU Lei, CHEN Rong-liang, CAI Xiao-chuan. Scalable Parallel Finite Volume Lattice Boltzmann Method Based on Unstructured Grid [J]. Computer Science, 2019, 46(8): 84-88.
[14] SHU Na,LIU Bo,LIN Wei-wei,LI Peng-fei. Survey of Distributed Machine Learning Platforms and Algorithms [J]. Computer Science, 2019, 46(3): 9-18.
[15] ZHANG Bin, LE Jia-jin. Hash Join in MapReduce Distributed Environment Based on Column-store [J]. Computer Science, 2018, 45(6A): 471-475.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!