A search procedure for perfect information games of chance: its formulation and analysis
Bruce W. Ballard · National Conference on Artificial Intelligence · 1982
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.