Proceedings:
Book One
Volume
Issue:
Proceedings of the AAAI Conference on Artificial Intelligence, 2
Track:
Problem Solving and Search
Downloads:
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.
AAAI
Proceedings of the AAAI Conference on Artificial Intelligence, 2