Answers.Body: <h1>Correction regarding policy encoding</h1>
  <p>The policy encoding you propose for Chess is not the one used by the original AlphaZero and would not work. The network needs to output a policy distribution over the possible moves, so there needs to be a dedicated output value for each move. Your encoding only allows the network to express a single move, or at best some low-rank approximation of the full distribution.</p>
  <p>The <a href="https://www.science.org/doi/10.1126/science.aar6404" rel="nofollow noreferrer">AlphaZero paper</a> (<a href="https://arxiv.org/abs/1712.01815.pdf" rel="nofollow noreferrer">free access</a>) has a section <em>Representation</em>, which explains the policy encoding they used. It has shape 73x8x8. Of course in a chess position there are never actually that many moves, so invalid moves are masked out.</p>
  <h1>Complex move representations in AlphaZero</h1>
  <p>As you also note there are two possible solutions to representing these types of compound moves:</p>
  <ul>
  <li><p>Figure out all possible moves and some reasonable way to encode them in a policy head. AlphaZero can still train quite well with a large, sparsely used policy head as shown by their chess results.</p>
  </li>
  <li><p>Represent the game differently, with moves split up into submoves that don't always change whose turn it is, and then find an encoding for this smaller set of moves. AlphaZero and more generally MCTS doesn't require alternating players, for example the followup work <a href="https://www.nature.com/articles/s41586-020-03051-4#Sec2" rel="nofollow noreferrer">MuZero</a> (<a href="https://arxiv.org/abs/1911.08265" rel="nofollow noreferrer">free access</a>) works just fine on the Atari games with only a single player.</p>
  </li>
  </ul>
  <h1>Practical advice for checkers</h1>
  <p>I think both solutions would work fine for checkers. Even including compound moves I think checkers still has less than <code>73*8*8 = 4672</code> possible moves, although I don't know for sure. If it's in the same ballpark or lower the first method should work. The first solution also has the advantage that it's simpler to implement and that you can achieve deeper search with a fixed number of neural network evaluations.</p>
  <p>The second solution is in some sense more general and scalable, so it could be interesting to experiment with as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T18:21:21.813Z
Answers.Text: I think I will end up separating multi moves into sub moves since trying to encode multi jumps in several different directions and including king moves jumping will be unworkable. I appreciate your detailed response
Answers.UserDisplayName: Anik Patel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T19:02:49.280Z
Answers.Text: @AnikPatel You could also go for a hybrid where you encode _some_ compound moves as a single move. (and disallow the sequence of single moves that would lead to the compound move to prevent duplication). I've seen this work for the game Arimaa for example.
Answers.UserDisplayName: KarelPeeters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-29T17:58:32.757Z
Answers.LastActivityDate: 2022-10-29T17:58:32.757Z
Answers.UserDisplayName: KarelPeeters
Body: <p>I'm trying to train a RL agent to play the game of checkers (AlphaZero style) and so far I've managed a proof of concept training a connect 4 agent up until perfection. However, unlike connect 4, checkers <em>moves</em> pieces rather than placing them and sometimes even multiple times. I think I understand how I would do this for chess: I have an output size of 80 (16+8*8) and have the first 16 outputs represent the <em>piece</em> that will move and the other 64 represent the <em>position</em> it will move to. I'm not sure if this is a valid solution though. The real problem arises when considering checkers with multiple jumps. Is there any solution to this and am I thinking about it the right way? I've pondered not changing the player turn whenever a double jump is available but I feel like this will screw with the MCTS.</p>
  
Tags: <neural-networks><reinforcement-learning><deep-rl><alphazero><board-games>
Title: Neural Network output for the game of Checkers
UserDisplayName: Anik Patel
ThreadText: # Neural Network output for the game of Checkers
  
  (Asked by: username_0 on 2022-10-28)
  
  I'm trying to train a RL agent to play the game of checkers (AlphaZero style) and so far I've managed a proof of concept training a connect 4 agent up until perfection. However, unlike connect 4, checkers *moves* pieces rather than placing them and sometimes even multiple times. I think I understand how I would do this for chess: I have an output size of 80 (16+8\*8) and have the first 16 outputs represent the *piece* that will move and the other 64 represent the *position* it will move to. I'm not sure if this is a valid solution though. The real problem arises when considering checkers with multiple jumps. Is there any solution to this and am I thinking about it the right way? I've pondered not changing the player turn whenever a double jump is available but I feel like this will screw with the MCTS.
  
  **Tags:** neural-networks, reinforcement-learning, deep-rl, alphazero, board-games
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-10-29. Score: 2 | Accepted answer
  
  # Correction regarding policy encoding
  
  The policy encoding you propose for Chess is not the one used by the original AlphaZero and would not work. The network needs to output a policy distribution over the possible moves, so there needs to be a dedicated output value for each move. Your encoding only allows the network to express a single move, or at best some low-rank approximation of the full distribution.
  
  The [AlphaZero paper](https://www.science.org/doi/10.1126/science.aar6404) ([free access](https://arxiv.org/abs/1712.01815.pdf)) has a section *Representation*, which explains the policy encoding they used. It has shape 73x8x8. Of course in a chess position there are never actually that many moves, so invalid moves are masked out.
  
  # Complex move representations in AlphaZero
  
  As you also note there are two possible solutions to representing these types of compound moves:
  
  * Figure out all possible moves and some reasonable way to encode them in a policy head. AlphaZero can still train quite well with a large, sparsely used policy head as shown by their chess results.
  * Represent the game differently, with moves split up into submoves that don't always change whose turn it is, and then find an encoding for this smaller set of moves. AlphaZero and more generally MCTS doesn't require alternating players, for example the followup work [MuZero](https://www.nature.com/articles/s41586-020-03051-4#Sec2) ([free access](https://arxiv.org/abs/1911.08265)) works just fine on the Atari games with only a single player.
  
  # Practical advice for checkers
  
  I think both solutions would work fine for checkers. Even including compound moves I think checkers still has less than `73*8*8 = 4672` possible moves, although I don't know for sure. If it's in the same ballpark or lower the first method should work. The first solution also has the advantage that it's simpler to implement and that you can achieve deeper search with a fixed number of neural network evaluations.
  
  The second solution is in some sense more general and scalable, so it could be interesting to experiment with as well.
  
  > **Comments:**
  > **username_0**: I think I will end up separating multi moves into sub moves since trying to encode multi jumps in several different directions and including king moves jumping will be unworkable. I appreciate your detailed response  
  > **username_1**: @username_0 You could also go for a hybrid where you encode _some_ compound moves as a single move. (and disallow the sequence of single moves that would lead to the compound move to prevent duplication). I've seen this work for the game Arimaa for example.  
  
  ---
  
  