>I honestly wonder whether a game like Stratego, which is much less competitive than Go but has tons of hidden state, would be harder for current AI techniques to compete at.

There don't seem to be good Stratego computer AIs (which actually surprised me a little). But I can easily believe that's at least in part because not a huge amount of effort has been put into it.