Electrifiedby vlvd.net

2048 Reinforcement Learning: How a Program Learns From Its Games

2048 reinforcement learning is a program teaching itself the game by playing it. It makes a move, sees the points and the board that follow, and corrects its own guess of how good the last board was. Nobody writes the strategy in. Over many games the guesses improve, and so do the moves.

To test the same ideas by hand, Evolved 2048 gives you the 2048 puzzle on a cube you turn like a Rubik's cube, six faces of nine squares, free in your browser on a computer or a phone.

What 2048 reinforcement learning means

Reinforcement learning is learning from consequences, not from examples. No one shows the program a good game. It gets a board, picks a move and gets a number back: the reward. Its job is to collect the most reward over a whole game, not only on the next move.

That is the hard part. A move that scores nothing now can set up a big merge ten moves later. The program has to work out which quiet moves pay off. Wikipedia's 2048 article puts it plainly: the programs that play 2048 well score each board with an evaluation function, and some papers tuned that function with temporal difference reinforcement learning.

That is a different job from search. The 2048 AI strategy post covers how a search looks ahead past the random tile. This post is about where the program's sense of a good board comes from.

Why 2048 suits a learning program

  • The rules are small and fixed. Slide, merge equal tiles, add a new tile. A program can play a move in a fraction of a second.
  • There is real chance in it. In Evolved 2048 each new tile is a 2 when a random number comes out under 0.9, otherwise a 4. Run the game's own random number code for 10,000 new tiles and 1,001 are 4s. A learner cannot memorise one perfect line. It has to plan for odds.
  • The score is a clean signal. Points come only from merges.
  • Mistakes stick. No undo was found in the game: Control+Z, Backspace, Z and Escape all do nothing after a slide.

Jaśkowski's 2016 paper says the same in formal terms: 2048 fits the framework of a discrete-state Markov decision process, so it makes a good testbed for reinforcement learning methods.

States, moves and rewards on the cube

Before a program can learn, you describe the game in three parts. On the cube they look like this.

The state

The state is the whole board: all 54 squares, six faces of nine. A learner sees every square, including the faces you are not looking at.

The moves

Slides move the front face. Twists turn one row or column a quarter and carry its tiles to the next face. A whole-cube turn adds no points and counts no move, so a learner can treat it as a change of view rather than a real move.

The reward

A slide adds the value of every tile its merges make. A twist adds no points, counts one move and adds a new tile. In one scripted game that got stuck at move 31 with a score of 148, the tiles on the board, each counted as if built from 2s, added up to 152. Exactly one new tile had been a 4, which no merge made, and 152 minus 4 is 148. The score tracks what you built.

Now the example that shows why the reward alone is not enough. Two scripted games:

  • Slides only: the front face was full at move 46 with a score of 332, and the other five faces were empty.
  • Slides plus a twist whenever the front was stuck: a 128 tile at move 118, and a score of 1160 by move 165, after 39 twists.

Each of those 39 twists earned zero points on the spot. The game that used them still scored more than three times as much. A program that only chases the next reward would never twist. It has to learn that a board is worth more than its current score.

Temporal difference learning, one step at a time

The fix is a value function: a guess, for any board, of how many more points you can still earn from it. Temporal difference learning, or TD learning, trains that guess during play. Wikipedia's article on it gives the key idea: instead of waiting for the final outcome, the program moves each prediction toward a later, better-informed prediction, before the game is over.

Here is one step, with made-up numbers so the arithmetic is easy to follow. The program valued the board before its slide at 500. The slide merges two 8s for 16 points, and the program values the new board at 520. The target is 16 plus 520, so 536. The error is 536 minus 500, which is 36. With a learning rate of 0.01 it raises its old guess by 0.36.

Diagram of one temporal difference step: guess 500, slide scores 16, next guess 520, target 536, error 36, new guess 500.36

One TD step with a learning rate of 0.01. Small steps, many games.

To store those guesses, the papers below use n-tuple networks. There are far too many boards to give each one its own value, so the program scores small groups of squares and adds the scores up. A pattern that keeps leading to points gains weight. The table never holds a rule like "keep the big tile in a corner". It holds numbers that happen to rate those boards highly.

What the research reports

The Jaśkowski, Yeh and Guei abstracts on arXiv trace how far the method went. Yeh and five co-authors note that Szubert and Jaśkowski first paired TD learning with n-tuple networks for 2048, and that those programs still hardly reached large tiles.

  • Jaśkowski, 2016. Added temporal coherence learning, multi-stage weight promotion, carousel shaping and redundant encoding, and spread delayed updates across several CPU cores. The result was the best known 2048 program at the time.
  • Yeh, Wu, Hsueh, Chang, Liang and Chiang, 2016. Multi-stage TD learning, with a 3-ply expectimax search on top, reached the 32768 tile in 18.31% of games, where plain TD reached none. Tuned further, it reached 32768 in 31.75% of 10,000 games, and one game made a 65536 tile, the first they knew of.
  • Guei, 2022. Optimistic TD learning starts every guess high, which pushes the program to try moves it has not tried. The program averaged 625,377 points and reached 32768 in 72% of games, the best among learning-based programs.
Table of three 2048 reinforcement learning papers from 2016 to 2022 with what each added and its reported result

From the three arXiv abstracts: 1604.05085, 1606.07374 and 2212.11087.

Guei's dissertation also describes courses that use 2048-like games to teach reinforcement learning to beginners.

Why one game tells a learner so little

A fixed script shows the floor a learner starts from. In a corner test with one seed, one game per target corner, aiming for the bottom left scored 432 and aiming for the top right scored 136. Across two seeds those scripted games lasted 29 to 72 moves, with best tiles from 16 to 64.

That was one game each, not an average, and the gap is mostly luck of the draw. A learner sees this noise in every game, which is why the papers report rates over many games (10,000 in Yeh's), never a single run. For more on why the random tile makes certainty impossible, see can you win 2048 every time.

What you can borrow from a trained program

  • Value empty squares. When you run out of moves, the game's own box says: keep room on one face so a twist can still bring tiles round to their match. A twist needs one empty square for its new tile. The empty squares post goes further.
  • Accept zero-point moves. Twists score nothing, yet they made the gap between 332 and 1160 in the test games.
  • Update your guess before the game ends. After each slide, ask whether the board looks better or worse than you expected, and adjust your plan right away, the way a TD step does.
  • Judge a habit over many games. Play ten games with one rule, write down each score, then change one thing and play ten more.

Frequently asked questions

Can reinforcement learning win 2048 every time?

No. New tiles are random, so some positions are lost whatever the program does. The strongest learning program in Guei's dissertation reached the 32768 tile in 72% of games, not all of them.

Is reinforcement learning better than expectimax search for 2048?

They do different jobs and work best together. Search looks ahead at play time and needs a way to score boards; TD learning learns that score. Yeh and co-authors ran their learned network inside a 3-ply expectimax search.

What is an n-tuple network in 2048?

It is the table of learned scores the programs use: weights for the patterns found on small groups of squares, added up to score a whole board. TD learning adjusts those weights after each move.

Do I need a powerful computer to train a 2048 program?

Not to start learning how it works. Jaśkowski's abstract describes spreading training across multiple CPU cores, and Guei's courses use 2048-like games to teach beginners.

Get started

Act like a learner. Pick one rule, such as keeping the biggest tile in one corner of the front face and twisting only when stuck. Play ten games and write down each score, then change one thing and play ten more. Each mode (Evolved, Edge and Fun) keeps its own best score, so compare results within one mode.

Play Evolved 2048: it is free and plays in your browser on a computer or a phone.

The 2048 puzzle on a Rubik's cube, and past 2048.

Visit evolved2048.vlvd.net
Evolved 2048 on desktop
Evolved 2048 on tablet
Evolved 2048 on phone
0 likes

Comments

No comments yet.

or make an account to comment.