A game theory approach to high-level strategic planning in first person shooters

ABSTRACT

As computer systems become more dependent on standalone devices such as graphics cards, video game developers can execute additional features on the CPU; high-level AI in video games is one such feature. The problem of developing high quality AI for video games is not simple, as human and computer interactions can be very complex. An exception can be found in the classical board game genre, which involves well defined games and players who apply rational policies to win. Many artificial board-game players can make moves within set time limits and are able to play at expert levels [10]. Given that high-quality AI technologies already exist for many board games, this paper explores the question: how can the technologies used in artificial board game players be applied to high-level strategic planning in First Person Shooters?

REFERENCES

• 1: Gérard M. Baudet, An analysis of the full alpha-beta pruning algorithm, Proceedings of the tenth annual ACM symposium on Theory of computing, p.296-313, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804359]
• 2: Erik D. Demaine, Playing Games with Algorithms: Algorithmic Combinatorial Game Theory, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.18-32, August 27-31, 2001
• 3: L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, editors, ECML, volume 4212 of Lecture Notes in Computer Science, pages 282--293. Springer, 2006.
• 4: L. Liden. Strategic and tactical reasoning with waypoints. In AI Game Programming Wisdom. Charles River Media, 2002.
• 5: J. Orkin. Three states and a plan: The a.i. of f.e.a.r. In Game Developers Conference, 2006.
• 6: Steve Rabin, Introduction To Game Development (Game Development), Charles River Media, Inc., Rockland, MA, 2005
• 7: R. Rasmussen, F. Maire, and R. Hayward. A move generating algorithm for hex solvers. In A. Sattar and B. H. Kang, editors, Australian Conference on Artificial Intelligence, volume 4304 of Lecture Notes in Computer Science, pages 637--646. Springer, 2006.
• 8: R. Rasmussen, F. Maire, and R. Hayward. A template matching table for speeding-up game-tree searches for hex. In M. A. Orgun and J. Thornton, editors, Australian Conference on Artificial Intelligence, volume 4830 of Lecture Notes in Computer Science, pages 283--292. Springer, 2007.
• 9: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 10: Jonathan Schaeffer, The Games Computers (and People) Play, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.1179, July 30-August 03, 2000
• 11: D. Schleicher and M. Stoll. An introduction to conway's games and numbers. Moscow Math Journal, 6:359, 2006.
• 12: C. Shannon. Programming a computer for playing chess. Philosophical Magazine, Series 7, 41(314), 1950.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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

General Terms:
Algorithms, Design, Theory

Keywords:
combinatorial game, first person shooter, game, two-player board game