What is the optimal algorithm for the game 2048? | Hacker News Reader

What is the optimal algorithm for the game 2048?

stackoverflow.com

69 pointsxmjw13 comments

Expectimax is the correct algorithm. But to get the best result, you will have to add a few heuristics to it and other tricks.

I wrote a "Zoolander" algorithm for beating 2048. OK, it's super simple, but I hope it helps-Enjoy!

http://blog.blainelight.com/2014/03/how-to-beat-2048.html

It seems there's a lot of buzz around this game. Is there a particular reason for that?

Computer folks seem to be attracted to games with simple rules that can be programmed easily. Life comes to mind. This one has a lot of permutations of rules to explore.

two kinds of buzz - playing and making. making is easy for the reasons outlined by protomyth.

playing, i think, is NP-hard, and that makes games really addictive. see this research:

http://arxiv.org/pdf/1001.4420v3.pdf

which talks about flood filling games as being NP-hard. there's a satisfaction we get when we succeed that tickles our humanity in a unique way.

--Spoiler alert--

Someone revealed in that thread that you should never move down. I tried moving only up, left, and right and won easily, so the strategy is solid.

The basic heuristic I use (playing as a human, win rate around 75%, and I've had 4096-2048-1024 on the same board before):

Pick a corner for the highest tile (for me: upper left). Try to keep the next highest tiles in line with it (I choose the top row). Never push the opposite direction from that (down), and only push the other "off" direction (right) if that row is full so the highest tile will stay put, or if it's the only move remaining. Try to build a "snake" with numbers in descending order, and compress it down to a single tile whenever that becomes possible.

From there, it's just little tricks -- learning when you can untrap a lower tile, or when to hold off on a move in order to set up a better one -- that bring up the win rate by a few percent here and there.

spot tested these strategies, they help. when i deviated from it in a fit of panic i lost.

similarly, i also find that keeping the small tiles accessible - outside - helps tremendously. if you never move down you get that for free, because you never make open space on top for a 2 to come in (and not combine with your 512 or whatever).

"Don't panic" is also a good strategy. If you get into a situation you don't understand, take your hand off the keyboard and think before you move.

True, for any arbitrary value of "down." I.e. normally you should have three allowed directions and one forbidden one. For me the forbidden one starts out as always up.

Note that in game play if you have to you can change the forbidden direction.

Isn't that equivalent to never moving up? That's what I do.

Indeed, you can also never move left, or never move right.

And if you have to move this way you can rotate 90 degrees the forbidden direction if you must.

The board is symmetrical so it should be.

Reply on news.ycombinator.com