Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

2048 AI

ov3y.github.io

Post reply on HN
Print view View original

31–40 of 197 posts

Re: 2048 AI

#31

Post by janezhu »

izzydata wrote: post #23

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

Re: 2048 AI

#32

Post by izzydata »

janezhu wrote: post #31
izzydata wrote: post #23

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 th…

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

Re: 2048 AI

#33

Post by cordite »

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.

Re: 2048 AI

#34

Post by glial »

aeonsky wrote: post #18
rcthompson wrote: post #14

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

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.

Re: 2048 AI

#36

Post by ovolve »

deletes wrote: post #29

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.

Re: 2048 AI

#37

Post by dllthomas »

crusso wrote: post #26

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.

Re: 2048 AI

#38

Post by feral »

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.

Re: 2048 AI

#39

Post by Patrick_Devine »

izzydata wrote: post #23

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 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.

Re: 2048 AI

#40

Post by cscheid »

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)

Post reply on HN