Structured parallel programming for Monte Carlo Tree Search

Leiden Repository

Structured parallel programming for Monte Carlo Tree Search

Type: Doctoral Thesis
Title: Structured parallel programming for Monte Carlo Tree Search
Author: Mirsoleimani, S.A.
Journal Title: SIKS Dissertation Series
Issue Date: 2020-06-17
Keywords: Structured Parallel Programming
Monte Carlo Tree Search
Artificial Intelligence
Manycore machine
Multi-core machine
Parallel pattern
Abstract: The thesis is part of a bigger project, the HEPGAME (High Energy Physics Game). The main objective for HEPGAME is the utilization of AI solutions, particularly by using MCTS for simplification of HEP calculations. One of the issues is solving mathematical expressions of interest with millions of terms. These calculations can be solved with the FORM program, which is software for symbolic manipulation. Since these calculations are computationally intensive and take a large amount of time, the FORM program was parallelized to solve them in a reasonable amount of time.Therefore, any new algorithm based on MCTS, should also be parallelized. This requirement was behind the problem statement of the thesis: “How do we design a structured pattern-based parallel programming approach for efficient parallelism of MCTS for both multi-core and manycore shared-memory machines?”.To answer this question, the thesis approached the MCTS parallelization problem in three levels: (1) implementation level, (2) data structure level, and (3) algorithm level.In the implementation level, we proposed task-level parallelization over thread-level parallelization. Task-level parallelization provides us with efficient parallelism for MCTS to utilize cores on both multi-core and manycore machines.In the data structure level, we presented a lock-free data structure that guarantees the correctness. A lock-free data structure (1) removes the synchronization overhead when a parallel program needs many tasks to feed its cores and (2) improves both performance and scalability.In the algorithm level, we first explained how to use pipeline pattern for parallelization of MCTS to overcome search overhead. Then, through a step by step approach, we were able to propose and detail the structured parallel programming approach for Monte Carlo Tree Search.
Promotor: Supervisor: Herik H.J. van den, Plaat A. Co-Supervisor: Vermaseren J.A.M.
Faculty: Faculty of Science
University: Leiden University
Handle: http://hdl.handle.net/1887/119358
 

Files in this item

Description Size View
application/pdf Full Text 2.080Mb View/Open
application/pdf Cover 99.53Mb View/Open
application/pdf Title Pages_Preface_Contents_Lists 399.7Kb View/Open
application/pdf Chapter 1 282.8Kb View/Open
application/pdf Chapter 2 419.1Kb View/Open
application/pdf Chapter 3 663.0Kb View/Open
application/pdf Chapter 4 401.1Kb View/Open Full text at publisher site
application/pdf Chapter 5 591.8Kb View/Open Full text at publisher site
application/pdf Chapter 6 744.5Kb View/Open Full text at publisher site
application/pdf Chapter 7 381.6Kb View/Open Full text at publisher site
application/pdf Chapter 8 418.7Kb View/Open Full text at publisher site
application/pdf Chapter 9 247.7Kb View/Open
application/pdf Bibliography_Appendices 349.5Kb View/Open
application/pdf Summary in English 106.1Kb View/Open
application/pdf Summary in Dutch 125.1Kb View/Open
application/pdf Acknowledgements_Curriculum Vitae_Publications 158.5Kb View/Open
application/pdf Propositions 122.9Kb View/Open

This item appears in the following Collection(s)