Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Like
2Likes
Dislike

Fast Heuristic Search for RTS Game Combat Scenarios

By David Churchill and Abdallah Saffidine and Michael Buro | Published Oct 12 2012 04:31 AM in Artificial Intelligence
Peer Reviewed by (Michael Tanczos)

rts heuristic ai research

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.

Attached File  aiide12-combat.pdf   210.84KB   785 downloads


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





Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS