0
$\begingroup$

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

Is there something I am missing?

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<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));
    }
}
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – DeepQZero Jun 12 at 3:17
  • $\begingroup$ "Could you explain in detail how you handle exploration?" With a high epsilon at the start. "Do you ever reset epsilon?" No $\endgroup$ – EmmanuelMess Jun 12 at 13:21
  • $\begingroup$ 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)? $\endgroup$ – DeepQZero Jun 12 at 15:36
  • $\begingroup$ "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. $\endgroup$ – EmmanuelMess Jun 12 at 16:19
  • $\begingroup$ The AI doesn't store anything to disk. $\endgroup$ – EmmanuelMess Jun 12 at 16:19
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
+50
$\begingroup$

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!

| improve this answer | |
$\endgroup$
  • $\begingroup$ I had considered that epsilon could be an issue, but never set it to reduce so slowly. Will try! Thanks! $\endgroup$ – EmmanuelMess Jun 12 at 20:57
  • $\begingroup$ 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. $\endgroup$ – EmmanuelMess Jun 12 at 22:41
  • 1
    $\begingroup$ 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! $\endgroup$ – DeepQZero Jun 13 at 3:40
  • 1
    $\begingroup$ Please see ai.stackexchange.com/q/22429/14892 $\endgroup$ – EmmanuelMess Jul 10 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.