Modeling billiards games

ABSTRACT

Two-player games of billiards, of the sort seen in recent Computer Olympiads held by the International Computer Games Association, are an emerging area with unique challenges for A.I. research. Complementing the heuristic/algorithmic aspect of billiards, of the sort brought to the fore in the ICGA billiards tournaments, we investigate formal models of such games. The modeling is surprisingly subtle. While sharing features with existing models (including stochastic games, games on a square, recursive games, and extensive form games), our model is distinct, and consequently requires novel analysis. We focus on the basic question of whether the game has an equilibrium. For finite versions of the game it is not hard to show the existence of a pure strategy Markov perfect Nash equilibrium. In the infinite case, it can be shown that under certain conditions a stationary pure strategy Markov perfect Nash equilibrium is guaranteed to exist.

REFERENCES

• 1: Dimitri P. Bertsekas , Steven E. Shreve, Stochastic Optimal Control: The Discrete-Time Case, Academic Press, Inc., Orlando, FL, 1978
• 2: H. F. Bohnenblust, S. Karlin, and L. S. Shapley. Games with Continuous Convex Payoff. Annals of Mathematics Studies 24. Princeton University Press, 1950.
• 3: H. Everett. Recursive Games, pages 47--78. Annals of Mathematics Studies 39. Princeton University Press, 1957.
• 4: E. A. Feinberg and A. Shwartz, editors. Handbook of Markov Decision Processes: Methods and Applications. Kluwer Academic, 2002.
• 5: D. Fudenberg and J. Tirole. Game Theory. The MIT Press, 2000.
• 6: O. Hernandez-Lerma, Adaptive Markov Control Processes, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 7: W. A. Kirk and B. Sims. Handbook of Metric Fixed Point Theory. Kluwer Academic, 2001.
• 8: W. Leckie and M. Greenspan. An Event-Based Pool Physics Simulator, pages 247--262. Lecture Notes in Computer Science. Springer, 2006.
• 9: A. Maitra and T. Parthasarathy. On stochastic games 1. Journal of Optimization Theory and Applications, 5:289--300, 1970.
• 10: A. Neyman and S. Sorin. Stochastic Games and Applications. Kluwer Academic Publishers, Dordrecht, 2003.
• 11: A. S. Nowak. Zero-sum Stochastic Games with Borel State Spaces. Kluwer Academic Publishers, Dordrecht, 2003.
• 12: Andrzej S. Nowak , Eitan Altman, $\varepsilon$-Equilibria for Stochastic Games with Uncountable State Space and Unbounded Costs, SIAM Journal on Control and Optimization, v.40 n.6, p.1821-1839, 2001 [doi>10.1137/S0363012900378371]
• 13: G. Owen. Game Theory. Academic Press, 2001.
• 14: L. S. Shapley. Stochastic games. Mathematics, 39:1095--1100, 1953.
• 15: M. Shiffman. Games of Timing. Annals of Mathematics Studies 28. Princeton University Press, 1953.
• 16: Michael Smith, Running the table: an AI for computer billiards, Proceedings of the 21st national conference on Artificial intelligence, p.994-999, July 16-20, 2006, Boston, Massachusetts
• 17: F. Thuijsman. Recursive Games, volume 570 of NATO Science Series C, Mathematical and Physical Sciences, chapter 16, pages 253--264. Kluwer Academic Publishers, Dordrecht, 2003.
• 18: Michael P. Wellman , Amy Greenwald , Peter Stone, Autonomous Bidding Agents: Strategies and Lessons from the Trading Agent Competition (Intelligent Robotics and Autonomous Agents), The MIT Press, 2007

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

General Terms:
Theory

Keywords:
best response, billiards games, equilibria, game theory, stochastic games