MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda
With CUDA computational model in mind, we introduce MCTS-NC (Monte Carlo Tree Search–numba.cuda ). It contains four, fast-operating and thoroughly parallel, variants of the MCTS algorithm. The design of MCTS-NC combines three parallelization levels (leaf/root/tree parallelizations). Additionally, al...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-05-01
|
| Series: | SoftwareX |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2352711025001062 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849761907887570944 |
|---|---|
| author | Przemysław Klęsk |
| author_facet | Przemysław Klęsk |
| author_sort | Przemysław Klęsk |
| collection | DOAJ |
| description | With CUDA computational model in mind, we introduce MCTS-NC (Monte Carlo Tree Search–numba.cuda ). It contains four, fast-operating and thoroughly parallel, variants of the MCTS algorithm. The design of MCTS-NC combines three parallelization levels (leaf/root/tree parallelizations). Additionally, all algorithmic stages – selections, expansions, playouts, backups – employ multiple GPU threads. We apply suitable reduction patterns to carry out summations or max/argmax operations. The implementation uses very few device-host memory transfers, no atomic operations (is lock-free), and takes advantage of threads cooperation. In the mathematical part of this article, we demonstrate how the confidence bounds on estimated action values become tightened by both the number of independent concurrent playouts and the number of independent concurrent trees. The experimental part reports the performance of MCTS-NC on two game examples: Connect4 and Gomoku. All computational results can be exactly reproduced. |
| format | Article |
| id | doaj-art-bfde37d628274fe28f150ce80c2da8c0 |
| institution | DOAJ |
| issn | 2352-7110 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | Elsevier |
| record_format | Article |
| series | SoftwareX |
| spelling | doaj-art-bfde37d628274fe28f150ce80c2da8c02025-08-20T03:05:52ZengElsevierSoftwareX2352-71102025-05-013010213910.1016/j.softx.2025.102139MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cudaPrzemysław Klęsk0Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, ul. Żołnierska 49, 71-210 Szczecin, PolandWith CUDA computational model in mind, we introduce MCTS-NC (Monte Carlo Tree Search–numba.cuda ). It contains four, fast-operating and thoroughly parallel, variants of the MCTS algorithm. The design of MCTS-NC combines three parallelization levels (leaf/root/tree parallelizations). Additionally, all algorithmic stages – selections, expansions, playouts, backups – employ multiple GPU threads. We apply suitable reduction patterns to carry out summations or max/argmax operations. The implementation uses very few device-host memory transfers, no atomic operations (is lock-free), and takes advantage of threads cooperation. In the mathematical part of this article, we demonstrate how the confidence bounds on estimated action values become tightened by both the number of independent concurrent playouts and the number of independent concurrent trees. The experimental part reports the performance of MCTS-NC on two game examples: Connect4 and Gomoku. All computational results can be exactly reproduced.http://www.sciencedirect.com/science/article/pii/S2352711025001062MCTS parallelizationCUDAPythonNumbaBounds on action values estimates |
| spellingShingle | Przemysław Klęsk MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda SoftwareX MCTS parallelization CUDA Python Numba Bounds on action values estimates |
| title | MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda |
| title_full | MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda |
| title_fullStr | MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda |
| title_full_unstemmed | MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda |
| title_short | MCTS-NC: A thorough GPU parallelization of Monte Carlo Tree Search implemented in Python via numba.cuda |
| title_sort | mcts nc a thorough gpu parallelization of monte carlo tree search implemented in python via numba cuda |
| topic | MCTS parallelization CUDA Python Numba Bounds on action values estimates |
| url | http://www.sciencedirect.com/science/article/pii/S2352711025001062 |
| work_keys_str_mv | AT przemysławklesk mctsncathoroughgpuparallelizationofmontecarlotreesearchimplementedinpythonvianumbacuda |