Understanding Sampling Style Adversarial Search Methods

Raghuram Ramanujan, Ashish Sabharwal, Bart Selman
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:473-482, 2010.

Abstract

UCT has recently emerged as an exciting new adversarial reasoning technique based on cleverly balancing exploration and exploita- tion in a Monte-Carlo sampling setting. It has been particularly successful in the game of Go but the reasons for its success are not well understood and attempts to replicate its success in other domains such as Chess have failed. We provide an in-depth analysis of the potential of UCT in domain-independent settings, in cases where heuristic values are available, and the effect of enhancing random playouts to more informed playouts between two weak minimax players. To provide fur- ther insights, we develop synthetic game tree instances and discuss interesting properties of UCT, both empirically and analytically.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-ramanujan10a, title = {Understanding Sampling Style Adversarial Search Methods}, author = {Ramanujan, Raghuram and Sabharwal, Ashish and Selman, Bart}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {473--482}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/ramanujan10a/ramanujan10a.pdf}, url = {https://proceedings.mlr.press/r8/ramanujan10a.html}, abstract = {UCT has recently emerged as an exciting new adversarial reasoning technique based on cleverly balancing exploration and exploita- tion in a Monte-Carlo sampling setting. It has been particularly successful in the game of Go but the reasons for its success are not well understood and attempts to replicate its success in other domains such as Chess have failed. We provide an in-depth analysis of the potential of UCT in domain-independent settings, in cases where heuristic values are available, and the effect of enhancing random playouts to more informed playouts between two weak minimax players. To provide fur- ther insights, we develop synthetic game tree instances and discuss interesting properties of UCT, both empirically and analytically.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Understanding Sampling Style Adversarial Search Methods %A Raghuram Ramanujan %A Ashish Sabharwal %A Bart Selman %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-ramanujan10a %I PMLR %P 473--482 %U https://proceedings.mlr.press/r8/ramanujan10a.html %V R8 %X UCT has recently emerged as an exciting new adversarial reasoning technique based on cleverly balancing exploration and exploita- tion in a Monte-Carlo sampling setting. It has been particularly successful in the game of Go but the reasons for its success are not well understood and attempts to replicate its success in other domains such as Chess have failed. We provide an in-depth analysis of the potential of UCT in domain-independent settings, in cases where heuristic values are available, and the effect of enhancing random playouts to more informed playouts between two weak minimax players. To provide fur- ther insights, we develop synthetic game tree instances and discuss interesting properties of UCT, both empirically and analytically. %Z Reissued by PMLR on 04 October 2026.
APA
Ramanujan, R., Sabharwal, A. & Selman, B.. (2010). Understanding Sampling Style Adversarial Search Methods. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:473-482 Available from https://proceedings.mlr.press/r8/ramanujan10a.html. Reissued by PMLR on 04 October 2026.

Related Material