Answers.Body: <p>Monte Carlo Tree Search is searching for the action with the best expected reward. If the reward is determined by whether it wins or losses, then all winning moves are equal and one will be selected arbitrarily. If you want them to win quickly, then you can adjust the reward for winning quickly.</p>
  <p>Supposing your reward distribution is [0, 1], I would keep some constant reward for winning and add some reward that decays as time to win increases. For example, your reward formula could be for a win <code>0.5 + 0.5 / T</code> where T is the time taken to achieve victory.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-11T07:53:16.153Z
Answers.LastActivityDate: 2023-10-11T07:53:16.153Z
Answers.UserDisplayName: CleverLikeAnOx
Answers.Body: <p>One option is that the RL is not there yet, you may need to continue with the training, or maybe add to the win/lose reward some tiny &quot;hints&quot; what is a good move (0.001 when you eat an enemy, -0.001 when your unit is being eliminated, etc..).</p>
  <p>I do assume that all the moves of your units are taken in one &quot;action&quot; of your army, and that you evaluate the reward for all the units as one single &quot;army&quot;.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-29T07:43:44.287Z
Answers.Text: The avaiable moves are modelled as individual unit moves, so during a turn, the AI moves all its units one by one, then it executes combats one by one, then the turn is over.  The playout ends with an evaluation of the position which is based on how much damage the AI inflicts the opponent minus how much damage it receives from the opponent
Answers.UserDisplayName: xpmatteo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-29T07:45:12.610Z
Answers.Text: If you have 6 units with about 4-5 available moves each, there is a lot of move combinations the AI needs to choose
Answers.UserDisplayName: xpmatteo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-29T07:48:02.720Z
Answers.Text: "the RL is not there yet" <-- I tried increasing the number of iterations, but it does not seem to find the solution I want. After a while, a "winner" move keeps getting selected even though it's not the move that I want, and increasing iterations does not help
Answers.UserDisplayName: xpmatteo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-29T12:41:39.833Z
Answers.Text: Can you please share code. It will be a bit clearer.  Should be interesting for me and for others.
Answers.UserDisplayName: Oren
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-29T13:49:59.323Z
Answers.Text: Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer).
Answers.UserDisplayName: Community
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-29T20:34:39.560Z
Answers.Text: Shared the code -- have fun!
Answers.UserDisplayName: xpmatteo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-30T19:22:59.290Z
Answers.Text: It is very nice and I recommend others to play with your code. Really nice.
  Did I get it right that the Carthaginian are the ones with extra power and you refer to them as the AI?
  It seems that the Carthaginian always win, so why should they learn to win this way rather than another way? If it is important to you how fast they will win, then add some penalty on the time maybe?
Answers.UserDisplayName: Oren
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-28T12:52:56.537Z
Answers.LastActivityDate: 2023-06-28T15:44:50.253Z
Answers.LastEditDate: 2023-06-28T15:44:50.253Z
Answers.UserDisplayName: Oren
Answers.Body: <p>It is very nice and I recommend others to play with your code. Really nice. Did I get it right that the Carthaginian are the ones with extra power and you refer to them as the AI? It seems that the Carthaginian always win, so why should they learn to win this way rather than another way? If it is important to you how fast they will win, then add some penalty on the time maybe?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-30T20:06:58.387Z
Answers.Text: Thanks Oren.  The problem is, if I start with equal forces, I always beat the AI because it does not play very intelligently
Answers.UserDisplayName: xpmatteo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-30T19:25:45.780Z
Answers.LastActivityDate: 2023-06-30T19:32:11.703Z
Answers.LastEditDate: 2023-06-30T19:32:11.703Z
Answers.UserDisplayName: Oren
Body: <p>I'm trying to implement Monte Carlo Tree Search for (a simplified version of) the boardgame Commands and Colors -- I'm setting up a scenario where the AI side has overwhelming force: 6 units vs 3 units played by the human.</p>
  <p>I would hope that MCTS moves the 6 units in for the kill; instead what happens is that some units attack, some move sideways, and some retreat.</p>
  <p>I suspect that the units in the front are already strong enough to make victory likely, so that the unit in the back does not see a difference in its moving closer to the action, and chooses to move away from it.  I suspect that when evaluating the value of the moves of the far away unit, the &quot;noise&quot; caused by the action of the units in the front, whose actions make the value of the position swing heavily, make it very difficult to evaluate the smaller contribution to the quality of the position made by moving the unit in the back.</p>
  <p>This is sad!  A human player would move all units towards the enemy, bc if the front units get damaged, they will be moved away from the front and replaced by second-line units.  Having units move randomly away from the action makes no sense.</p>
  <p>How do I fix it?</p>
  <p>-- Edit:</p>
  <p>The source code is here <a href="https://github.com/xpmatteo/auto-cca" rel="nofollow noreferrer">https://github.com/xpmatteo/auto-cca</a>
  The case that does not work as expected can be observed with:</p>
  <ul>
  <li>make server</li>
  <li>(open another terminal)</li>
  <li>make open</li>
  <li>click &quot;End Phase&quot; twice</li>
  </ul>
  <p>The lone brown (Carthaginian) unit should close in against the gray (Roman) ones, but it doesnt.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-28T12:39:44.383Z
Comments.Text: Do you have one centralized logic for all the units, or is it a logic per piece? The way you describe it, each piece has its own agent?
Comments.UserDisplayName: Oren
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-29T07:40:10.943Z
Comments.Text: Unit logic is centralized -- at every step I generate the set of possible moves, which are the same for all units: they can move one hex each.  Once a unit has moved, it's "spent" for the current turn and cannot move again, so the set of available moves is reduced by one
Comments.UserDisplayName: xpmatteo
Tags: <monte-carlo-tree-search><board-games>
Title: MCTS: Units away from the action
UserDisplayName: xpmatteo
ThreadText: # MCTS: Units away from the action
  
  (Asked by: username_0 on 2023-06-25)
  
  I'm trying to implement Monte Carlo Tree Search for (a simplified version of) the boardgame Commands and Colors -- I'm setting up a scenario where the AI side has overwhelming force: 6 units vs 3 units played by the human.
  
  I would hope that MCTS moves the 6 units in for the kill; instead what happens is that some units attack, some move sideways, and some retreat.
  
  I suspect that the units in the front are already strong enough to make victory likely, so that the unit in the back does not see a difference in its moving closer to the action, and chooses to move away from it. I suspect that when evaluating the value of the moves of the far away unit, the "noise" caused by the action of the units in the front, whose actions make the value of the position swing heavily, make it very difficult to evaluate the smaller contribution to the quality of the position made by moving the unit in the back.
  
  This is sad! A human player would move all units towards the enemy, bc if the front units get damaged, they will be moved away from the front and replaced by second-line units. Having units move randomly away from the action makes no sense.
  
  How do I fix it?
  
  -- Edit:
  
  The source code is here <https://github.com/username_0/auto-cca>
  The case that does not work as expected can be observed with:
  
  * make server
  * (open another terminal)
  * make open
  * click "End Phase" twice
  
  The lone brown (Carthaginian) unit should close in against the gray (Roman) ones, but it doesnt.
  
  **Tags:** monte-carlo-tree-search, board-games
  
  > **Comments:**
  > **username_1**: Do you have one centralized logic for all the units, or is it a logic per piece? The way you describe it, each piece has its own agent?  
  > **username_0**: Unit logic is centralized -- at every step I generate the set of possible moves, which are the same for all units: they can move one hex each.  Once a unit has moved, it's "spent" for the current turn and cannot move again, so the set of available moves is reduced by one  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2023-10-11. Score: 1
  
  Monte Carlo Tree Search is searching for the action with the best expected reward. If the reward is determined by whether it wins or losses, then all winning moves are equal and one will be selected arbitrarily. If you want them to win quickly, then you can adjust the reward for winning quickly.
  
  Supposing your reward distribution is [0, 1], I would keep some constant reward for winning and add some reward that decays as time to win increases. For example, your reward formula could be for a win `0.5 + 0.5 / T` where T is the time taken to achieve victory.
  
  
  ---
  
  ### Answer by username_1 on 2023-06-28. Score: 1
  
  One option is that the RL is not there yet, you may need to continue with the training, or maybe add to the win/lose reward some tiny "hints" what is a good move (0.001 when you eat an enemy, -0.001 when your unit is being eliminated, etc..).
  
  I do assume that all the moves of your units are taken in one "action" of your army, and that you evaluate the reward for all the units as one single "army".
  
  > **Comments:**
  > **username_0**: The avaiable moves are modelled as individual unit moves, so during a turn, the AI moves all its units one by one, then it executes combats one by one, then the turn is over.  The playout ends with an evaluation of the position which is based on how much damage the AI inflicts the opponent minus how much damage it receives from the opponent  
  > **username_0**: If you have 6 units with about 4-5 available moves each, there is a lot of move combinations the AI needs to choose  
  > **username_0**: "the RL is not there yet" <-- I tried increasing the number of iterations, but it does not seem to find the solution I want. After a while, a "winner" move keeps getting selected even though it's not the move that I want, and increasing iterations does not help  
  > **username_1**: Can you please share code. It will be a bit clearer.  Should be interesting for me and for others.  
  > **username_3**: Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer).  
  > **username_0**: Shared the code -- have fun!  
  > **username_1**: It is very nice and I recommend others to play with your code. Really nice. Did I get it right that the Carthaginian are the ones with extra power and you refer to them as the AI? It seems that the Carthaginian always win, so why should they learn to win this way rather than another way? If it is important to you how fast they will win, then add some penalty on the time maybe?  
  
  ---
  
  ### Answer by username_1 on 2023-06-30. Score: 1
  
  It is very nice and I recommend others to play with your code. Really nice. Did I get it right that the Carthaginian are the ones with extra power and you refer to them as the AI? It seems that the Carthaginian always win, so why should they learn to win this way rather than another way? If it is important to you how fast they will win, then add some penalty on the time maybe?
  
  > **Comments:**
  > **username_0**: Thanks username_1.  The problem is, if I start with equal forces, I always beat the AI because it does not play very intelligently  
  
  ---
  
  