Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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 :)

like image 412
Abhinav Chauhan Avatar asked Oct 07 '22 08:10

Abhinav Chauhan


1 Answers

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.)

like image 171
Larry OBrien Avatar answered Oct 13 '22 18:10

Larry OBrien