Generalized Nested Rollout Policy Adaptation
This work addresses performance enhancements for single-player game algorithms, but it is incremental as it builds directly on NRPA.
The authors tackled the problem of improving the Nested Rollout Policy Adaptation (NRPA) algorithm for single-player games by generalizing it with a temperature and bias, resulting in GNRPA, which showed improvements in experiments on SameGame and the Traveling Salesman Problem with Time Windows.
Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo search algorithm for single player games. In this paper we propose to generalize NRPA with a temperature and a bias and to analyze theoretically the algorithms. The generalized algorithm is named GNRPA. Experiments show it improves on NRPA for different application domains: SameGame and the Traveling Salesman Problem with Time Windows.