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

91–100 of 197 posts

Re: 2048 AI

#91

Post by seventytwo »

pzs wrote: post #73
seventytwo wrote: post #55

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

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 :) )

Re: 2048 AI

#92

Post by ovolve »

[deleted] wrote: post #86
primitivesuave wrote: post #81

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

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

Re: 2048 AI

#94

Post by tambourine_man »

tyilo wrote: post #87
feral wrote: post #38

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

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.

Re: 2048 AI

#96

Post by primitivesuave »

ovolve wrote: post #89
primitivesuave wrote: post #81

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

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

Re: 2048 AI

#98

Post by mediocregopher »

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.

Re: 2048 AI

#100

Post by sixothree »

avalaunch wrote: post #64
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 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…

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