Body: <p>I was recently introduced to this simple board game called &quot;Battle Sheep&quot;. In this game, two to four players try to acquire as many hex tiles from a hex grid as possible.</p>
  <p>You can find the complete rules <a href="https://www.ultraboardgames.com/battle-sheep/game-rules.php" rel="nofollow noreferrer">here</a>.</p>
  <p>I decided to program a game engine for this game. You can find it <a href="https://github.com/jussihi/BattleSheep/tree/master/engine" rel="nofollow noreferrer">here</a>. I also created a SFML-based graphical interface for the game, which can be found from the same repo - <a href="https://github.com/jussihi/BattleSheep/tree/master/sfml-gui" rel="nofollow noreferrer">here</a>.</p>
  <p>The reason I created the game engine in the first place was a challenge to myself - I wanted to create an AI which would have superhuman skills in this game, since I thought that the game is pretty simple and it would be easy for a neural network to master it. I have been studying the work about deep reinforcement learning networks, especially Leela chess zero (Alphazero) and AlphaGo. I thought that a DQN should be possible to master the BattleSheep game, but I have stumbled across a problem:</p>
  <p>Let's consider a game with 2 players. Since the game has two phases (map creation and the gameplay itself), the action space of the game is unknown at the start because the two players can place their pasture boards as they wish as long as it follows the rules (see the link above). In my game engine, I have solved this problem by creating large-enough map so that any kind of piece placement combination in the map creation phase will fit inside of its bounds. During the map creation phase, the chosen hexes are set &quot;active&quot; (defined <code>HEX_FREE</code> in my engine). &quot;inactive&quot; hexes cannot be used, or could be considered &quot;out of bounds&quot; during gameplay (defined <code>HEX_OOB</code> in my engine). For this code, see <a href="https://github.com/jussihi/BattleSheep/blob/master/engine/Map.cpp#L11" rel="nofollow noreferrer">the constructor of my Map class</a>.</p>
  <p><strong>Now the question itself:</strong> Deep Q-learning requires a fixed-size action space, which is hard to define in BattleSheep, since the map is different in every game. One possibility would be to create an action space that consists of the complete map (including these &quot;inactive&quot; hexes in my game engine), and define every possible move in that map. However, if we consider a map with for example 40 width and 40 height, the action space would be</p>
  <pre><code>40 x 40 x 6 x (40 x?) 16
  </code></pre>
  <p>40 x 40 - from which hex the player will start the move</p>
  <p>6 - to which direction the player will move</p>
  <p>40? - how far the pieces will move (is this required since you are always forced to move as far as possible?)</p>
  <p>16 - how many pieces the player will move</p>
  <p>Without the extra x40, the action space will yield 153600 different moves, and with the extra 40 (move length), the action space will have 6.1 <strong>million</strong> different possible moves. This is surely too large. How should I tackle this problem?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-08T01:34:25.557Z
Comments.Text: I can't write a full answer yet, but checkout parametrized reinforcement learning or hierarchical reinforcement learning. You can either treat those extra details as the parameter of your action or as the sub-action of your action (hierarchical).
Comments.UserDisplayName: Sanyou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-09T10:04:55.950Z
Comments.Text: Thank you for the insight @Sanyou . I will surely check it out. I guess by "extra details" you mean the state of the hex tile on the hex map (active/oob)?
Comments.UserDisplayName: Jussi Hietanen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-10T16:54:11.510Z
Comments.Text: you could also just make the entire map the action space, but mask or filter the move that is infeasible for each player, then the action space will just be Area of Map * num of players
Comments.UserDisplayName: Sanyou
Tags: <reinforcement-learning><deep-learning><dqn><action-spaces><board-games>
Title: Deep reinforcement learning the board game "Battle Sheep" - too large action space?
UserDisplayName: Jussi Hietanen
ThreadText: # Deep reinforcement learning the board game "Battle Sheep" - too large action space?
  
  (Asked by: username_0 on 2022-09-07)
  
  I was recently introduced to this simple board game called "Battle Sheep". In this game, two to four players try to acquire as many hex tiles from a hex grid as possible.
  You can find the complete rules here.
  I decided to program a game engine for this game. You can find it here. I also created a SFML-based graphical interface for the game, which can be found from the same repo - here.
  The reason I created the game engine in the first place was a challenge to myself - I wanted to create an AI which would have superhuman skills in this game, since I thought that the game is pretty simple and it would be easy for a neural network to master it. I have been studying the work about deep reinforcement learning networks, especially Leela chess zero (Alphazero) and AlphaGo. I thought that a DQN should be possible to master the BattleSheep game, but I have stumbled across a problem:
  Let's consider a game with 2 players. Since the game has two phases (map creation and the gameplay itself), the action space of the game is unknown at the start because the two players can place their pasture boards as they wish as long as it follows the rules (see the link above). In my game engine, I have solved this problem by creating large-enough map so that any kind of piece placement combination in the map creation phase will fit inside of its bounds. During the map creation phase, the chosen hexes are set "active" (defined HEX_FREE in my engine). "inactive" hexes cannot be used, or could be considered "out of bounds" during gameplay (defined HEX_OOB in my engine). For this code, see the constructor of my Map class.
  Now the question itself: Deep Q-learning requires a fixed-size action space, which is hard to define in BattleSheep, since the map is different in every game. One possibility would be to create an action space that consists of the complete map (including these "inactive" hexes in my game engine), and define every possible move in that map. However, if we consider a map with for example 40 width and 40 height, the action space would be
  40 x 40 x 6 x (40 x?) 16
  
  40 x 40 - from which hex the player will start the move
  6 - to which direction the player will move
  40? - how far the pieces will move (is this required since you are always forced to move as far as possible?)
  16 - how many pieces the player will move
  Without the extra x40, the action space will yield 153600 different moves, and with the extra 40 (move length), the action space will have 6.1 million different possible moves. This is surely too large. How should I tackle this problem?
  
  **Tags:** reinforcement-learning, deep-learning, dqn, action-spaces, board-games
  > **Comments:**
  > **username_1**: I can't write a full answer yet, but checkout parametrized reinforcement learning or hierarchical reinforcement learning. You can either treat those extra details as the parameter of your action or as the sub-action of your action (hierarchical).  
  > **username_0**: Thank you for the insight @Sanyou . I will surely check it out. I guess by "extra details" you mean the state of the hex tile on the hex map (active/oob)?  
  > **username_1**: you could also just make the entire map the action space, but mask or filter the move that is infeasible for each player, then the action space will just be Area of Map * num of players  
  
  ---
  
  ## 0 answers
  
  