Answers.Body: <p>I participated in this contest and ended up 30th (out of ~4500). I used mainly neural network. I split the problem into parts:</p>
  <ul>
  <li>for each my own cell, I ask the NN what to do (build, spawn, move)</li>
  <li>inputs for the NN was mainly the 5x5 square vision around the cell</li>
  <li>there were 2 networks:
  <ul>
  <li>first network with 2 outputs - if first output is &gt; 0 then build. if second output &gt; 0, then spawn</li>
  <li>if the above not occurred, second network was responsible for move, 5 outputs (WAIT, N, S, E, W), highest value wins</li>
  </ul>
  </li>
  <li>for multiple units per cell, I asked the NN several times, each time with the updated inputs as if the move happened</li>
  </ul>
  <p>Training was done via neuroevolution, particularly evolution strategies. Personally I don't know (yet) how to train this type of NN by more conventional means.</p>
  <p>More details in: <a href="https://www.codingame.com/forum/t/fall-challenge-2022-feedbacks-strategies/199055/4" rel="nofollow noreferrer">https://www.codingame.com/forum/t/fall-challenge-2022-feedbacks-strategies/199055/4</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-07T15:37:18.113Z
Answers.LastActivityDate: 2023-01-07T15:37:18.113Z
Answers.UserDisplayName: derjack
Answers.Body: <p>I replied to a very similar question about checkers <a href="https://ai.stackexchange.com/a/37686/52372">here</a>.</p>
  <p>To summarize, there are two options:</p>
  <ul>
  <li>Have a large policy head that encodes all possible (combinations of) moves. It can be pretty large, AlphaZero for chess had 73x8x8 = 4672 output values.</li>
  <li>View the game in a different way where turns are split into multiple, smaller turns that don't always change whose turn to play it is, and then use a smaller policy head.</li>
  </ul>
  <p>It seems like this game is better suited to the second approach.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-02T19:09:47.800Z
Answers.Text: The second approach is interesting. So you'd basically have the combination of actions for a real meta turn, be the combination of individual actions produced in a series of "fake" mini turn. That could work. I guess you'd need to add some kind of stopping action to know when to exit fake mini turns. Thanks for the idea.
Answers.UserDisplayName: snowfrogdev
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-31T17:52:56.270Z
Answers.LastActivityDate: 2023-01-02T22:25:44.663Z
Answers.LastEditDate: 2023-01-02T22:25:44.663Z
Answers.UserDisplayName: KarelPeeters
Body: <p>I was looking at an AI coding challenge for a two player game on a 2D grid of variable size (from one game to the next).</p>
  <p>Here is a screen shot example of the playfield.
  <a href="https://i.sstatic.net/DsLao.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DsLao.jpg" alt="Game played on a 2D grid" /></a></p>
  <p>Each player has multiple units on the board. In fact, each tile can hold multiple units and you can move all or a part of those units. Each turn, each player may perform several actions at a time.</p>
  <p>You feed your actions to the game engine on one line, separated by a ;</p>
  <ul>
  <li>MOVE amount fromX fromY toX toY.</li>
  <li>BUILD x y.</li>
  <li>SPAWN amount x y.</li>
  <li>WAIT.</li>
  </ul>
  <p>Example of possible command sent to the game engine on one turn:</p>
  <pre><code>MOVE 2 2 3 3 3; SPAWN 1 6 6; BUILD 1 1; MOVE 1 9 8 9 9; MOVE 3 11 2 12 2
  </code></pre>
  <p>And the very next turn your command might be:</p>
  <pre><code>WAIT
  </code></pre>
  <p>And the turn after that</p>
  <pre><code>SPAWN 1 6 6; SPAWN 2 3 3
  </code></pre>
  <p>You get the idea. Each turn you can play a variable amount of &quot;moves&quot; or &quot;actions&quot;. And, on bigger boards, the number of valid possible actions can be very big.</p>
  <p>I was wondering how would one go about dealing with games like these when trying to use a NN to predict the best move(s) to play on any given turn.</p>
  <p>I know how I would handle the variable map size in the input, I'd probably just use the biggest possible map size and then pad the input for smaller map sizes. What I'm really scratching my head about is the output.</p>
  <p>How would one setup the output layer in order for the NN to output the best set of actions to play on a given turn?</p>
  <p>If we structured the output layer to account for each possible actions, whether they are legal or not on the current turn, the layer would be positively huge, wouldn't it? Number of tiles x number of neighbors, and that's just for moves, add to that spawning and building. Oh, and that doesn't even account for the fact that you can move or spawn more that one unit on a tile. How would you even structure that in your output?</p>
  <p>I did see this unanswered question <a href="https://ai.stackexchange.com/questions/25392/designing-policy-network-for-deep-rl-with-large-variable-action-space">Designing Policy-Network for Deep-RL with Large, Variable Action Space</a> which I think might be similar to what I'm asking but I'm not 100% sure as it is using some terms I'm unfamiliar with.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-25T10:08:29.660Z
Comments.Text: I'd suggest going over some basic concepts in reinforcement learning, which is a branch of machine learning that is probably most suitable for your problem. a good start may be  https://spinningup.openai.com/en/latest/
Comments.UserDisplayName: Hadar Sharvit
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-25T14:05:01.937Z
Comments.Text: This looks great, thank you. So far, I've had a hard time finding learning resources that are at the level I need. Everything is either super basic or just a bit too advanced and mathy, expecting prior knowledge or experience that I don't possess.
Comments.UserDisplayName: snowfrogdev
Tags: <neural-networks><deep-learning><convolutional-neural-networks><dqn><muzero>
Title: How are NNs output setup for games that allow multiple actions each turn and have very large sets of possible actions?
UserDisplayName: snowfrogdev
ThreadText: # How are NNs output setup for games that allow multiple actions each turn and have very large sets of possible actions?
  
  (Asked by: username_0 on 2022-12-25)
  
  I was looking at an AI coding challenge for a two player game on a 2D grid of variable size (from one game to the next).
  
  Here is a screen shot example of the playfield.
  [![Game played on a 2D grid](https://i.sstatic.net/DsLao.jpg)](https://i.sstatic.net/DsLao.jpg)
  
  Each player has multiple units on the board. In fact, each tile can hold multiple units and you can move all or a part of those units. Each turn, each player may perform several actions at a time.
  
  You feed your actions to the game engine on one line, separated by a ;
  
  * MOVE amount fromX fromY toX toY.
  * BUILD x y.
  * SPAWN amount x y.
  * WAIT.
  
  Example of possible command sent to the game engine on one turn:
  
  ```
  MOVE 2 2 3 3 3; SPAWN 1 6 6; BUILD 1 1; MOVE 1 9 8 9 9; MOVE 3 11 2 12 2
  
  ```
  
  And the very next turn your command might be:
  
  ```
  WAIT
  
  ```
  
  And the turn after that
  
  ```
  SPAWN 1 6 6; SPAWN 2 3 3
  
  ```
  
  You get the idea. Each turn you can play a variable amount of "moves" or "actions". And, on bigger boards, the number of valid possible actions can be very big.
  
  I was wondering how would one go about dealing with games like these when trying to use a NN to predict the best move(s) to play on any given turn.
  
  I know how I would handle the variable map size in the input, I'd probably just use the biggest possible map size and then pad the input for smaller map sizes. What I'm really scratching my head about is the output.
  
  How would one setup the output layer in order for the NN to output the best set of actions to play on a given turn?
  
  If we structured the output layer to account for each possible actions, whether they are legal or not on the current turn, the layer would be positively huge, wouldn't it? Number of tiles x number of neighbors, and that's just for moves, add to that spawning and building. Oh, and that doesn't even account for the fact that you can move or spawn more that one unit on a tile. How would you even structure that in your output?
  
  I did see this unanswered question [Designing Policy-Network for Deep-RL with Large, Variable Action Space](https://ai.stackexchange.com/questions/25392/designing-policy-network-for-deep-rl-with-large-variable-action-space) which I think might be similar to what I'm asking but I'm not 100% sure as it is using some terms I'm unfamiliar with.
  
  **Tags:** neural-networks, deep-learning, convolutional-neural-networks, dqn, muzero
  
  > **Comments:**
  > **username_1**: I'd suggest going over some basic concepts in reinforcement learning, which is a branch of machine learning that is probably most suitable for your problem. a good start may be  https://spinningup.openai.com/en/latest/  
  > **username_0**: This looks great, thank you. So far, I've had a hard time finding learning resources that are at the level I need. Everything is either super basic or just a bit too advanced and mathy, expecting prior knowledge or experience that I don't possess.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-01-07. Score: 2
  
  I participated in this contest and ended up 30th (out of ~4500). I used mainly neural network. I split the problem into parts:
  
  * for each my own cell, I ask the NN what to do (build, spawn, move)
  * inputs for the NN was mainly the 5x5 square vision around the cell
  * there were 2 networks:
    + first network with 2 outputs - if first output is > 0 then build. if second output > 0, then spawn
    + if the above not occurred, second network was responsible for move, 5 outputs (WAIT, N, S, E, W), highest value wins
  * for multiple units per cell, I asked the NN several times, each time with the updated inputs as if the move happened
  
  Training was done via neuroevolution, particularly evolution strategies. Personally I don't know (yet) how to train this type of NN by more conventional means.
  
  More details in: <https://www.codingame.com/forum/t/fall-challenge-2022-feedbacks-strategies/199055/4>
  
  
  ---
  
  ### Answer by username_3 on 2022-12-31. Score: 1
  
  I replied to a very similar question about checkers [here](https://ai.stackexchange.com/a/37686/52372).
  
  To summarize, there are two options:
  
  * Have a large policy head that encodes all possible (combinations of) moves. It can be pretty large, AlphaZero for chess had 73x8x8 = 4672 output values.
  * View the game in a different way where turns are split into multiple, smaller turns that don't always change whose turn to play it is, and then use a smaller policy head.
  
  It seems like this game is better suited to the second approach.
  
  > **Comments:**
  > **username_0**: The second approach is interesting. So you'd basically have the combination of actions for a real meta turn, be the combination of individual actions produced in a series of "fake" mini turn. That could work. I guess you'd need to add some kind of stopping action to know when to exit fake mini turns. Thanks for the idea.  
  
  ---
  
  