You overestimate the number of "viable" strategies in Starcraft. The game seems extremely complex only because perfect play is physically impossible for a human player, which leads to a ridiculous number of possible situations arising from long strings of sub-optimal play from both players. Just like what happens in Chess, and Go, and fighting games, and Quake duels, and....
The primary obstacle in the way of a Starcraft computer is that programming AI in a gridless game is infinitely more difficult than programming AI on an 8x8 grid. Creating algorithms so that a computer can recognize a strategy that has 10^5 different "variations" in which each unit in the formation has moved one sliver of one pixel to the left or right is fucking hard. In fact it's fucking impossible. You'd have to map out some way for the computer to form and recognize zones of play on the fly then somehow apply these zones to the actual strategy of the game. This is also fucking hard. Not because these concepts are extremely complex, but because computers are dumb and need to parse everything as 1s and 0s.
Same goes for basically every non-grid-based video game ever made. Unless it's a game where programming unbeatable AI is trivial because the genre relies on fundamental player error to work at all (e.g. fighting games or FPS games) the AI usually sucks. And when it doesn't suck, it's programmed to let the player win anyway.
Also, and I'm surprised no one bothered to say this: Chess isn't popular because it's complex. It's popular because it's good.
Outside of a completely open map with no interesting geometry and hitscan weapons placed right next to the spawn points, I think it's basically impossible, for the same reason programming Starcraft bots is a pain in the ass. Teaching a computer to navigate 3d space is hard enough when it's not getting knocked off its trajectory by rockets every five seconds. A skilled player won't let it pick up any weapons. And even if it does manage to pick one up the player can suicide rush until it dies, then resume spawnfragging.