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)
王亚杰,邱虹坤,吴燕燕,等.计算机博弈的研究与发展[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] 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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[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 .