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: UCT algorithm, EinStein würfelt nicht! game, Parallel computing, Balance optimization

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)
[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)
[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)
[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)
[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)
[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)
[14]ZHU L M.Strategy research on artificial intelligence heuristicsearch[J].Electronic Design Engineering,2013,21(16):61-64.(in Chinese)
[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)
[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)
[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)
[1] 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.
[2] CHEN Guo-liang, ZHANG Yu-jie, . Development of Parallel Computing Subject [J]. Computer Science, 2020, 47(8): 1-4.
[3] 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.
[4] 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.
[5] DENG Ding-sheng. Application of Improved DBSCAN Algorithm on Spark Platform [J]. Computer Science, 2020, 47(11A): 425-429.
[6] 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.
[7] 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.
[8] 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.
[9] ZHANG Bin, LE Jia-jin. Hash Join in MapReduce Distributed Environment Based on Column-store [J]. Computer Science, 2018, 45(6A): 471-475.
[10] LIAO Xing, YUAN Jing-ling and CHEN Min-cheng. Parallel PSO Container Packing Algorithm with Adaptive Weight [J]. Computer Science, 2018, 45(3): 231-234.
[11] LI Jun, TONG Zhao, WANG Zheng. Approach to Solve TSP with Parallel ACS-2-opt [J]. Computer Science, 2018, 45(11A): 138-142.
[12] YAO Qing, ZHENG Kai, LIU Yao, WANG Su, SUN Jun, XU Meng-xuan. Implementation and Optimization of SOM Algorithm on Sunway Many-core Processors [J]. Computer Science, 2018, 45(11A): 591-596.
[13] HUANG Zhong-ping, BAI Guang-wei, SHEN Hang, CHENG Xiao and HUA Zhi-xiang. Speculative Execution Optimization Algorithm with MapReduce [J]. Computer Science, 2017, 44(4): 193-196.
[14] WANG Zhen, HAN Zhong-ming and LI Jin. Research on Social Network Structural Holes Discovery Algorithm under Large-scale Data [J]. Computer Science, 2017, 44(4): 188-192.
[15] JIANG Wen-chao, LIN Sui, WANG Duo-qiang, LI Dong-ming and JIN Hai. Three-level Parallel Optimization and Application of Calculix in TH-2 Super-computing Environments [J]. Computer Science, 2017, 44(3): 32-35.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .