You can view Stratego as the "Cartesian product" of a public information board game and an imperfection information "card" game. The board game has much simpler local tactics than e.g. chess or checkers, although whole board tactics where 2+ high pieces are trapping 1 lower piece defended by 1+ high piece are extremely complicated to reason about.
The "card" game can be viewed as a form of Limit Poker. The bidding in poker is done with secret cards and public bets. In Stratego, you bet with your secret pieces, so it's more like a closed bid auction. But since there are only 10 moveable ranks, the range of bluffs you can pull off is rather limited compared to e.g. No Limit Poker.
Each of the "subgames" in itself are quite tractable for computers. But the numerical product of all public game states times the number of secret information states is humongous. Combine this with the fact that imperfect information game trees don't decompose as nicely as e.g. chess game trees, and computers will also not be able to divide-and-conquer their way out of the numerical complexity with brute force. Whereas humans can come a long way with heuristics.
Comments
It’s explained right in the abstract why Stratego is a more difficult game for AI than go or poker.
You can view Stratego as the "Cartesian product" of a public information board game and an imperfection information "card" game. The board game has much simpler local tactics than e.g. chess or checkers, although whole board tactics where 2+ high pieces are trapping 1 lower piece defended by 1+ high piece are extremely complicated to reason about.
The "card" game can be viewed as a form of Limit Poker. The bidding in poker is done with secret cards and public bets. In Stratego, you bet with your secret pieces, so it's more like a closed bid auction. But since there are only 10 moveable ranks, the range of bluffs you can pull off is rather limited compared to e.g. No Limit Poker.
Each of the "subgames" in itself are quite tractable for computers. But the numerical product of all public game states times the number of secret information states is humongous. Combine this with the fact that imperfect information game trees don't decompose as nicely as e.g. chess game trees, and computers will also not be able to divide-and-conquer their way out of the numerical complexity with brute force. Whereas humans can come a long way with heuristics.