17 ms·
2048 AI
- shmageggy 13y agoSource code here https://github.com/ov3y/2048-AI https://github.com/ov3y/2048-AI
- andyhmltn 13y agoThat'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?
- rcoh 13y agoFrom 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.
- shmageggy 13y agoSorry, 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.
- andyhmltn 13y agoAwesome, thanks for that! I was going to try when I saw the thread earlier but couldn't figure out how.
- dshibarshin 13y agoWorks like a charm, got to 2048 and over 10k points Second time around was pretty close http://i.imgur.com/psdSwjM.png http://i.imgur.com/psdSwjM.png
- yukichan 13y agoIt failed when I tried it.
- deleted 13y ago[deleted]
- danmaz74 13y agoI tried twice and it didn't finish, after getting to 1024 both times... this shows just how difficult is that game!
- message 13y agoYeap, same here. http://i.imgur.com/TIr88B0.png http://i.imgur.com/TIr88B0.png
- syntern 13y agoA new browser performance benchmark has born?
- brink 13y agoIt runs based on random numbers, so it's hardly a reliable benchmark.
- munificent 13y agoJust use a fixed seed and it's 100% deterministic. Benchmarks use random numbers all the time. (In fact, PRNGs themselves often make OK benchmarks.)
- irollboozers 13y agoI was actually thinking a new game AI competition.
- terabytest 13y agoHahah, I knew this was coming sooner or later. Thanks! Great job! EDIT: This AI is a better player than me.
- Crito 13y agoI 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.
- kaybe 13y agoMe too, I have this weird overlay of the game in my vision. It took a lot more of tetris to reach that effect.
- vlad00 13y agoAll the fonts seem smaller, not sure if only one.
- shibby 13y agoI'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.
- positivejam 13y agoI'm getting the same thing. All the text in my Chrome window looks microscopic after playing.
- chilldream 13y agoAssuming 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.
- rplnt 13y agoOh well, I lost with AI as well. I just let it run and got to a game over with 8476 points.
- rcthompson 13y agoIs this game always guaranteed to be winnable, or is it like Solitaire?
- Fuxy 13y agoI would go with Solitaire sine mine just lost. Did reach 1024 though.
- ulam2 13y agoMine too got stuck at 1024.
- rcthompson 13y agoThat 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.
- aeonsky 13y agoI pressed solve from the start, and the AI lost.
- glial 13y agoThis AI losing doesn't mean the game isn't winnable in principle. I don't know whether it is or not though.
- chilldream 13y agoDoesn'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.
- ansimionescu 13y agoQuick 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
- joeblau 13y agoMath... the fun killer.
- mturmon 13y agoNah, just fun at a higher level.
- dmarlow 13y agoSo close to getting 2048. Cool stuff!
- jheriko 13y agovery cool. now... for a who can make the optimal AI competition... :P
- izzydata 13y agoI'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.
- janezhu 13y agoI 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
- Patrick_Devine 13y agoI 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.
- pedrocr 13y agoInteresting. 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.
- crusso 13y agoWhile 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.
- dllthomas 13y agoWhen 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.
- eck 13y agoWhat are the rules for new tile placement? Is it deterministic, random, or adversarial?
- shmageggy 13y agoRandom 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.
- theandrewbailey 13y agoWhen 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.
- gabriel34 13y agoThat 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.
- sritchie 13y agoBoom, 13,068 points and 2048! I'm feeling some pride in my AI. http://cl.ly/image/3G1a0e1T0Q2O http://cl.ly/image/3G1a0e1T0Q2O
- GFunc 13y agomine lost at 11,012 :| my AI has a lower IQ
- drx 13y agoMine won as well, on the first try. http://cl.ly/image/0H1o1P2Q0A0u/Image%202014-03-12%20at%2012.44.31%20AM.png http://cl.ly/image/0H1o1P2Q0A0u/Image%202014-03-12%20at%2012... I feel bad about my 1024 now, bested by a minmax.
- netcraft 13y agoso awesome, mine just barely beat yours with 13088 points on the first try: http://i.imgur.com/nxgFk57.png http://i.imgur.com/nxgFk57.png
- deletes 13y agoHow does it decide where the new tile will appear, or it just tries every possibility?
- shmageggy 13y agoTrying 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.
- cordite 13y agoIt gets so close! http://puu.sh/7rrD6.png 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.
- stuaxo 13y agoI found you can get to 256 by just being twiddle-fingers, sometimes even 512 ..
- lelandbatey 13y agoInteresting, mine beat the game: http://puu.sh/7rwqf.png http://puu.sh/7rwqf.png
- mturmon 13y agoDoes 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.
- feral 13y agoThe 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.
- cscheid 13y agoYup, the way to do it is via a small variant of http://en.wikipedia.org/wiki/Expectiminimax_tree 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').
- shmageggy 13y agoHeh. 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).
- mistercow 13y ago> 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?
- cscheid 13y agoHeh, I did something like this for the original Threes games via computer vision and screenshots :) http://www.youtube.com/watch?v=Sn2o2hb1bi0 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)
- danatkinson 13y agoBrilliant 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 http://i.imgur.com/F2ldDAS.png
- lettergram 13y agoI 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.
- notme_ 13y agosame here
- danielsamuels 13y agoIt won first time, impressive! http://i.imgur.com/epUtjyB.png http://i.imgur.com/epUtjyB.png
- LolWolf 13y agoYep, same here! http://i.imgur.com/4uNBOoj.jpg http://i.imgur.com/4uNBOoj.jpg
- seventytwo 13y agoI'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...
- pzs 13y agoIf 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.
- seventytwo 13y agoInitially, 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 :) )
- 3rd3 13y agoI’d be curious to see evolutionary or machine learning algorithms playing this.
- mattieshoes 13y agoI was curious too, was thinking about coding it. Anybody know the odds for a 2 or 4 appearing? Is it 50-50 or...?
- mkoryak 13y agoBack 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-AI 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 http://mkoryak.github.io/checkers/nn_checker_ai_demo.html (requires java, might also require a 7 year old computer)
- js2 13y agoIt's like watching War Games - http://www.youtube.com/watch?v=NHWjlCaIrQo http://www.youtube.com/watch?v=NHWjlCaIrQo
- deletes 13y agoA 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 ) )
- mightybyte 13y agoNice 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.
- LambdaAlmighty 13y agoLovely! Creating something like this was my initial reaction after seeing 2048, too :-) An ideal mini-project and good PR for an entry level AI dev. Or, indeed, for a post-exit AI dev...
- krastanov 13y agoI 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.
- rrival 13y agoStrange game. The only way to win is not to play.
- rafeed 13y agoI 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).
- tbenst 13y agoHere'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
- iandanforth 13y agoI was genuinely surprised when the AI lost.
- primitivesuave 13y agoYesterday 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.
- deleted 13y ago[deleted]
- shmageggy 13y agoI'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.
- shmageggy 13y ago=) Check out the eval function, and specifically the function smoothness() in grid.js. It implements the edge weighting you describe!
- primitivesuave 13y agoFantastic! 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.
- jjallen 13y agoPlease, please, please don't implement rankings...
- jjallen 13y agoDoes the AI guarantee winning?
- mediocregopher 13y agoMy 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.
- drydot 13y agoI find this game quite addictive, contratulations!
- rhapsodyv 13y agoAnyone implementing other IA technique? What's the link?
- buro9 13y agoI'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.
- Xcelerate 13y agoI got up to 9,000 with: left, down, right, down, (repeat)
- deleted 13y ago[deleted]
- buro9 13y agoNot 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.
- stevesearer 13y agoRight/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.
- buro9 13y ago15,456 Yup, this one works very well.
- stevesearer 13y agoI'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.
- itsmohit 13y agoCool
- itsmohit 13y agoCool, spent 15 minutes.
- seventytwo 13y agoBUG: 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.
- deleted 13y ago[deleted]
- shmageggy 13y agoAhh good catch. That got messed up during refactoring the original code. Thanks to the person who submitted the fix on github too.
- seventytwo 13y agoGreat... 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!
- ltray 13y agoI 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.
- deleted 13y ago[deleted]
- kemo 13y agoIt just won on 1st attempt here. Good job
- spyckie2 13y agoYou 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.
- deeteecee 13y agowhat 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 http://imgur.com/KuqAJTM&hrfol9i
- JanecekPetr 13y agoI 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?
- taternuts 13y agoI'm just counting down until someone builds this for the iPhone/Android for $.99
- homakov 13y agoif this is AI why it scores only 512 square as max?
- benjamincburns 13y agoAssuming 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...
- johnnymonster 13y agoSeeing the AI work makes me no longer want to play the game. Take to long to get to 2048!
- JetSpiegel 13y agoSadly, totally unrelated to the Hong Kong film...
- Houshalter 13y agoHow would I go about making an AI for this game? Mainly getting it to interface with the actual game input and output.
- pyed 13y agomy AI won the game with a score of 20388 pic: https://cloudup.com/chDTLSElXDN https://cloudup.com/chDTLSElXDN
- rhapsodyv 13y agoI always get at least 1024 now. I'm playing somehow like tetris...
- reignsly 13y agoGuys. 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/edit?usp=sharing https://drive.google.com/file/d/0Bz9_OO8kXRkfY0RWdzZ6cDA4RDQ...
- flaxin 13y agomemorizing watching it "play" by it's self i KNEW the AI would have been coming sooner or later [no this fast though], GREAT JOB!
- pharshal 13y agoNot sure why but every time I ran it on Firefox it failed, but it succeeded solving it on chrome always.
- NKCSS 13y agoLol, even the AI failed :) https://www.dropbox.com/s/bwdmj5rbgvackls/Screenshot%202014-03-12%2009.03.33.png https://www.dropbox.com/s/bwdmj5rbgvackls/Screenshot%202014-...
- frabcus 13y agoWhat algorithms might do better than this minimax? I've just read all the comments and there are no suggestions...
- sireat 13y agoThis 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).
- BenoitP 13y agoNice 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?
- helgefmi 13y agoI was coincidentally working on the same thing when I saw this yesterday. Pushed the code to https://github.com/helgefmi/c2048 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 :-).
- nkg 13y agoCool But why the autorun can't get a win?
- elwell 13y agoI 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 https://github.com/ov3y/2048-AI/blob/master/js/ai.js#L230
- satchipear 13y agoCool game!! Can't stop playing it. Finally achieved 2048 w/ score 21028 :)
- ericcumbee 13y agoI think it's pretty clear the Author of this game is a NSA agent trying to distract us.
- tUrG0n 13y agoYAY made it :3 http://grab.by/v9BA http://grab.by/v9BA ^_^
- popox 13y agoRandomness will not help you guys, look at what a horde of monkeys do on the game when left alone: http://popox.github.io/2048/ http://popox.github.io/2048/