TemplateRex

It's true that many move sequences can be collapsed to a single maneuver. However, the area control remark is inaccurate: controlling or occupying the 3 alleys is very important and requires careful positional play. Getting the right "lane parity" to attack pieces frontally is crucial here, as is pincer movements around the lake with multiple power pieces. You seem to view Stratego as a superficial and repetitive game, but high level play goes considerable beyond a few bluffs and mechanical exchanges.

It depends on player attitudes. The maneuvering is simpler than in chess or even checkers, although you can have very intricate multi-piece pincers around the lakes. Most top players however tend to be quite aggressive, sacking majors or even colonels to expose the opponent’s top two pieces, while at the same time having their counter attacks ready. Typically there are 3 simultaneous battles for each of the 3 alleys. But, yeah, as in chess, there can be bloodless draws or fortress positions where neither wants or can make headway.

But their NN already outputs a policy conditional on public and private info! Why not have a separate intermediate branch in the NN that is fed with the current estimate of private info (for both players) and outputs the policies (again for both players) given those info estimates? Wouldn't it be possible to learn from that?

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.

What I don't understand is why they don't try to make inferences about the opponent's private state. I get that the full Bayesian update is intractable, but some sort of RNN or LSTM should be able to produce pretty accurate estimates for the opponent's private info. And with self-play, you can train the deduction head of a NN by adding a KL-divergence between inferred and ex-post observed pieces. That would both make you guess better and also try and "jam" your opponent's inference by randomizing your own piece distribution.

In actual live game play, none of the top players use such kids' ploys as touching bombs pretending to be moveable pieces. Actual game play wouldn't change if the one touch move rule from chess or checkers were to be introduced.

The main thing the rules guard against is accidentally tripping over your opponent's or your own pieces. Especially during time trouble, it sometimes happens that you drop a piece. If your opponent reveals < 4 of your pieces, you can exchange all of them with any other of your pieces. With >= 4 "accidents", it's an automatic forfeit. If you tip over your opponent's flag, he is entitled to 3 swaps (may or may not be bombs).

The pace in online games is too fast (4s per move usually, with a 12m buffer) to use pen and paper aides. Short of having some sort of screen-scrabbing AI-tool that auto-labels pieces as they are revealed (doable by a decent programmer, but Stratego is no poker, there's no money in it), I think it's safe to assume top-level players don't cheat. Top-level play in live tournaments has a high correlation with top-level online play as well.

The best available bot that is also mentioned in the paper, is Probe. Expert humans will score the same as DeepNash against Probe. The best humans have no trouble recalling every piece that moved, and the square it originated from. Top-level play usually has very few moved pieces (since they are vulnerable to your opponent's general once your own marshal gets revealed), so memory is important but typically not the main bottleneck.