David Churchill and Abdallah Saffidine and Michael Buro University of Alberta Computing Science Department Edmonton, Alberta, Canada

Abstract

Heuristic search has been very successful in abstract game domains such as Chess and Go. In video games, however, adoption has been slow due to the fact that state and move spaces are much larger, real-time constraints are harsher, and constraints on computational resources are tighter. In this paper we present a fast search method -- Alpha-Beta search for durative moves -- that can defeat commonly used AI scripts in RTS game combat scenarios of up to 8 vs. 8 units running on a single core in under 50ms per search episode. This performance is achieved by using standard search enhancements such as transposition tables and iterative deepening, and novel usage of combat AI scripts for sorting moves and state evaluation via playouts. We also present evidence that commonly used combat scripts are highly exploitable -- opening the door for a promising line of research on opponent combat modelling.

References

Balla, R.-K., and Fern, A. 2009. UCT for tactical assault planning in real-time strategy games. In Boutilier, C., ed., IJCAI, 40-45. Churchill, D., and Buro, M. 2011. Build order optimization in starcraft. In Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE. Coulom, R. 2006. Efficient selectivity and back-up operators in Monte-Carlo tree search. In Proceedings of the 5th Conference on Computers and Games (CG'2006), volume 4630 of LNCS, 72-83. Torino, Italy: Springer. Furtak, T., and Buro, M. 2010. On the complexity of two-player attrition games played on graphs. In Youngblood, G. M., and Bulitko, V., eds., Proceedings of the Sixth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2010. Kovarsky, A., and Buro, M. 2005. Heuristic search applied to abstract combat games. Advances in Artificial Intelligence 66-78. Orkin, J. 2006. Three states and a plan: the AI of FEAR. In Game Developers Conference. Citeseer. Saffidine, A.; Finnsson, H.; and Buro, M. 2012. Alpha-Beta pruning for games with simultaneous moves. In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12).