Fire Emblem/Advance Wars/Turn Based Strategy like Artificial Intelligence

Question

I have made a Fire Emblem/Advance Wars like game, and I was wondering if there are any particular techniques in the AI's in those games.

I was wondering how to let the AI make the best decisions. I have the tiles a unit can move to, I have the enemy unit positions and I have formulas to calculate battle outcomes, now I want to add those together so that, for example, the AI attacks the weakest unit, blocks a chokepoint or just moves closer to the enemy if nobody is in range.

What is the best approach to this?

Answer 1

Here's the easy approach, which is typically the one used for board games:

Write a heuristic which is able to determine how good a position one side is in. Think of it as estimating "from this position, how likely am I to win?" Factors to consider are relative force strength, how well your units are supporting each other, how large an area you threaten, vs. how many of your units are threatened, and the inverse of all these factors for the enemy faction. Figure out a whole bunch of factors like these, weight them according to their importance, and turn them into a 0% -> 100% estimate for how likely you think it is that you'll win.

Now do this:

1. Each turn, look at all possible moves you can make. For each possible move, evaluate your heuristic on the resulting game state that you'd reach after making that move.
2. After testing each move, actually make the move which had the best resulting heuristic value.

As a result, your AI will pick the moves which maximise those things that your heuristic measures, which you believe correspond to being more likely to win. If having fewer or weaker units makes you less likely to win, the AI will prefer moves which don't result in losing units. If the opponent having fewer or weaker units makes you more likely to win, the AI will prefer moves which do result in the opponent losing units. And so on.

If you want to be clever, you can "look ahead" more moves; assume that the opponent will be doing things similar to you, and so for each move, also take the best move from the opponent's point of view, and find the best heuristic for your side, after the opponent's best move. And take that move; that would be 2-ply thinking. You can keep flipping back and forth, taking best moves, and thinking deeper and deeper about the future state of the game board, as long as you have processor time to think about it.

Of course, if there are lots of different possible moves each turn, or if those moves have different possible outcomes (say, if random numbers are involved), then this becomes a little more complicated. But in systems like Advance Wars or Fire Emblem where random numbers have only a small impact, this approach should be perfectly serviceable.

Answer 2

Games like Fire Emblem and Advance Wars use finite state machines on the individual unit level. That is, all of the units act independently without any concern for achieving the armies overall condition for victory (this is most easily seen when the AI messes up by having one unit do a bad move which prevents another unit from doing a better move). The units that have different behaviors (go towards enemy, hold position, etc) simply have different FSMs.

FSMs are good for game AI because they're easy to implement and give good behavior (assuming you write good FSMs). The AI doesn't need to actually be smart or think, it just needs to make good moves.

At some point more sophisticated (let's call it "real") AI will be better, but it's much more costly to implement. It's kind of like an FSM has linear growth while "real" AI has parabolic growth, in terms of cost v quality.

I remember an anecdote about a game AI programmer for an FPS (I forget the game) that got fed up having to update FSMs so he re-wrote the whole AI system with some "real" AI. This gave some really unexpected (but ultimately desirable) behavior where the enemies were doing cool things like breaking through windows instead of going through doors. In the sequels to this game they went back to using FSMs.