November – 2008 ^December

We consider scenarios where a sequence of tests is to be applied to an object, where the result of a test may be that a decision (such as classification of the object) can be made without running additional tests. Thus, one seeks an ordering of the tests that is optimal in some sense, such as minimum expected resource consumption. Such sequences of tests are commonly used in computer vision cite{Viola2001} and other applications. We examine conditions under which one can efficiently find an optimal ordering of the tests. Two types of dependencies between tests are examined: ordering constraints, and statistical dependencies. We show that with dependencies the optimization problem is NP-hard in the general case, and provide low-order polynomial time algorithms for special cases with non-trivial constraint structures. (Patent pending)

Poker is a challenging problem for artificial intelligence research: multiple opponents (up to 10), stochastic element (cards being dealt), imperfect information (don't know the opponent's cards), deception (bluffing), user modeling (identifying player patterns), and risk management (betting decisions). Unlike the classic AI game, chess, poker is more relevant to real-world situations including negotiations, military strategy, and e-commerce. For over a decade, the University of Alberta Computer Poker Group has been working on building a high-performance poker program. This work has led us through multiple distinct phases of program design, each new idea "promising" to be the breakthrough to world-class play. Finally, we appear to be close. In a recent Man Versus Machine Match, University of Alberta programs narrowly defeated a team of world-class players. In this talk we will motivate the research, compare the different program designs, and discuss what it will take to raise the stakes in man-machine poker competitions.