Time management for Monte-Carlo tree search applied to the game of Go

Shih Chieh Huang; Remi Coulom; Shun-Shii Lin

doi:10.1109/TAAI.2010.78

Time management for Monte-Carlo tree search applied to the game of Go

Shih Chieh Huang, Remi Coulom, Shun-Shii Lin

Department of Computer science & Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Citations (Scopus)

Abstract

Monte-Carlo tree search (MCTS) is a new technique that has produced a huge leap forward in the strength of Go-playing programs. An interesting aspect of MCTS that has been rarely studied in the past is the problem of time management. This paper presents the effect on playing strength of a variety of time-management heuristics for 19 × 19 Go. Results indicate that clever time management can have a very significant effect on playing strength. Experiments demonstrate that the most basic algorithm for sudden-death time controls (dividing the remaining time by a constant) produces a winning rate of 43.2±2.2% against GNU Go 3.8 Level 2, whereas our most efficient time-allocation strategy can reach a winning rate of 60±2.2% without pondering and 67.4±2.1% with pondering.

Original language	English
Title of host publication	Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010
Pages	462-466
Number of pages	5
DOIs	https://doi.org/10.1109/TAAI.2010.78
Publication status	Published - 2010 Dec 1
Event	2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010 - Hsinchu, Taiwan Duration: 2010 Nov 18 → 2010 Nov 20

Publication series

Name	Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010

Other

Other	2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010
Country	Taiwan
City	Hsinchu
Period	10/11/18 → 10/11/20

Fingerprint

Keywords

Game of Go
Monte-Carlo tree search
Time management

ASJC Scopus subject areas

Artificial Intelligence
Computational Theory and Mathematics

Cite this

Huang, S. C., Coulom, R., & Lin, S-S. (2010). Time management for Monte-Carlo tree search applied to the game of Go. In Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010 (pp. 462-466). [5695493] (Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010). https://doi.org/10.1109/TAAI.2010.78

Time management for Monte-Carlo tree search applied to the game of Go. / Huang, Shih Chieh; Coulom, Remi; Lin, Shun-Shii.

Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010. 2010. p. 462-466 5695493 (Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Huang, SC, Coulom, R & Lin, S-S 2010, Time management for Monte-Carlo tree search applied to the game of Go. in Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010., 5695493, Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010, pp. 462-466, 2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010, Hsinchu, Taiwan, 10/11/18. https://doi.org/10.1109/TAAI.2010.78

Huang SC, Coulom R, Lin S-S. Time management for Monte-Carlo tree search applied to the game of Go. In Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010. 2010. p. 462-466. 5695493. (Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010). https://doi.org/10.1109/TAAI.2010.78

@inproceedings{b2ba836898bc4ebe8d91d79d3b38cf0a,

title = "Time management for Monte-Carlo tree search applied to the game of Go",

abstract = "Monte-Carlo tree search (MCTS) is a new technique that has produced a huge leap forward in the strength of Go-playing programs. An interesting aspect of MCTS that has been rarely studied in the past is the problem of time management. This paper presents the effect on playing strength of a variety of time-management heuristics for 19 × 19 Go. Results indicate that clever time management can have a very significant effect on playing strength. Experiments demonstrate that the most basic algorithm for sudden-death time controls (dividing the remaining time by a constant) produces a winning rate of 43.2±2.2% against GNU Go 3.8 Level 2, whereas our most efficient time-allocation strategy can reach a winning rate of 60±2.2% without pondering and 67.4±2.1% with pondering.",

keywords = "Game of Go, Monte-Carlo tree search, Time management",

author = "Huang, {Shih Chieh} and Remi Coulom and Shun-Shii Lin",

year = "2010",

month = dec

day = "1",

doi = "10.1109/TAAI.2010.78",

language = "English",

isbn = "9780769542539",

series = "Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010",

pages = "462--466",

booktitle = "Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010",

note = "2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010 ; Conference date: 18-11-2010 Through 20-11-2010",

}

TY - GEN

T1 - Time management for Monte-Carlo tree search applied to the game of Go

AU - Huang, Shih Chieh

AU - Coulom, Remi

AU - Lin, Shun-Shii

PY - 2010/12/1

Y1 - 2010/12/1

N2 - Monte-Carlo tree search (MCTS) is a new technique that has produced a huge leap forward in the strength of Go-playing programs. An interesting aspect of MCTS that has been rarely studied in the past is the problem of time management. This paper presents the effect on playing strength of a variety of time-management heuristics for 19 × 19 Go. Results indicate that clever time management can have a very significant effect on playing strength. Experiments demonstrate that the most basic algorithm for sudden-death time controls (dividing the remaining time by a constant) produces a winning rate of 43.2±2.2% against GNU Go 3.8 Level 2, whereas our most efficient time-allocation strategy can reach a winning rate of 60±2.2% without pondering and 67.4±2.1% with pondering.

AB - Monte-Carlo tree search (MCTS) is a new technique that has produced a huge leap forward in the strength of Go-playing programs. An interesting aspect of MCTS that has been rarely studied in the past is the problem of time management. This paper presents the effect on playing strength of a variety of time-management heuristics for 19 × 19 Go. Results indicate that clever time management can have a very significant effect on playing strength. Experiments demonstrate that the most basic algorithm for sudden-death time controls (dividing the remaining time by a constant) produces a winning rate of 43.2±2.2% against GNU Go 3.8 Level 2, whereas our most efficient time-allocation strategy can reach a winning rate of 60±2.2% without pondering and 67.4±2.1% with pondering.

KW - Game of Go

KW - Monte-Carlo tree search

KW - Time management

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

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

U2 - 10.1109/TAAI.2010.78

DO - 10.1109/TAAI.2010.78

M3 - Conference contribution

AN - SCOPUS:79951753159

SN - 9780769542539

T3 - Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010

SP - 462

EP - 466

BT - Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010

T2 - 2010 15th Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010

Y2 - 18 November 2010 through 20 November 2010

ER -

Access to Document

10.1109/TAAI.2010.78