MCTS with multi actions

Question

I know that MCTS usually is meant for games where each player plays turn by turn and the canonical form of the board is passed through the tree but is it possible for one player to make multiple moves and still he compatible for MCTS? For example a game of checkers where one player can jump multiple times and capture several pieces in “one” turn. I think if when I pass through the tree, instead of changing to canonical form and updating the player turn, I do neither and don’t negate the final value from the search to be compatible with the multi actions. Is this a viable solution or is there something else?

Answer 1

Yes, for MCTS this is no problem at all. In fact it is slightly more annoying for minimax/alpha-beta based engines, because there we usually like (if possible) to use efficient negamax implementations which automatically keep alternating signs every time. But in MCTS such implementations are already not customary. In fact, MCTS is very flexible, with respect to your question as well as many other aspects. It can be easily implemented to:

1. Have multiple moves in a row made by the same player. You're probably already storing a State object in every node. You'll just have to make sure to store a variable in such State objects that tell you which player is the next player to make a move.
2. Handle games that are not zero-sum. Instead of storing a single value in every node, where you assume that one player is a max player and the other is a min player, just keep track of a separate value for each player in each node (which need not necessarily be each other's negation).

3. Handle games with more than two players. Same solution as above really, just use an array of values (one per player).

Note that, technically, it would in general also be possible to model the kinds of games you're thinking of (like Checkers with sequences of multiple jumps) in different ways, such that every turn becomes a single move again. You would have to think of a "move" as being a sequence of jumps, rather than a single jump. Modelling the game in this way would produce a game tree (and search tree) that is less deep, but significantly wider (a much bigger branching factor per node). I'm saying that this is technically possible, but doing this often produces a weaker MCTS agent, so I do not recommend it.

Conversely, it is also often possible to take a game that you would usually think of as having only one move per turn (say, Chess), and split every turn up into multiple decisions. For example, in Chess you could think of every turn consisting of a sequence of two moves: first selecting which piece to move, and afterwards selecting where to move it to. These kinds of ideas are explored in the Split Moves for Monte-Carlo Tree Search paper from the AAAI 2022 conference.