0 votes
1 view
in AI and Deep Learning by (21.1k points)

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

1 Answer

0 votes
by (46.3k points)

It seems MCTS can be used for imperfect information games if it's modified to ISMCTS. Unfortunately, there is a dearth of examples and I am having a similar problem in that a particular game am developing involves both chance and incomplete information. But you can prevail etheses.whiterose.ac.uk/8117/1/Feb 16 - FINAL.pdf 

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