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?
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:
- 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.
- 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).
- 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.
$\begingroup$ Thanks for the detailed response. I'm wondering however (since im following the path of AlphaZero) if the concept of "trading" would be effected? For example, if I capture 2 pieces in "one" move and then my opponent captures that piece, I am up by 1 in the trade. However, If I implement them as single turns, the MCTS won't know that the pieces has already captured an opponents pieces and may value the trade as being equal...? $\endgroup$ Oct 29, 2022 at 14:33
$\begingroup$ @AnikPatel I don't see how anything would be negatively affected here. Evaluations of nodes (through AlphaZero-style value functions, or through classic MCTS-style playouts) evaluate the node based on what the game state looks like. I.e., if you have more pieces than your opponent, you get a higher value. Value estimators are unaffected by when in recent history something about the state changed, they just look at the state right now. $\endgroup$ Oct 29, 2022 at 14:53
$\begingroup$ Ah, that clears it up. I was looking at an implementation of AlphaZero and it used stacked observation for some reason but your answer makes more sense $\endgroup$ Oct 29, 2022 at 15:37
$\begingroup$ @AnikPatel Ah, now I understand what you were thinking of there. In theory, it should not be necessary to use such stacks including previous state observations (from, say, a game-theoretic point of view). Indeed, in practice it is sometimes done (such as in AlphaZero), and probably for good reason. They probably found it to speed up training in practice. It is plausible that doing this might help a neural network to more quickly learn to "focus" around areas where things changed, which are often "important" areas. $\endgroup$ Oct 29, 2022 at 15:50
$\begingroup$ So, if you model the tree differently, it is possible that a different number of such stacks for the input of a neural network provides the best empirical performance. But from the theoretical point of view, there is no reason to be concerned. And from the practical point of view, I wouldn't expect huge differences in learning speed personally, but indeed it is possible that there might be some differences. $\endgroup$ Oct 29, 2022 at 15:51