A Hybrid Approach for GTS Using Min-Max Algorithm on GPU and CPU

Abstract: In field of the game theories and artificial intelligence Game-tree-search is the classical problem. The general use of GTS algorithm is in the real time applications having much higher complexity like video games, chess, connect4/connect6 etc. Different algorithms for game tree are used to search out the player's next best move on the game tree in minimum time. Main focus of system is on increasing massive parallelism abilities of GPUs to accelerate the speed of game tree algorithms and propose general parallel game tree algorithm on the GPUs. In game tree search, GPU surpasses CPU if there is highest level of parallelism is achieved due to its searching is in BFS manner and CPU is in DFS manner so that CPU didn�t produce improvement. Here combination of DFS and BFS technique is main focus and appropriate selection will be the depth-first-search on CPU and use breadth-first-search on GPU and looks like hybrid CPU and GPU solutions.

Keywords: SIMD, MIMD, GPU, Connect6, Parallel Computing.