A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis
Abstract
An algorithm is developed for searching the trees of perfect information games involving chance events. Many dice games (e.g. backgammon, craps, and monopoly and similar board games), and some card games (e.g. casino blackjack), have this property. For depth 3 trees, empirical observation reveals a search reduction of more than 50 percent, while closed-form analysis reveals a best-case complexity of O(N**2). This represents a substantial savings over the O(N**3) behavior of the obvious search strategy.
Cite
Text
Ballard. "A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis." AAAI Conference on Artificial Intelligence, 1982.Markdown
[Ballard. "A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis." AAAI Conference on Artificial Intelligence, 1982.](https://mlanthology.org/aaai/1982/ballard1982aaai-search/)BibTeX
@inproceedings{ballard1982aaai-search,
title = {{A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis}},
author = {Ballard, Bruce W.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1982},
pages = {111-114},
url = {https://mlanthology.org/aaai/1982/ballard1982aaai-search/}
}