Real Time Strategy Games as Domain for AI Research

CPSCI 370: Artificial Intelligence

Final Research Presentation

Rachael Arnold

Over the past 20+ years, the interactive "video" game has become a staple entertainment object. To this day, the bulk of video game production time is spent on the graphics of the game: each new generation of game is expected to far exceed the "look" of the previous with the ultimate goal being life-like quality. With this in mind, AI has often been overlooked. The consumer, especially one who can be considered a "hardcore gamer", is increasingly demanding "smarter" opponents, which has prompted use of often-elementary AI use. However, this demand is creating need for increasingly advanced AI techniques to be used in video game production. With the size of the industry and its role in current society, research into AI techniques for video gaming is becoming more important.

I chose to focus on one specific genre of video game - real-time strategy (RTS) games (Command and Conquer, Warcraft, Starcraft, etc...) - for two reasons. Like most other video games, RTS games are partially observable with imperfect information and have exceedingly complex state-spaces. In addition to that, however, time constraints play an active role in complexity with this specific genre. The second reason is that Mark Ponsen, Pieter Spronck, and others have made great progress in the field of adaptive AI for RTS games with their technique of dynamic scripting, so it is easy to see first hand the results of academic research in gaming AI.

Historically, game designers have created the illusion of intelligence through scripting. The problem with scripting is that to be effective, it must be complex, but the complexity ultimately gives opportunity for weakness and predictability. Eventually, the human player will be able to recognize and exploit those weaknesses, which kills the illusion. Dynamic scripting reduces the predictability of traditional scripting by automatically generating a new script for each instance of the action. To do this, a rulebase is constructed manually comprising a series of rules based on game states, where each rule has a weight value determining the probability of the rule being chosen during script generation. The weight value corresponds to a calculation of the rule's success in the overall game and within the specific state.

Acording to Spronck, Ponsen, Sprinkhiuzen-Kuyper amd Postma (2006), there are eight requirements for adaptive AI techniques in two categories:

Computational:

Functional:

Because dynamic scripting only requires knowledge base extraction and weight computation once per encounter, it is computationally fast. With sensible rules, every generated script will be reasonably effective. Because of the nature of the generation, one unjust penalty will not remove a rule from the database, and likewise an unjust reward will quickly be reversed, so it is robust. Clarity is not a problem, as it simply generates a script, and it is varied due to a new script being generated for each instance. Efficiency is less clear, as it depends on tactics, but in many cases, it proves to be very efficient. Consistency requires that the rulebase contains reasonably rated rules to start, but with offline evolutionary computation, this is not a problem. Scalability requires an added technique of top-culling: computed weights should be allowed to exceed WMAX, so that if the computer is playing too strongly, the strongest rules will not be used, and thus the computer will play down to the player's level.

Initial research proved that with balanced tactics, dynamic scripting was able to adapt quickly and efficiently. With "super tactics," such as rushes aimed at overwhelming the enemy with a large army, specific, static counter-tactics are better suited. Using the Evolutionary state-based tactics generator developed by Ponson, et al, the rulebases can be improved upon to react to even some "super tactics."

Annotated Bibliography

Anderson, E. F. 2003. "Playing smart - artificial intelligence in computer games." Proceedings of zxfCON03 Conference on Game Development .

Aimed at game developers, this paper serves to give a brief overview of computer science and AI research. It details the use of techniques in the gaming industry that allow for the illusion of AI, particularly in reference to commercial computer chess, adversary behavior in PacMan, and smart environment objects in The Sims. The last half of the paper addresses AI techniques being employed by current games (circa. 2003), arranged under the topics of rule-based techniques, machine learning and intelligence, extensible AI, knowledge based techniques and other techniques such as agents and annotated environments.

Buro, M. (2003). "Real-time strategy games: A new AI research challenge." Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (pp. 1534-1535). Acapulco, Mexico: Morgan Kaufmann. Retrieved December 7, 2006 from Google Scholar [PS link].

This is a short article summarizing real-time strategy (RTS) games as a domain for AI research. It outlines many of the fundamental AI research problems found in RTS games. It goes on to focus on the author's research in an open-source RTS project, which I did not delve into more deeply.

Fairclough, C. et al. 2001. "Research Directions for AI in Computer Games." Technical Report TCD-CS-2001-29. Trinity College, Dublin. Retrieved December 7, 2006 from Google Scholar [PDF link].

Fairclough, et al summarize the different needs each game genre has for AI, gives a little information about the state of the art in the industry, and gives an optimistic view of academic research into game AI. Although outside of the scope of this presentation, the discussion of Case-based plan recognition used by non-player characters (NPC), proactive persistent NPCs and interactive story engines was interesting.

Graham, J., L. Zheng, & C. Gonzalez. 2006. "A Cognitive Approach to game Usability and Design: Mental Model Development in Novice Real-Time Strategy Gamers." CyberPsychology & Behavior 9(3) , pp.361-366.

This article explores the novice gamer's concept development of game-embedded AI in RTS games. It was not useful to my research on this topic as it only explores the mental models of research subjects in relation to AI.

Laird, J. 2002. "Research Human-Level AI Using Computer Games." Communications of the ACM 45(1) , pp.32-35.

In this short article, Laird summarizes his research to date in the field of video game AI. It is essentially an essay aimed to convince readers that games are an inexpensive domain for human-level AI research in complex environments.

Laird, J. & M. van Lent. 2001. "Human-level AI's Killer Application: Interactive Computer Games." Artificial Intelligence Magazine 22(2) , pp. 15-26.

Laird and van Lent propose that interactive computer games provide the perfect domain for human-level AI research, as the industry demands increasingly believable characters and real-time strategy adjustment. They outline a few of the basic game genres: action, role-playing, adventure, strategy, God, team sports, and individual sports. Within these genres are five roles to which AI research is most beneficial: tactical opponents, strategic opponents, partners, support characters, units, and commentators. They conclude that regardless of the importance of human-level AI research, the domain is important to many isolated research problems in AI.

Livingstone, D. 2006. "Turing's Test and Believable AI in Games." ACM Computers in Entertainment 4(1) .

Livingstone explores the validity of the Turing test and whether it is useful in assessing intelligence. As a part of this, he discusses its relevance to game AI's believability. Ultimately, he concludes that game AI cannot be considered a true Turing test because it does not follow Turing's Imitation Game strategy, regardless of demand for AI that can fool the human player into thinking he or she is playing vs. another human. The article itself is outside of the scope of this particular topic, and its only value in my research was the reaffirmation of the exploitability of flaws in current AI systems.

Lucas, S. & G. Kendall. 2006. "Evolutionary Computation and Games." IEEE Computational Intelligence Magazine 1(1) , pp.10-18.

Lucas and Kendall provide an overview of why evolutionary computation is useful in the gaming industry, and why the industry needs AI. They discuss video games as an interesting research topic due to their being games of imperfect information with vastly complex state-spaces For research in this domain to be truly functional, it must be more generalized than is required for board games. The article also includes a short sidebar debating the use of co-evolution vs. temporal difference learning.

Ponsen, M., H. Munoz-Avila, P. Spronck, & D. W. Aha. 2006. "Automatically Generating Game Tactics through Evolutionary Learning." AI Magazine 27(3) , pp.75-84.

This article builds on the research of Ponsen and Spronck (2004) on the subject of evolutionary learning in RTS games. They introduce the evolutionary state-based tactics generator (ESTG) to implement automatically-generated rules for use with the dynamic scripting technique.

Ponsen, M. & P. Spronck. 2004. "Improving Adaptive Game AI with Evolutionary Learning." Retrieved December 7, 2006 from Google Scholar [PDF link].

Ponsen and Spronck discuss their use of evolutionary computation and its use in game AI. They empirically prove that evolutionary learning is valuable to the process of adaptive game AI by using offline evolutionary algorithms to improve a rulebase employed in a RTS game. The rulebase is used in this game with the online AI technique known as dynamic scripting.

Schaeffer, J., H. J. van den Herik. 2002. "Games, Computers, and Artificial Intelligence." Artificial Intelligence 134 , p1.

This is the introduction article to a gaming-filled issue of Artificial Intelligence. It summarizes research on board and card games. The only information pertaining to my topic was mention of interactive video games as a future domain, and a short statement about Laird's promotion of video games as an opportunity for research.

Spronck, P., M. Ponsen, I. Sprinkhuizen-Kuyper, & E. Postma. 2006. "Adaptive game AI with dynamic scripting." Machine Learning 63(3) , pp.217-248.

Spronck, et. al. detail, in depth, the use of dynamic scripting as an online technique in game AI. They discuss rule fitness and weight and the tactical categories relevant to dynamic scripting in a computer-based role playing game (CRPG). Although this does not discuss to a large extent dynamic scripting in relation to RTS games, it was exceptionally useful in helping to understand the implementation of dynamic scripting as a whole.

Page last updated 25 May 2007