Solve game 2048

This graph illustrates this point: The blue line shows the board score after each move. The red line shows the algorithm's best random-run end game score from that position. In essence, the red values are "pulling" the blue values upwards towards them, as they are the algorithm's best guess.

It's interesting to see the red line is just a tiny bit above the blue line at each point, yet the blue line continues to increase more and more. I find it quite surprising that the algorithm doesn't need to actually foresee good game play in order to chose the moves that produce it. First I created a JavaScript version which can be seen in action here.

This version can run 's of runs in decent time. Open the console for extra info. This version allows for up to runs per move and even if you have the patience. Building instructions provided. It runs in the console and also has a remote-control to play the web version. Surprisingly, increasing the number of runs does not drastically improve the game play.

There seems to be a limit to this strategy at around points with the tile and all the smaller ones, very close to the achieving the tile. After implementing this algorithm I tried many improvements including using the min or max scores, or a combination of min,max,and avg.

I also tried using depth: Instead of trying K runs per move, I tried K moves per move list of a given length "up,up,left" for example and selecting the first move of the best scoring move list.

Later I implemented a scoring tree that took into account the conditional probability of being able to play a move after a given move list. However, none of these ideas showed any real advantage over the simple first idea. I did add a "Deep Search" mechanism that increased the run number temporarily to when any of the runs managed to accidentally reach the next highest tile.

This offered a time improvement. I'd be interested to hear if anyone has other improvement ideas that maintain the domain-independence of the AI.

Just for fun, I've also implemented the AI as a bookmarklet , hooking into the game's controls. This allows the AI to work with the original game and many of its variants. This is possible due to domain-independent nature of the AI. Some of the variants are quite distinct, such as the Hexagonal clone. EDIT: This is a naive algorithm, modelling human conscious thought process, and gets very weak results compared to AI that search all possibilities since it only looks one tile ahead.

It was submitted early in the response timeline. I have refined the algorithm and beaten the game! It may fail due to simple bad luck close to the end you are forced to move down, which you should never do, and a tile appears where your highest should be.

Just try to keep the top row filled, so moving left does not break the pattern , but basically you end up having a fixed part and a mobile part to play with. This is your objective:. The chosen corner is arbitrary, you basically never press one key the forbidden move , and if you do, you press the contrary again and try to fix it.

For future tiles the model always expects the next random tile to be a 2 and appear on the opposite side to the current model while the first row is incomplete, on the bottom right corner, once the first row is completed, on the bottom left corner.

Here goes the algorithm. A few pointers on the missing steps. The model has changed due to the luck of being closer to the expected model. The model the AI is trying to achieve is. So it will press right, then right again, then right or top depending on where the 4 has created then will proceed to complete the chain until it gets:.

Second pointer, it has had bad luck and its main spot has been taken. It is likely that it will fail, but it can still achieve it:. I copy here the content of a post on my blog.

The solution I propose is very simple and easy to implement. Although, it has reached the score of Several benchmarks of the algorithm performances are presented. The assumption on which my algorithm is based is rather simple: if you want to achieve higher score, the board must be kept as tidy as possible. In particular, the optimal setup is given by a linear and monotonic decreasing order of the tile values.

This intuition will give you also the upper bound for a tile value: where n is the number of tile on the board. There's a possibility to reach the tile if the 4-tile is randomly generated instead of the 2-tile when needed. Several linear path could be evaluated at once, the final score will be the maximum score of any path. An implementation of the minmax or the Expectiminimax will surely improve the algorithm.

Obviously a more sophisticated decision rule will slow down the algorithm and it will require some time to be implemented. I will try a minimax implementation in the near future. In case of T2, four tests in ten generate the tile with an average score of My attempt uses expectimax like other solutions above, but without bitboards. In my case, this depth takes too long to explore, I adjust the depth of expectimax search according to the number of free tiles left:.

The scores of the boards are computed with the weighted sum of the square of the number of free tiles and the dot product of the 2D grid with this:. I am the author of a controller that scores better than any other program mentioned in this thread.

An efficient implementation of the controller is available on github. In a separate repo there is also the code used for training the controller's state evaluation function. The training method is described in the paper. The controller uses expectimax search with a state evaluation function learned from scratch without human expertise by a variant of temporal difference learning a reinforcement learning technique. The state-value function uses an n-tuple network , which is basically a weighted linear function of patterns observed on the board.

It involved more than 1 billion weights , in total. I think I found an algorithm which works quite well, as I often reach scores over , my personal best being around My solution does not aim at keeping biggest numbers in a corner, but to keep it in the top row. There is already an AI implementation for this game here. The algorithm is iterative deepening depth first alpha-beta search. The evaluation function tries to keep the rows and columns monotonic either all decreasing or increasing while minimizing the number of tiles on the grid.

There is also a discussion on Hacker News about this algorithm that you may find useful. More spaces makes the state more flexible, we multiply by which is the median since a grid filled with faces is an optimal impossible state. Here we evaluate faces that have the possibility to getting to merge, by evaluating them backwardly, tile 2 become of value , while tile is evaluated 2.

This is a simplified check of the possibility of having merges within that state, without making a look-ahead. This is not a direct answer to OP's question, this is more of the stuffs experiments I tried so far to solve the same problem and obtained some results and have some observations that I want to share, I am curious if we can have some further insights from this.

I just tried my minimax implementation with alpha-beta pruning with search-tree depth cutoff at 3 and 5. I applied convex combination tried different heuristic weights of couple of heuristic evaluation functions, mainly from intuition and from the ones discussed above:.

In my case, the computer player is completely random, but still i assumed adversarial settings and implemented the AI player agent as the max player. If I assign too much weights to the first heuristic function or the second heuristic function, both the cases the scores the AI player gets are low.

I played with many possible weight assignments to the heuristic functions and take a convex combination, but very rarely the AI player is able to score Most of the times it either stops at or I also tried the corner heuristic, but for some reason it makes the results worse, any intuition why? Also, I tried to increase the search depth cut-off from 3 to 5 I can't increase it more since searching that space exceeds allowed time even with pruning and added one more heuristic that looks at the values of adjacent tiles and gives more points if they are merge-able, but still I am not able to get I think it will be better to use Expectimax instead of minimax, but still I want to solve this problem with minimax only and obtain high scores such as or I am not sure whether I am missing anything.

Below animation shows the last few steps of the game played by the AI agent with the computer player:. Any insights will be really very helpful, thanks in advance. The following animation shows the last few steps of the game played where the AI player agent could get scores, this time adding the absolute value heuristic too:.

The following figures show the game tree explored by the player AI agent assuming the computer as adversary for just a single step:. And that the new tile is not random, but always the first available one from the top left. This variant is also known as Det I used an exhaustive algorithm that favours empty tiles. It performs pretty quickly for depth , but on depth 5 it gets rather slow at a around 1 second per move. Below is the code implementing the solving algorithm. The grid is represented as a length array of Integers.

And scoring is done simply by counting the number of empty squares. I thinks it's quite successful for its simplicity. The result it reaches when starting with an empty grid and solving at depth 5 is:.

This algorithm is not optimal for winning the game, but it is fairly optimal in terms of performance and amount of code needed:. Many of the other answers use AI with computationally expensive searching of possible futures, heuristics, learning and the such. These are impressive and probably the correct way forward, but I wish to contribute another idea. Read the squares in the order shown above until the next squares value is greater than the current one.

This presents the problem of trying to merge another tile of the same value into this square. To resolve this problem, their are 2 ways to move that aren't left or worse up and examining both possibilities may immediately reveal more problems, this forms a list of dependancies, each problem requiring another problem to be solved first.

I think I have this chain or in some cases tree of dependancies internally when deciding my next move, particularly when stuck. The whole approach will likely be more complicated than this but not much more complicated. It could be this mechanical in feel lacking scores, weights, neurones and deep searches of possibilities. The tree of possibilities rairly even needs to be big enough to need any branching at all.

Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. Learn more. Finally, make sure that you go right more than up.

Not Helpful 17 Helpful You may go far, but you'll be lucky to win. One move not mentioned here is to concentrate on merging big tiles. In fact, they actually say not to do that, but rather than making it your primary goal, just merge your bigger tiles when they touch.

The bigger tiles are more difficult to merge, so it's important to take every opportunity to combine them. Not Helpful 22 Helpful It gets you quite a high score, but since it is based on luck, it will usually not get you to the block. Not Helpful 26 Helpful No, not true at all. My friends have won many times and they swiped down a bunch.

Not Helpful 54 Helpful Yes, but it is solely based on luck if you do so. You are better off following algorithms, or just doing the math. Not Helpful 25 Helpful You can play it on the app or you can just search it up. There are many different variations of the game, so if you get bored with the original one, just look at variations of it on other websites.

Not Helpful 12 Helpful Ethan Ong. There isn't an easy way to beat this game but the best way to beat the game is to practice.

Not Helpful 26 Helpful 9. It is impossible to know if it is 2 or 4. This is completely random. But, it's most likely 2. Not Helpful 8 Helpful Solving this game is an interesting problem because it has a random component. As such, it is impossible to have an algorithm that will correctly solve the puzzle every time. Not Helpful 6 Helpful 6. It is called because it is the original last number. It is still possible to get The highest number in the game is Not Helpful 6 Helpful Include your email address to get a message when this question is answered.

By using this service, some information may be shared with YouTube. If you've beat and want more of a challenge, try to reach with the lowest score possible. Since you get points each time you make a move, this is really a challenge to reach with the lowest number of moves you can. Helpful 0 Not Helpful 0. Submit a Tip All tip submissions are carefully reviewed before being published.

You Might Also Like How to. How to. More References 1. Co-authors: Updated: December 10, Article Summary X is a popular video game where the goal is to swipe tiles of the same value to form multiples of 2 until you get the tile or larger.

In other languages Italiano: Vincere a Bahasa Indonesia: Menyelesaikan Game Nederlands: Winnen bij Deutsch: schaffen. Thanks to all authors for creating a page that has been read 1,, times. Is this article up to date? Cookies make wikiHow better. It seems obvious after a little practice that this version is impossible, and it just corresponds to being unlucky in the original game.

A rigorous proof that this version is impossible will likely be very tedious though Sign up to join this community. The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Learn more. Is the game always solveable? Ask Question. Asked 7 years, 10 months ago. Active 3 years, 11 months ago. Viewed 4k times. I always want to play best.

Yiyuan Lee