Jump to content
  • Advertisement
  • 10/12/12 10:31 AM
    Sign in to follow this  

    Fast Heuristic Search for RTS Game Combat Scenarios

    Artificial Intelligence

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


    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. aiide12-combat.pdf


    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).

      Report Article
    Sign in to follow this  

    User Feedback

    There are no comments to display.

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!