Turn Based AI Algorithm (Small Board, Two Steps)

This is my Game-Board:

-> The Red Balls are the AI-Controlled Actors.
-> The Blue Balls are the Player-Controlled Actors.
-> The Yellow Cells are the locations, from which the Red Balls can attack.
-> Each Red Ball can do 2 actions: move-move, move-attack, attack-attack.
-> At no time there can be 2 minions on one cell, but a minion can arrive on a cell another just left.

Its the AI's turn. Its planning the whole turn for all minions, each of them has the two moves.
The objective is to maximize the number of melee attacks, which can performed in a single turn (2 actions) on the player balls.

Problem I have in my current (brute-force) implementation:

• Sometimes it is advisable for a minion to move, although it is already in a melee position, to make space for another minion, which can then move into melee range aswell.

Example:

In this situation its more effective for the front minion to move once, so another minion can move into melee range as well.

Do you know an effective algorithm for this job? Thank you for your time!

• Your first step would be to calculate all possible moves for each AI unit without regard for other AI units, rate each move by tactical and strategic considerations and order them by rating so you got a first, second, third etc. choice per unit. Then you need to find the solution with the best overall happiness. I am pretty sure that this last step is a quite well-researched optimization problem in computer science. I just can't remember how it was called. Commented Dec 14, 2016 at 16:10
• Thanks. Would you mind to elaborate on this, maybe in an answer? :)
– user60245
Commented Dec 14, 2016 at 16:54
• I would if I could remember how that problem was called so I could look up how it is usually solved. I don't write incomplete answers. Commented Dec 14, 2016 at 16:58
• I understand and appreciate this.
– user60245
Commented Dec 15, 2016 at 11:37