Hacker News new | comments | show | ask | jobs | submit login
2048 AI (ov3y.github.io)
1040 points by shmageggy 930 days ago | hide | past | web | 189 comments | favorite



The AI implements minimax using alpha-beta pruning.

Minimax assumes that the game/computer which the AI is playing against is playing adversarially - i.e. that the computer will insert the new tile that's the worst possible tile for the player/AI to receive.

But that's not actually what the game is doing. Instead, new tiles are inserted randomly. As a result, minimax probably isn't the best approach here.

I think something like monte carlo rollouts would work better. In other words, rather than evaluating a move by "what's the worst that could happen if I make this move", evaluate a move by "what is stochastically likely to happen if I make this move, weighted by how good/bad that outcome is for me." (Losing the game would have a big negative weight, of course).

Given that the current AI isn't actually winning the game, I guess that some sort of monte carlo rollout strategy would do better.

It's still cool to see how minimax does, though, so kudos to the authors - it'd be really interesting to see a comparison of different methods.


Heh. If you look in the code you'll see a big commented out chunk where I tried randomly sampling computer moves to get sort of an 'expected value' for the opposition's move. Empirically, it performed worse. I think this is for the same reason that all minimax algos assume optimal play by the opponent: if you assume optimal and they play less than so, it can only work in your favor. However I think there's some truth in the fact that sometimes an unpredicted random computer move can mess things up. Unfortunately exhaustively enumerating all possible computer moves was way too slow (for single-threaded javascript in the browser).


Its interesting that your approach performed worse; I wonder if it could be modified to do better? Interesting.

>I think this is for the same reason that all minimax algos assume optimal play by the opponent: if you assume optimal and they play less than so, it can only work in your favor.

That doesn't make sense when talking about a random opponent, though.

Imagine its chess. You are considering moving a pawn into a position where it can be obviously taken with no cost by the other player, but where, if the other player doesn't take the pawn, you'll get a sure checkmate on the next go.

You'd never make that move against an 'intelligent' player (i.e. in a minimax setup). But you'd definitely consider it against an enemy that moves randomly, because the expected value is so high.

This isn't to discount your empirical experience with this game, just to make a more general point.


When playing against a random opponent, sometimes it will "accidentally" make the best possible move. In chess, this might be extremely unlikely, as there are so many possible moves: the probability that, of all the pieces on the board, with all of the positions it could have made, that it would stumble upon a move that devastates your position--especially considering that often multiple correct moves must be performed in specific sequence to take advantage of what "should be" a winning position--is vanishingly small.

Further: the potential for gain (trivial mate against a stupid opponent in a handful of moves) is great. If you are thereby playing for "fastest win over time", taking advantage of random's suboptimality seems sane. In 2048, the bottleneck on your score seems best approximated by how long you survive: pulling stunts won't get you to 2048 all that faster as you need to have worked through enough tiles to arrive at that point: I'd imagine the difference would be at best a tiny fraction of the "required" moves.

Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal. As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess.

In summary: I just don't think comparing this game to chess is leading to useful intuitions.


It sounds like you're thinking he suggested just greedily taking the best possible move. But that's not what he suggested; he suggested evaluating the actual distribution of the opponent's moves and making the move with the highest expected value.


The question is do you want to have the shortest expected number of turns until you win, or a 100% win rate. Playing safe (min-max) is what ensures the 100% win rate, but you might be making games longer on average.


It doesn't have a 100% win rate as it stands.

Mini-max isn't even 'playing safe'.

Consider the following choice of moves, each leading to one of 5 random tile inserts:

Move A, which leads to 5 possible moves with the following game state goodnesses: ['Loss','Win','Win','Win','Win']

Move B, resulting in: ['99%CertainLoss','99%CertainLoss','99%CertainLoss','99%CertainLoss','99%CertainLoss']

Minimax is never going to choose A. Is that really what you want, even if your strategy is 'play it safe'?


Fair enough; I only ran it a couple times and it got to 2048 so I assumed it's a guaranteed win.


Min-max optimizes your chance of winning under the assumption of a rational adversary. That chance will be lower than "certain victory," especially in un-solved, symmetric games, because a rational adversary will also be playing min-max. The guarantee min-max provides is that it will do even better against a non-rational adversary than it does against a rational adversary; not that it will do better than any other algorithm against non-rational adversaries--which is the way I think it often gets parsed.

Also, we should note that the "value" in "expected value" doesn't have to mean "score." It could be the logarithm of your score, or your chance of winning against a rational adversary, or even the enjoyability of the game to spectators (if you have a precise metric for that).


No, I entirely understood that. I am quite happily willing to believe that I misunderstand the ramifications of that algorithm (I spent a lot of time talking about game theory in college, but it was not my field, and that was a long time ago), but that is the algorithm I inferred. (I would respond more, but you didn't leave me with any specific complaints to respond to, so all I can really say is "no".)


My impression is that you don't understand how these things work, so I'll start from the basics; apologies if wrong.

First off, the chess counter-example was in response to something general shmageggy said about 'all minimax algos'.

More broadly, in practice the issue is that you only have computational resources to search a fraction of possible game states. So where do you direct your limited resources?

Some candidate strategies: minimax with AB, exhaustive, MC sampling.

Even with any of these strategies, we can usually only search the game state tree to a given depth. (This is the tree of 'If I go here, then the game goes there, then I go here etc'.) When we reach our depth limit (if we haven't reached a terminal state - i.e. a win or loss), we use a heuristic (maybe 'number of free tiles') which approximates the value of the state to us at that point.

>Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal.

If the computer only has a few possible moves, then, yes, it might randomly choose the best one. But if it only has a few possible moves, chances are that any tree search technique, even stochastic, will start to expand all of them.

The question is, though, how will you know how good each of these moves is when you start examining are? I.e. Which of the moves available to you right now should you make? With Minimax/AB, you'll get a sense the move is optimal, because you'll look at the consequences of the move, (if the game makes the worst response to me (if I make the best move for me (if the game makes the worst response for me ... (heuristic evaluation)))).

With (sensible) MC search, you'll instead get a sense of which move is optimal by looking at more like what happens (if I make the best move for me (for each of a bunch of random moves the game could make (then if I make the best move for me (for each of a bunch of random moves the game could make ... (heuristic evaluation)))).

My point is that the latter is more suitable for this domain.

>As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess.

Well, then, if the probability of it randomly hitting a problematic move is high in a certain state, your MC search will be highly likely to come across that move, and thus you'll be likely to avoid moves that bring you to that state. So, no problem.

In summary: 1) If the game is highly likely to make a devastating move by random chance, then you are highly likely to come across that move in your stochastic search, so that's not really an objection. 2) In this game, just as in chess, there are always more states you'd like to search and expand than you have the resources to. Even if the computer only has a handful of 'moves' at any time, in order to tell how good these moves around, you've still got to expand out a lot of states. Choosing to use minimax instead of MC doesn't save you from that.


I am having a difficult time figuring out how to respond to this comment given that the assumption going into this conversation is that you are wrong and we are only interested in figuring out why you are wrong. For avoidance of doubt, we are assuming you are wrong because shmageggy claimed to have implemented an algorithm matching your description, that implementation was available for your perusal (it is only commented out, not deleted), and it didn't actually work better. Your comments, however, seem to continue to operate from the assumption that you are correct.

Also, while I do not have the background you do with search functions, I didn't feel like my comment (which I saw as offering an idea more than a proof: a comment about intuitions based on having wasted way way too much time playing 2048 yesterday and from being in the chess club at a different time in my life) warranted the "let me teach you the basics" paragraph, especially under the "we are working together to figure out why you are wrong" assumption. I am sufficiently confused by these differing approaches to the conversation as to not be certain how to proceed.

Like, "huh, ok, if you had a different idea for why you are wrong, what would it be?" is all I can come up with, but I don't think that fits your side of this interaction. (Maybe, if you simply feel you aren't wrong, you could look at shmageggy's code and find something "wrong"/suboptimal with his algorithm? I assumed you had already done this, given the context, but maybe not? Clearly my assumptions are failing here.) I think I will just bow out, actually get some work done, and maybe ask my friends (whom have much more experience in this space than, to my belief, either of us) to explain this to me later ;P.


I am with saurik.

The utility function is an approximation. So MCMC is aggregating information over an erroneous space, and min/max is also optimizing over an erroneous space too.

Which is the correct thing to do is conditioned on how the utility function behaves. In this scenario I think min/max plays maximumly conservative, which empirically seems to be the best thing to do.

If the utility is minimize free space on the board, the min/max will try to get to a free board but doesn't take risks so gets there in a suboptimal route. The MCMC will take the odd risky move as long as a large proportion of the futures lead to a even emptier board.

Clearly you don't want risky moves, because do enough of them and it ends in disaster (and its a long game). So the utility function should be exponentially weighted against going near risky situations. However, developing such a utility function which combines well in MCMC really requires understanding too much about the future game dynamics.

For MCM to work, the utility function really needs to capture how potentially bad a situation is, and I don;t think that is easy. Min/max is naturally pessimistic in stratergy, which is probably the correct thing to do.


I agree that all approaches are approximations, and which would actually perform best in this game is an empirical question. It'd take some work to really explore and tune either minimax or MC approach, so I wouldn't throw either out due to one failed attempt.

I accept the argument that "minimax is conservative, and conservative is good" might be correct. But I don't think its likely, and, without the time to code my own solution, all I can do is give arguments to that end.

I gave one intuitive argument here: https://news.ycombinator.com/item?id=7381382

Another argument is to remember that minimax, and AB-pruning, is a really strong way of reducing your search space - because of how unfavourable adversary moves are propagated up the tree - which could result in drastic pruning if the minimax assumption is wrong.

One 'bad' state, 6 or 8 ply deep through your branching factor ~10 tree, can result in you pruning entire lines of enquiry using minimax AB; surely that can't be right if the chance of the bad state happening is tiny, and especially if an alternative is chosen which isn't much better.

So I still think that if you want to tune the search algorithm to be risk adverse, then, yes, do so; but minimax is a drastic way to achieve that. But yes, how big of an effect that decision has in practice depends on complicated things, such as correlations in the search tree. (i.e. If you find a bad state in a section of the game tree, maybe there are likely to be other bad states nearby, so its not such a big deal to prune that whole section using minimax).


I was initially surprised that minimax worked at all for the exact reasons you cite. But it actually matches my intuition from playing the game kind of a lot. I think it's generally the case that most "opponent" moves are completely OK but there's one move that results in a high probability of loss (the one that's behind your "stack"). Avoiding worse case scenarios is really the entire game (i.e. your example wherein low probability of certain loss is being compared unfavorably to a guaranteed 99% loss rate does not actually come up). So if you built a really good, comprehensive MC approach, it might just reduce itself to minimax anyway. Thus perhaps the minimax is just a simpler way to implement the right approach from the get-go.


Actually I thought about it more. There are a few approaches

so you only need to decide 1 of 4 moves at the beginning

1. min max to a finite horizon using a heuristic utility function (as implemented)

2. Dynamic program/MCMC to a finite horizon and use the heuristic. Good at modelling the opponent behaviour, but could lead to bad results with a bad heuristic. (commented out approach)

3. Sample till the game ends (infinite horizon), pick the first move that lead to the game that went the longest (or won). This avoids developing an ad hoc heuristic.

So now I vote for 3. :p


> That doesn't make sense when talking about a random opponent, though.

Sure it does. AB search means you play to maximise your own value and minimise the value for your opponent. If your opponent is using a random strategy they will likely make a poor move and that's extra advantage for you.

Your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This is simply not true. Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go).


Consider this game:

You choose either Die or Coin.

If you chose Die, I will roll a die. If the die is 1, I give you $0; otherwise, $1000.

If you choose the coin, I'll give you $10 for heads, and $20 for tails.

If you use a minimax policy, you will choose the coin, because the worst outcome of that choice is a $10 payoff. The 'best' 'worst' outcome is what you get with minimax, and that's $10.

It is true that, as you say, if you instead get $20, you will be pleasantly surprised. "extra advantage for you", as you put it.

But it should be crystal clear that minimax is nonetheless the wrong decision policy here. If you use a minimax policy when the outcomes are random, you will generally be doing it wrong.

There are exceptions (e.g. you are starving and need $10 or else you'll die; or you are in my casino, and you think I'm using loaded dice, in which case the outcomes aren't random and you have an adversary; etc.) but in general, minimax is just wrong there.

>your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This is simply not true.

No - my argument is that if an opponent is random a minimax strategy is generally not best.

>Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go).

Yes, that's also true.


In the game of 2048, it's actually about risk minimization - in general, you progress at a steady, fixed speed unless something ugly happens. If you're in a safe position (which you should be throughout almost all of the game) then your possible gains from a great move are zero; if you don't take some advantage this turn then you'll generally get it next turn; but a single bad move can put you in an unfixable position.

There are almost no opportunities to make a 'great' move - since a great move with a significantly better effect on chance of winning than a move which doesn't change anything at all - is possible only if the move fixes a huge earlier mistake that you wouldn't have made in the first place.

For this particular game, advantages are temporary and disadvantages are near-permanent - so it makes sense to play very defensively, which minmax does. Imagine a game of Die or Coin, where if you choose coin, then you get $10 for heads, and $20 for tails; and for dice you throw a hundred-side die and get $25 for values 2-100 but if you roll 1, then you get shot and die.

[edit] what I'm saying is that assuming that [a] all payoffs are either effectively 0 or -infinity; and [b] most moves will (in the near expected future) be either 0 chance of the bad event or >0 chance of the bad event; then minmax would generate equal results to MC search - however, MC search would fail badly if you put overly optimistic payoffs, i.e., give too large rewards for 'good moves' and too little penalties for bad moves; and this is hard to estimate.

Minmax works if your payoff scale is completely wrong by orders of magnitude as long as the preference ordering is correct, MC search doesn't. If you know that position A is better than B but don't know if it is 1.1 times better or a million times better - then you can't implement a good MC search but can implemnt minmax.


You describe a one-player game with stochastic outcomes. I'm talking about a deterministic two-player game with one player making random moves. They're not the same thing.


Actually they're exactly the same. As in, completely identical games under a very trivial mapping. Think about how you'd formulate each one in terms of payoff matrices...


You're right. Still, there is something missing here: the game has no win condition. It is true that the best play seems to be to go for dice but suppose that rolling a 1 means I lose the game and forefit all my winnings. Why would I ever play that?


Why would you ever play dice, if rolling 1 meant losing everything?

Lots of situations. If you had $0, obviously.

Probably if you had less than $833.33 (the expected value of the dice in my game), slightly more subtly.

Maybe even other scenarios, depending on how long you wanted to play for, if there was a time cost to playing, if you could play for as long as you wanted, what your utility/risk preferences were, etc.

The point is that there are appropriate tools for reasoning about such games correctly - utility, decision theory, etc. - and they beat minimax.


You're changing the rules and shifting the goalposts. Look, it's simple: if the objective is to win then you want to avoid giving your opponent any chance to beat you. That means you never choose dice.

> The point is that there are appropriate tools for reasoning about such games correctly - utility, decision theory, etc. - and they beat minimax.

Perhaps this is true but you have not convinced me that this is the case here. Moreover, the OP claims to have empirical results showing that AB-pruning does better than MC-search for the game of 2048.


I'm not too surprised that alpha-beta does well, because when you are in a "good" state, playing so as to ensure that even in the worst case, you will still remain in as good a state as possible is very similar to playing to minimize the probability of ending up in a bad state in the next few moves. Obviously, the latter is your actual goal rather than the former. But the former is often a decent approximation and has the benefit that if most of the time there actually does exist a way you can maintain a "good" state even under perfectly adversarial play, then alpha-beta pruning will let you search much deeper and faster to find that way.

However, I would not dismiss MC-search or expectimax. Whereas alpha-beta should perform well when the current position is in a "good" state, when the current position is in a "bad" or "tricky" state, it almost certainly will perform way worse than search methods that actually take into account the opponent being random.

To consider the extreme example, imagine the position is extremely tenuous and that alpha-beta has proven that if the tiles are placed in the worst possible way in the next several turns, it is guaranteed the position is a loss and a 2048 is impossible. Obviously, it would be better that point to switch to something like expectimax and play so as to minimize the probability of a loss and maximize the probability of recovering, which could still be quite large. Whereas with alpha-beta the only thing you can do is maximize the number of moves until the forced loss, which will often not be the same thing as maximizing the probability of recovery, particularly if most reasonable branches of play lead to a forced loss in the same number of moves.

Similar arguments apply when the position is not a forced loss yet but is still "bad". For example, if the "bad" position is such that your long-term win probability is only 30%, I would expect alpha-beta to pass-up opportunities to fix the position if those opportunities carried any risk of making the position worse, whereas taking those risks is clearly correct if they could fix the position into a probable win and the probability of making things worse was only 1/2 or 1/3.

On the relevant stackoverflow thread, there is another answer much further down that has received far less attention, which is a shame: http://stackoverflow.com/questions/22342854/what-is-the-opti...

I've downloaded and compiled the solver, which uses expectimax rather than alpha-beta, and uses heuristics that are arguably even simpler and dumber, and yet it seems to outperform the OP's solver. It gets 4096 with good consistency and even often gets an 8192, whereas the OP's solver (after a tweak to make it not stop at 2048) can sometimes require a few tries to get a 4096 and only rarely gets an 8192. Granted, there's a large computing power difference, since one runs as native compiled code and one runs as javascript in the browser, but it shows that expectimax, which one would expect to be the most theoretically-sound approach, is indeed at least a comparably good approach, and possibly a superior one.


I suspect that the best objective function would be "maximize the time until I lose" which is closer to avoiding the worst case scenario than it is to performing best in the average case scenario.


I was also working on a 2048 AI, but you beat me to it! Nice job.

I was at an early stage, my scoring is just the game score (which apparently is flawed!) so nothing fancy. My approach to the large branching factor with the random tiles was just to ignore them and continue the search with a random one until there are less than N tiles free (I empirically found 4/5 to be good), where I perform a full search and apply a simple mean to the resulting scores. Mine is not even minimax, just a simple depth-first search. It wins between 1/4 and 1/5 of the time in a small sample of 200 games, how does yours perform?

This would be a great AI competition! Too bad it takes so long to run lots of games (mine is ~10 turns a second).

I wonder if web workers would speed it up.


> However I think there's some truth in the fact that sometimes an unpredicted random computer move can mess things up.

Isn't this guaranteed by the no free lunch theorem?


No. No Free Lunch Theorem means that there is no algorithm (that is programmed with no awareness of any specific search space) can be successful in ALL search spaces (problems).

But 2048 is a highly-structured search space. Even with random opponent, the opponent's choices are constrained by the game's rule structure.

http://en.wikipedia.org/wiki/No_free_lunch_theorem


The new tiles only appears on the opposite of your move direction. Your code does not seem to care about that. Maybe it will perform better if this is considered?


A friend has a question for you: "How many moves does it think ahead? Or does it just think in the 'here-and-now' (only 1 move ahead)?"


Someone else posted that it uses the minimax algorithm with alpha beta pruning and iterative deepening.

Minimax[1] looks "several" moves ahead to see what may happen. It assumes you always play your best possible move (to MAXimise your score) and your opponent always plays their best possible move (to maximise their score and MINimises yours). Because this creates a huge amount of possibilities, their is a method to reduce the number of moves considered called alpha beta pruning[2]. Some future moves can never lead to a better score for you and so are discarded or ignored.

Both approaches need you to look as many moves ahead as you can - each extra move you consider multiplies the number of possibilities exponentially, so there is another method called iterative deepening[3] which uses the algorithm to look 1 move ahead to find the best move and records that move. Then it repeats looking at 2 moves ahead and if it finds a better score than with 1 move it keeps that instead. Then 3 moves, then 4. The program will continue looking at more and more moves ahead until it reaches a time limit (or a size limit.)

[1] https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with...

[2] https://en.wikipedia.org/wiki/Alpha-beta_pruning

[3] https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs...


Yup, the way to do it is via a small variant of http://en.wikipedia.org/wiki/Expectiminimax_tree. Backgammon has "min", "max" and "expectation" nodes. The "correct" solver in this case only has "max" nodes (for the human moves) and "expectation" nodes (for the computer 'moves').


Its not always winning, but it does sometimes win. Is this game even winnable with every possible prng seed? I wouldn't be surprised if there were guaranteed-loss states.


It did win for me on the first try: http://i.imgur.com/uMB2J7f.png


It won for me too, kind of mesmerizing to watch it play it all by itself. Congratulations to the author.


Won for me on the second run: http://i.imgur.com/zc0uNLz.png


If new tiles are inserted randomly, you have to defend adequately against the worst case. Avoid-death always has a very good expected value, relatively.

So minimax is probably right in many cases and close enough to being right in most cases.


To check how the game would play out if the opponent (the computer who in the original game places the tiles randomly) would acutally play instead of randomly dropping the tiles I made a fork of the original game: http://sztupy.github.io/2048-Hard/

It's kinda nice to see how much harder the game becomes if you'd be playing against someone, as even getting to the 128 is hard. The current AI usually only gets to the 32 and sometims the 64 tile.


Yesterday I showed this game to a fellow graph theory buff and we also sat down to think about how to solve this game with AI.

The most straightforward solution is expectiminimax, which I see this solution has implemented quite nicely. In case someone here isn't familiar with minimax, the OP wrote some very elegant and well-commented code that would be a great primer.

The less computationally-intensive approach we came up with was to model the game state as a graph G(V, E), where V is the set of active tiles and E is a set of edges connecting adjacent tiles, weighted by the function c(v1, v2), which returns the absolute value of the difference between two tiles. For each decision, the AI picks the move that minimizes the sum of all edge weights in the new game state.

The reasoning behind this is that the only way to progress in the game is to have tiles of equal values adjacent to each other, for which the weight in G would be 0. Thus, the AI should try to minimize total weight. Eventually there will be large numbers on the boards with large edge weights to adjacent tiles, so the AI would try to keep these tiles next to other large tiles to minimize the difference.

Since the game is stochastic the approach I described may not work in a worst case scenario, but it could also be applied to the existing minimax solution as the weight function for each node in the tree.


=)

Check out the eval function, and specifically the function smoothness() in grid.js. It implements the edge weighting you describe!


Fantastic! Thanks for pointing that out. My cursory glance over the code in ai.js led me to believe that you were weighting it by score, now I see the full picture.

One more thing - have you looked into storing the game tree? I noticed it is starting the search from the beginning every time. I'd expect you would see a branching factor of around 10, so this would only really make a difference at depths greater than 4.

You started an excellent and inspiring GitHub project - I feel like the AI research into this game has only just begun.


[deleted]


I've been messing around trying to find a balance between both of those heuristics. They're both implemented, but there doesn't seem to be any magic bullet.


Heh, I did something like this for the original Threes games via computer vision and screenshots :)

http://www.youtube.com/watch?v=Sn2o2hb1bi0

Mine is using a minimax variant that replaces the minimum nodes with expectation (given that the choice of next tile is uniformly at random). This is sort of the algorithm used by backgammon solvers. The fun thing is that when expectation factors in, the branching factor is quite wide, but the necessary depth for the algorithm to beat humans is much smaller (with 8-ply on Threes this thing is miles ahead of me, no contest)


I've been playing this for awhile now and I think I have found that the best method is to only use 3 directions. This forces your highest number into a corner and only spawns 2's and 4's in the opposite corner. You build up numbers that cascade down to the corner. It almost never gets stuck, but if you do I guess you'd have to push the 4th direction you haven't been using.


I got up to 16220 that way-- the thing you have to look out for though is as you build the cascading layers, when you get the row three, not to block yourself in (having all 3 rows full so that the only direction you can go, is the one you are avoiding).

Try to keep your cascading layers down to 2, and keep about 2 steps ahead when you get to the 3rd layer. Many people have suggested keeping your highest number in the corner but I've found that doing so makes it easier to have 2's and 4's "invade" that fortress of high numbers you're building close to the wall. The best position is for the highest number to be 2nd or 3rd in the row closest to the wall cushioned by the second highest numbers on either side so that you can build up the numbers to either side of them, and eventually add them in.

Example:

X___X___X___X

X___X___2___4

8___16__32__16

64__256_512_128


Thanks for the suggestion. I can't stop until I beat this eventually.


Finally made it-- cascade gif: https://vine.co/v/Mbb07Wh0UPM/


I won 4 times in a row using a variant of that strategy where I lined up biggest to smallest numbers in a snake like pattern across the bottom of the grid. I only used up if my largest number got moved from the corner and I only used left if my bottom row was completely filled or my choices were narrowed to up or left.

EDIT: 5 times in a row now. I think I'm addicted.

EDIT: lost on my attempt for 6 in a row. I had to press up right after the 1024 appeared and was scrambling the rest of the game. I managed to get the 512 and 2 256s to appear as well but couldn't get them together.


The problem with pressing up (in your case) is that some random 2 is likely to get stuck in the position you needed.


I was doing the same. I got up to 1024 before losing, so I wonder if the algorithm would be better if you changed it to do a minmax search on three directions, and always omit the fourth unless you're forced to move that way.

That way your large values tend to be clump together and you don't get a small value buried which burns up a square.


I've been using this strategy too, and (at least for me) it works pretty well. I get to 1042 pretty often.

Also every time I move in the 4th direction I lose in few more moves (I did it at the begining to try this "theory", and it happened then too).



I won with using basically this strategy. I was forced to use the other direction exactly once.

http://i.imgur.com/4Ig74Q9.jpg


Likewise, I wouldn't say I only used the other direction only once, but I definitely keep the highest tile in the top right, and build up the top row, mostly moving up and right only


I've been doing that, too, but my impression is that it's a human cognitive convenience, rather than something algorithmically stronger.


That's what I have been doing. It "feels" like a good strategy.

But I couldn't tell if it was really just for my own cognitive convenience. That is, it's easier for me to reason about moves if I constrain moves to keep my high tiles against an edge.

I watched the AI play once, and it of course does not constrain itself this way. To really rub it in, the AI won the game, which I have not.


Back in college I implemented a checker AI that used minimax and a neural network that was trained with a genetic algorithm. After 4 days of tournament on a 400mhz box the resulting AI would almost always beat me. It was always fascinating to me that it used a 4 ply minimax with a 50 hidden nodes and 90 inputs to handily kick my ass.

I always wanted to re-implement it in node and for a cooler game. Alas! I have too many side projects.

The source is here: https://github.com/mkoryak/Evolutionary-Neural-Net-Checker-A...

and you can play against it here: http://mkoryak.github.io/checkers/nn_checker_ai_demo.html (requires java, might also require a 7 year old computer)


Hahah, I knew this was coming sooner or later. Thanks! Great job!

EDIT: This AI is a better player than me.


I don't know if you've experienced it yourself or have heard other reports of it, but after playing your game for a few hours last night I've been experiencing a 2048-flavored "tetris effect" all day today. My brain keeps on trying to identify "like things" to collapse together; pretty wild.


I had this a lot while developing 2048. At some point, I'd feel like I could collapse letters while typing, and that's when I decided I should probably stop playing so often.


Me too, I have this weird overlay of the game in my vision. It took a lot more of tetris to reach that effect.


All the fonts seem smaller, not sure if only one.


Assuming you mean all fonts everywhere, I got that too. I thought the next website I looked at went through some kind of redesign until I realized that the next two websites I looked at also looked like that.


I'm getting that as well.

I've won once.

The 'technique' I used was to keep the numbers on the left hand edge.

Then using left, down and up built up the rest of the tiles with the movement to left hand edge being the preferred move when it is possible.

I've not managed to repeat the victory yet though.


I'm getting the same thing. All the text in my Chrome window looks microscopic after playing.


I played for about 2 hours right before bed and couldn't get to sleep for hours. I was wired. Don't know if this is related to what you're suggesting or not, but I won't be playing this game again at night time.


This happened to me during my commute. I was visualizing stacks of cars smashing together and disappearing in front of me. Very unsettling.


I used to get that with other games such as Amplitude on the PS2. I'd close my eyes and my brain could see the game being played with incredible detail. It's happened to me with other games also. I think of it as a type of mental burn in. Goes away after a while.


Here's the routine I've used to win multiple times in a row:

1. "tumbler" until 128 can move to the upper left corner (up right down left, repeat)

2. The highest number on the board is always in the upper left. Make the top row descend left to right.

3. Before combining values on the top row, keep hitting up until one of the lower rows will not combine from a left.

4. Often, the slot you are filling (eg, top right or one below top right) will have a two. Alternate pressing left and right until a two appears, allowing you to combine

5. Keep the second row locked as soon as possible with unique values ASCENDING left to right. This way you can use up, left and right without moving the slot you are filling on the far left of the second row.

6. Never fill the top three rows such that a left or right cannot be used. You will be forced to use a down, messing up the top row.

There are a few other pattern recognition tricks that you'll pick up to aid in filling a slot for higher values. Other misc tips:

* try to keep high number squares close together, and merge up to the top row as soon as possible. Otherwise, they will just close off a slot

* You may get a 2 trapped on the top row blocked by a higher value below it. Unfreeze the second row by combining squares & hope that a two appears in the new opening

* only 2's or 4's will appear. They (always?) appear in the space left behind by the previous movement


BUG:

Whenever two sets of tiles combine in a single move, only one of their scores is counted. For example, let's say that a pair of 8s and a pair of 4s are about to be combined into a new 16 tile and a new 8 tile. The game should be giving us 24 points total for this move because we are creating a 16 tile (16 pts) and an 8 tile (8 pts) where 8+16=24.

However, this does not happen. Only one or the other combination will actually be counted, it seems. In a more egregious case, I combined two 512 tiles to form a new 1024 tile and should have gotten those corresponding points. However, there was also a pair of 2s which combined to make a 4-tile. I only received 4 points for the entire move.

The game should be counting the score from all combined tiles!!! This is why my calculated minimum theoretical score of 20480 (assuming only twos are generated) was completely blown out of the water by winning scores of 12k - because in many cases, the score is incorrectly calculated!

If this is fixed.......

The minimum possible score to win the game (I think...) is 18432, although right now, with the bug, scores can be much lower. Here's how I get that. If we assume only 2s can be generated, then the minimum score is 10*2048 = 20480. However, sometimes a 4 is generated rather than a 2. Apparently, this happens 10% of the time. In theory, it is possible for someone to be given only 4s and also have a perfectly efficient game. In this case, the scoring contribution to get all the 4s from the 2s in the first example is eliminated. The total score of any tier is 2048, so we're remove 2048 from 20480, yielding 18432.

The minimum possible score to reach a winning 2048 tile, once this bug is fixed, should be 18432.


Ahh good catch. That got messed up during refactoring the original code. Thanks to the person who submitted the fix on github too.


Great... yeah, it looks a lot better now! Nice work on the solver. I just tried it and it won the game with 20312 pts. Pretty good one!



I'm consistently scoring higher than 2,500, and frequently as high as 3,500 with a tile of 512, by doing this:

1. Up

2. Right

3. Down

4. Left

5. Go to 1.

That loop scores better than my trying.


I had some luck (winning the game, that is) by following this general heuristic:

- Default to placing tiles in one corner, so, for example, using Up & Left primarily so that high numbers will accumulate in the upper left corner.

- Don't automatically consolidate tiles, but rather, maximally fill out the diagonal half-matrix with 2-4-8-etc... before moving to force a consolidation. Example:

https://www.dropbox.com/s/aargiwvoyg1shdp/Screen%20Shot%2020...

- When no Up or Left move is available, move right. Sometimes, this allows for a general consolidation chain reaction to occur, which generally radically empties the board.

- repeat - sometimes you'll need to switch corners to the upper right.


I used this strategy.

What's important to realize that after being forced to go right you will occasionally get a small tile trapped either in the corner or directly below it. You need to focus all your energy into merging other tiles into this small corner until it is the largest tile on the top row. Learning how to deal with these small tiles correctly was the key to my victory.


I got up to 9,000 with:

left, down, right, down, (repeat)


Not bad.

My new simple algo is:

1. Down until you cannot go down

2. Left

3. Down until you cannot go down

4. Right

5. Go to 1.


Right/Down/right/Down with an Up/Right/Down thrown in when stuck has worked well for me. My first 1024 block came that way.

When I began playing I was moving around the board in an unorganized fashion, but am now finding that moving the larger numbers to one corner (bottom-right for me) is the best method. By having your block consolidation take place in one particular area, the odds that you'll have matching large numbers goes up dramatically.


15,456

Yup, this one works very well.


I've tried a few games where I do those exact moves with no human judgement and the score ends up quite a bit lower than when I 'generally' follow those moves and consolidate using my best judgement.

Another interesting test was to always play a clockwise or counter-clockwise pattern. The consolidation happens in the middle of the board. This method seemed to result in higher scores than the right/down/right/down pattern.


Easy to implement in an AI as well. Could try various permutations and see which works best fairly trivially then too, eg up down left right / up left down right / up left right down etc...


I got to 1024 with a 512 by keeping the biggest tiles in one corner


I'm running some trials here and keeping track of the results with this AI. I'll edit this when I have the data to provide the information.

Something that occurred to me is that "score" and "winning" can have different optimizations. Score is based upon combining blocks, where as winning is based upon reaching the 2048 block. This means the game can be optimzed in two different ways: 1) To maximize score, wherein your goal is to delay reaching 2048 until the last possible moment to allow yourself time to rack up score, and 2) to reach 2048 in the optimal number of moves, which means a lower score.

You're scored on what you combine in a move. So, if you combine two "4" tiles to yield and "8" tile, you'll get 8 points, and so on. To maximize score, the idea would be to basically waste space on the board building up tiles you don't need, while avoiding getting to 2048. In theory, one could build up many 1024 tiles, and maybe even combine several at once to yield multiple 2048 tiles.

To minimize moves in order to reach the fastest would basically be a game of golf. You'd need to reach 2048, but the lowest score in doing so would, by default, mean you've completed the game more efficiently. There's probably some absolute minimum score, but I'm too lazy to figure that out right now...


Looks like I can't edit this anymore, but here are the results of a few trials.

http://i.imgur.com/4rqdhQQ.jpg

3/10 games were won. Of these three, the lowest score was 12268, with only 8, 4, and 2 tiles left on the board (aside from the 2048 tile, obviously). The highest score of all was also the first game to be won with a score of 13404. This was also the least "efficient" game to be won, with 10 other tiles left on the board aside from 2048.


If you have only a single 2048 tile in the end, and arrived to that by only combining the minimum number of required tiles, then your score will be 10*2048. If you think backwards, you'll get 2048 for the last tile, before that you need to get twice 1024 for the previous two, and so on until the level of 4's, which is the first one at which you get scores. This assumes only twos appear on the board.


Initially, I had arrived at this conclusion as well, but I've seen solutions (both from other people posting and from running this script) that have gotten to 2048 with 14000 or less. I'm not entirely sure where the discrepancy is coming from, though... Obviously with a certain number of "4"s being generated each turn, the 10x2048 value will be reduced, but not to the degree we see. For example, I have logged a win with a score of 13404 points, and other people in here have screenshots of wins with significantly less than 20480 pts.

Intuitively, I want to say that the optimal score is more like 10x2048/2, but I haven't been able to prove that yet (at least not in between work today :) )


It seems there is a bug where only the higher or two cascades trigger at once, will be scored. So some of the points seem to being lost.


You can add a simple heuristic to the scoring to increase the win rate by a lot - weighted corners.

Add the logged value of the numbers on the corners to the score and the higher numbers will tend to 'stick' to them. This also serves as a mechanism to guarantee that the new numbers appear away from the large numbers, which tend to block them from combining.

I also turned down the compute time to 20ms and it still runs well.


That's awesome. I'm looking at the source code but I can't seem to grasp it. What's a simple explanation of how it works?


Sorry, the code is a little unkempt.

The basic idea is minimax search. Googling that will get you started, but basically the algorithm plays out the game and keeps a score of the position after every move. Then it just makes the move that leads to the best score.

The "score" here is basically a count of how many free squares there are (with a little extra to keep things aligned if possible).

One major thing with these search algorithms is that the game tree grows exponentially as you move forward. To combat that, implemented alpha-beta pruning and a heuristic to only search the nastier computer moves rather than all of the possibilities.


Awesome, thanks for that! I was going to try when I saw the thread earlier but couldn't figure out how.


From github: The algorithm is iterative deepening depth first alpha-beta search. The evaluation function tries to minimize the number of tiles on the grid while keeping same/similar tiles in line with each other.

This basically means he's running an optimized version of minimax -- essentially, depth first search of game states looking for states that minimize tiles and keep them in line.

At each step, he looks several steps into the future, assigns them each a numerical score, then picks the move that leads to the best outcome.

Iterative deepening means that he evaluates all 1 move options, then all two move options, then all 3 moves options and so on. It increases the chances of finding a good move within a time constraint.

Alpha beta is a "lossless" optimization that allows you to more aggressively prune the tree when you're searching.


I haven't read the source code yet, so this might be off right of the bat. But from the general knowledge of minmax I think the end-game code might need some tweaking.

If there is a guaranteed win, the algorithm will find it. However, if there isn't any, how does it pick a path when it thinks it will lose every time? Are all losses equal to each other? Are some better than the others? Could the elgorithm take the path with best chances where the most of the plays end up winning while only a few of them end up losing?


Interesting. It seems the solution I and a couple of people more came up with of keeping the top value in a corner isn't being used. It's amazing how it's able to keep the large numbers together throughout the game.

The gameplay is much more interesting but it seems that getting from 1024 to 2048 is much harder this way, probably because the randomness accumulates over time making the depth search unreliable. The more structured solution accumulates much less risk so has some margin to deal with this.


I find the translate function, though very simple, rather elegant JS:

  AI.prototype.translate = function(move) {
   return {
      0: 'up',
      1: 'right',
      2: 'down',
      3: 'left'
    }[move];
  }
Ref: https://github.com/ov3y/2048-AI/blob/master/js/ai.js#L230


It won first time, impressive! http://i.imgur.com/epUtjyB.png



It gets so close! http://puu.sh/7rrD6.png

I find it frustrating to watch it hit (where I have not managed to get to) where you have one block 128, 256, 512, and a 1024. Moving around only makes it harder to join things together.

I am rather convinced this game is more by luck than actual good-play.


Does anyone know of a quantitative way to measure the influence of random draws vs. skill on the final score? I would have guessed that strategy would be effective on this game, but that could be wrong.


Interesting, mine beat the game: http://puu.sh/7rwqf.png


I found you can get to 256 by just being twiddle-fingers, sometimes even 512 ..


My friend found you can get pretty far in the game (at least a 1024 block) if you just spam RIGHT-DOWN-LEFT-DOWN repeatedl (basically rolling your fingers across the bottom row of arrow keys).

It was a little upsetting when I had actually been putting thought into my play and he was doing better.


I watched this run for about 5 minutes and it failed at 1024 with under 5000 points. It looks pretty cool, although it defies all logic when forming the squares (it put the largest number in the middle several times).


A new browser performance benchmark has born?


I was actually thinking a new game AI competition.


It runs based on random numbers, so it's hardly a reliable benchmark.


Just use a fixed seed and it's 100% deterministic. Benchmarks use random numbers all the time. (In fact, PRNGs themselves often make OK benchmarks.)


I was coincidentally working on the same thing when I saw this yesterday. Pushed the code to https://github.com/helgefmi/c2048 if it's of anyones interest.

It's just a wicked fast board implementation with a simple depth first search, as of now. But the idea of "making up" an opponent to make it possible to do alpha beta pruning is a cool idea. I might try to implementet it myself.

I regularly get scores above 50k with AI_DEPTH=5-6 and NUM_TRIES=20-30. My record so far is a score of 220k :-).


Is this game always guaranteed to be winnable, or is it like Solitaire?


The game isn't a stacked deck in that the outcome can be determined but there is a specific point in the game where you are guaranteed to only have a few tiles available (ex: 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 yields half the board) and you may or may not need a 2 to continue when the random selects a 4 locking your 2 in a corner or other similar manner.

I can't speak on statistics but I had best luck when following a set of heuristic rules that minimized the chances of locking valuable tiles in an unreachable location. If you stack the higher value blocks to a corner you're less likely to trap them with lower value blocks that are almost impossible to reach.

Ultimately I think the game is a better comparison to minesweeper where there are rules that will help you progress but at some point you're forced to guess and hope the outcome is in your favor.


Quick idea for empirically determining "winnability": implement the complement AI for computer moves [which are (i) position and (ii) value i.e. 2 or 4], perform a decent number of runs with depth limits for I.D. set much bigger, then look at the results. Also, I haven't looked at the code but I don't think looking into improved heuristics can hurt.

edit: I used 'look' 3 times in the last 20 words, what's wrong with me


I would go with Solitaire sine mine just lost. Did reach 1024 though.


That just means that this particular AI isn't capable of winning all the time. It doesn't tell us weather a theoretical perfect player could always win.


Mine too got stuck at 1024.


Solitaire is perfectly winnable.

I have finished solitaire a lot of times.


It's not guaranteed to be always winnable.


I pressed solve from the start, and the AI lost.


This AI losing doesn't mean the game isn't winnable in principle. I don't know whether it is or not though.


Doesn't the fact that it's minimax mean that it's "unwinnable with sufficiently bad luck" though? I mean if there's a mistake in the AI it's that it assumes that the game is maliciously picking the worst possible tile placements. If it dropped those assumptions, then it would lose if the AI just happened to hit the "worst" placement every time by accident.


It's like watching War Games - http://www.youtube.com/watch?v=NHWjlCaIrQo


A book with a vaguely similar idea, I recommend over the movie.

Colossus by Dennis Feltham Jones

( don't read the wikipedia entry as it contains spoilers ( whole plot ) )


This AI was doing impressively well but still did not quite reach 2048 stopping just before the end.

The way I won myself rather quickly was using bottom right priority and ignoring up key(which was suggested by HN).

That is put highest scoring tiles bottom and sorted to the right if possible.

So it is mostly down, right, with some lefts, but no ups. This way is really easy to get 1024, I think I reached 2048 on the 3rd try with this strategy(score was 20k something).


I tried twice and it didn't finish, after getting to 1024 both times... this shows just how difficult is that game!



Guys. I dont need the AI anymore. I have created my own patterns and methods.

Tada! I got my 2048 tile :) So happy

https://drive.google.com/file/d/0Bz9_OO8kXRkfY0RWdzZ6cDA4RDQ...


Nice job on the AI! I can still do much better much quicker by hand using the left-down-right-down-left-... strategy. Obviously an alpha-beta search should be able to do better than that naive strategy, but it needs a little more domain knowledge.


What are the rules for new tile placement? Is it deterministic, random, or adversarial?


Random location (uniform). 90% chance of a 2, 10% chance of a 4. This actually made it hard to model the computer move in the search.


When playing, it seemed like a 50% chance the new tile would be placed in exactly the spot or two that I didn't want it, even if there were 8+ open spaces.


That is a sampling bias caused by confirmation bias. Extreme cases such as the one pointed out tend to reinforce the hypothesis because they are more traumatic and, therefore, better remembered then the avalanche of cases where the higher probability positive outcome happens.



Brilliant game! I got pretty close, but even the AI managged to fail just a few moves before the completion. :( http://i.imgur.com/F2ldDAS.png


I’d be curious to see evolutionary or machine learning algorithms playing this.


I was curious too, was thinking about coding it. Anybody know the odds for a 2 or 4 appearing? Is it 50-50 or...?


Randomness will not help you guys, look at what a horde of monkeys do on the game when left alone:

http://popox.github.io/2048/


I wrote a script last night that does a simple: up, right, down, left. Ran it for a few thousand games last night -- highest it got was over 10k, and consistently got around 2.5-3k.


Works like a charm, got to 2048 and over 10k points

Second time around was pretty close http://i.imgur.com/psdSwjM.png


It failed when I tried it.


Nice one :)

Now, since the board is 16 tiles, and that you need two 2^n can make a 2^(n+1), the max game that can be played is 2^16=65536.

Can a 65536 game can be reallistically won, can it be by OP's AI?


I think that the scoring system can be improved. This AI wins with a lot less moves than me, hence it gets lower score for a solution "smarter" than mine.


Boom, 13,068 points and 2048! I'm feeling some pride in my AI.

http://cl.ly/image/3G1a0e1T0Q2O


Mine won as well, on the first try.

http://cl.ly/image/0H1o1P2Q0A0u/Image%202014-03-12%20at%2012...

I feel bad about my 1024 now, bested by a minmax.


so awesome, mine just barely beat yours with 13088 points on the first try: http://i.imgur.com/nxgFk57.png


mine lost at 11,012 :| my AI has a lower IQ


I ran it twice and it failed to achieve 2048, are other people having similar issues? Either way, nice attempt it works pretty darn well for 1 night of work.


same here


Strange game. The only way to win is not to play.


What algorithms might do better than this minimax? I've just read all the comments and there are no suggestions...


How would I go about making an AI for this game? Mainly getting it to interface with the actual game input and output.


I was genuinely surprised when the AI lost.


what a fun and easy game. beats a lot of the fps games for me out there. my strategy was just stack the higher numbers together, left down right up and never use right. i ended up with this: http://imgur.com/KuqAJTM&hrfol9i


YAY made it :3 http://grab.by/v9BA ^_^


Not sure why but every time I ran it on Firefox it failed, but it succeeded solving it on chrome always.


I think it's pretty clear the Author of this game is a NSA agent trying to distract us.


Oh well, I lost with AI as well. I just let it run and got to a game over with 8476 points.


I'm just counting down until someone builds this for the iPhone/Android for $.99


I would go crazy trying to play without arrow keys.


even this particular game plays surprisingly well on mobile.


swipe up down left right?


Seeing the AI work makes me no longer want to play the game. Take to long to get to 2048!


How does it decide where the new tile will appear, or it just tries every possibility?


Trying every possibility was way too slow (branching factor of ~15 to 20), so it only searches the most "annoying" moves, where annoying is defined by lining up with the highest value tiles and not being adjacent to other 2's (or 4's). The game is random though, so it can and does make moves that haven't been searched.


Cool game!! Can't stop playing it. Finally achieved 2048 w/ score 21028 :)


Does the AI guarantee winning?


I ran 9 browser windows in parallel and 2 of them won the others failed.


no. i ran it a bunch of times and it seems to have a win rate of around 30-40%


I always get at least 1024 now. I'm playing somehow like tetris...


Anyone implementing other IA technique? What's the link?


Please, please, please don't implement rankings...


very cool.

now... for a who can make the optimal AI competition... :P


my AI won the game with a score of 20388

pic: https://cloudup.com/chDTLSElXDN


I find this game quite addictive, contratulations!


Sadly, totally unrelated to the Hong Kong film...


Cool But why the autorun can't get a win?


While the game is difficult to finish, I'm kind of saddened at how far I can go just by randomly hitting up arrow, left arrow, down arrow, right arrow, etc.


When you get up to 128 and 256 it's been easy and it kind of feels like you've come a ways, but remember that you're only 1/16th or 1/8th of the way there.


It just won on 1st attempt here. Good job


So close to getting 2048. Cool stuff!


Cool, spent 15 minutes.


Math... the fun killer.


Nah, just fun at a higher level.


if this is AI why it scores only 512 square as max?


Assuming you're not trolling, it's because this AI is using a heuristic approach rather than a guaranteed correct approach.

Heuristics rely on simplified rules which don't accurately model the system on which they're acting 100% of the time. Good heuristics can come close to 100%, however.

But why? Glad you asked!

A 100% correct solution would be to write an algorithm which enumerates all of the possible moves as a decision tree, and walks the decision tree to find the correct answer.

However, given that there are four possible moves the user can make (up, down, left, right) and an upper bound of 32 possible moves the computer can make (computer places "2" or "4" anywhere in a 4x4 grid), each level of the tree could require up to 128 times the number of computations that it took to compute the previous level of the tree.

For example, calculating the first turn is on the order of 128 calculations. Calculating the second move is on the order of 128^2 calculations. Calculating the third is 128^3, an so on. By order of magnitude, how many moves do you think it takes on average to get to 2048? 10^3? Even if we were being really optimistic, maybe it's 10^2. In that case, you'd have to perform somewhere around 128^100 computations in order to solve the game perfectly every time.

Incidentally, python tells me that'd be

    5260135901548373507240989882880128665550339802823173859498280903068732154297080822113666536277588451226982968856178217713019432250183803863127814770651880849955223671128444598191663757884322717271293251735781376
calculations.

Or for fun, this is 128^1000:

    16216967556622020264666650854783770951911124303637432562359820841515270231627023529870802378794460004651996019099530984538652557892546513204107022110253564658647431585227076599373340842842722420012281878260072931082617043194484266392077784125099996860169436006660011209817579296678781962552377006552947572566780558092938446272186402161088626008160971328747492043520874011018626908423275017246052311293955235059054544214554772509509096507889478094683592939574112569473438619121529684847434440674120417402088754037186942170155022073539838122429925874353753616104159343594557666561701790904172597025336526662682021808493892812699709528570890696375575414344876088248369941993802415197514510125127043829087280919538476302857811854024099958895964192277601255360491156240349994714416090573084242931396211995367937301294479560024833357073899839202991032234659803895306904298017400980173252106913079712420169633972302183530075897845195258485537108858195631737000743805167411189134617501484521767984296782842287373127422122022517597535994839257029877907706355334790244935435386660512591079567291431216297788784818552292819654176600980398997991681404749384215743515802603811510682864067897304838292203460427757655073776567547507027144662263487685709621261074762705203049488907208978593689047063428548531668665657327174660658185609066484950801276175461457216176955575199211750751406777510449672859082255854777144724233490076402632176089211355256124119453870268029904400183858505767193696897593661213568888386800238409325673807775018914703049621509969838539752071549396339237202875920415172949370790977853625108320092839604807237954887069546621688044652112493076290091990717742355039135117441532973747930089955830518884135334798464113680004999403737245600354288112326328218661131064550772899229969469156018580839820741704606832124388152026099584696588161375826382921029547343888832163627122302921229795384868355483535710603407789177417026363656202726955437517780741313455101810009468809407811220573803353711246329589162370895804762245950918253016369092362406714116443316561598280583720783439888562390892028440902553829376
So throwing a few assumptions in there isn't a bad idea...


Actually, to make a 2048 you need to make two 1024s. It's unlikely that you'll make two 1024s at the same time. Similarly for the lower tiles. As a sort of upper bound you expect the game to be over in about 1024 moves and it's likely to not be much less than that. I think a more realistic number is somewhere in the 500s


I'm not sure I follow, but I think we're saying the same thing.

It's been too long since I've taken any hardcore discrete math for me to reliably reason about the bounds on the number of moves required to win. All I can do is make estimates based on simplifications.

How I arrived at my estimates for the order of magnitude of the minimum number of moves required to win:

At most, you can merge 4 tiles in one move. Assuming you were doing 4 tiles every move, and the game just didn't produce twos, it'd take just 128 moves. Order of magnitude: 10^2.

Assuming exactly one merge per move, and that the game only produces twos, it'd take 1024 moves. Order of magnitude: 10^3.


Cool


memorizing watching it "play" by it's self

i KNEW the AI would have been coming sooner or later [no this fast though], GREAT JOB!




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: