Body: <p>I implemented a MCES for 2048 (the game), with a quality function implemented as a neural net of a single layer.</p>
  <p>The starts are created with 6 cells filled with values between 64 and 1024, two cells are 1024 an ther other 8 cells are filled with 0. The game is then progressed until the AI loses or wins and another start is created.</p>
  <p>After 10 wins the max cell created in the start is reduced in half. Thus, after the first 10 wins, the max cell created in the start is 512.</p>
  <p>The issue I am having is that after the first 10 wins, the AI gets stuck, it can run around 3 million steps but doesn't get any more wins.</p>
  <p>How should I create the starts for it to actually learn?</p>
  <p>Code for reward (<a href="https://github.com/EmmanuelMess/2048AI" rel="nofollow noreferrer">complete code here</a>):</p>
  <pre><code>        ArrayList&lt;DataSet&gt; dataSets = new ArrayList&lt;&gt;();
          double gain = 0;
  
          for(int i = rewards.size()-1; i &gt;= 0; i--) {
              gain = gamma * gain + rewards.get(i);
  
              double lerpGain = reward(gain);
              INDArray correctOut = output.get(i).putScalar(actions.get(i).ordinal(), lerpGain);
              dataSets.add(new DataSet(input.get(i), correctOut));
          }
  
          Qnetwork.fit(DataSet.merge(dataSets));  
  </code></pre>
  <p><a href="https://github.com/EmmanuelMess/2048AI" rel="nofollow noreferrer">Code</a>:</p>
  <pre><code>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(4)
                      .build())
              .layer(new OutputLayer.Builder()
                      .nIn(4).nOut(4)
                      .lossFunction(LossFunctions.LossFunction.SQUARED_LOSS)
                      .build())
              .build();
  
  
      public SimpleAgent() {
          Qnetwork.init();
          ui();
      }
  
      private static final double gamma = 0.02;
  
      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 final ArrayList&lt;GameAction&gt; actions = new ArrayList&lt;&gt;();
  
      private MultiLayerNetwork Qnetwork = new MultiLayerNetwork(conf);
      private GameEnvironment oldState;
      private GameEnvironment currentState;
      private INDArray oldQuality;
      private double epsilon = 1;
  
      public void setCurrentState(GameEnvironment currentState) {
          this.currentState = currentState;
      }
  
      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);
  
              epsilon -= (1 - 0.01) / 1000000.;
          }
  
          oldState = currentState;
          oldQuality = Qnetwork.output(currentState.boardState);
  
          GameAction action;
  
          if(random.nextDouble() &lt; 1-epsilon) {
              action = GameAction.values()[oldQuality.argMax(1).getInt()];
          } else {
              action = GameAction.values()[new Random().nextInt(GameAction.values().length)];
          }
  
          actions.add(action);
  
          return action;
      }
  
      private final int WINS_TO_NORMAL_GAME = 100;
      private int wonTimes = 0;
  
      public void setHasWon(boolean won) {
          if(won) {
              wonTimes++;
          }
      }
  
      public boolean playNormal() {
          return wonTimes &gt; WINS_TO_NORMAL_GAME;
      }
  
      public boolean shouldRestart() {
          if (currentState.lost || input.size() == 20) {
              ArrayList&lt;DataSet&gt; dataSets = new ArrayList&lt;&gt;();
              double gain = 0;
  
              for(int i = rewards.size()-1; i &gt;= 0; i--) {
                  gain = gamma * gain + rewards.get(i);
  
                  double lerpGain = reward(gain);
                  INDArray correctOut = output.get(i).putScalar(actions.get(i).ordinal(), lerpGain);
                  dataSets.add(new DataSet(input.get(i), correctOut));
              }
  
              Qnetwork.fit(DataSet.merge(dataSets));
  
              input.clear();
              output.clear();
              rewards.clear();
              actions.clear();
  
              return true;
          }
  
          return false;
      }
  
      public Game2048.Tile[] generateState() {
          double lerped = lerp(wonTimes, WINS_TO_NORMAL_GAME);
          int filledTiles = 8;
  
          List&lt;Integer&gt; values = new ArrayList&lt;&gt;(16);
  
          for (int i = 0; i &lt; 16-filledTiles; i++) {
              values.add(0);
          }
  
          for (int i = 16-filledTiles; i &lt; 14; i++) {
              values.add((int) (7-7*lerped) + random.nextInt((int) (2- 2*lerped)));
          }
  
          values.add((int) ceil(10-10*lerped));
          values.add((int) ceil(10-10*lerped));
  
          Collections.shuffle(values);
  
          return values
                  .stream()
                  .map((value) -&gt; (value == 0? 0: 1 &lt;&lt; value))
                  .map(Game2048.Tile::new)
                  .toArray(Game2048.Tile[]::new);
      }
  
      private static double reward(double x) {
          return x/ 2048;
      }
  
      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-07-19T17:57:47.077Z
Comments.Text: Could you add more details, like what policy iteration are you going to use, what are rewards, when an episode ends ?
Comments.UserDisplayName: Daniel Wiczew
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-19T22:40:09.207Z
Comments.Text: The implementation is the standard Monte Carlo exploring starts, but with an NN to save the expected rewards.
Comments.UserDisplayName: EmmanuelMess
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-19T22:40:29.730Z
Comments.Text: Episode ends when the AI losses or wins.
Comments.UserDisplayName: EmmanuelMess
Tags: <game-ai><monte-carlo-methods>
Title: Monte Carlo Exploring Starts broke for 2048 game AI
UserDisplayName: EmmanuelMess
ThreadText: # Monte Carlo Exploring Starts broke for 2048 game AI
  
  (Asked by: username_0 on 2020-07-10)
  
  I implemented a MCES for 2048 (the game), with a quality function implemented as a neural net of a single layer.
  The starts are created with 6 cells filled with values between 64 and 1024, two cells are 1024 an ther other 8 cells are filled with 0. The game is then progressed until the AI loses or wins and another start is created.
  After 10 wins the max cell created in the start is reduced in half. Thus, after the first 10 wins, the max cell created in the start is 512.
  The issue I am having is that after the first 10 wins, the AI gets stuck, it can run around 3 million steps but doesn't get any more wins.
  How should I create the starts for it to actually learn?
  Code for reward (complete code here):
          ArrayList dataSets = new ArrayList<>();
          double gain = 0;
  
          for(int i = rewards.size()-1; i >= 0; i--) {
              gain = gamma * gain + rewards.get(i);
  
              double lerpGain = reward(gain);
              INDArray correctOut = output.get(i).putScalar(actions.get(i).ordinal(), lerpGain);
              dataSets.add(new DataSet(input.get(i), correctOut));
          }
  
          Qnetwork.fit(DataSet.merge(dataSets));  
  
  Code:
  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(4)
                      .build())
              .layer(new OutputLayer.Builder()
                      .nIn(4).nOut(4)
                      .lossFunction(LossFunctions.LossFunction.SQUARED_LOSS)
                      .build())
              .build();
  
  
      public SimpleAgent() {
          Qnetwork.init();
          ui();
      }
  
      private static final double gamma = 0.02;
  
      private final ArrayList input = new ArrayList<>();
      private final ArrayList output = new ArrayList<>();
      private final ArrayList rewards = new ArrayList<>();
      private final ArrayList actions = new ArrayList<>();
  
      private MultiLayerNetwork Qnetwork = new MultiLayerNetwork(conf);
      private GameEnvironment oldState;
      private GameEnvironment currentState;
      private INDArray oldQuality;
      private double epsilon = 1;
  
      public void setCurrentState(GameEnvironment currentState) {
          this.currentState = currentState;
      }
  
      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);
  
              epsilon -= (1 - 0.01) / 1000000.;
          }
  
          oldState = currentState;
          oldQuality = Qnetwork.output(currentState.boardState);
  
          GameAction action;
  
          if(random.nextDouble() < 1-epsilon) {
              action = GameAction.values()[oldQuality.argMax(1).getInt()];
          } else {
              action = GameAction.values()[new Random().nextInt(GameAction.values().length)];
          }
  
          actions.add(action);
  
          return action;
      }
  
      private final int WINS_TO_NORMAL_GAME = 100;
      private int wonTimes = 0;
  
      public void setHasWon(boolean won) {
          if(won) {
              wonTimes++;
          }
      }
  
      public boolean playNormal() {
          return wonTimes > WINS_TO_NORMAL_GAME;
      }
  
      public boolean shouldRestart() {
          if (currentState.lost || input.size() == 20) {
              ArrayList dataSets = new ArrayList<>();
              double gain = 0;
  
              for(int i = rewards.size()-1; i >= 0; i--) {
                  gain = gamma * gain + rewards.get(i);
  
                  double lerpGain = reward(gain);
                  INDArray correctOut = output.get(i).putScalar(actions.get(i).ordinal(), lerpGain);
                  dataSets.add(new DataSet(input.get(i), correctOut));
              }
  
              Qnetwork.fit(DataSet.merge(dataSets));
  
              input.clear();
              output.clear();
              rewards.clear();
              actions.clear();
  
              return true;
          }
  
          return false;
      }
  
      public Game2048.Tile[] generateState() {
          double lerped = lerp(wonTimes, WINS_TO_NORMAL_GAME);
          int filledTiles = 8;
  
          List values = new ArrayList<>(16);
  
          for (int i = 0; i < 16-filledTiles; i++) {
              values.add(0);
          }
  
          for (int i = 16-filledTiles; i < 14; i++) {
              values.add((int) (7-7*lerped) + random.nextInt((int) (2- 2*lerped)));
          }
  
          values.add((int) ceil(10-10*lerped));
          values.add((int) ceil(10-10*lerped));
  
          Collections.shuffle(values);
  
          return values
                  .stream()
                  .map((value) -> (value == 0? 0: 1 << value))
                  .map(Game2048.Tile::new)
                  .toArray(Game2048.Tile[]::new);
      }
  
      private static double reward(double x) {
          return x/ 2048;
      }
  
      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:** game-ai, monte-carlo-methods
  > **Comments:**
  > **username_1**: Could you add more details, like what policy iteration are you going to use, what are rewards, when an episode ends ?  
  > **username_0**: The implementation is the standard Monte Carlo exploring starts, but with an NN to save the expected rewards.  
  > **username_0**: Episode ends when the AI losses or wins.  
  
  ---
  
  ## 0 answers
  
  