I don’t think it is more challenging than StarCraft or Dota. Does the blog post claim that anywhere?

Stratego is way more challenging than Poker, though. StarCraft/Dota/Stratego have the property that you can’t represent their imperfect information as a vector in memory, whereas you can easily do that in Texas hold’em poker (there’s only 52C2 = 1024 possible hands). So for those games, you have to use an approximate distribution rather than the exact one.

I’m an author on this paper (although my contributions were relatively minimal) and on the Player of Games paper (which did Poker, Chess, and Go).