PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCH

Guillaume M. J-B. Chaslot (), Mark H. M. Winands (), H. Jaap van Den Herik (), Jos W. H. M. Uiterwijk () and Bruno Bouzy ()
Additional contact information
Guillaume M. J-B. Chaslot: MICC-IKAT, Games and AI Group, Faculty of Humanities and Sciences, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands
Mark H. M. Winands: MICC-IKAT, Games and AI Group, Faculty of Humanities and Sciences, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands
H. Jaap van Den Herik: MICC-IKAT, Games and AI Group, Faculty of Humanities and Sciences, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands
Jos W. H. M. Uiterwijk: MICC-IKAT, Games and AI Group, Faculty of Humanities and Sciences, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands
Bruno Bouzy: Centre de Recherche en Informatique de Paris 5, Université Paris 5 Descartes, 45, rue des Saints Pères, 75270 Cedex 06, France

New Mathematics and Natural Computation (NMNC), 2008, vol. 04, issue 03, 343-357

Abstract: Monte-Carlo Tree Search (MCTS) is a new best-first search guided by the results of Monte-Carlo simulations. In this article, we introduce twoprogressive strategiesfor MCTS, called progressive bias and progressive unpruning. They enable the use of relatively time-expensive heuristic knowledge without speed reduction. Progressive bias directs the search according to heuristic knowledge. Progressive unpruning first reduces the branching factor, and then increases it gradually again. Experiments assess that the two progressive strategies significantly improve the level of our Go programMango. Moreover, we see that the combination of both strategies performs even better on larger board sizes.

Keywords: Monte-Carlo Tree Search; heuristic search; Computer Go (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S1793005708001094
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:nmncxx:v:04:y:2008:i:03:n:s1793005708001094

Ordering information: This journal article can be ordered from

DOI: 10.1142/S1793005708001094

Access Statistics for this article

New Mathematics and Natural Computation (NMNC) is currently edited by Paul P Wang

More articles in New Mathematics and Natural Computation (NMNC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().