Can “Monte-Carlo Tree Search” be applied on a “two player game with imperfect information” like Stratego?

Question

I want to develop a two player game with imperfect information - "Stratego".

The game is "somewhat" like chess but initially we don't know anything about the ranks of the opponent's pieces. When a piece attacks or is attacked by some opponent's piece, their ranks are revealed and the higher rank piece kills/captures the lower rank piece. More detail on the game can be found here.

I did a little research. I read "Opponent Modeling in Stratego" by J.A. Stankiewicz. But I couldn't find a complete tutorial on how to develop the game. I have successfully developed before a two player game - "Othello" a.k.a. Reversi, and I'm familiar with MINIMAX algorithm and alpha-beta pruning.

I found somewhere that Monte-Carlo Tree Search is also used in developing zero-sum two player games. Can it be used for games like stratego? Can I get a complete tutorial for the same?

Any other tutorial not involving Monte-Carlo Tree Search would also be useful :)

Answer 1

I think MCTS would have a difficult time in Stratego since the initial spreading function is so large while the best play is very dependent on the ground-truth of the game. That is to say, MCTS would, in the best case, give you a play that's statistically good amongst all the possible variations of your opponent's pieces, but the best next move is highly dependent on which particular variation they've chosen.

I'm still developing a solid understanding of MCTS, but it seems to me that MCTS does not do well in games where multi-round deceptive play involving hidden information is important (poker, canonically, but stratego, I would say, also). In such games, you really need to develop a model of the other player(s) situation/strategy and MCTS by its nature is going to give you an answer that is statistically related to all trees, not just the ground-truth tree.

MCTS works fine with games involving large amounts of chance (backgammon and other board games involving dice and many card games) and seems to me an excellent general-purpose solution that could be rapidly adopted to a large number of modern "European-style" board games. (The interesting thing with those is that although they involve "deceptive strategy" they generally involve relatively little hidden information.)

Answer 2

I don't know of any MCTS for incomplete information off the top of my had, and it seems like it would take substantial modification to the algorithm to get it to work.

Even in a very restricted type of Stratego where there are only ten pieces on each side, only two types of piece, and only one of the "stronger" piece, you're still playing one of ten possible actual games. In a full game of stratego there is far more uncertainty than that because of the large number of combinations of starting position, which all look alike.

It seems like you would also have to augment the algorithm to capture "revealed knowledge," as it happens, e.g., in our toy example, every encounter between pieces reveals some information about the enemy position.

It seems like it would be interesting to try, but only for a very restricted Stratego-like problem at first, and with the understanding that off the shelf MCTS is not sufficient and that you'd have to think carefully and deeply about the right extensions to the algorithm.