To install StudyMoose App tap and then “Add to Home Screen”
Save to my list
Remove from my list
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.
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 ”
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.
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.
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
| Game | Depth | Width | Tree Complexity |
|---|---|---|---|
| Tic-tac-toe | 9 | 4.0 | 10^5 |
| Sim | 14 | 3.7 | 10^8 |
| Connect Four | 36 | 4.0 | 10^21 |
| Chess | 80 | 35.0 | 10^123 |
| Connect6 | 30 | 46000.0 | 10^140 |
| Havannah | 66 | 240.0 | 10^157 |
| Arima | 92 | 17281.0 | 10^402 |
| Go (19x19) | 150 | 250.0 | 10^360 |
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.
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.
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.
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:
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.
Optimizing AI Game Strategies with GPU Parallel Computing. (2024, Feb 21). Retrieved from https://studymoose.com/document/optimizing-ai-game-strategies-with-gpu-parallel-computing
👋 Hi! I’m your smart assistant Amy!
Don’t know where to start? Type your requirements and I’ll connect you to an academic expert within 3 minutes.
get help with your assignment
