Aaron Davidson's Academic Work

This page contains all sorts of papers and things related to my university work.

MSc. Thesis: Opponent Modeling in Poker: Learning and Acting in a Hostile Environment
[PostScript File -- 576k]

Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terence Schauenberg, and Duane Szafron. Approximating Game-Theoretic Optimal Strategies for Full-scale Poker. Proceedings of the 2003 International Joint Conference on Artificial Intelligence (IJCAI-03). 2003. [Postscript File] [PDF File]
Darse Billings, Aaron Davidson, Jonathan Schaeffer, Duane Szafron. The Challenge of Poker, Artificial Intelligence Journal, 2001. [PostScript File -- 311k]
Aaron Davidson, Darse Billings, Jonathan Schaeffer, Duane Szafron. Improved Opponent Modeling in Poker, Proceedings of The 2000 International Conference on Artificial Intelligence (ICAI'2000), Las Vegas, Nevada, pp 1467-1473, 2000. [PostScript File -- 154k]
Using Artificial Neural Networks to Model Opponents in Texas Hold'em [PDF file -- 110k]
Abstract
This paper describes a system for predicting an opponent's next action in the game of Texas Hold'em, a common Poker variant. Network performance in a variety of situations is shown, as well as compared to current opponent modeling systems. A technique for graphical representation of neural networks is also discussed as a useful tool for feature discovery.

Aaron Davidson. A Fast Pruning Algorithm for Optimal Sequence Alignment. Proceedings of The 2nd IEEE International Symposium on Bioinformatics & Bioengineering (BIBE'2001), November 2001. [PostScript File -- 105k]
Abstract
Sequence alignment is an important operation in computational biology. Both dynamic programming and A* heuristic search algorithms for optimal sequence alignment are discussed and evaluated. Presented here are two new algorithms for optimal pairwise sequence alignment which outperform traditional methods on very large problem instances (hundreds of thousands of characters, for example). The technique combines the benefits of dynamic programming and A* heuristic search, with a minimal amount of additional overhead. The dynamic programming matrix is traversed along antidiagonals, bounding the computation to exclude portions of the matrix that cannot contain optimal paths. An admissible heuristic assists in pruning away unnecessary areas of the matrix, while preserving optimal solutions for any given scoring function. Since memory requirements are a major concern for large sequence alignment problems, it is shown how the standard algorithm (requiring quadratic space) can be reformulated as a divide and conquer algorithm (requiring only linear space, at the cost of some recomputuation).

Solving Games with Distributed Computing: A System for Network RAM

Abstract
The problem of solving games is introduced as a memory-bound computation (requiring a great deal more memory than is physically available) and distributed network memory is introduced as a possible technique for providing large amounts of relatively fast memory (compared to disk-based virtual memory) to these applications. A specialized system is built and evaluated for managing large shared, read-only memory spaces for parallel access. A large amount of effort is focused on robustness and proper idle resource management. The final system provides significantly better access times than were previously possible.
[PostScript File -- 172k]
Aaron Davidson, John Anvik, Mario A. Nascimento. Parallel Traversal of Signature Trees for Fast CBIR, Proceedings of the ACM Multimedia 2001. September 2001. [PostScript File -- 46k]
Abstract
We present a technique for using parallel computing to speedup the traversal of image signature tree for color-based image retrieval from large databases.