1. Time Management for Monte Carlo Tree Search
- Author
-
Mark H. M. Winands, Hendrik Baier, DKE Scientific staff, RS: FSE DACS NSO, and RS: FSE DACS
- Subjects
Artificial intelligence ,Computer science ,Monte Carlo Tree Search ,Time allocation ,Monte Carlo tree search ,Monte Carlo method ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,time management ,0202 electrical engineering, electronic engineering, information engineering ,Resource management ,Time management ,Electrical and Electronic Engineering ,Duration (project management) ,business.industry ,020207 software engineering ,game tree search ,Variety (cybernetics) ,Tree (data structure) ,010201 computation theory & mathematics ,Control and Systems Engineering ,business ,computer ,Software - Abstract
Monte Carlo Tree Search (MCTS) is a popular approach for tree search in a variety of games. While MCTS allows for fine-grained time control, not much has been published on time management for MCTS programs under tournament conditions. This paper first investigates the effects of various time-management strategies on playing strength in the challenging game of Go. A number of domain-independent strategies are then tested in the domains Connect-4, Breakthrough, Othello, and Catch the Lion. We consider strategies taken from the literature as well as newly proposed and improved ones. Strategies include 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. Furthermore, we analyze the effects of time management strategies on the distribution of time over the moves of an average game, allowing us to partly explain their performance. In the experiments, the domain-independent strategy STOP provides a significant improvement over the state of the art in Go, and is the most effective time management strategy tested in all five domains.
- Published
- 2016