On the Complexity of Two-Player Attrition Games Played on Graphs

Authors

  • Timothy Furtak University of Alberta
  • Michael Buro University of Alberta

Keywords:

complexity, rts

Abstract

The attrition game considered in this study is a graph based strategic game which is a movement-prohibited analogue of small-scale combat situations that arise frequently in popular real-time strategy video games. We present proofs that the attrition game, under a variety of assumptions, is a computationally hard problem in general. We also analyze the 1 vs. n unit case, for which we derive optimal target-orderings that can be computed in polynomial time and used as a core for heuristics for the general case. Finally, we present small problem instances that require randomizing moves — a fact that at first glance seems counter-intuitive.

Downloads

Published

2010-10-10

How to Cite

Furtak, T., & Buro, M. (2010). On the Complexity of Two-Player Attrition Games Played on Graphs. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 6(1), 113-119. Retrieved from https://ojs.aaai.org/index.php/AIIDE/article/view/12410