[lmm]

Maybe. There are indeed many possible moves, but how many represent important strategic choices that take learning to understand, and how many are just the obvious thing that even beginners will see how to do after a little study? (there are plenty of "broken" RTS games where there are millions of choices but there's a clear winning strategy in building lots of one particular unit as fast as possible - StarCraft is the exception and not the rule in sustaining interesting gameplay years after its release).

And if we're talking about computer playability, the real-time nature of these games cuts both ways; in StarCraft analysis we literally talk about how many "actions per second" a player was able to execute, a field where a computer will naturally have an enormous advantage (part of why I prefer to play Supreme Commander).