A Parallel Algorithm for Game Tree Search Using GPGPU

被引:11
|
作者
Li, Liang [1 ]
Liu, Hong [1 ]
Wang, Hao [2 ]
Liu, Taoying [1 ]
Li, Wei [1 ]
机构
[1] Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
[2] Virginia Tech, Dept Comp Sci, Blacksburg, VA USA
关键词
Parallel computing; GPU; game tree search; alpha-beta pruning; Conect6; Chess;
D O I
10.1109/TPDS.2014.2345054
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Game tree search is a classical problemin the field of game theory and artificial intelligence. Fast game tree search algorithm is critical for computer games asking for real-time responses. In this paper, we focus on how to leverage massive parallelism capabilities of GPU to accelerate the speed of game tree search algorithms and propose a concise and general parallel game tree search algorithm on GPU. The performance model of our algorithm is presented and analyzed theoretically. We implement the algorithm for two real computer games called Connect6 and Chess. We also use these two games to verify the effectiveness and efficiency of our algorithm. Experiments support our theoretical results and show good performance of our approach. Compared to classical CPU-based game tree search algorithms, our algorithm can achieve speedups of 89.95x for Connect6 and 11.43x for Chess, in case of no pruning. When pruning is considered, which means the practical performance of our algorithm, the speedup can reach about 10.58x for Connect6 and 7.26x for Chess. The insight of our work is that using GPU is a feasible way to improve the performance of game tree search algorithms.
引用
收藏
页码:2114 / 2127
页数:14
相关论文
共 50 条
  • [31] Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search
    Yokoyama, Shu
    Kaneko, Tomoyuki
    Tanaka, Tetsuro
    ADVANCES IN COMPUTER GAMES, ACG 2015, 2015, 9525 : 210 - 222
  • [32] A parallel local search algorithm for Euclidean Steiner tree problem
    Bin Muhammad, Rashid
    SNPD 2006: Seventh ACIS International Conference on Software Engineering Artificial Intelligence, Networking, and Parallel/Distributed Computing, Proceedings, 2006, : 157 - 162
  • [33] DESIGN, ANALYSIS, AND IMPLEMENTATION OF A PARALLEL TREE-SEARCH ALGORITHM
    AKL, SG
    BARNARD, DT
    DORAN, RJ
    IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1982, 4 (02) : 192 - 203
  • [34] Boosting material modeling using game tree search
    Sawada, Ryohto
    Iwasaki, Yuma
    Ishida, Masahiko
    PHYSICAL REVIEW MATERIALS, 2018, 2 (10):
  • [35] A parallel hardware architecture for accelerating alpha-beta game tree search
    Ke, YF
    Parng, TM
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1996, E79D (09) : 1232 - 1240
  • [36] Enhancing the Monte Carlo Tree Search Algorithm for Video Game Testing
    Ariyurek, Sinan
    Betin-Can, Aysu
    Surer, Elif
    2020 IEEE CONFERENCE ON GAMES (IEEE COG 2020), 2020, : 25 - 32
  • [37] Parallel Implementation of Morphological Image Processing Algorithm for GPGPU
    Ismail, Muhammad Ali
    Shamim, Kamran
    PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON RECENT ADVANCES IN COMPUTER SYSTEMS, 2016, 38 : 130 - 134
  • [38] An Evolutionary Game Tree Search Algorithm of Military Chess Game Based on Neural Value Network
    Liu, Tingzhen
    Ai, Derun
    Ma, Yimin
    Yu, Xia
    Duan, Yong
    He, Yuan
    PROCEEDINGS OF THE 32ND 2020 CHINESE CONTROL AND DECISION CONFERENCE (CCDC 2020), 2020, : 220 - 225
  • [39] Parallel Implementation of an Evolutionary Algorithm for Function Minimization on a GPGPU
    Almeida Arrieta, Betrand J.
    Alvarado-Nava, Oscar
    Chable Martinez, Hilda M.
    Rodriguez-Martinez, Eduardo
    Zaragoza Martinez, Francisco Javier
    HIGH PERFORMANCE COMPUTER APPLICATIONS, 2016, 595 : 213 - 224
  • [40] An Asynchronous Parallel Genetic Algorithm for the Maximum Likelihood Phylogenetic Tree Search
    Tsuji, Miwako
    Sato, Mitsuhisa
    Tanabe, Akifumi S.
    Inagaki, Yuji
    Hashimoto, Tetsuo
    2012 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2012,