A Review on Parallelization of Node based Game Tree Search Algorithms on GPU

Rutuja U. Gosavi, Payal S. Kulkarni
Computer Engg. Department, GES’s R. H. Sapat COE Nashik, Pune University, India
International Journal of Computer Science and Information Technologies (IJCSIT), Vol. 5 (6), 2014


   title={A Review on Parallelization of Node based Game Tree Search Algorithms on GPU},

   author={Gosavi, Ms Rutuja U and Kulkarni, Payal S},



Download Download (PDF)   View View   Source Source   



Game tree search is a classical problem in the field of game theory and artificial intelligence. Focus of the system is on how to leverage massive parallelism capabilities of GPUs to accelerate the speed of game tree algorithms and propose a concise and general parallel game tree algorithm on GPUs. Comparison can be done for classical CPU-based game tree algorithms with pruning and without pruning. The purpose is to identify possibilities of tasks parallelization when searching and assess game search trees that would perform better on SIMD processors of graphics cards. For game tree search CPU did not produce improvement but GPU surpasses a single CPU if high level of parallelism is achieved; because its searching is in BFS manner whereas CPU precedes BFS approach. The focus is on combination of DFS and BFS. Thus selection will be the depth-first search on CPU due to memory limit and use breadth-first search on GPU. Approach can be made for multi-computer environments, which look into better pruning algorithms for the GPU-based GTS algorithms. GTS algorithm used for games having much higher complexity to find best real time response, such as CHESS, SUDOKU, and HEX to weigh up the effectiveness of parallelization on the GPU. It intends to look into hybrid CPU-GPU solutions with heuristic GPU activation for deeper searches.
Rating: 0.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: