Can I use the Monte Carlo Tree Search on a double-player game with imperfect information such as Stratego?

Question

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

The game "somewhat" resembles chess, but initially we do not know anything about the ranks of enemy units. When a piece attacks or is attacked by some part of the enemy, their ranks are revealed, and a piece of a higher rank kills / captures the lower part of the rank. More information about the game can be found here .

I did a little research. I read "Modeling Adversaries in Strategists" by J. A. Stankevich. But I could not find the complete game development tutorial. I have successfully developed to a dual-player game, Othello aka Reversi, and I am familiar with the MINIMAX algorithm and alpha beta pruning.

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

Any other tutorial not related to finding a Monte Carlo tree would also be helpful :)

Answer 1

I think that MCTS will have a difficult time in Strategyo, since the initial expansion function is so great that the best game is very dependent on the truth of the game. In other words, MCTS at best will give you a game that is statistically good among all your opponents' options, but the best next move depends heavily on which particular option they choose.

I am still developing a solid understanding of MCTS, but it seems to me that MCTS is not succeeding in games where a recharging deceptive game involving hidden information is important (poker, canonically, but a strategist, I would say, also). In such games, you really need to develop a model of the situation / strategy of another player, and MCTS by its nature is going to give you an answer that is statistically related to all trees, not just the tree of truth.

MCTS works great with games with a lot of chances (backgammon and other board games with dice and many card games), and it seems to me an excellent general-purpose solution that can be quickly adopted in a large number of modern "Euro-style" board games. (Interestingly, although they are associated with a “deceptive strategy”, they usually contain relatively little hidden information.)

Answer 2

I don’t know any MCTS for incomplete information from the top of mine, and it looks like it will require a significant change in the algorithm to make it work.

Even in the very limited type of Strategyo, where on each side there are only ten pieces, only two types of pieces and only one of the “stronger” pieces, you still play one of ten possible real games. There is much more uncertainty in a full game with strategy than because of the large number of combinations of the starting position that all look the same.

It seems that you will also have to increase the algorithm to capture the “discovered knowledge”, as it happens, for example, in our toy example, each meeting between pieces shows some information about the enemy’s position.

It seems like it would be interesting to try, but only for a very limited strategy, similar to the first, and with the understanding that the MCTS on the shelf is not enough, and you will need to carefully and deeply think about the correct extensions of the algorithm.