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 and 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/Territory	Taiwan
City	Hsinchu
Period	2010/11/18 → 2010/11/20

Keywords

Game of Go
Monte-Carlo tree search
Time management

ASJC Scopus subject areas

Artificial Intelligence
Computational Theory and Mathematics

Access to Document

10.1109/TAAI.2010.78

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, SS 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, 2010/11/18. https://doi.org/10.1109/TAAI.2010.78

Huang SC, Coulom R, Lin SS. 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 Lin, {Shun Shii}",

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 -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this