TY - JOUR AU - Furtak, Timothy AU - Buro, Michael PY - 2010/10/10 Y2 - 2024/03/28 TI - On the Complexity of Two-Player Attrition Games Played on Graphs JF - Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment JA - AIIDE VL - 6 IS - 1 SE - Research Track Posters DO - 10.1609/aiide.v6i1.12410 UR - https://ojs.aaai.org/index.php/AIIDE/article/view/12410 SP - 113-119 AB - <p> 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. <em>n</em> 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 &mdash; a fact that at first glance seems counter-intuitive. </p> ER -