  One-shot neural architecture search (NAS) methods significantly reduce the
search cost by considering the whole search space as one network, which only
needs to be trained once. However, current methods select each operation
independently without considering previous layers. Besides, the historical
information obtained with huge computation cost is usually used only once and
then discarded. In this paper, we introduce a sampling strategy based on Monte
Carlo tree search (MCTS) with the search space modeled as a Monte Carlo tree
(MCT), which captures the dependency among layers. Furthermore, intermediate
results are stored in the MCT for the future decision and a better
exploration-exploitation balance. Concretely, MCT is updated using the training
loss as a reward to the architecture performance; for accurately evaluating the
numerous nodes, we propose node communication and hierarchical node selection
methods in the training and search stages, respectively, which make better uses
of the operation rewards and hierarchical information. Moreover, for a fair
comparison of different NAS methods, we construct an open-source NAS benchmark
of a macro search space evaluated on CIFAR-10, namely NAS-Bench-Macro.
Extensive experiments on NAS-Bench-Macro and ImageNet demonstrate that our
method significantly improves search efficiency and performance. For example,
by only searching $20$ architectures, our obtained architecture achieves
$78.0\%$ top-1 accuracy with 442M FLOPs on ImageNet. Code (Benchmark) is
available at: \url{https://github.com/xiusu/NAS-Bench-Macro}.
