A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis

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.

Authors

• Bruce W. Ballard

Keywords

No keywords are indexed for this paper.