Indeed. Though the crucial difference is, that chess is a game of complete information, while StarCraft hides your enemy. It's much harder to do tree search without complete information.
As a comparison, look at the recent progress made in computer Go that employs Monte Carlo simulations. (And Genetic Algorithms are closer to Monte Carlo than to tree searches.)
I believe it's only harder when you want to optimise for the outcome (winning), since it's hard to know what your opponent will do if you can't see them. However, if you optimise for total offensive/defensive power, I think you can do quite well with trees!
As a comparison, look at the recent progress made in computer Go that employs Monte Carlo simulations. (And Genetic Algorithms are closer to Monte Carlo than to tree searches.)