Answers.Body: <p>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 <a href="https://en.wikipedia.org/wiki/Negamax" rel="nofollow noreferrer">negamax implementations</a> 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:</p>
  <ol>
  <li>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.</li>
  <li>Handle games that are not zero-sum. Instead of storing a single value in every node, where you assume that one player is a <strong>max</strong> player and the other is a <strong>min</strong> player, just keep track of a separate value for each player in each node (which need not necessarily be each other's negation).</li>
  </ol>
  <ol start="3">
  <li>Handle games with more than two players. Same solution as above really, just use an array of values (one per player).</li>
  </ol>
  <p>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 &quot;move&quot; 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). <strong>I'm saying that this is technically possible, but doing this often produces a weaker MCTS agent, so I do not recommend it</strong>.</p>
  <p>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 <a href="https://ojs.aaai.org/index.php/AAAI/article/view/21265" rel="nofollow noreferrer">Split Moves for Monte-Carlo Tree Search</a> paper from the AAAI 2022 conference.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T14:33:39.427Z
Answers.Text: 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...?
Answers.UserDisplayName: Anik Patel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T14:53:39.870Z
Answers.Text: @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.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T15:37:30.590Z
Answers.Text: 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
Answers.UserDisplayName: Anik Patel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T15:50:11.543Z
Answers.Text: @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.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T15:51:07.970Z
Answers.Text: 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.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T10:34:14.780Z
Answers.LastActivityDate: 2022-10-29T10:34:14.780Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>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?</p>
  
Tags: <game-ai><monte-carlo-tree-search><board-games>
Title: MCTS with multi actions
UserDisplayName: Anik Patel
ThreadText: # MCTS with multi actions
  
  (Asked by: username_0 on 2022-10-29)
  
  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?
  
  **Tags:** game-ai, monte-carlo-tree-search, board-games
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-10-29. Score: 1 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/Negamax) 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](https://ojs.aaai.org/index.php/AAAI/article/view/21265) paper from the AAAI 2022 conference.
  
  > **Comments:**
  > **username_0**: 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...?  
  > **username_1**: @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.  
  > **username_0**: 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  
  > **username_1**: @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.  
  > **username_1**: 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.  
  
  ---
  
  