How far did they get with Starcraft? Stratego should be a stepping stone to get there - it introduces imperfect information.
Edit: After looking at some games again, the AI also benefits from precise target selection for the phoenix's graviton beam. A human player might take 3 phoenixes and a bunch of stalkers into a fight against an army containing 3 immortals, some sentries, some stalkers, and some zealots, and use graviton beam to pick up some mix of units including units other than immortals. The bot can pick up only the immortals.
I haven't checked out the linked paper yet but if they managed to do something from first principles that would still be an interesting development.