Rollout-based Game-tree Search Outprunes Traditional Alpha-beta

[edit]

Ari Weinstein, Michael L. Littman, Sergiu Goschin ;
Proceedings of the Tenth European Workshop on Reinforcement Learning, PMLR 24:155-167, 2013.

Abstract

Recently, rollout-based planning and search methods have emerged as an alternative to traditional tree-search methods. The fundamental operation in rollout-based tree search is the generation of trajectories in the search tree from root to leaf. Game-playing programs based on Monte-Carlo rollouts methods such as “UCT” have proven remarkably effective at using information from trajectories to make state-of-the-art decisions at the root. In this paper, we show that trajectories can be used to prune more aggressively than classical alpha-beta search. We modify a rollout-based method, FSSS, to allow for use in game-tree search and show it outprunes alpha-beta both empirically and formally.

Related Material