techniques for an AI for a highly cramped turn-based tactics game

Question

I'm trying to write an AI for a tactics game in the vein of Final Fantasy Tactics or Vandal Hearts. I can't change the game rules in any way, only upgrade the AI. I have experience programming AI for classic board games (basically minimax and its variants), but I think the branching factor is too great for the approach to be reasonable here. I'll describe the game and some current AI flaws that I'd like to fix. I'd like to hear ideas for applicable techniques. I'm a decent enough programmer, so I only need the ideas, not an implementation (though that's always appreciated). I'd rather not expend effort chasing (too many) dead ends, so although speculation and brainstorming are good and probably helpful, I'd prefer to hear from somebody with actual experience solving this kind of problem.

For those who know it, the game is the land battle mini-game in Sid Meier's Pirates! (2004) and you can skim/skip the next two paragraphs. For those who don't, here's briefly how it works. The battle is turn-based and takes place on a 16x16 grid. There are three terrain types: clear (no hindrance), forest (hinders movement, ranged attacks, and sight), and rock (impassible, but does not hinder attacks or sight). The map is randomly generated with roughly equal amounts of each type of terrain. Because there are many rock and forest tiles, movement is typically very cramped. This is tactically important. The terrain is not flat; higher terrain gives minor bonuses. The terrain is known to both sides. The player is always the attacker and the AI is always the defender, so it's perfectly valid for the AI to set up a defensive position and just wait. The player wins by killing all defenders or by getting a unit to the city gates (a tile on the other side of the map).

There are very few units on each side, usually 4-8. Because of this, it's crucial not to take damage without gaining some advantage from it. Units can take multiple actions per turn. All units on one side move before any units on the other side. Order of execution is important, and interleaving of actions between units is often useful. Units have melee and ranged attacks. Melee attacks vary widely in strength; ranged attacks have the same strength but vary in range.

The main challenges I face are these:

• Lots of useful move combinations start with a "useless" move that gains no immediate advantage, or even loses advantage, in order to set up a powerful flank attack in the future. And, since the player units are stronger and have longer range, the AI pretty much always has to take some losses before they can start to gain kills. The AI must be able to look ahead to distinguish between sacrificial actions that provide a future benefit and those that don't.
• Because the terrain is so cramped, most of the tactics come down to achieving good positioning with multiple units that work together to defend an area. For instance, two defenders can often dominate a narrow pass by positioning themselves so an enemy unit attempting to pass must expose itself to a flank attack. But one defender in the same pass would be useless, and three units can defend a slightly larger pass. Etc. The AI should be able to figure out where the player must go to reach the city gates and how to best position its few units to cover the approaches, shifting, splitting, or combining them appropriately as the player moves.
• Because flank attacks are extremely deadly (and engineering flank attacks is key to the player strategy), the AI should be competent at moving its units so that they cover each other's flanks unless the sacrifice of a unit would give a substantial benefit. They should also be able to force flank attacks on players, for instance by threatening a unit from two different directions such that responding to one threat exposes the flank to the other.
• The AI should attack if possible, but sometimes there are no good ways to approach the player's position. In that case, the AI should be able to recognize this and set up a defensive position of its own. But the AI shouldn't be vulnerable to a trivial exploit where the player repeatedly opens and closes a hole in his defense and shoots at the AI as it approaches and retreats. That is, the AI should ideally be able to recognize that the player is capable of establishing a solid defense of an area, even if the defense is not currently in place. (I suppose if a good unit allocation algorithm existed, as needed for the second bullet point, the AI could run it on the player units to see where they could defend.)
• Because it's important to choose a good order of action and interleave actions between units, it's not as simple as just finding the best move for each unit in turn.

All of these can be accomplished with a minimax search in theory, but the search space is too large, so specialized techniques are needed. I thought about techniques such as influence mapping, but I don't see how to use the technique to great effect. I thought about assigning goals to the units. This can help them work together in some limited way, and the problem of "how do I accomplish this goal?" is easier to solve than "how do I win this battle?", but assigning good goals is a hard problem in itself, because it requires knowing whether the goal is achievable and whether it's a good use of resources.

So, does anyone have specific ideas for techniques that can help cleverize this AI?

Update: I found a related question on Stackoverflow: https://stackoverflow.com/questions/3133273/ai-for-a-final-fantasy-tactics-like-game The selected answer gives a decent approach to choosing between alternative actions, but it doesn't seem to have much ability to look into the future and discern beneficial sacrifices from wasteful ones. It also focuses on a single unit at a time and it's not clear how it could be extended to support cooperation between units in defending or attacking.

Answer 1

Here is how I would approach this:

I would start by performing terrain analysis (pdf) and creating a set of influence maps based on various attributes (conflict maps, resource maps, etc). You might want to combine the influence maps together with associated weights. You'll probably update some of them at the start of each turn.

But assuming you have the above, and since the game does not control that many agents, I think a simple two level system is sufficient: the high-level, where strategic decisions are made, and the low-level, where tactical decisions are made.

In the high-level, you could have an Utility-Based system that would feed the state of the game (including the analysis) and get a decision. Or have a trained neural network that takes the same information and outputs a decision.

In both cases, you would end up with a strategic decision. You would then break that down into multiple steps that each agent would have to perform. I.e. if the strategic decision is to attack a certain location, the first step for each agent would be to path find to a specific tile and attack a specific enemy unit. Depending on the system, you can use a planner to break that decision down (might be too complicated) or have those steps embedded in the decision itself (depends on your architecture).

Answer 2

I have no experience programming AI. However, I can offer you my naive strategy that might help you brainstorm a little. I know you said you'd prefer experienced individuals for this question, but this is an intimidating question to say the least.

Right then. What I would do is implement a per-turn checklist/surveillance. Each AI unit, every turn, would:

1. Scan the map for advantageous positions (high ground, bottlenecks, etc) either within a range or globally, depending on how smart/fast you want them to be.
2. Compute the number of minimum turns required to reach that spot, and compare that number to the number of turns the player would have to use to get there.
3. If the AI should decide to move, scan the immediate surroundings. If the terrain's obstacles are purely static(mountains, forest, etc), then find the quickest route around. If the obstacles are dynamic (other AI, or (I guess) player units), check if the AI is in the way, and if so, determine if it is about to move. If it is moving soon, wait it out, otherwise, go around.

4. In order to move as a team, I would implement a 'squad' sort of class/array. Assign one squad to the front; if another is available, assign it to the rear; if another is available, assign it to the side closest to the nearest hostile.

5. If a single unit is dispatched to reach the gates, dispatch a single unit (or two, if you want to smite the player) from the largest squad.

I realize this may be of little to no use to you, but some help is better than none.

Answer 3

Curious to hear what ideas you ended up going with. I've worked on this type of problem myself, so I'm interested to hear what you found that works, and what not.

In my own projects, I currently use a very simple approach to determine AI:

First, I determine which units should go first. This is done by assigning an initiative to each unit; fast unit, units closer to the enemy, and units on the flanks are usually prioritized.

I then iterate over each unit. For each unit, I map its possible moves (including staying in place). Each move is assigned a utility, depending on a number of factors (terrain benefits, can I attack from here, cost to move there, closeness to enemy, etc). A location's utility can also be set by factoring in which "good" locations are within range from it (e.g., or #2 from igrad above). I then sort by utility and pick the best move (or randomly from among the best, depending on difficulty level).

The trick of the effective AI is getting the utility constants right. It's very dependent on that, but when it clicks, it gives a fairly effective AI - albeit not very creative.

It does not look too far ahead, because generally I do not find that this leads to all that useful behavior, unless you can also predict what the player will do.

Two simple added refinements that I am considering:

• Do two passes over the unit planning, in order to avoid the situation where a unit enters the intended path of another unit, thereby blocking it from engaging.
• Implement a basic strategic layer, that "forces" specific movement based on a strategic plan (e.g., outflank left/right, double envelopment, etc). Choice of strategy would of course be limited by terrain. Essentially what the strategy would do is affect the utility functions when dealing with the relevant sector of the battlefield (e.g., outflank right would make all units on the right flank prioritize a rapid advance in the beginning).

Answer 4

A very complicated question, but here are my 2 cents.

Judging from your explanation, this game has some broad sets of movements which are generally desirable, such as 'take a high position' or 'defend the flanks'. I think these kind of game calls more for the Artificial part in the term Artificial Intelligence.

Maybe you could implement a movement library, so that the player makes these kind of movements in a more automatic way (probably using some kind of rule system), and then let the minmax act when there is no obvious optimal strategy.

You can also go completely out of your way and actually implement the AI using some kind of machine learning. By using traces from previous games (against the AI itself, or ideally against people) you can train a ML of your choice. Maybe its a long shot, but worth exploring.