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


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




complexity, rts


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.




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. https://doi.org/10.1609/aiide.v6i1.12410