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

Maciej Świechowski , Jacek Mańdziuk

Abstract

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 ZSIMO
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
Pages199-215
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
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).
DOIDOI:10.1007/978-3-319-30165-5_10
URL http://link.springer.com/chapter/10.1007%2F978-3-319-30165-5_10
Languageen angielski
Score (nominal)0
ScoreMinisterial score [Punktacja MNiSW] = 0.0, 26-05-2018, BookChapterNotSeriesNotMainLanguages
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


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