D. Chris Rayner

AAAI Conference 2011 Conference Paper

Euclidean Heuristic Optimization

• D. Chris Rayner
• Michael Bowling
• Nathan Sturtevant

We pose the problem of constructing good search heuristics as an optimization problem: minimizing the loss between the true distances and the heuristic estimates subject to admissibility and consistency constraints. For a well-motivated choice of loss function, we show performing this optimization is tractable. In fact, it corresponds to a recently proposed method for dimensionality reduction. We prove this optimization is guaranteed to produce admissible and consistent heuristics, generalizes and gives insight into differential heuristics, and show experimentally that it produces strong heuristics on problems from three distinct search domains.

IJCAI Conference 2007 Conference Paper

• D. Chris Rayner
• Katherine Davison
• Vadim Bulitko
• Kenneth Anderson
• Jieshan Lu

Learning real-time search, which interleaves planning and acting, allows agents to learn from multiple trials and respond quickly. Such algorithms require no prior knowledge of the environment and can be deployed without pre-processing. We introduce Prioritized-LRTA* (P-LRTA*), a learning real-time search algorithm based on Prioritized Sweeping. P-LRTA* focuses learning on important areas of the search space, where the importance of a state is determined by the magnitude of the updates made to neighboring states. Empirical tests on path-planning in commercial game maps show a substantial learning speed-up over state-of-the-art real-time search algorithms.

UAI Conference 2005 Conference Paper

Bayes? Bluff: Opponent Modelling in Poker

• Finnegan Southey
• Michael H. Bowling
• Bryce Larson
• Carmelo Piccione
• Neil Burch
• Darse Billings
• D. Chris Rayner

Poker is a challenging problem for artificial intelligence, with non-deterministic dynamics, partial observability, and the added difficulty of unknown adversaries. Modelling all of the uncertainties in this domain is not an easy task. In this paper we present a Bayesian probabilistic model for a broad class of poker games, separating the uncertainty in the game dynamics from the uncertainty of the opponent's strategy. We then describe approaches to two key subproblems: (i) inferring a posterior over opponent strategies given a prior distribution and observations of their play, and (ii) playing an appropriate response to that distribution. We demonstrate the overall approach on a reduced version of poker using Dirichlet priors and then on the full game of Texas hold'em using a more informed prior. We demonstrate methods for playing effective responses to the opponent, based on the posterior.