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

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v24-weinstein12a, title = {Rollout-based Game-tree Search Outprunes Traditional Alpha-beta}, author = {Weinstein, Ari and Littman, Michael L. and Goschin, Sergiu}, booktitle = {Proceedings of the Tenth European Workshop on Reinforcement Learning}, pages = {155--167}, year = {2013}, editor = {Deisenroth, Marc Peter and Szepesvári, Csaba and Peters, Jan}, volume = {24}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {30 Jun--01 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v24/weinstein12a/weinstein12a.pdf}, url = {https://proceedings.mlr.press/v24/weinstein12a.html}, 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.} }
Endnote
%0 Conference Paper %T Rollout-based Game-tree Search Outprunes Traditional Alpha-beta %A Ari Weinstein %A Michael L. Littman %A Sergiu Goschin %B Proceedings of the Tenth European Workshop on Reinforcement Learning %C Proceedings of Machine Learning Research %D 2013 %E Marc Peter Deisenroth %E Csaba Szepesvári %E Jan Peters %F pmlr-v24-weinstein12a %I PMLR %P 155--167 %U https://proceedings.mlr.press/v24/weinstein12a.html %V 24 %X 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.
RIS
TY - CPAPER TI - Rollout-based Game-tree Search Outprunes Traditional Alpha-beta AU - Ari Weinstein AU - Michael L. Littman AU - Sergiu Goschin BT - Proceedings of the Tenth European Workshop on Reinforcement Learning DA - 2013/01/12 ED - Marc Peter Deisenroth ED - Csaba Szepesvári ED - Jan Peters ID - pmlr-v24-weinstein12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 24 SP - 155 EP - 167 L1 - http://proceedings.mlr.press/v24/weinstein12a/weinstein12a.pdf UR - https://proceedings.mlr.press/v24/weinstein12a.html AB - 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. ER -
APA
Weinstein, A., Littman, M.L. & Goschin, S.. (2013). Rollout-based Game-tree Search Outprunes Traditional Alpha-beta. Proceedings of the Tenth European Workshop on Reinforcement Learning, in Proceedings of Machine Learning Research 24:155-167 Available from https://proceedings.mlr.press/v24/weinstein12a.html.

Related Material