This page contains all sorts of papers and things related to my academic work (1996 – 2002).
Computer Poker Artificial Intelligence
[PostScript File — 576k]
[Postscript File] [PDF File]
[PostScript File — 311k]
[PostScript File — 154k]
[PDF file — 110k]
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.
Sequence Alignment Algorithms
[PostScript File — 105k]
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).
Parallel and Distributed Systems
[PostScript File — 172k]
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 — 46k]
We present a technique for using parallel computing to speedup the traversal of image signature tree for color-based image retrieval from large databases.