The problem as I see it here is more about getting strategy into the game, and there just happens to be such genre called just that, strategy games.
I'm mostly thinking of Rome total war, where there was a rock, paper, scissors element in.
It worked like this if I can remember correctly:
Phalanx spearmen beats everything head on.
Cavalry beats everything while charging (except charging into spears).
Swordsmen beats everything in melee.
Axemen beats heavily armored units.
Slingers, bowmen beats everything at a distance.
Artillery beats everything at a even grater distance.
Skirmishers beats non-ranged infantry on open ground.
Light cavalry beats lightly armored enemies.
Heavy cavalry beats everything in melee.
Cavalry archers beats everything except light cavalry on open ground.
Elephants beats everything (even heavy cavalry and swordsmen) in melee, except phalanxes.
And then one has to consider the terrain, morale and lots of other things.
And this isn't even strategy, just the rules of the strategy.
"Here's something to think about: How come you never see a headline like `Psychic Wins Lottery.'" -- Comedian Jay Leno