Help with Strategy-game AI

Question

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.

Answer 1

There are a lot of applications that you could use for this kind of AI. Personally, one of the most obvious techniques you could make use of is a position evaluation function. Killzone made use of this technique and it's described in the following paper:

http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf

Actually, you could probably utilise a lot of that paper since it describes world representation, line of sight data, lookup tables, etc, and you've basically got a graph already with your hex grid (you just need to add neighbouring nodes, which in this case would be the neighbouring hexagons to a single hexagon).

Another thing to look into (that's pretty impressive at the moment, but slightly more advanced) is planners. I haven't read up much on Hierarchical Task Networks, I'll leave that to you. One planner that might help is GOAP (Goal Oriented Action Planning)

This link has lots of information regarding GOAP: http://web.media.mit.edu/~jorkin/goap.html

Something that I just thought of with regards to your "Survive for X number of turns" goal is the use of an influence map. An influence map is just a very simple representation for your world where each node (hexagon) has a single value associated with it (called the influence).

The influence can be calculated in a number of ways, but an example for your case could be to have the players generate +10 influence on the hexagon they are placed on and +1 influence on the hexagon that is designated as the maximum range of the player.

So for example, if you have a group of players clustered together, the influence around them would be relatively high. This could be construed by the AI as a threat to its life and moves away from the points of highest influence.

These are just a few techniques that you could use, but there are loads others. If you want something simple, use something like hierarchical FSMs (pretty much FSMs with each state containing another FSM with a higher level of detail). If you want something complex but functional and practical use GOAP and influence maps. It doesn't really matter to be honest because the MAIN POINT is to make the AI fun, and to do that you need to implement some sort of "artificial stupidity". No one will want to play an AI that's infinitely smarter than they are, regardless of how much effort you put into it. I'm not saying this to sound harsh, I'm saying this because it's important that the AI make mistakes cos their human counterparts sure do!

Good luck! :)

Answer 2

Over the years I've written 3 game AIs, all of which played a respectable game.

Two of the cases had limited options per turn and so I explored all possibilities and evaluated the resulting positions--I altered the depth I searched based on the difficulty and it didn't take very many layers to make a quite respectable opponent. I could get a couple of layers down and still have a response back in a second or two and that was on some pretty ancient processors. (All of these were before Windows was on the scene.) The quality of the position analysis is VERY important when using this approach.

The third case did not permit such an analysis as the number of possible moves per turn could easily exceed the particles in the universe. It was a situation sort of like Risk--territory with a number of armies on it but you could make any number of moves per turn, the key factor being moves took time. A province next door generally took 1 turn, one on the other side of the map could take 9.

I used a totally different approach here. I decided the percent of the forces to be allocated to defense and allocated those based on the value of the territory and the estimated enemy threat (While you could see what forces your opponent moved you could not see where they were going--it assumed the human would be concentrating it's forces somewhere and figured it was much more likely to be where they could all arrive at once rather than piecemeal.) Anything not needed for defense became available for offense. I looked at each possible objective and computed what it would take to have a good chance of taking it quickly (a protracted battle would destroy basically all it's production) and generated a set of attack orders for it. The value of the order was the value of the province, the cost was the number of army/turns committed to the attack. Pick the highest value and execute the orders, repeat until the available forces couldn't take anything. The execution time was trivial.

I hope I gave you some ideas here.

Answer 3

Your note about quitting/waiting suggests to me you're doing all the processing work on the main thread of the application. You could, assuming there is sufficient thread support in the Android's SDK (which I assume there must be), offload the "thinking" portion of your AI to a worker thread while the main thread pops up an in-game "AI is considering..." UI but otherwise renders normally.

Of course there are good reasons not to want to do that, such as not wanting the AI to take so long anyhow because the player will get bored.

As for your actual question, while your "current idea" is workable, it's very simple. It's a good starting point, though. It's a system where the AI is purely result-focused -- trying to maximum one value (damage). Other options include a target-focused approach, where you pick a target from the opposing team (randomly, one with the most HP, some combination thereof, et cetera), and move to that target, trying to damage it.

One thing you might want to consider is giving each ability a 'power' or 'effectiveness' stat that is hidden from the player and is used only internally by your AI. You determine the values of this stat yourself, based on your own knowledge of the abilities as the game's programmer.

Your AI would then select their highest rated ability and try to use that, if they can't for whatever reason, pick the next, et cetera. If built appropriately general enough, you could start to tie these two systems together, so that once you establish a target you have heuristics for the best kinds of attacks on that target (for example, weight an attack that does MP damage as more effective if the target has high MP).