Persistent URL of this record https://hdl.handle.net/1887/119358
Documents
-
- Download
- Title Pages_Preface_Contents_Lists
- open access
-
- Download
- Chapter 4
- open access
- Full text at publishers site
-
- Download
- Chapter 5
- open access
- Full text at publishers site
-
- Download
- Chapter 6
- open access
- Full text at publishers site
-
- Download
- Chapter 7
- open access
- Full text at publishers site
-
- Download
- Chapter 8
- open access
- Full text at publishers site
-
- Download
- Bibliography_Appendices
- open access
-
- Download
- Summary in English
- open access
-
- Download
- Summary in Dutch
- open access
-
- Download
- Propositions
- open access
In Collections
This item can be found in the following collections:
Structured parallel programming for Monte Carlo Tree Search
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...Show moreThe 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.Show less
- All authors
- Mirsoleimani, S.A.
- Supervisor
- Herik, H.J. van den; Plaat, A.
- Co-supervisor
- Vermaseren, J.A.M.
- Committee
- Mulders, P.J.G.; Verbeek, F.J.; Wijshoff, H.A.G.; Khunjush, F.; Kosters, W.A.; Varbanescu, A.L.
- Qualification
- Doctor (dr.)
- Awarding Institution
- Leiden Institute of Advanced Computer Science (LIACS) , Faculty of Science , Leiden University
- Date
- 2020-06-17
- Title of host publication
- SIKS Dissertation Series
Publication Series
- Name
- 2020-08