The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions

Sylvain Gelly; Marc Schoenauer; Michèle Sebag; Olivier Teytaud; Levente Kocsis; David Silver; Csaba Szepesvari

hal-00695370, version 2

The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions

Sylvain Gelly () ^1, 2, Marc Schoenauer () ^1, 3, Michèle Sebag () ^1, 2, Olivier Teytaud (, ) ^{1, 2, 4, 5}, Levente Kocsis^a^, 6, David Silver^b^, 7, Csaba Szepesvari () ⁸

Communication of the ACM 55, 3 (2012) 106-113

Résumé : The ancient oriental game of Go has long been considered a grand challenge for artiﬁcial intelligence. For decades, com- puter Go has deﬁed the classical methods in game tree search that worked so successfully for chess and checkers. How- ever, recent play in computer Go has been transformed by a new paradigm for tree search based on Monte-Carlo meth- ods. Programs based on Monte-Carlo tree search now play at human-master levels and are beginning to challenge top professional players. In this paper we describe the leading algorithms for Monte-Carlo tree search and explain how they have advanced the state of the art in computer Go.

a – Mta Sztaki
b – University of Alberta
1 : TAO (INRIA Saclay - Ile de France)
INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
2 : Laboratoire de Recherche en Informatique (LRI)
CNRS : UMR8623 – Université Paris XI - Paris Sud
3 : Microsoft Research - Inria Joint Centre (MSR - INRIA)
INRIA – Microsoft – Microsoft Research Laboratory Cambridge
4 : OASE, National University of Tainan, Taiwan (OASE)
National University of Tainan
5 : Department of Electrical Engineering and Computer Science (Institut Montefiore)
Université de Liège
6 : LPDS
Mta Sztaki
7 : University of Alberta, Canada
University of Alberta
8 : Department of Computing Science
Department of Computing Science, University of Alberta

Collaboration : Grid'5000

hal-00695370, version 2
http://hal.inria.fr/hal-00695370
oai:hal.inria.fr:hal-00695370
Contributeur : Olivier Teytaud <>
Soumis le : Dimanche 19 Août 2012, 10:35:22
Dernière modification le : Samedi 15 Septembre 2012, 13:53:38

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00695370"><analytic>
<author><persName><forename>Sylvain</forename><surname>Gelly</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Saclay - Ile de France</orgName>
<orgName type="team">TAO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
</author>
<author><persName><forename>Marc</forename><surname>Schoenauer</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Saclay - Ile de France</orgName>
<orgName type="team">TAO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">MSR - INRIA</orgName>
<orgName type="team">Microsoft Research - Inria Joint Centre</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Microsoft</orgName>
<orgName type="institution">Microsoft Research Laboratory Cambridge</orgName>
</affiliation>
</author>
<author><persName><forename>Michèle</forename><surname>Sebag</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Saclay - Ile de France</orgName>
<orgName type="team">TAO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Teytaud</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Saclay - Ile de France</orgName>
<orgName type="team">TAO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">OASE</orgName>
<orgName type="team">OASE, National University of Tainan, Taiwan</orgName>
<country>TW</country>
<orgName type="institution">National University of Tainan</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">Institut Montefiore</orgName>
<orgName type="team">Department of Electrical Engineering and Computer Science</orgName>
<country>BE</country>
<orgName type="institution">Université de Liège</orgName>
</affiliation>
</author>
<author><persName><forename>Levente</forename><surname>Kocsis</surname></persName>
<affiliation>
<orgName type="team">LPDS</orgName>
<country>HU</country>
<orgName type="institution">Mta Sztaki</orgName>
</affiliation>
</author>
<author><persName><forename>David</forename><surname>Silver</surname></persName>
<affiliation>
<orgName type="team">University of Alberta, Canada</orgName>
<country>CA</country>
<orgName type="institution">University of Alberta</orgName>
</affiliation>
</author>
<author><persName><forename>Csaba</forename><surname>Szepesvari</surname></persName>
<affiliation>
<orgName type="team">Department of Computing Science</orgName>
<country>CA</country>
<orgName type="institution">Department of Computing Science, University of Alberta</orgName>
</affiliation>
</author>
<title type="main" level="a">The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions</title></analytic><monogr><title level="j" type="main">Communications- ACM</title><imprint><publisher>ACM</publisher><biblScope type="publicationDate">2012-00-00</biblScope><biblScope type="vol">55</biblScope><biblScope type="issue">3</biblScope><biblScope type="pp">106-113</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00695370</idno><idno type="HALFile">http://hal.inria.fr/hal-00695370/PDF/CACM-MCTS.pdf</idno></biblStruct>
</listBibl>
</listBibl>