Time Management for Monte-Carlo Tree Search in Go

Hendrik Baier; Mark H.M. Winands

doi:10.1007/978-3-642-31866-5_4

Time Management for Monte-Carlo Tree Search in Go

Hendrik Baier, Mark H.M. Winands

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

Abstract

The dominant approach for programs playing the game of Go is nowadays Monte-Carlo Tree Search (MCTS). While MCTS allows for fine-grained time control, little has been published on time management for MCTS programs under tournament conditions. This paper investigates the effects that various time-management strategies have on the playing strength in Go. We consider strategies taken from the literature as well as newly proposed and improved ones. We investigate both semi-dynamic strategies that decide about time allocation for each search before it is started, and dynamic strategies that influence the duration of each move search while it is already running. In our experiments, two domain-independent enhanced strategies, EARLY-C and CLOSE-N, are tested; each of them provides a significant improvement over the state of the art.

Original language	English
Title of host publication	Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers
Editors	H.J. van den Herik, A. Plaat
Place of Publication	Berlin
Publisher	Springer
Pages	39-51
Number of pages	13
ISBN (Electronic)	978-3-642-31866-5
ISBN (Print)	9783642318658
DOIs	https://doi.org/10.1007/978-3-642-31866-5_4
Publication status	Published - 2012
Externally published	Yes
Event	13th International Conference on Advances in Computer Games, ACG 2011 - Tilburg, Netherlands Duration: 20 Nov 2011 → 22 Nov 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7168 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Conference on Advances in Computer Games, ACG 2011
Country/Territory	Netherlands
City	Tilburg
Period	20/11/11 → 22/11/11

Access to Document

10.1007/978-3-642-31866-5_4

Cite this

Baier, H., & Winands, M. H. M. (2012). Time Management for Monte-Carlo Tree Search in Go. In H. J. van den Herik, & A. Plaat (Eds.), Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers (pp. 39-51). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7168 LNCS). Springer. https://doi.org/10.1007/978-3-642-31866-5_4

Baier, Hendrik ; Winands, Mark H.M. / Time Management for Monte-Carlo Tree Search in Go. Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers. editor / H.J. van den Herik ; A. Plaat. Berlin : Springer, 2012. pp. 39-51 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5be2872618964bdbb92b6d5aaad1500c,

title = "Time Management for Monte-Carlo Tree Search in Go",

abstract = "The dominant approach for programs playing the game of Go is nowadays Monte-Carlo Tree Search (MCTS). While MCTS allows for fine-grained time control, little has been published on time management for MCTS programs under tournament conditions. This paper investigates the effects that various time-management strategies have on the playing strength in Go. We consider strategies taken from the literature as well as newly proposed and improved ones. We investigate both semi-dynamic strategies that decide about time allocation for each search before it is started, and dynamic strategies that influence the duration of each move search while it is already running. In our experiments, two domain-independent enhanced strategies, EARLY-C and CLOSE-N, are tested; each of them provides a significant improvement over the state of the art.",

author = "Hendrik Baier and Winands, {Mark H.M.}",

year = "2012",

doi = "10.1007/978-3-642-31866-5_4",

language = "English",

isbn = "9783642318658",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "39--51",

editor = "{van den Herik}, H.J. and A. Plaat",

booktitle = "Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers",

note = "13th International Conference on Advances in Computer Games, ACG 2011 ; Conference date: 20-11-2011 Through 22-11-2011",

}

Baier, H & Winands, MHM 2012, Time Management for Monte-Carlo Tree Search in Go. in HJ van den Herik & A Plaat (eds), Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7168 LNCS, Springer, Berlin, pp. 39-51, 13th International Conference on Advances in Computer Games, ACG 2011, Tilburg, Netherlands, 20/11/11. https://doi.org/10.1007/978-3-642-31866-5_4

Time Management for Monte-Carlo Tree Search in Go. / Baier, Hendrik; Winands, Mark H.M.
Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers. ed. / H.J. van den Herik; A. Plaat. Berlin: Springer, 2012. p. 39-51 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7168 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Time Management for Monte-Carlo Tree Search in Go

AU - Baier, Hendrik

AU - Winands, Mark H.M.

PY - 2012

Y1 - 2012

N2 - The dominant approach for programs playing the game of Go is nowadays Monte-Carlo Tree Search (MCTS). While MCTS allows for fine-grained time control, little has been published on time management for MCTS programs under tournament conditions. This paper investigates the effects that various time-management strategies have on the playing strength in Go. We consider strategies taken from the literature as well as newly proposed and improved ones. We investigate both semi-dynamic strategies that decide about time allocation for each search before it is started, and dynamic strategies that influence the duration of each move search while it is already running. In our experiments, two domain-independent enhanced strategies, EARLY-C and CLOSE-N, are tested; each of them provides a significant improvement over the state of the art.

AB - The dominant approach for programs playing the game of Go is nowadays Monte-Carlo Tree Search (MCTS). While MCTS allows for fine-grained time control, little has been published on time management for MCTS programs under tournament conditions. This paper investigates the effects that various time-management strategies have on the playing strength in Go. We consider strategies taken from the literature as well as newly proposed and improved ones. We investigate both semi-dynamic strategies that decide about time allocation for each search before it is started, and dynamic strategies that influence the duration of each move search while it is already running. In our experiments, two domain-independent enhanced strategies, EARLY-C and CLOSE-N, are tested; each of them provides a significant improvement over the state of the art.

UR - http://www.scopus.com/inward/record.url?scp=84865039634&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31866-5_4

DO - 10.1007/978-3-642-31866-5_4

M3 - Conference contribution

SN - 9783642318658

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 39

EP - 51

BT - Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers

A2 - van den Herik, H.J.

A2 - Plaat, A.

PB - Springer

CY - Berlin

T2 - 13th International Conference on Advances in Computer Games, ACG 2011

Y2 - 20 November 2011 through 22 November 2011

ER -

Baier H, Winands MHM. Time Management for Monte-Carlo Tree Search in Go. In van den Herik HJ, Plaat A, editors, Advances in Computer Games - 13th International Conference, ACG 2011, Revised Selected Papers. Berlin: Springer. 2012. p. 39-51. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31866-5_4

Time Management for Monte-Carlo Tree Search in Go

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this