AI: Turn-Based Movement with 2 actions per Unit

Question

I am currently building a turnbased tactics game.

The Board is a small (about 4*6) tiled grid.

The AI plans all moves of its units, each unit can

• move 2 times
• move and attack
• or attack

at least in this basic stage.

Only one unit can be on a grid cell at any given moment. But a Unit can take a turn to a grid cell which was just left by the former occupant.

The AI plans out the whole turn in advance, and then the actions is played.

The Mission: The AI should maximize the attacks for each round. Currently only Melee is implemented, so this means maximize the count of own units in the grid cells next to the player units, and they should have a turn left to attack, if possible.

I am having a hard time with units getting moved on tiles, where a other unit is still present and so on.

Is there some kind of algorithm or even brute-force approach to match the the criteria?

Answer 1

One bug you could encounter is that in a single turn moving up to make space will never increase the total attacks that turn. Since moving up consumes one action it prevents one attack. The ally that moves into the freed space can attack once. The total attacks this turn are unchanged.

You could resolve this in two ways:

1. looking ahead multiple turns and maximizing attacks using a brute force method (something like min-max) this is doable but of approximate complexity O( (36p)^n ) where p=pieces and n=turns that you look ahead.
2. Decide on a behavior, and write a program to have the pieces move that way. This is less resource intensive, but a bit abstract. It will not give a strategically perfect AI.

Given what you describe I would recommend the second option. The desired behavior is to shuffle up in oder to let an ally advance.

This could be done by evaluating units that are within one tile of the players units. They can mark tiles as desired. Units whose tile is desired by an ally will try to advance and attack instead of attacking twice. If this is not possible they decide to attack twice, and the piece behind them tries to find a different square to move into. Pieces further away will move towards enemies, until they get close enough to start requesting that their allies give them space.