To successfully apply min/max to a turn based strategy game, you need to correctly apply all available chess-techniques...
Even chess engines have a very bad strength, if your evaluation functions is bad. The most simple version of a evaluation function is: 1=game won by white, -1=game won by black, 0 = all other cases; But, this would give you a very bad performance. The same happens to your turn based game!
If you want to use min/max (with alpha/beta pruning and stuff) like in chess, you must also implement a reasonable evaluation function! Else, you cannot compare those algorithms performance when being applied to your strategy game to the case it's applied to chess.
What evaluation functions of chess engines do, is evaluating stuff like:
- How well is a position of a piece on the board?
- How many times is a piece attacked?
- How many times is the piece protected?
- How well can each piece freely "move" on the board? (or: How many tiles does it "control")
Those parts of the evaluation function must first be "translated" to your game:
- Position of piece: Is it e.g. on a hill, which is extending its shooting range?
- Attacked: How much is each piece in danger? (e.g. sum of attack values of units able to attack a special unit multiplied by some probability to be attacked by it; probability increases, if the unit is already damaged; decreases if many other units are in range of the attacking unit)
- Own Attack: How many units can be attacked by this each unit?
- Protection: How much own pieces are next to it (to help)? Maybe a unit may not attack units under a minimum distance and its preferable to protect it by unit having the possibility to attack nearby units.
- Mobility: How mobile is your unit? (can it flee?)
The different ratings must be summed up by weighting function (factor_a * rating_a + factor_b * ranting_b + ...) for all units...
In strategy games also the resources (gold, wood, ...) left must be taken into account.
If your evaluation function is well enough, you do not need to really search "deep" into the tree for most cases. So you probably only need to take a closer look at the 3 or 10 most promising choices. See next chapter...
Possible moves at each position
The most problematic thing about using min/max for strategy games is that you can command multiple units in one turn, whereas in chess you are only be allowed to command one unit (except for castling, but this is a clearly defined move combination). This causes 5^N possible moves for N units for each "position" (chess term), if you would only decide between "move north, south, west, east OR stop" for each unit.
You could solve this by breaking down the complex command into the low level commands: e.g. choose action for unit A, go into depth and decide for unit B.... decide for unit N ... and then end this turn. But, this alone doesn't change the complexity! You must optimize the order in which actions are assigned to units (e.g. first unit B, C, D and then unit A). You could record the impact of the decision for each unit during the last calculation and then sort by importance. This way alpha-beta pruning can be used to cut away any bad combination from the search tree very early. The highest priority should always be "do nothing more and end your turn" (null move pruning) in each iteration. This way you can "skip" assigning most tasks to most units and let them just continue what they did before. This way the search will go into depth quickly by just taking a look at the "critical" units (e.g. the ones really in combat right now). Make sure to only command each unit once...
You can also use some randomness to make sure that the "important" units are getting a command from time to time, too. Especially, units finishing some job (e.g. harvesting - or having no enemy assigned anymore) should slightly increase in importance.
Iterative Deepening + Caching/Hash Table
Then, you can "interative deepening" to go into depth more and more until some time limit has been reached. So you will search deeper if there are less units, and you have always some "result" if you stop searching for a better solution.
Iterative deepening would require to use a hash table to cache former results of searches. This also enables to reuse some of the results from the last turns search (the branch of the search tree that covers the commands that were actually executed in the last turn). To implement this, you need a very good hashing function (have a look at the "zobrist key"), which is able to be iteratively updated. Updating the hash key means, that you can just take the hash key of the old "position" and can just kick in the change in the position (e.g. take away unit at position x and put it at position y). This way calculating the hash key is quick and you don't need to process the whole boards situation to calculate it, just to check if the hash contains a former entry for this position. In a way you must make sure that no hash collisions happen.
Non-deterministic behaviour is a problem for min/max searches. This means, it isn't sure if you will hit an attacked target (e.g. probability is 10%). Then you can not just plan this happens. In that case you need to modify the algorithm and put a "probabilty" layer in between. It's a bit like "its the probabilities turn". Each independent result must be regard separately. The evaluation through this depth "layer" must then be sampled (monte carlo sampling) and the result of the in-depth evaluation must be weighted by the probabilty of occurance. Different results of the probability layer must be regarded like different opponenent moves (but instead of min/max the "average" must be calculated). This will of course increase the complexity of the search tree. So this would in fact be something like min/max/avg-search (not min/max-search anymore).
When applying all those techniques (which are all used by current chess engines) to a deterministic game, you will surely be able to achieve reasonable results for a game, too. For non-deterministic games, this will be probably more complicated, but I think still manageable.
A good resource for explanation of those techniques (for chess) is http://chessprogramming.wikispaces.com/
You can even implement some sort of directed randomness in min/max searches. Instead of deterministically investigate the best results first in each iteration, you can just randomize this and let its order be decided by a probability distribution that is based on the current evaluations...