A Hybrid Approach to Parallelization of Monte Carlo Tree Search in General Game Playing

Maciej Świechowski , Jacek Mańdziuk


In this paper, we investigate the concept of a parallelization of Monte Carlo Tree Search applied to games. Specifically, we consider General Game Playing framework, which has originated at Stanford University in 2005 and has become one of the most important realizations of the multi-game playing idea. We introduce a novel parallelization method, called Limited Hybrid Root-Tree Parallelization, based on a combination of two existing ones (Root and Tree Parallelization) additionally equipped with a mechanism of limiting actions available during the search process. The proposed approach is evaluated and compared to the non-limited hybrid version counterpart and to the Tree Parallelization method. The advantages over Root Parallelization are derived on a theoretical basis. In the experiments, the proposed method is more effective than Tree Parallelization and also than non-limited hybrid version in certain games.
Author Maciej Świechowski
Maciej Świechowski,,
, Jacek Mańdziuk (FMIS / DAICM)
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
Publication size in sheets0.8
Book Tré Guy De, Grzegorzewski Przemysław, Kacprzyk Janusz, Owsiński Jan W, Penczek Wojciech, Zadrozny S. (eds.): Challenging Problems and Solutions in Intelligent Systems, Studies in Computational Intelligence, vol. 634, 2016, SPRINGER-VERLAG BERLIN, ISBN 978-3-319-30164-8, 347 p.
Keywords in EnglishMonte Carlo Tree Search, Upper Confidence Bounds Applied for Trees, General Game Playing, Parallelization, Parallel Computing
ASJC Classification1702 Artificial Intelligence
Abstract in PolishW pracy proponowany jest nowy sposób zrównoleglenia algorytmu MCTS (Monte Carlo Tree Search) w kontekście jego zastosowań w domenie gier. W szczególności omawiane jest zastosowanie proponowanej metody w dziedzinie General Game Playing. Proponowana metoda, nazwana w pracy Limited Hybrid Root-Tree Parallelization, stanowi kombinację dwóch znanych w literaturze podejść, mianowicie Root Parallelization oraz Tree Parallelization, wyposażonych dodatkowo w mechanizm ograniczający wybór akcji w trakcie (zrównoleglanego) przeszukiwania przestrzeni stanów (drzewa gry).
URL http://link.springer.com/chapter/10.1007%2F978-3-319-30165-5_10
Languageen angielski
Score (nominal)0
ScoreMinisterial score = 0.0, 30-01-2020, MonographChapterAuthor
Publication indicators WoS Citations = 0; Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 0.39
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?