• 10/12/12 10:31 AM
    Sign in to follow this  
    Followers 0

    Fast Heuristic Search for RTS Game Combat Scenarios

    Artificial Intelligence

    Gaiiden
    • Posted By Gaiiden
    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. aiide12-combat.pdf

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


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

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

    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

    udksmith

    • 5
      
    0

    Share this review


    Link to review
    Ectara

    • 5
      
    0

    Share this review


    Link to review