The basic idea of a chess AI is to make a list of all possible moves from the currently estimated best move, then to rate them and to repeat the process. It drops those with too little chance as they won't be taken (or can be assumed not to be taken as they do not appear to give an advantage).
The basic idea requires you to make a list of all possible moves, and to repeat that process for all those moves etc. This is possible in chess (where the list of likely next moves is effectively enumerable; a starting chess board has 20 possible moves) and up to a point for other things such as backgammon, checkers and solving a Rubik's cube.
If I take a simple turn-based game (Civilization 2) as an example, each of your guys can move to a total of 8 squares (or 24) in a single turn. If you have 10 guys (which isn't a lot, you typically have more by the time it starts to get somewhat interesting) the total number of possible "moves" from the current state (so a single level) is already 8^10 or about 4 billion. Even if you prune 99.99% of those, you still can't go deep on the tree as the number of possible moves explodes really quickly.
Add to that that the game is a bit like the Rubik's cube problem, where you only see progress after some 10 or 12 moves, the problem explodes to a point where the advantages of a standard min/max are only prevalent at a memory capacity of more than your typical computer will have.
In other words, the strategies it will find will be reproducible but bad.
For the actual problem, how to make a decent AI, I would go in the direction of basically steered random movement (move each guy with a bit of basic intelligence), evaluation and tuning. Do this in parallel for 100 or 1000 different ones and pick the one that ends up being the best. You can feedback the results from this into the original intelligent steering to tune it again. A bit like monte-carlo simulation.