Answers.Body: <p>Q learning on its own isn't enough to learn a winning strategy for a game like 2048. 2048 requires predictive thinking for possible outcomes and good positional awareness. Performance of the agent is heavily dependent on the reward function. The approach to give the reward proportional to the obtained points after every move is naive since it might sacrifice better positional play for short term rewards. The way it's posed it seems like the agent will try to maximize its performance for the last 20 moves or so. That could lead an agent to the positional situation which leads to a loss in couple of moves. Possibly better strategy would be to give positive reward when the agent actually completes the 2048 tiles and negative reward if it loses. Such parse rewards would add difficulty to training since it would require sophisticated exploration strategies which <span class="math-container">$\epsilon$</span>-greedy certainly isn't. The stochastic nature of the game would pose difficulty to the agent as well. Similar positions might lead to different outcomes because in some cases the new tile would spawn in a bad position for the continuation while in other cases it might be beneficial. The suggested approach would be to definitely include Monte Carlo tree search approach along with some RL algorithm which was successfully applied to agents like AlphaZero and AlphaGo. MCTS would sample moves ahead and agent would get better representation of how good certain actions are.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T01:58:09.690Z
Answers.Text: Tried a MCES, but it gets stuck, see here https://ai.stackexchange.com/q/22429/14892
Answers.UserDisplayName: EmmanuelMess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-13T07:50:50.290Z
Answers.LastActivityDate: 2020-06-13T07:50:50.290Z
Answers.UserDisplayName: Brale
Answers.Body: <blockquote>
    <p>There is an epsilon for discovery, set at 100% at the start and it decreases by 10% until it reaches 1%.</p>
  </blockquote>
  
  <p>After looking through your code on the linked GitHub repository, I think that the annealing of the <code>epsilon</code> parameter is a major issue.  As clarified in the above comments, the <code>act()</code> method is called once per episode time step to determine the agent's choice of action. Within this method, it seems that <code>epsilon</code> is decreased extremely rapidly. The code states that <code>epsilon = Math.max(1, epsilon - 10)</code>, which means epsilon is decreased to 1 after 10 time steps. Also as clarified in the comments, <code>epsilon</code> is never reset to a larger number. Therefore, it seems that <code>epsilon</code> will be reduced from 100 to 1 after 10 time steps after (most likely) a single episode, which in my opinion is much too quick and <strong>will stifle exploration</strong>. </p>
  
  <p>As a first guess, I suggest annealing <code>epsilon</code> more slowly from 100 to 1 after roughly one million time steps. If you want to anneal the parameter linearly, then each of the first million time steps could reduce epsilon by  <code>(starting epsilon - ending epsilon) / annealing time steps</code>, where <code>starting epsilon</code> = 100, <code>ending epsilon</code> = 1, and <code>annealing time steps</code> = 1000000. </p>
  
  <p>Other issues may crop up after making the above change, but I think this is a good starting point. This seems like a very fun project, and it would be fun if you kept us posted about the results!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-12T20:57:28.633Z
Answers.Text: I had considered that epsilon could be an issue, but never set it to reduce so slowly. Will try! Thanks!
Answers.UserDisplayName: EmmanuelMess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-12T22:41:31.153Z
Answers.Text: After around 1M iterations it doesn't seem to be as good as it should be, only getting to 256 in best cases. I also gets considerably more often stuck.
Answers.UserDisplayName: EmmanuelMess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-13T03:40:00.777Z
Answers.Text: Deep reinforcement learning is notoriously difficult to debug since bugs are often silent. The exploration problem that I helped with above is most likely only one problem with the code, albeit an important one. Unfortunately the rules in the Tour of this site discourage the discussion of programming issues and bugs, so I can't debug the entire codebase (I don't even know much Java). I suggest that you try your best to locate any other problems with the code and then post a more specific question about your code as a separate question in the future. I hope that you get good results!
Answers.UserDisplayName: DeepQZero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T01:58:48.250Z
Answers.Text: Please see https://ai.stackexchange.com/q/22429/14892
Answers.UserDisplayName: EmmanuelMess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-12T18:18:20.587Z
Answers.LastActivityDate: 2020-06-12T18:18:20.587Z
Answers.UserDisplayName: DeepQZero
Body: <p>I am having trouble making a reinforcement algorithm than can win the 2048 game.</p>
  
  <p>I have tried with deep Q (which I think is the simplest algorithm that should be able to learn a winning strategy).</p>
  
  <p>My Q function is given by a NN of two hidden layers 16 -> 8 -> 4. Weight initialization is XAVIER. Activation function is RELU. Loss function is cuadratic loss. Correction is via gradient descent.</p>
  
  <p>To train the NN I used a reward given by :</p>
  
  <p><span class="math-container">$$r_t = \frac{1}{1024} \sum_{i=0}^{n}{p^i r_{((t-n)+i)}}$$</span></p>
  
  <p>Where n is 20 or the amount of iterations since the last update if a game is lost and <span class="math-container">$p = 1.4$</span>.</p>
  
  <p>There is an epsilon for discovery, set at 100% at the start and it decreases by 10% until it reaches 1%.</p>
  
  <p>I have tried to optimize the parameters but can't get better results than a "256" in the board. And the cuadratic loss seems to get stuck at 0.25:
  <a href="https://i.sstatic.net/i9T42.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/i9T42.png" alt="DL4J web UI for neural net info"></a></p>
  
  <p>Is there something I am missing?</p>
  
  <p><a href="https://github.com/EmmanuelMess/2048AI" rel="nofollow noreferrer">Code</a>:</p>
  
  <pre><code>
  public enum GameAction {
      UP, DOWN, LEFT, RIGHT
  }
  
  public final class GameEnvironment {
  
      public final int points;
      public final boolean lost;
      public final INDArray boardState;
  
      public GameEnvironment(int points, boolean lost, int[] boardState) {
          this.points = points;
          this.lost = lost;
          this.boardState = new NDArray(boardState, new int[] {1, 16}, new int[] {16, 1});
      }
  }
  
  public class SimpleAgent {
      private static final Random random = new Random(SEED);
  
      private static final MultiLayerConfiguration conf = new NeuralNetConfiguration.Builder()
              .seed(SEED)
              .weightInit(WeightInit.XAVIER)
              .updater(new AdaGrad(0.5))
              .activation(Activation.RELU)
              .optimizationAlgo(OptimizationAlgorithm.STOCHASTIC_GRADIENT_DESCENT)
              .weightDecay(0.0001)
              .list()
              .layer(new DenseLayer.Builder()
                      .nIn(16).nOut(8)
                      .build())
              .layer(new OutputLayer.Builder()
                      .nIn(8).nOut(4)
                      .lossFunction(LossFunctions.LossFunction.SQUARED_LOSS)
                      .build())
              .build();
      MultiLayerNetwork Qnetwork = new MultiLayerNetwork(conf);
  
      private GameEnvironment oldState;
      private GameEnvironment currentState;
      private INDArray oldQuality;
  
      private GameAction lastAction;
  
      public SimpleAgent() {
          Qnetwork.init();
          ui();
      }
  
      public void setCurrentState(GameEnvironment currentState) {
          this.currentState = currentState;
      }
  
      private final ArrayList&lt;INDArray&gt; input = new ArrayList&lt;&gt;();
      private final ArrayList&lt;INDArray&gt; output = new ArrayList&lt;&gt;();
      private final ArrayList&lt;Double&gt; rewards = new ArrayList&lt;&gt;();
  
      private int epsilon = 100;
  
      public GameAction act() {
          if(oldState != null) {
              double reward = currentState.points - oldState.points;
  
              if (currentState.lost) {
                  reward = 0;
              }
  
              input.add(oldState.boardState);
              output.add(oldQuality);
              rewards.add(reward);
  
              if (currentState.lost || input.size() == 20) {
                  for(int i = 0; i &lt; rewards.size(); i++) {
                      double discount = 1.4;
                      double discountedReward = 0;
  
                      for(int j = i; j &lt; rewards.size(); j++) {
                          discountedReward += rewards.get(j) * Math.pow(discount, j - i);
                      }
  
                      rewards.set(i, lerp(discountedReward, 1024));
                  }
  
                  ArrayList&lt;DataSet&gt; dataSets = new ArrayList&lt;&gt;();
  
                  for(int i = 0; i &lt; input.size(); i++) {
                      INDArray correctOut = output.get(i).putScalar(lastAction.ordinal(), rewards.get(i));
  
                      dataSets.add(new DataSet(input.get(i), correctOut));
                  }
  
                  Qnetwork.fit(DataSet.merge(dataSets));
  
                  input.clear();
                  output.clear();
                  rewards.clear();
              }
  
              epsilon = Math.max(1, epsilon - 10);
          }
  
          oldState = currentState;
          oldQuality = Qnetwork.output(currentState.boardState);
  
          GameAction action;
  
  
          if(random.nextInt(100) &lt; 100-epsilon) {
              action = GameAction.values()[oldQuality.argMax(1).getInt()];
          } else {
              action = GameAction.values()[new Random().nextInt(GameAction.values().length)];
          }
  
          lastAction = action;
  
          return action;
      }
  
      private static double lerp(double x, int maxVal) {
          return x/maxVal;
      }
  
      private void ui() {
          UIServer uiServer = UIServer.getInstance();
          StatsStorage statsStorage = new InMemoryStatsStorage();
          uiServer.attach(statsStorage);
          Qnetwork.setListeners(new StatsListener(statsStorage));
      }
  }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-12T03:17:44.543Z
Comments.Text: Could you explain in detail how you handle exploration? It seems that you decrease epsilon very quickly (-10%) after each time step. Do you ever reset epsilon?
Comments.UserDisplayName: DeepQZero
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-12T13:21:05.237Z
Comments.Text: "Could you explain in detail how you handle exploration?" With a high epsilon at the start. "Do you ever reset epsilon?" No
Comments.UserDisplayName: EmmanuelMess
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-12T15:36:50.710Z
Comments.Text: Is a single call to `act()` analogous to one time step in the environment? Also, does a single call to `startGame()` play a single game (and then store the relevant data)?
Comments.UserDisplayName: DeepQZero
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-12T16:19:00.337Z
Comments.Text: "Is a single call to act() analogous to one time step in the environment?" Yes, each time a play is ready to be done act is called. "Also, does a single call to startGame() play a single game (and then store the relevant data)?" No, when the AI losses a new game is started. The same game is never played twice.
Comments.UserDisplayName: EmmanuelMess
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-12T16:19:52.877Z
Comments.Text: The AI doesn't store anything to disk.
Comments.UserDisplayName: EmmanuelMess
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T13:19:15.520Z
Comments.Text: one of problems is to treat all values on a board as categorial data, this single observation is crucial for solve this game, also then you can do cnn 1d, 2d or even 3d...
Comments.UserDisplayName: quester
Tags: <q-learning><feedforward-neural-networks>
Title: Help with deep Q learning for 2048 game getting stuck
UserDisplayName: EmmanuelMess
ThreadText: # Help with deep Q learning for 2048 game getting stuck
  
  (Asked by: username_0 on 2020-06-03)
  
  I am having trouble making a reinforcement algorithm than can win the 2048 game.
  
  I have tried with deep Q (which I think is the simplest algorithm that should be able to learn a winning strategy).
  
  My Q function is given by a NN of two hidden layers 16 -> 8 -> 4. Weight initialization is XAVIER. Activation function is RELU. Loss function is cuadratic loss. Correction is via gradient descent.
  
  To train the NN I used a reward given by :
  
  $$r\_t = \frac{1}{1024} \sum\_{i=0}^{n}{p^i r\_{((t-n)+i)}}$$
  
  Where n is 20 or the amount of iterations since the last update if a game is lost and $p = 1.4$.
  
  There is an epsilon for discovery, set at 100% at the start and it decreases by 10% until it reaches 1%.
  
  I have tried to optimize the parameters but can't get better results than a "256" in the board. And the cuadratic loss seems to get stuck at 0.25:
  [![DL4J web UI for neural net info](https://i.sstatic.net/i9T42.png)](https://i.sstatic.net/i9T42.png)
  
  Is there something I am missing?
  
  [Code](https://github.com/username_0/2048AI):
  
  ```
  
  public enum GameAction {
      UP, DOWN, LEFT, RIGHT
  }
  
  public final class GameEnvironment {
  
      public final int points;
      public final boolean lost;
      public final INDArray boardState;
  
      public GameEnvironment(int points, boolean lost, int[] boardState) {
          this.points = points;
          this.lost = lost;
          this.boardState = new NDArray(boardState, new int[] {1, 16}, new int[] {16, 1});
      }
  }
  
  public class SimpleAgent {
      private static final Random random = new Random(SEED);
  
      private static final MultiLayerConfiguration conf = new NeuralNetConfiguration.Builder()
              .seed(SEED)
              .weightInit(WeightInit.XAVIER)
              .updater(new AdaGrad(0.5))
              .activation(Activation.RELU)
              .optimizationAlgo(OptimizationAlgorithm.STOCHASTIC_GRADIENT_DESCENT)
              .weightDecay(0.0001)
              .list()
              .layer(new DenseLayer.Builder()
                      .nIn(16).nOut(8)
                      .build())
              .layer(new OutputLayer.Builder()
                      .nIn(8).nOut(4)
                      .lossFunction(LossFunctions.LossFunction.SQUARED_LOSS)
                      .build())
              .build();
      MultiLayerNetwork Qnetwork = new MultiLayerNetwork(conf);
  
      private GameEnvironment oldState;
      private GameEnvironment currentState;
      private INDArray oldQuality;
  
      private GameAction lastAction;
  
      public SimpleAgent() {
          Qnetwork.init();
          ui();
      }
  
      public void setCurrentState(GameEnvironment currentState) {
          this.currentState = currentState;
      }
  
      private final ArrayList<INDArray> input = new ArrayList<>();
      private final ArrayList<INDArray> output = new ArrayList<>();
      private final ArrayList<Double> rewards = new ArrayList<>();
  
      private int epsilon = 100;
  
      public GameAction act() {
          if(oldState != null) {
              double reward = currentState.points - oldState.points;
  
              if (currentState.lost) {
                  reward = 0;
              }
  
              input.add(oldState.boardState);
              output.add(oldQuality);
              rewards.add(reward);
  
              if (currentState.lost || input.size() == 20) {
                  for(int i = 0; i < rewards.size(); i++) {
                      double discount = 1.4;
                      double discountedReward = 0;
  
                      for(int j = i; j < rewards.size(); j++) {
                          discountedReward += rewards.get(j) * Math.pow(discount, j - i);
                      }
  
                      rewards.set(i, lerp(discountedReward, 1024));
                  }
  
                  ArrayList<DataSet> dataSets = new ArrayList<>();
  
                  for(int i = 0; i < input.size(); i++) {
                      INDArray correctOut = output.get(i).putScalar(lastAction.ordinal(), rewards.get(i));
  
                      dataSets.add(new DataSet(input.get(i), correctOut));
                  }
  
                  Qnetwork.fit(DataSet.merge(dataSets));
  
                  input.clear();
                  output.clear();
                  rewards.clear();
              }
  
              epsilon = Math.max(1, epsilon - 10);
          }
  
          oldState = currentState;
          oldQuality = Qnetwork.output(currentState.boardState);
  
          GameAction action;
  
          if(random.nextInt(100) < 100-epsilon) {
              action = GameAction.values()[oldQuality.argMax(1).getInt()];
          } else {
              action = GameAction.values()[new Random().nextInt(GameAction.values().length)];
          }
  
          lastAction = action;
  
          return action;
      }
  
      private static double lerp(double x, int maxVal) {
          return x/maxVal;
      }
  
      private void ui() {
          UIServer uiServer = UIServer.getInstance();
          StatsStorage statsStorage = new InMemoryStatsStorage();
          uiServer.attach(statsStorage);
          Qnetwork.setListeners(new StatsListener(statsStorage));
      }
  }
  
  ```
  
  **Tags:** q-learning, feedforward-neural-networks
  
  > **Comments:**
  > **username_1**: Could you explain in detail how you handle exploration? It seems that you decrease epsilon very quickly (-10%) after each time step. Do you ever reset epsilon?  
  > **username_0**: "Could you explain in detail how you handle exploration?" With a high epsilon at the start. "Do you ever reset epsilon?" No  
  > **username_1**: Is a single call to `act()` analogous to one time step in the environment? Also, does a single call to `startGame()` play a single game (and then store the relevant data)?  
  > **username_0**: "Is a single call to act() analogous to one time step in the environment?" Yes, each time a play is ready to be done act is called. "Also, does a single call to startGame() play a single game (and then store the relevant data)?" No, when the AI losses a new game is started. The same game is never played twice.  
  > **username_0**: The AI doesn't store anything to disk.  
  > **username_2**: one of problems is to treat all values on a board as categorial data, this single observation is crucial for solve this game, also then you can do cnn 1d, 2d or even 3d...  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2020-06-13. Score: 3
  
  Q learning on its own isn't enough to learn a winning strategy for a game like 2048. 2048 requires predictive thinking for possible outcomes and good positional awareness. Performance of the agent is heavily dependent on the reward function. The approach to give the reward proportional to the obtained points after every move is naive since it might sacrifice better positional play for short term rewards. The way it's posed it seems like the agent will try to maximize its performance for the last 20 moves or so. That could lead an agent to the positional situation which leads to a loss in couple of moves. Possibly better strategy would be to give positive reward when the agent actually completes the 2048 tiles and negative reward if it loses. Such parse rewards would add difficulty to training since it would require sophisticated exploration strategies which $\epsilon$-greedy certainly isn't. The stochastic nature of the game would pose difficulty to the agent as well. Similar positions might lead to different outcomes because in some cases the new tile would spawn in a bad position for the continuation while in other cases it might be beneficial. The suggested approach would be to definitely include Monte Carlo tree search approach along with some RL algorithm which was successfully applied to agents like AlphaZero and AlphaGo. MCTS would sample moves ahead and agent would get better representation of how good certain actions are.
  
  > **Comments:**
  > **username_0**: Tried a MCES, but it gets stuck, see here https://ai.stackexchange.com/q/22429/14892  
  
  ---
  
  ### Answer by username_1 on 2020-06-12. Score: 2
  
  > There is an epsilon for discovery, set at 100% at the start and it decreases by 10% until it reaches 1%.
  
  After looking through your code on the linked GitHub repository, I think that the annealing of the `epsilon` parameter is a major issue. As clarified in the above comments, the `act()` method is called once per episode time step to determine the agent's choice of action. Within this method, it seems that `epsilon` is decreased extremely rapidly. The code states that `epsilon = Math.max(1, epsilon - 10)`, which means epsilon is decreased to 1 after 10 time steps. Also as clarified in the comments, `epsilon` is never reset to a larger number. Therefore, it seems that `epsilon` will be reduced from 100 to 1 after 10 time steps after (most likely) a single episode, which in my opinion is much too quick and **will stifle exploration**.
  
  As a first guess, I suggest annealing `epsilon` more slowly from 100 to 1 after roughly one million time steps. If you want to anneal the parameter linearly, then each of the first million time steps could reduce epsilon by `(starting epsilon - ending epsilon) / annealing time steps`, where `starting epsilon` = 100, `ending epsilon` = 1, and `annealing time steps` = 1000000.
  
  Other issues may crop up after making the above change, but I think this is a good starting point. This seems like a very fun project, and it would be fun if you kept us posted about the results!
  
  > **Comments:**
  > **username_0**: I had considered that epsilon could be an issue, but never set it to reduce so slowly. Will try! Thanks!  
  > **username_0**: After around 1M iterations it doesn't seem to be as good as it should be, only getting to 256 in best cases. I also gets considerably more often stuck.  
  > **username_1**: Deep reinforcement learning is notoriously difficult to debug since bugs are often silent. The exploration problem that I helped with above is most likely only one problem with the code, albeit an important one. Unfortunately the rules in the Tour of this site discourage the discussion of programming issues and bugs, so I can't debug the entire codebase (I don't even know much Java). I suggest that you try your best to locate any other problems with the code and then post a more specific question about your code as a separate question in the future. I hope that you get good results!  
  > **username_0**: Please see https://ai.stackexchange.com/q/22429/14892  
  
  ---
  
  