Hi, I am developing a strategy-game AI (think: Final Fantasy Tactics), and I am having trouble coming up for the design of the AI. My main problem is determining which is the optimal thing for it to do.

First let me describe the priority of what action I would like the AI to take:

1. Kill nearest player unit

2. Fulfill primary directive (kill all player units, kill target unit, survive for x turns)

3. Heal ally unit / cast buffer

Now the AI can do the following in its turn:

• Move -> {Attack / Ability / Item} (either attack or ability or item)

• {Attack / Ability / Item} -> Move

• Move closer (if targets not in range)

• {Attack / Ability / Item} (if move not available)

Notes

Abilities have various ranges / effects / costs / effects. Each ai unit has maybe 5-10 abilities to choose from. The AI will prioritize killing over safety unless its directive is to survive for x turns. It also doesn't care about ability cost much. While a player may want to save a big spell for later, the AI will most likely use it asap.

Movement is on a (hex) grid

num of player units: 3-6

num of ai units: 3-7 or more. Probably max 10.

AI and player take turns controlling ONE unit, instead of all at the same time.

Platform is Android (if program doesnt respond after some time, there will be a popup saying to Force Quit or Wait - which looks really bad!).

Now comes the questions:

• The best ability to use would obviously be the one that hits the most targets for the most damage. But since each ability has different ranges, I won't know if they are in range without exploring each possible place I can move to.

• One solution would be to go through each possible places to move to, determine the optimal attack at that location - which gives me a list of optimal moves for each location. Then choose the optimal out of the list and execute it. But this will take a lot of CPU time. Is there a better solution?

• My current idea is to move as close as possible towards the closest, largest group of people, and determine the optimal attack/ability from there. I think this would be a lot less work for the CPU and still allow for wide-range attacks. Its sub-optimal but the AI will still seem 'smart'.

Other notes/questions:

• Am I over-thinking/over-complicating it? Better solution? I am open to all sorts of suggestions
• I have taken a look at the spell-casting question, but it doesn't take into account the movement - so perhaps use that algo for each possible move location? The top answer mentioned it wasn't great for area-of-effect and group fights - so maybe requires more tweaking?
• Please, if you mention a graph/tree, let me know basically how to use it. E.g. Node means ability, level corresponds to damage, then search for the deepest node.