Abstract
Creating strong AI forces in military war simulations or RTS video games poses many challenges including partially observable states, a possibly large number of agents and actions, and simultaneous concurrent move execution. In this paper we consider a tactical sub–problem that needs to be addressed on the way to strong computer generated forces: abstract combat games in which a small number of inhomogeneous units battle with each other in simultaneous move rounds until all members of one group are eliminated. We present and test several adversarial heuristic search algorithms that are able to compute reasonable actions in those scenarios using short time controls. Tournament results indicate that a new algorithm for simultaneous move games which we call “randomized alpha–beta search” (RAB) can be used effectively in the abstract combat application we consider. In this application it outperforms the other algorithms we implemented. We also show that RAB’s performance is correlated with the degree of simultaneous move interdependence present in the game.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
ORTS — a free software RTS game engine, http://www.cs.ualberta.ca/~mburo/orts
Bouzy, B.: Associating domain–dependent knowledge and Monte Carlo approaches within a go program. In: Proc. of the Joint Conf. on Information Sciences, Cary, pp. 505–508 (2003)
Buro, M.: Solving the Oshi–Zumo game. In: Proceedings of the 10. Advances in Computer Games Conference, Graz, pp. 361–366 (2003)
Fogel, B., Hays, T., Johnson, D.: A platform for evolving characters in competitive games. In: Proceedings of CEC 2004, pp. 1420–1426 (2004)
Gozel, R.: Firepower score attrition algorithms in highly aggregated combat models. RAND, 47–60 (2000)
Hauk, T., Buro, M., Schaeffer, J.: *–minimax performance in backgammon. In: Proceedings of the Computers and Games Conference (2004)
Knuth, D., Moore, R.: An analysis of alphabeta pruning. Artif. Intell. 6(4), 293–326 (1975)
Laird, J.E.: A test bed for developing intelligent synthetic characters. In: Proceedings of Spring Symposium on Artificial Intelligence and Interactive Entertainment. AAAI, Menlo Park (2002)
Ruml, W.: Incomplet tree search using adaptive probing. In: Proceedings of the International Joint Conference on AI, pp. 235–241 (2001)
Slate, D., Atkin, L.: Chess 4.5. Springer, Heidelberg (1977)
Taylor, J.: Lanchester models of warfare. Operations Res. Soc. 1+2 (Arlington 1983)
von Neumann, J.: Zur Theorie der Gesellschaftsspiele. Math.Ann. 100, 295–320 (1928)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kovarsky, A., Buro, M. (2005). Heuristic Search Applied to Abstract Combat Games. In: Kégl, B., Lapalme, G. (eds) Advances in Artificial Intelligence. Canadian AI 2005. Lecture Notes in Computer Science(), vol 3501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11424918_9
Download citation
DOI: https://doi.org/10.1007/11424918_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25864-3
Online ISBN: 978-3-540-31952-8
eBook Packages: Computer ScienceComputer Science (R0)