Working with @Gajet and @BlueRaja 's input (the optimum is somewhere in the middle?):
Let's assume a finite state machine for the item/character that decides on an item level how it behaves (e.g. idle, create and follow path, attack, capture building, heal, defend other item) with some cost function. That would give 6 possible scores for this item.
Note: behavior may not be the right term, because it's the overall AI that decides in the end what each item is to do (see below).
In the screenshot below, red has 5 items, blue has 7 (neglecting the factories for the time being). Lets assume, blue is the AI and is to move next.
(picture to follow, I am not allowed to post yet, need > 10 rep points)
With 7 units and 6 states/scores per unit, there are 7*6=42 possible scores in total, yet not independently, as the scores of items may interfere, i.e. if the enemy is killed by item A, it cannot be killed again by item B.
So this is where the search tree starts: out of the 42 states/scores, select 1, e.g. start with the higher scores first. With this state fixed, there are 6*6=36 states remaining for the second level of this node. We now need to check if something has changed in the situation because of the action of item 1, or if the remaining 36 states are still valid. With, or without update, again pick one out 36 and proceed with the remaining 5 items. When at the lowest level move backwards to the top and pick the 2nd best move of the 1st item and build the next branch. This will create a tree of 42*36*30*24*18*12*6=1.4 billion nodes.
This is too much, but it is also clear that there are many useless nodes in this tree, for one because the order of actions may have an effect, but in most cases it has no effect. Also, branches with low scores may turn out be be beneficial after the opponent has played (like an piece offer in chess), but most of them are not. (how to decide?).
To reduce the search tree, you could decide to limit the number of states per item to be considered. E.g. only pick the best and 2nd best. (could be a parameter in the program setting). This helps: 7*2=14 possible states to start with and 14*12*10*8*6*4*2=645 thousand nodes in total. Probably still many doubles.
Assuming this can still be much improved, but a search tree is created. Add the scores per branch up to the top and select one (there will be many) with the highest score. This is the first AI move.
Now we get to the minimax.
Flip sides and repeat the above for the red items. Minimizing the score. Pick a move, execute and flip back to the blue side. Depth = 1.
Store the score - create a new search tree - blue moves - flip - new tree - red moves - flip - depth = 2 - store score. Continue up to a predefined depth.
This blows up, because at every blue move (645 thousand), red can respond with a similar amount of moves (actually 5*2=10*8*4*2=640 in this case), but with 7 units the total number of combinations would be 0.4 trillion. And for each you would like to search some levels deep...
Unless the search tree is seriously pruned, this goes nowhere.
Will alpha beta sort this mess?