Running the Table: An AI for Computer Billiards

Michael SmithAAAI 2006

Abstract

This paper presents PickPocket, a world-champion billiards AI that integrates physics-based simulation with specialized search algorithms. By addressing the challenges of continuous action spaces and physical stochasticity, PickPocket demonstrates superior strategic reasoning and position play, ultimately winning the international computer billiards competition at the 10th Computer Olympiad.

The Challenge of Computer Billiards

Billiards presents a unique intersection of robotics and strategic reasoning. Unlike discrete games like Chess or Go, billiards operates in a continuous state and action space. A single shot is defined by infinite variations in angle, velocity, and spin.

Figure 1: Parameters defining a billiard shot, including angle (phi), elevation (theta), and spin (a, b).

Furthermore, the game is inherently stochastic; physical imperfections mean that even a perfectly calculated "intended" shot will have a random error or "delta." Finally, success requires "position play"—planning shots not just to sink the current ball, but to leave the cue ball in an advantageous position for the next. Standard game-tree search algorithms fail here because they cannot branch every possible outcome in a continuous, noisy environment.

Methods and Architecture

PickPocket's architecture consists of three main pillars:

  1. Move Generation: To handle the infinite variations of shots, the AI generates a discrete set of "relevant" shots, prioritizing high-probability "straight-in" shots while varying velocity and spin to explore follow-up positions.
  2. Difficulty Estimation: Real-time physics calculation is computationally expensive. The authors precomputed a 4D lookup table using the poolfiz simulator to provide instant success probabilities based on shot geometry.
  3. Search Algorithms: The core of the AI's decision-making is a comparison between two search strategies:
  4. Probabilistic Search: An expectimax-style algorithm that searches deeper (4-ply) but focuses on the intended outcome of a shot, weighted by its success probability.
  5. Monte-Carlo (MC) Sampling: A shallower search (2-ply) that simulates multiple random variations of a shot to see the "average" result. This captures the risk of a shot more accurately.

Results and Tournament Performance

The AI's performance was evaluated through head-to-head testing and tournament play. In internal testing, Monte-Carlo search consistently outperformed deeper Probabilistic search. This suggests that in noisy physical domains, accounting for the "shape" of failure—i.e., whether a miss leaves the opponent with an easy table—is more critical than raw search depth.

Figure 3: Comparative performance of search algorithms (Greedy, Probabilistic, and Monte-Carlo) across high and low error levels.

PickPocket's strategic depth was further validated at the 10th Computer Olympiad. It dominated the round-robin tournament, scoring 200 points and defeating top-tier programs like Pool Master and SkyNet. The AI's ability to prioritize "mobility" (the number of high-probability options available after a shot) allowed it to "run the table" with professional-level consistency.

Conclusion

While PickPocket represents a significant leap in computer billiards, limitations remain. Current models use simplified Gaussian noise, and safety shot generation is relatively rudimentary. Future work will explore more complex error models and continuous function approximations to refine shot selection and defensive play.

Summary updated

BibTeX
@inproceedings{smith2006running,
  author = {Michael Smith},
  title = {{Running the Table: An AI for Computer Billiards}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure