Optimizing AI Game Strategies with GPU Parallel Computing

Abstract

The developments in the field of computer architecture, it allows humans to play games like Chess, Tic-tac-toe, Go, etc. with computer machines using AI technology. In AI, Game tree search is important to approach and Game tree search (GST) is used to find the best move for computer games. Using the traditional GST algorithm the computer could not win a human. So there is a need for enhancing algorithms using dynamic parallelism of GPU. Parallel computation on GPU is performed as a concurrently executing thread blocks set.

These are organized into a 1D grid or a 2D grid.1D, 2D or 3D grid with each thread designated by a unique combination of indices.

In this paper, parallel computing of node-based Principal Variation Search (PVS) GST algorithm presented, which runs on GPU using libraries of CUDA. This work tested with chess games with different depths and compared with previous results including threads on CPU and GPU. The result shows speed up for parallel GPU up to 80x at 14 depth for checkers game and 90x at 14 depth for a chess game, which doubled the previous research results.

Get quality help now

Doctor Jennifer

Verified writer

Proficient in: Technology

5 (893)

“ Thank you so much for accepting my assignment the night before it was due. I look forward to working with you moving forward ”

+84 relevant experts are online

Hire writer

Parallel computing great-ly increasing the efficient use of CPU and improves the performances of the PVS-GST algorithm on GPU to search deeper layers and find the optimal moves for the current players for two-player computer games.

Introduction

Game tree search(GTS) is the method to find the best optimal strategy for games played by computers using AI. In-game theory, a game tree is a directed graph in which positions are nodes represents different states, edges are choices of moves players' current game choices.

The principle of the GTS method is, aggressively engender the tree structure from the current node (position), traversing the tree, assess all possible edges(moves) and encounter the finest edge. GTS performs two primary functions. One, the tree search function mainly focuses on traversing the game tree to find the optimal way to move.

In this case, using historic knowledge and pruning, we can avoid irrelevant visiting on convinced positions. The second, node function consists of the evaluation function and moves generation function. It calculates scores and assigns for each node or position. the position with a high score value will be selected for the best move by player. This calculation of scores depends on rules for the respective game and may differ for different games.

Experimental Procedure

In general complexity of the game can be measured by quite a few factors such as depth average, branching factor, time complexity and computation time. Different rules and implementations are differed from game to game but even have some level of complexity games i.e., calculation of essential nodes and moves. Table 1 list outs the depth, width and it’s time complexities of different two-player computer games. Solution for the current challenging problem, adopt parallel computing of node-based GST algorithm on GPU. In this, our algorithm will assign a collection of different sets of nodes from one or multiple sub-trees to different processors.

Table 1. Types of Game trees for some Games

The algorithms like Negamax [4], PVS [5], YBWC [6] or DTS where multiple nodes run parallelly on CPU or GPU for two player computer games like chess etc. In this the work started by implementing the parallel computing algorithm initially on CPU using the language C and execute correctly and it is converted to code of GPU using Compute Unified Device Architecture (CUDA) [2]. As a first step CPU calls the kernel with current position of game board, then the kernel call new kernel with a dynamic number of threads and these are processed concurrently in the GPU using dynamic parallelism. And also its eliminates go back to CPU and call new kernel on GPU.

Parallel Node based GST algorithm

We present the parallel computing of nodes based PVS game tree searching algorithm, advantages of our approach. Principal Variation Search(PVS) [8] is a straightforward and efficient parallel GTS algorithm on GPU. The basic idea of our work is to take massive nodes to GPU and calculates leaves and branches concurrently and explained the process of these two GPU based functions in the algorithm1 and algorithm 1. By making a list of all positions of a game(PI) as input to GPU from CPU and returns candidates move for the branch calculation, returns an evaluated value(i.e. parameter V) for leaf calculation. After taking the current position from the PI list starts execution on GPU calculates the optimal moves for the current player.

Performance Analysis

The performance of the parallel PVS node-based GST algorithm was analyzed through a chess game simulation, revealing speedups of up to 80x at depth 14 for checkers and 90x at depth 14 for chess, doubling previous research results. These findings underscore the GPU's dynamic parallelism in calculating optimal moves for AI games.

Experimental Results

The above experiment implemented and executed on a two-player computer chess game, results are attained. Besides the comparison of our proposed algorithm with all other algorithms by using the same evaluation function. Even our algorithm also gives the worst results when compare with other algorithms when the search depth is too small and also tests were made for large depth search. The experiment was done on the computer which has the configuration setup as follows:

• Intel(R) Core™ i7-8750H CPU @ 2.20GHz 2.21GHz with six physical cores and twelve logical cores
• 16GB RAM
• NVIDIA GeForce GTX 1050 Ti

Conclusion

In the framework of the two-player computer game, this paper studies the PVS algorithm and its optimization and parallel computing of the node-based PVS GST algorithm. This method can be tested by applying it for the CHESS game. By using both CPU and GPU architecture, this algorithm takes advantage of dynamic parallelism of GPU to calculate best that gives the optimization solution for two-player computer games.

References

1. L. Li, S. Member, H. Liu and H. Wang, 'A Parallel Algorithm for Game Tree Search Using GPGPU,' IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 8, pp. 2114-2127, 2015.
2. A. A., M. Abdel, M. Gadallah and H. El-Deeb, 'A Comparative Study of Game Tree Searching Methods,' International Journal of Advanced Computer Science and Applications, vol. 5, no. 5, pp. 68-77, 2014.
3. C. Johnson, L. Barford, S. M. Dascalu and F. C. Harris, 'CUDA implementation of computer go game tree search,' Advances in Intelligent Systems and Computing, vol. 448, pp. 339-350, 2016.
4. T. Heineman, Algorithms in Nutshells, vol. 18, 2012, pp. 995-996.
5. A. I. G. Seminar, 'Enhanced Forward Pruning,' no. 3529070, 2019.
6. A. Kishimoto and J. Schaeffer, 'Distributed game-tree search using transposition table driven work scheduling,' Proceedings of the International Conference on Parallel Processing, Vols. 2002-Janua, pp. 323-330, 2002.
7. A. A. Elnaggar, M. Gadallah, M. A. Aziem and H. El-Deeb, 'Enhanced parallel NegaMax tree search algorithm on GPU,' PIC 2014 - Proceedings of 2014 IEEE International Conference on Progress in Informatics and Computing, pp. 546-550, 2014.
8. B. Tong, H. Qiu, T. Guo and Y. Wang, 'Research and Application of Parallel Computing of PVS Algorithm Based on Amazon Human-Machine Game,' 2019 Chinese Control And Decision Conference (CCDC), pp. 6293-6298, 2019.
9. K. Rocki and R. Suda, 'Parallel minimax tree searching on GPU,' Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6067 LNCS, no. PART 1, pp. 449-456, 2010.
10. D. Strnad and N. Guid, 'Parallel alpha-beta algorithm on the GPU,' Journal of Computing and Information Technology, vol. 19, no. 4, pp. 269-274, 2011.