Skip to content
Fix Code Error

What is the optimal algorithm for the game 2048?

March 13, 2021 by Code Error
Posted By: Anonymous

I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make “bigger” tiles. After each move, a new tile appears at random empty position with a value of either 2 or 4. The game terminates when all the boxes are filled and there are no moves that can merge tiles, or you create a tile with a value of 2048.

One, I need to follow a well-defined strategy to reach the goal. So, I thought of writing a program for it.

My current algorithm:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

What I am doing is at any point, I will try to merge the tiles with values 2 and 4, that is, I try to have 2 and 4 tiles, as minimum as possible. If I try it this way, all other tiles were automatically getting merged and the strategy seems good.

But, when I actually use this algorithm, I only get around 4000 points before the game terminates. Maximum points AFAIK is slightly more than 20,000 points which is way larger than my current score. Is there a better algorithm than the above?

Solution

I developed a 2048 AI using expectimax optimization, instead of the minimax search used by @ovolve’s algorithm. The AI simply performs maximization over all possible moves, followed by expectation over all possible tile spawns (weighted by the probability of the tiles, i.e. 10% for a 4 and 90% for a 2). As far as I’m aware, it is not possible to prune expectimax optimization (except to remove branches that are exceedingly unlikely), and so the algorithm used is a carefully optimized brute force search.

Performance

The AI in its default configuration (max search depth of 8) takes anywhere from 10ms to 200ms to execute a move, depending on the complexity of the board position. In testing, the AI achieves an average move rate of 5-10 moves per second over the course of an entire game. If the search depth is limited to 6 moves, the AI can easily execute 20+ moves per second, which makes for some interesting watching.

To assess the score performance of the AI, I ran the AI 100 times (connected to the browser game via remote control). For each tile, here are the proportions of games in which that tile was achieved at least once:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

The minimum score over all runs was 124024; the maximum score achieved was 794076. The median score is 387222. The AI never failed to obtain the 2048 tile (so it never lost the game even once in 100 games); in fact, it achieved the 8192 tile at least once in every run!

Here’s the screenshot of the best run:

32768 tile, score 794076

This game took 27830 moves over 96 minutes, or an average of 4.8 moves per second.

Implementation

My approach encodes the entire board (16 entries) as a single 64-bit integer (where tiles are the nybbles, i.e. 4-bit chunks). On a 64-bit machine, this enables the entire board to be passed around in a single machine register.

Bit shift operations are used to extract individual rows and columns. A single row or column is a 16-bit quantity, so a table of size 65536 can encode transformations which operate on a single row or column. For example, moves are implemented as 4 lookups into a precomputed “move effect table” which describes how each move affects a single row or column (for example, the “move right” table contains the entry “1122 -> 0023” describing how the row [2,2,4,4] becomes the row [0,0,4,8] when moved to the right).

Scoring is also done using table lookup. The tables contain heuristic scores computed on all possible rows/columns, and the resultant score for a board is simply the sum of the table values across each row and column.

This board representation, along with the table lookup approach for movement and scoring, allows the AI to search a huge number of game states in a short period of time (over 10,000,000 game states per second on one core of my mid-2011 laptop).

The expectimax search itself is coded as a recursive search which alternates between “expectation” steps (testing all possible tile spawn locations and values, and weighting their optimized scores by the probability of each possibility), and “maximization” steps (testing all possible moves and selecting the one with the best score). The tree search terminates when it sees a previously-seen position (using a transposition table), when it reaches a predefined depth limit, or when it reaches a board state that is highly unlikely (e.g. it was reached by getting 6 “4” tiles in a row from the starting position). The typical search depth is 4-8 moves.

Heuristics

Several heuristics are used to direct the optimization algorithm towards favorable positions. The precise choice of heuristic has a huge effect on the performance of the algorithm. The various heuristics are weighted and combined into a positional score, which determines how “good” a given board position is. The optimization search will then aim to maximize the average score of all possible board positions. The actual score, as shown by the game, is not used to calculate the board score, since it is too heavily weighted in favor of merging tiles (when delayed merging could produce a large benefit).

Initially, I used two very simple heuristics, granting “bonuses” for open squares and for having large values on the edge. These heuristics performed pretty well, frequently achieving 16384 but never getting to 32768.

Petr Morávek (@xificurk) took my AI and added two new heuristics. The first heuristic was a penalty for having non-monotonic rows and columns which increased as the ranks increased, ensuring that non-monotonic rows of small numbers would not strongly affect the score, but non-monotonic rows of large numbers hurt the score substantially. The second heuristic counted the number of potential merges (adjacent equal values) in addition to open spaces. These two heuristics served to push the algorithm towards monotonic boards (which are easier to merge), and towards board positions with lots of merges (encouraging it to align merges where possible for greater effect).

Furthermore, Petr also optimized the heuristic weights using a “meta-optimization” strategy (using an algorithm called CMA-ES), where the weights themselves were adjusted to obtain the highest possible average score.

The effect of these changes are extremely significant. The algorithm went from achieving the 16384 tile around 13% of the time to achieving it over 90% of the time, and the algorithm began to achieve 32768 over 1/3 of the time (whereas the old heuristics never once produced a 32768 tile).

I believe there’s still room for improvement on the heuristics. This algorithm definitely isn’t yet “optimal”, but I feel like it’s getting pretty close.


That the AI achieves the 32768 tile in over a third of its games is a huge milestone; I will be surprised to hear if any human players have achieved 32768 on the official game (i.e. without using tools like savestates or undo). I think the 65536 tile is within reach!

You can try the AI for yourself. The code is available at https://github.com/nneonneo/2048-ai.

Answered By: Anonymous

Related Articles

  • How do I keep only the first map and when the game…
  • How do i update a javascript variable as its value changes?
  • Vuetify Navigation Drawer works once then stops
  • Why doesnt my table sort my div variable in numerical order?
  • error LNK2005: ✘✘✘ already defined in…
  • collision detection from picturebox in a list c#
  • Vuetify Navigation Drawer with Sub-Menus
  • Ember 2, filter relationship models (hasMany,…
  • Ukkonen's suffix tree algorithm in plain English
  • How to generate a random number in C++?
  • Undefined reference to 'vtable for ✘✘✘'
  • How to get partial information from JSON data in Python?
  • Vuetify nagviation drawer main text displays on…
  • How do I bind an input from an element of a 2D array…
  • Re-arrange position in a table maitaining order
  • Peak signal detection in realtime timeseries data
  • Inheritance of customized polymer element in version 1.0
  • How to tell Entity Framework to not include a nested object?
  • Pygame enemy not staying at the intended position on the map
  • Polymer CSS inline elements alignment
  • Requirements for getting the tile-cascade page…
  • How do I 'overwrite', rather than 'merge', a branch…
  • Pygame Enemy not showing on screen
  • Vueutify Navigation Drawer - Change Background Image
  • Drawing a rectangle on mouse position in Python using pygame
  • Resize Repeated Image in Javascript
  • Drawing Isometric game worlds
  • Javascript validate all checkboxes are selected
  • What is the best way for a smart contract to…
  • Octave using 'for' statement to show two animations…
  • Matplotlib scatter plot legend
  • Loading a single model with Ember.js
  • why print none for some lines
  • Content size - Vuetify
  • Practical uses of git reset --soft?
  • changing the background color of a v-list header
  • center 3 items on 2 lines
  • vuejs - How to append html with click event
  • Best way to Receive Consecutives Input calls?
  • Git merge with force overwrite
  • How to generate a random string of a fixed length in Go?
  • The form is not center aligned (vertically centered/middle)
  • How can I use packery with polymer elements?
  • Python is not calling fucntions properly
  • how to use canvas in JavaScript flappy bird code
  • What is the difference between dynamic programming…
  • Pandas Merging 101
  • How to refresh DOM when props change in Svelte?
  • Is it possible to apply CSS to half of a character?
  • Adding an image to a toolbar in a Vue + Vuetify…
  • What algorithms compute directions from point A to…
  • Setting up and using Meld as your git difftool and mergetool
  • Heuristic function prolog
  • C++ class forward declaration
  • Get value of clicked item in Vuetify multiple select…
  • Vuetify: How to add an avatar or an icon to the…
  • Vuetify grid system row management
  • Not all CSS functioning in Vuetify with Vue.js and Webpack
  • What is the difference between bottom-up and top-down?
  • How to get Navigation drawer clipped under dialog…
  • What is your most productive shortcut with Vim?
  • Generate a random point within a circle (uniformly)
  • How to show title in hover - css / jquery
  • Javascript if statement inside return
  • Fastest way to iterate over all the chars in a String
  • How to get a vuetify data table to span the entire…
  • Component based game engine design
  • How to get file path in iPhone app
  • How do I update an individual component using aurelia store?
  • When would you use the different git merge strategies?
  • Active tab issue on page load HTML
  • How to filter a RecyclerView with a SearchView
  • How to use html template with vue.js
  • SecondaryTile.DisplayName not getting updated
  • Recalculate merge conflicts (ie. how to generate…
  • In plain English, what does "git reset" do?
  • How do I pass a unique_ptr argument to a constructor…
  • Items in Vuetify list subgroup not stacking vertically
  • How to combine the data from two different…
  • Rust lifetime confusion
  • Tkinter understanding mainloop
  • Angular 2 @ViewChild annotation returns undefined
  • Best way to extract messy HTML tables using BeautifulSoup
  • Polymer 1.0 strategies for caching JSON data
  • How to get a random number in Ruby
  • Knight's tour Problem - storing the valid moves then…
  • Git workflow and rebase vs merge questions
  • Sending an Array of Objects to a component in vuejs
  • How does PHP 'foreach' actually work?
  • Random number generator only generating one random number
  • Using String Replace Only When Value Contains no…
  • Getting the closest string match
  • Spring data jpa- No bean named…
  • How to create Nested menus on Vuetify?
  • Python, random.randint does not print out
  • In this tic tac toe game, why the last move of last…
  • Vuetify - Center content in v-list-tile-content
  • Vue JS - How do I get WebGL to render via Vue…
  • Why does C++ code for testing the Collatz conjecture…
  • Sort table rows In Bootstrap

Disclaimer: This content is shared under creative common license cc-by-sa 3.0. It is generated from StackExchange Website Network.

Post navigation

Previous Post:

Checking if an object is null in C#

Next Post:

Node.js version on the command line? (not the REPL)

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

.net ajax android angular arrays aurelia backbone.js bash c++ css dataframe ember-data ember.js excel git html ios java javascript jquery json laravel linux list mysql next.js node.js pandas php polymer polymer-1.0 python python-3.x r reactjs regex sql sql-server string svelte typescript vue-component vue.js vuejs2 vuetify.js

  • you shouldn’t need to use z-index
  • No column in target database, but getting “The schema update is terminating because data loss might occur”
  • Angular – expected call-signature: ‘changePassword’ to have a typedeftslint(typedef)
  • trying to implement NativeAdFactory imports deprecated method by default in flutter java project
  • What should I use to get an attribute out of my foreign table in Laravel?
© 2022 Fix Code Error