> Compared to other games like Chess and Go, not much work has been done on creating an AI agent for Stratego. As such, the available literature is far and few between, and mostly consists of bachelor’s and master’s theses. In fact, most agents created for Stratego are largely undocumented or closed-source, making it difficult to effectively ascertain exactly which particular methods and techniques have been applied and how effective they were.
edit: the claim about bots not beating humans appears to hold, but I'm not convinced its just shoddy bot quality.
Beyond those two infinities of greater complexity, Stratego is imperfect information, so it is played relative to the infostate, not the state. In Stratego there are thirty three pieces with unknown information on the first move. We can definitely get a lower upper bound by applying abstraction via domain knowledge, but just so I don't have to deal with the complexity I'll state that there are at most 8683317618811886495518194401280000000 different states associated with the infostate of your first move. Meanwhile, on your first move in Go, you are in at most 1 state.
In practice though the average length of a game of Go is ~200ish, the average length of Stratego ~400ish.
Much like chess, I would expect optionality to be an important strategic consideration in Stratego. So branching factors are likely selected for such that they get higher by good agents. In contrast to something like Go, the branching factor would tend to diminish over time.
Mostly sharing this because I think most people are bad at reasoning about complexity - our mind is really good at making complex things seem simple and simple things seem complex because we can actually deal with the complexity of simple things in their full complexity but dealing with the full complexity of the complicated is intractable. I imagine a lot of people's mind latch onto the things like "we get information so playing well means memorization" and don't pay as much focus to the dizzying complexity; but playing well isn't memorizing. Playing well is playing perfectly according to your uncertainty and it just so happens that as part of doing that you sometimes reduce your uncertainty by scouting.
Maybe this is just me but when I thought about stratego I'm pretty sure I only thought about a few units at a time. Moving all of them is a bad idea because of bombs anyway. Your mental model of the game does not consider the state of units in the back row of either side. It probably doesn't even consider all of the units in the front.
I also suspect a lot of optimal play is just doing dumb shit back and forth to force your opponent into making the more aggressive move in a lot of cases without technically forfeiting which most humans likely wouldn't do but ai would like to do if not constrained otherwise.
But I agree a simple tree search on possible moves is unlikely to work very well until the end game.
Of course, we ought to be focused on the situations which lead to these nice situations - which leads us back to the imperfect information situations which lead to those positions we can reason about.
Interestingly, you can invert your point and get a similar rule more generally. The trick is to backward induction on the abstracted category transitions. So your point is actually so valid that is valid even in situations where your examples don't apply. I hope you can see I'm strong manning here. I agree with you that this should be done and is critical to making things tractable.
There is an issue though, at least in the generalized case, which is that perfect information is much easier than imperfect information.
See, in perfect information games when you do the backward induction step you actually just flat out solve the game. Meanwhile, in imperfect information games, this backward induction step merely makes solving the game more tractable. Chess endgames are the backward induction version of your forward induction from the rules abstraction, but the abstraction rule is so hard to determine we wouldn't usually think of it that way. Notice that chess is hard enough that we don't have endgame tables that go all the way back to the start of the game? Yet the average game length in Stratego is hundreds of moves longer and there are more then double the number of pieces.
I still think your point is right and someone who pushes hard enough in this direction would manage to tackle the complexity. So I basically agree with you. But if you take standard approaches like counterfactual regret minimization and throw it at the game without adjusting them for the fact that the problem is "hard" then they just wont terminate.
