DOI: 10.1145/2093548.2093574. The grand challenge of computer Go

10.1145/2093548.2093574

Crossref journal-article

Association for Computing Machinery (ACM)

Communications of the ACM (320)

Abstract

The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. For decades, computer Go has defied the classical methods in game tree search that worked so successfully for chess and checkers. However, recent play in computer Go has been transformed by a new paradigm for tree search based on Monte-Carlo methods. 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.

Bibliography

Gelly, S., Kocsis, L., Schoenauer, M., Sebag, M., Silver, D., SzepesvÃ¡ri, C., & Teytaud, O. (2012). The grand challenge of computer Go. Communications of the ACM, 55(3), 106â113.

Authors 7

Sylvain Gelly (first)
Levente Kocsis (additional)
Marc Schoenauer (additional)
Michèle Sebag (additional)
David Silver (additional)
Csaba Szepesvári (additional)
Olivier Teytaud (additional)

References 25 Referenced 124

Special issue on Monte Carlo techniques and computer Go. In C.-S. Lee, M. Müller, and O. Teytaud, eds , IEEE Trans. Comput. Intell. AI in Games , 2 ( 2010 ). Special issue on Monte Carlo techniques and computer Go. In C.-S. Lee, M. Müller, and O. Teytaud, eds, IEEE Trans. Comput. Intell. AI in Games, 2 (2010). / IEEE Trans. Comput. Intell. AI in Games / Carlo techniques and computer Go. In C.-S. Lee, M. Müller, and O. Teytaud, eds by Special (2010)
10.1109/34.44404
10.1023/A:1013689704352
10.5555/1950322.1950327
Bouzy , B. , Chaslot , G. Bayesian generation and integration of k-nearest-neighbor patterns for 19 × 19 Go . In IEEE Symposium on Computational Intelligence and Games (CIG-05) ( 2005 ). Bouzy, B., Chaslot, G. Bayesian generation and integration of k-nearest-neighbor patterns for 19 × 19 Go. In IEEE Symposium on Computational Intelligence and Games (CIG-05) (2005). / IEEE Symposium on Computational Intelligence and Games (CIG-05) by Bouzy B. (2005)
Bouzy , B. , Helmstetter , B. Monte-Carlo Go developments . In 10th International Conference on Advances in Computer Games (ACG-03) ( 2003 ), 159--174. Bouzy, B., Helmstetter, B. Monte-Carlo Go developments. In 10th International Conference on Advances in Computer Games (ACG-03) (2003), 159--174. / 10th International Conference on Advances in Computer Games (ACG-03) by Bouzy B. (2003)
Brügmann , B. Monte-Carlo Go . Technical report , Max Planck Institute of Physics , 1993 . Brügmann, B. Monte-Carlo Go. Technical report, Max Planck Institute of Physics, 1993. / Technical report by Brügmann B. (1993)
Bubeck , S. , Munos , R. , Stoltz , G. , Szepesvári , C. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems 22 (NIPS-22), D. Koller and D. Schuurmans and Y. Bengio and L. Bottou, eds . MIT Press , 2009 , 201--208. Bubeck, S., Munos, R., Stoltz, G., Szepesvári, C. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems 22 (NIPS-22), D. Koller and D. Schuurmans and Y. Bengio and L. Bottou, eds. MIT Press, 2009, 201--208. / MIT Press by Bubeck S. (2009)
Cazenave , T. , Balbo , F. , Pinson , S. Monte-Carlo bus regulation . In 12th International IEEE Conference on Intelligent Transportation Systems ( 2009 ), 340--345. Cazenave, T., Balbo, F., Pinson, S. Monte-Carlo bus regulation. In 12th International IEEE Conference on Intelligent Transportation Systems (2009), 340--345. / 12th International IEEE Conference on Intelligent Transportation Systems by Cazenave T. (2009)
10.5555/1944566.1944583
Coquelin , P.A. , Munos , R. Bandit algorithms for tree search . In 23rd Conference on Uncertainty in Artificial Intelligence (UAI-07) ( 2007 ), 67--74. Coquelin, P.A., Munos, R. Bandit algorithms for tree search. In 23rd Conference on Uncertainty in Artificial Intelligence (UAI-07) (2007), 67--74. / 23rd Conference on Uncertainty in Artificial Intelligence (UAI-07) by Coquelin P.A. (2007)
10.5555/1777826.1777833
Coulom , R . Computing Elo ratings of move patterns in the game of Go . Int. Comput. Game. Assoc. J. 30 , 4 ( 2007 ), 198--208. Coulom, R. Computing Elo ratings of move patterns in the game of Go. Int. Comput. Game. Assoc. J. 30, 4 (2007), 198--208. / Int. Comput. Game. Assoc. J. / Computing Elo ratings of move patterns in the game of Go by Coulom R (2007)
Finnsson , H. , Björnsson , Y. Simulation-based approach to general game playing . In 23rd AAAI Conference on Artificial Intelligence (AAAI-08) ( 2008 ), 259--264. Finnsson, H., Björnsson, Y. Simulation-based approach to general game playing. In 23rd AAAI Conference on Artificial Intelligence (AAAI-08) (2008), 259--264. / 23rd AAAI Conference on Artificial Intelligence (AAAI-08) by Finnsson H. (2008)
10.1016/j.artint.2011.03.007
Gelly , S. , Wang , Y. , Munos , R. , Teytaud , O. Modification of UCT with Patterns in Monte-Carlo Go. Rapport de recherche INRIA RR-6062 , 2006 . Gelly, S., Wang, Y., Munos, R., Teytaud, O. Modification of UCT with Patterns in Monte-Carlo Go. Rapport de recherche INRIA RR-6062, 2006. / Modification of UCT with Patterns in Monte-Carlo Go. Rapport de recherche INRIA RR-6062 by Gelly S. (2006)
Huang , S. , Coulom , R. , Lin , S. Monte-Carlo simulation balancing in practice . In 7th International Conference on Computers and, Games (CG-09) ( 2009 ), 119--126. Huang, S., Coulom, R., Lin, S. Monte-Carlo simulation balancing in practice. In 7th International Conference on Computers and, Games (CG-09) (2009), 119--126. / 7th International Conference on Computers and, Games (CG-09) by Huang S. (2009)
10.1007/11871842_29
10.1016/0196-8858(85)90002-8
10.5555/1661445.1661729
10.1090/S0002-9904-1952-09620-8
Schaeffer , J . The games computers (and people) play . Adv. Comput. , 52 ( 2000 ), 190 -- 268 . Schaeffer, J. The games computers (and people) play. Adv. Comput., 52 (2000), 190--268. / Adv. Comput. / The games computers (and people) play by Schaeffer J (2000)
10.5555/1736406.1736447
10.1109/TSMC.1973.4309272
10.5555/1597538.1597631

Dates

Type	When
Created	13 years, 6 months ago (Feb. 22, 2012, 1:42 p.m.)
Deposited	2 months, 1 week ago (June 18, 2025, 5:54 a.m.)
Indexed	1 month, 3 weeks ago (July 5, 2025, 12:46 a.m.)
Issued	13 years, 5 months ago (March 1, 2012)
Published	13 years, 5 months ago (March 1, 2012)
Published Online	13 years, 5 months ago (March 1, 2012)
Published Print	13 years, 5 months ago (March 1, 2012)

Funders 2

Seventh Framework Programme 10.13039/501100004963
Region: Europe
gov (National government)
Labels5
1. EC Seventh Framework Programme
2. European Commission Seventh Framework Programme
3. EU Seventh Framework Programme
4. European Union Seventh Framework Programme
5. FP7
Awards1
1. 216886
Sixth Framework Programme 10.13039/501100004965
Region: Europe
gov (National government)
Labels5
1. EC Sixth Framework Programme
2. European Commission Sixth Framework Programme
3. EU Sixth Framework Programme
4. European Union Sixth Framework Programme
5. FP6
Awards1
1. IST 2002-506778

BibTeX

@article{Gelly_2012, title={The grand challenge of computer Go: Monte Carlo tree search and extensions}, volume={55}, ISSN={1557-7317}, url={http://dx.doi.org/10.1145/2093548.2093574}, DOI={10.1145/2093548.2093574}, number={3}, journal={Communications of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Gelly, Sylvain and Kocsis, Levente and Schoenauer, Marc and Sebag, Michèle and Silver, David and Szepesvári, Csaba and Teytaud, Olivier}, year={2012}, month=mar, pages={106–113} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        5
      ]
    ],
    "date-time": "2025-07-05T04:46:31Z",
    "timestamp": 1751690791309,
    "version": "3.41.0"
  },
  "reference-count": 25,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2012,
            3,
            1
          ]
        ],
        "date-time": "2012-03-01T00:00:00Z",
        "timestamp": 1330560000000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "funder": [
    {
      "DOI": "10.13039/501100004963",
      "name": "Seventh Framework Programme",
      "doi-asserted-by": "publisher",
      "award": [
        "216886"
      ],
      "id": [
        {
          "id": "10.13039/501100004963",
          "id-type": "DOI",
          "asserted-by": "publisher"
        }
      ]
    },
    {
      "DOI": "10.13039/501100004965",
      "name": "Sixth Framework Programme",
      "doi-asserted-by": "publisher",
      "award": [
        "IST 2002-506778"
      ],
      "id": [
        {
          "id": "10.13039/501100004965",
          "id-type": "DOI",
          "asserted-by": "publisher"
        }
      ]
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2012,
        3
      ]
    ]
  },
  "abstract": "<jats:p>The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. For decades, computer Go has defied the classical methods in game tree search that worked so successfully for chess and checkers. However, recent play in computer Go has been transformed by a new paradigm for tree search based on Monte-Carlo methods. 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.</jats:p>",
  "DOI": "10.1145/2093548.2093574",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2012,
        2,
        22
      ]
    ],
    "date-time": "2012-02-22T18:42:36Z",
    "timestamp": 1329936156000
  },
  "page": "106-113",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 124,
  "title": "The grand challenge of computer Go",
  "prefix": "10.1145",
  "volume": "55",
  "author": [
    {
      "given": "Sylvain",
      "family": "Gelly",
      "sequence": "first",
      "affiliation": [
        {
          "name": "EPC TAO, INRIA Saclay &amp; LRI, Orsay, France"
        }
      ]
    },
    {
      "given": "Levente",
      "family": "Kocsis",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "MTA SZTAKI, Budapest, Hungary"
        }
      ]
    },
    {
      "given": "Marc",
      "family": "Schoenauer",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "EPC TAO, INRIA Saclay &amp; LRI, Orsay, France"
        }
      ]
    },
    {
      "given": "Mich\u00e8le",
      "family": "Sebag",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "EPC TAO, INRIA Saclay &amp; LRI, Orsay, France"
        }
      ]
    },
    {
      "given": "David",
      "family": "Silver",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "University College London, London, U.K."
        }
      ]
    },
    {
      "given": "Csaba",
      "family": "Szepesv\u00e1ri",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "University of Alberta, Edmonton, Canada"
        }
      ]
    },
    {
      "given": "Olivier",
      "family": "Teytaud",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "EPC TAO, INRIA Saclay &amp; LRI, Orsay, France"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        2012,
        3
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_1",
      "first-page": "2",
      "article-title": "Carlo techniques and computer Go. In C.-S. Lee, M. M\u00fcller, and O. Teytaud, eds",
      "author": "Special",
      "year": "2010",
      "unstructured": "Special issue on Monte Carlo techniques and computer Go. In C.-S. Lee, M. M\u00fcller, and O. Teytaud, eds , IEEE Trans. Comput. Intell. AI in Games , 2 ( 2010 ). Special issue on Monte Carlo techniques and computer Go. In C.-S. Lee, M. M\u00fcller, and O. Teytaud, eds, IEEE Trans. Comput. Intell. AI in Games, 2 (2010).",
      "journal-title": "IEEE Trans. Comput. Intell. AI in Games"
    },
    {
      "key": "e_1_2_1_2_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/34.44404"
    },
    {
      "key": "e_1_2_1_3_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1023/A:1013689704352"
    },
    {
      "key": "e_1_2_1_4_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1950322.1950327"
    },
    {
      "key": "e_1_2_1_5_1",
      "volume-title": "IEEE Symposium on Computational Intelligence and Games (CIG-05)",
      "author": "Bouzy B.",
      "year": "2005",
      "unstructured": "Bouzy , B. , Chaslot , G. Bayesian generation and integration of k-nearest-neighbor patterns for 19 \u00d7 19 Go . In IEEE Symposium on Computational Intelligence and Games (CIG-05) ( 2005 ). Bouzy, B., Chaslot, G. Bayesian generation and integration of k-nearest-neighbor patterns for 19 \u00d7 19 Go. In IEEE Symposium on Computational Intelligence and Games (CIG-05) (2005)."
    },
    {
      "key": "e_1_2_1_6_1",
      "volume-title": "10th International Conference on Advances in Computer Games (ACG-03)",
      "author": "Bouzy B.",
      "year": "2003",
      "unstructured": "Bouzy , B. , Helmstetter , B. Monte-Carlo Go developments . In 10th International Conference on Advances in Computer Games (ACG-03) ( 2003 ), 159--174. Bouzy, B., Helmstetter, B. Monte-Carlo Go developments. In 10th International Conference on Advances in Computer Games (ACG-03) (2003), 159--174."
    },
    {
      "key": "e_1_2_1_7_1",
      "volume-title": "Technical report",
      "author": "Br\u00fcgmann B.",
      "year": "1993",
      "unstructured": "Br\u00fcgmann , B. Monte-Carlo Go . Technical report , Max Planck Institute of Physics , 1993 . Br\u00fcgmann, B. Monte-Carlo Go. Technical report, Max Planck Institute of Physics, 1993."
    },
    {
      "key": "e_1_2_1_8_1",
      "volume-title": "MIT Press",
      "author": "Bubeck S.",
      "year": "2009",
      "unstructured": "Bubeck , S. , Munos , R. , Stoltz , G. , Szepesv\u00e1ri , C. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems 22 (NIPS-22), D. Koller and D. Schuurmans and Y. Bengio and L. Bottou, eds . MIT Press , 2009 , 201--208. Bubeck, S., Munos, R., Stoltz, G., Szepesv\u00e1ri, C. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems 22 (NIPS-22), D. Koller and D. Schuurmans and Y. Bengio and L. Bottou, eds. MIT Press, 2009, 201--208."
    },
    {
      "key": "e_1_2_1_9_1",
      "volume-title": "12th International IEEE Conference on Intelligent Transportation Systems",
      "author": "Cazenave T.",
      "year": "2009",
      "unstructured": "Cazenave , T. , Balbo , F. , Pinson , S. Monte-Carlo bus regulation . In 12th International IEEE Conference on Intelligent Transportation Systems ( 2009 ), 340--345. Cazenave, T., Balbo, F., Pinson, S. Monte-Carlo bus regulation. In 12th International IEEE Conference on Intelligent Transportation Systems (2009), 340--345."
    },
    {
      "key": "e_1_2_1_10_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1944566.1944583"
    },
    {
      "key": "e_1_2_1_11_1",
      "volume-title": "23rd Conference on Uncertainty in Artificial Intelligence (UAI-07)",
      "author": "Coquelin P.A.",
      "year": "2007",
      "unstructured": "Coquelin , P.A. , Munos , R. Bandit algorithms for tree search . In 23rd Conference on Uncertainty in Artificial Intelligence (UAI-07) ( 2007 ), 67--74. Coquelin, P.A., Munos, R. Bandit algorithms for tree search. In 23rd Conference on Uncertainty in Artificial Intelligence (UAI-07) (2007), 67--74."
    },
    {
      "key": "e_1_2_1_12_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1777826.1777833"
    },
    {
      "key": "e_1_2_1_13_1",
      "first-page": "4",
      "article-title": "Computing Elo ratings of move patterns in the game of Go",
      "volume": "30",
      "author": "Coulom R",
      "year": "2007",
      "unstructured": "Coulom , R . Computing Elo ratings of move patterns in the game of Go . Int. Comput. Game. Assoc. J. 30 , 4 ( 2007 ), 198--208. Coulom, R. Computing Elo ratings of move patterns in the game of Go. Int. Comput. Game. Assoc. J. 30, 4 (2007), 198--208.",
      "journal-title": "Int. Comput. Game. Assoc. J."
    },
    {
      "key": "e_1_2_1_14_1",
      "volume-title": "23rd AAAI Conference on Artificial Intelligence (AAAI-08)",
      "author": "Finnsson H.",
      "year": "2008",
      "unstructured": "Finnsson , H. , Bj\u00f6rnsson , Y. Simulation-based approach to general game playing . In 23rd AAAI Conference on Artificial Intelligence (AAAI-08) ( 2008 ), 259--264. Finnsson, H., Bj\u00f6rnsson, Y. Simulation-based approach to general game playing. In 23rd AAAI Conference on Artificial Intelligence (AAAI-08) (2008), 259--264."
    },
    {
      "key": "e_1_2_1_15_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.artint.2011.03.007"
    },
    {
      "key": "e_1_2_1_16_1",
      "volume-title": "Modification of UCT with Patterns in Monte-Carlo Go. Rapport de recherche INRIA RR-6062",
      "author": "Gelly S.",
      "year": "2006",
      "unstructured": "Gelly , S. , Wang , Y. , Munos , R. , Teytaud , O. Modification of UCT with Patterns in Monte-Carlo Go. Rapport de recherche INRIA RR-6062 , 2006 . Gelly, S., Wang, Y., Munos, R., Teytaud, O. Modification of UCT with Patterns in Monte-Carlo Go. Rapport de recherche INRIA RR-6062, 2006."
    },
    {
      "key": "e_1_2_1_17_1",
      "volume-title": "7th International Conference on Computers and, Games (CG-09)",
      "author": "Huang S.",
      "year": "2009",
      "unstructured": "Huang , S. , Coulom , R. , Lin , S. Monte-Carlo simulation balancing in practice . In 7th International Conference on Computers and, Games (CG-09) ( 2009 ), 119--126. Huang, S., Coulom, R., Lin, S. Monte-Carlo simulation balancing in practice. In 7th International Conference on Computers and, Games (CG-09) (2009), 119--126."
    },
    {
      "key": "e_1_2_1_18_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/11871842_29"
    },
    {
      "key": "e_1_2_1_19_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0196-8858(85)90002-8"
    },
    {
      "key": "e_1_2_1_20_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1661445.1661729"
    },
    {
      "key": "e_1_2_1_21_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1090/S0002-9904-1952-09620-8"
    },
    {
      "key": "e_1_2_1_22_1",
      "first-page": "190",
      "article-title": "The games computers (and people) play",
      "volume": "52",
      "author": "Schaeffer J",
      "year": "2000",
      "unstructured": "Schaeffer , J . The games computers (and people) play . Adv. Comput. , 52 ( 2000 ), 190 -- 268 . Schaeffer, J. The games computers (and people) play. Adv. Comput., 52 (2000), 190--268.",
      "journal-title": "Adv. Comput."
    },
    {
      "key": "e_1_2_1_23_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1736406.1736447"
    },
    {
      "key": "e_1_2_1_24_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TSMC.1973.4309272"
    },
    {
      "key": "e_1_2_1_25_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/1597538.1597631"
    }
  ],
  "container-title": "Communications of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/2093548.2093574",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/2093548.2093574",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T09:54:48Z",
    "timestamp": 1750240488000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/2093548.2093574"
    }
  },
  "subtitle": [
    "Monte Carlo tree search and extensions"
  ],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2012,
        3
      ]
    ]
  },
  "references-count": 25,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          2012,
          3
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/2093548.2093574"
  ],
  "URL": "http://dx.doi.org/10.1145/2093548.2093574",
  "relation": {},
  "ISSN": [
    "0001-0782",
    "1557-7317"
  ],
  "subject": [],
  "container-title-short": "Commun. ACM",
  "published": {
    "date-parts": [
      [
        2012,
        3
      ]
    ]
  },
  "assertion": [
    {
      "value": "2012-03-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}