Nested Monte Carlo Search (NMCS) [1]} is
a related algorithm that works well for puzzles and optimization problems. It biases its playouts using lower level playouts. At level zero NMCS adopts a randomized playout policy. The main improvement of NMCS over NS is the memorization of the best sequence at each recursion level. Without the memorization of the best sequence the algorithm does not give good results for levels greater than one. Applications of NMCS include Single Player General Game Playing [2]}, Cooperative Pathfinding [3]}, Software testing [4]}, heuristic Model-Checking [5]}, the Pancake problem [6]}, Games [7]} and the RNA inverse folding problem [8]}. Online learning of playout strategies combined with NMCS has given good results on optimization problems [9]}. Online learning of a playout policy in the context of nested searches has been further developed for puzzles and optimization with Nested Rollout Policy Adaptation (NRPA) [10]}. NRPA has found new world records in Morpion Solitaire and crosswords puzzles. Edelkamp, Cazenave and co-workers have applied the NRPA algorithm to multiple problems: The TSPTW problem [11]}, [12]}, 3D Packing with Object Orientation [13]}, the physical traveling salesman problem [14]}, the Multiple Sequence Alignment problem [15]}, Logistics [16]}, [17]}, Graph Coloring [18]} and Inverse Folding [19]}. The principle of NRPA is to adapt the playout policy reinforcing the moves of the best sequence of moves found so far at each level.
