PACHI: State of the Art Open Source Go Program
Lecture notes in computer sciencePublished 1 January 2012
P Baudis, Jean-loup Gailly
Citations64
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A state of the art implementation of the Monte Carlo Tree Search algorithm for the game of Go and three notable original improvements: an adaptive time control algorithm, dynamic komi, and the usage of the criticality statistic are described.
Abstract
We present a state of the art implementation of the Monte Carlo Tree Search algorithm for the game of Go. Our Pachi software is currently one of the strongest open source Go programs, competing at the top level with other programs and playing evenly against advanced human players. We describe our implementation and choice of published algorithms as well as three notable original improvements: (1) an adaptive time control algorithm, (2) dynamic komi, and (3) the usage of the criticality statistic. We also present new methods to achieve efficient scaling both in terms of multiple threads and multiple machines in a cluster.
Keywords
PsychologyComputer ScienceEconomics, Econometrics and Finance
New Mathematics and Natural ComputationPROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCH
436 Citations2008Guillaume Chaslot, Mark H. M. Winands +3 more
Two progressive strategies for MCTS are introduced, called progressive bias and progressive unpruning, which enable the use of relatively time-expensive heuristic knowledge without speed reduction.
HAL (Le Centre pour la Communication Scientifique Directe)Modification of UCT with Patterns in Monte-Carlo Go
293 Citations2006Sylvain Gelly, Yizao Wang +2 more
Lecture notes in computer scienceParallel Monte-Carlo Tree Search
232 Citations2008Guillaume Chaslot, Mark H. M. Winands +1 more
Three parallelization methods for MCTS are discussed: leaf parallelization, root Parallelization, and tree parallelization.
Lecture notes in computer scienceArtificial Neural Networks — ICANN 2001
184 Citations2001Georg Dorffner, Kurt Hornik
Some of the concepts underpinning Recursive Neural Networks, i.e. neural network models able to deal with data represented as directed acyclic graphs, are reviewed.
IEEE Transactions on Computational Intelligence and AI in GamesFuego—An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search
176 Citations2010Markus Enzenberger, Martin Müller +2 more
An overview of the development and current state of the FUEGO project is given, which describes the reusable components of the software framework and specific algorithms used in the Go engine.
Parallel Algorithms
88 Citations2008Henri Casanova
Parallel Algorithms presents a rigorous yet accessible treatment of theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and essential notions of scheduling.
Lecture notes in computer scienceAdding Expert Knowledge and Exploration in Monte-Carlo Tree Search
61 Citations2010Guillaume Chaslot, Christophe Fiter +3 more
A new exploration term, more efficient than classical UCT-like exploration terms, which combines efficiently expert rules, patterns extracted from datasets, All-Moves-As-First values, and classical online values is presented.
Lecture notes in computer scienceOn the Scalability of Parallel UCT
43 Citations2011Richard Segal
This paper first analyzes the single-threaded scaling of Fuego and finds that there is an upper bound on the play-quality improvements which can come from additional search, and determines the maximum amount of parallelism supported by MCTS.
Lecture notes in computer scienceScalability and Parallelization of Monte-Carlo Tree Search
41 Citations2011Amine Bourki, Guillaume Chaslot +10 more
This work analyzes Monte-Carlo Tree Search's scalability, and in particular its limitations and the implications in terms of parallelization, on the Go program MoGo and the Havannah program Shakti, and achieves adequate efficiency for the parallel version.
Proceedings of the International Symposium on Combinatorial SearchScalable Distributed Monte-Carlo Tree Search
40 Citations2021Kazuki Yoshizoe, Akihiro Kishimoto +3 more
This work presents a massively parallel MCTS algorithm, that applies the TDS parallelism to the Upper Confidence bound Applied to Trees (UCT) algorithm, which is the most representative M CTS algorithm and introduces a reformulation of UCT called Depth-First UCT to drastically decrease communication overhead.
Lecture notes in computer scienceLearning on Graphs in the Game of Go
38 Citations2001Thore Graepel, Mike Goutrié +2 more
The common fate graph (CFG) is introduced as an adequate representation of board positions for learning and a support vector machine (SVM) and a kernel perceptron are trained to discriminate good moves from bad moves on a collection of life-and-death problems and on 9 × 9 game records.
Time Management for Monte-Carlo Tree Search Applied to the Game of Go
18 Citations2010Shih-Chieh Huang, Rémi Coulom +1 more
Results indicate that clever time management can have a very significant effect on playing strength in the case of Monte-Carlo tree search.
ICGA JournalBalancing MCTS by Dynamically Adjusting the Komi Value
14 Citations2011P Baudis
A conjecture on the resilience of the game search tree to changes in the evaluation function throughout the search is formulated and a comparison of MCTS and the traditional tree search in the context of extreme positions is compared.
ICGA JournalLocalizing Search in Monte-Carlo Go using Statistical Covariance
6 Citations2009Seth Pellegrino, Andrew Hubbard +3 more
Using statistical covariance as a tool to execute spatial localization in the authors' Go program, OREGO, to overcome the challenge of static board evaluation.