Turn-based combat AI with multi turn planning

Question

My current AI system uses the now very common utility AI. I generate a list of possible actions, I then calculate fitness score for each action and generate a list of possible chains of actions (Move > Attack > Reload or Use Offensive Ability > Leap backwards). The sum of those scores are then sorted and I pick the most (or not, depending on how smart I want the particular AI player to be) appropriate chain to execute.

The issue that I've run into though is that I'm having issues with more complex interactions that require multi-turn planning. To give an actual example: one of my characters got two spells that can deal massive damage when used in the right order.

1) A buff ability that increases target's Mind attribute (cast on self)

2) A powerful spell that deals damage based on your Mind (cast on the enemy)

Both of those actions cost a lot of Action Points and so you can't execute them both in one turn. A very obvious combo is to use the buff and then the damage spell, but if both of those actions are available to the AI, then it always chooses to open with the second action. The buff itself, when considered in isolation, produces a very low fitness score.

A very obvious idea is to then to allow the AI to build chains of actions for two or even three turns ahead. However, this greatly increases the performance cost as I'd have to use similar heuristics for other players to get at least somewhat reasonable gamestate for the AI to go off of. I would also have to think of a fail-safe mechanic for when the player does something unexpected, thus ruining this long-term plan.

Another idea that I had is to let the designer define interesting combos and have the AI see if it can execute one, but it feels messy and a bit hard to implement with the current generic system.

How do the other games do it?

Answer 1

When you have a game with a decision tree which grows too much when you plan too far ahead, then the standard solution is alpha-beta pruning: Don't waste time with exploring branches of the tree which are unlikely to provide good results.

Usually you would discard those branches with the lowest fitness ratings on their current iteration depth. But in this particular situation it could be useful to instead break off those branches early which are unlikely to result in useful combos.

You could add a flag to those actions which have the potential to be useful in a combo (buffs, debuffs, etc) and explore those branches which contain such actions to a deeper level than those which do not.