Tristan Cazenave - Monte Carlo Search: First Workshop, MCS 2020, Held in Conjunction with IJCAI 2020, Virtual Event, January 7, 2021, Proceedings

More information about this series at http://www.springer.com/series/7899

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

These proceedings contain the papers presented at the first Monte Carlo Search Workshop, which was held virtually as an IJCAI workshop on January 7, 2021.

Monte Carlo search is a family of search algorithms that have many applications in different domains. It is the state of the art in many perfect- and imperfect-information games. Other applications include the RNA inverse folding problem, logistics, multiple sequence alignment, general game playing, puzzles, 3D packing with object orientation, cooperative pathfinding, software testing and heuristic model checking.

Each paper was sent to three reviewers. If conflicting views on a paper were reported, it was sent to an additional reviewer. Program chairs were not involved in the review assignment and final selection of their own papers as these were handled separately by the other chairs. In the end, 11 contributions were accepted for presentation at the workshop, of which nine made it into these proceedings. Here we provide a brief outline of these nine contributions, in the order in which they appear in the proceedings.

The Search Algorithm for the Game of Bridge by Tristan Cazenave and Vronique Ventos proposes a search algorithm that improves on perfect information Monte Carlo search for some contracts of bridge. It repairs two known defects of perfect information Monte Carlo search, namely strategy fusion and non locality.

Stabilized Nested Rollout Policy Adaptation by Tristan Cazenave, Jean-Baptiste Sevestre, and Mathieu Toulemont presents a straightforward improvement of Nested Rollout Policy Adaptation (NRPA) that gives good results in SameGame, the Traveling Salesman with Time Windows, and Expression Discovery. It stabilizes the learning of the policy by playing multiple playouts before adaptations at level one.

In zoNNscan: A Boundary-Entropy Index for Zone Inspection of Neural Models, Adel Jaouen and Erwan Le Merrer introduce an index that is intended to inform the boundary uncertainty (in terms of the presence of other classes) around one given input data point. It is based on confidence entropy, and is implemented through Monte Carlo sampling in the multidimensional ball surrounding that input.

Reward shaping is often a hidden critical component of reinforcement learning. In Ordinal Monte Carlo Tree Search, Tobias Joppen and Johannes Frnkranz discuss the use of only a ranking information on rewards (as opposed to numerical values). This makes their proposed Monte Carlo tree search (MCTS) variant robust to poorly chosen reward values.

Monte Carlo Game Solver by Tristan Cazenave uses the information on move ordering collected during a Monte Carlo tree search to order moves in Alpha-Beta search. Various small games are solved with this Alpha-Beta variant equipped with Monte Carlo move ordering. Overall, it improves on Alpha-Beta with simple move ordering heuristics.

Generalized Nested Rollout Policy Adaptation by Tristan Cazenave demonstrates mathematically that Generalized Nested Rollout Policy Adaptation with a bias and a temperature is equivalent to Nested Rollout Policy Adaptation with initialization of the weights and a different learning rate. Using a bias is more convenient and more general than initializing weights as demonstrated for SameGame. Good results are also obtained for the Traveling Salesman Problem with Time Windows.

Monte Carlo Inverse Folding by Tristan Cazenave and Thomas Fournier addresses the design of RNA molecules with Monte Carlo search. They test various optimizations of NRPA on the RNA design problem and reach state-of-the-art results on the Eterna100 benchmark using general improvements of Monte Carlo search.