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.
>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.
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.
Isn't this guaranteed by the no free lunch theorem?
So minimax is probably right in many cases and close enough to being right in most cases.
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.
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
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.
That way your large values tend to be clump together and you don't get a small value buried which burns up a square.
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).
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.
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.
edit: I used 'look' 3 times in the last 20 words, what's wrong with me
I have finished solitaire a lot of times.
EDIT: This AI is a better player than me.
1. Up
2. Right
3. Down
4. Left
5. Go to 1.
That loop scores better than my trying.
- 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.
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.
left, down, right, down, (repeat)
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.
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...
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.
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 :) )
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.
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 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.
http://cl.ly/image/0H1o1P2Q0A0u/Image%202014-03-12%20at%2012...
I feel bad about my 1024 now, bested by a minmax.
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!
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.
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.
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
Or for fun, this is 128^1000:
16216967556622020264666650854783770951911124303637432562359820841515270231627023529870802378794460004651996019099530984538652557892546513204107022110253564658647431585227076599373340842842722420012281878260072931082617043194484266392077784125099996860169436006660011209817579296678781962552377006552947572566780558092938446272186402161088626008160971328747492043520874011018626908423275017246052311293955235059054544214554772509509096507889478094683592939574112569473438619121529684847434440674120417402088754037186942170155022073539838122429925874353753616104159343594557666561701790904172597025336526662682021808493892812699709528570890696375575414344876088248369941993802415197514510125127043829087280919538476302857811854024099958895964192277601255360491156240349994714416090573084242931396211995367937301294479560024833357073899839202991032234659803895306904298017400980173252106913079712420169633972302183530075897845195258485537108858195631737000743805167411189134617501484521767984296782842287373127422122022517597535994839257029877907706355334790244935435386660512591079567291431216297788784818552292819654176600980398997991681404749384215743515802603811510682864067897304838292203460427757655073776567547507027144662263487685709621261074762705203049488907208978593689047063428548531668665657327174660658185609066484950801276175461457216176955575199211750751406777510449672859082255854777144724233490076402632176089211355256124119453870268029904400183858505767193696897593661213568888386800238409325673807775018914703049621509969838539752071549396339237202875920415172949370790977853625108320092839604807237954887069546621688044652112493076290091990717742355039135117441532973747930089955830518884135334798464113680004999403737245600354288112326328218661131064550772899229969469156018580839820741704606832124388152026099584696588161375826382921029547343888832163627122302921229795384868355483535710603407789177417026363656202726955437517780741313455101810009468809407811220573803353711246329589162370895804762245950918253016369092362406714116443316561598280583720783439888562390892028440902553829376
Colossus by Dennis Feltham Jones
( don't read the wikipedia entry as it contains spoilers ( whole plot ) )
Second time around was pretty close http://i.imgur.com/psdSwjM.png
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 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)
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
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.
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?
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.
AI.prototype.translate = function(move) {
return {
0: 'up',
1: 'right',
2: 'down',
3: 'left'
}[move];
}
It was a little upsetting when I had actually been putting thought into my play and he was doing better.
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 :-).
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).
Tada! I got my 2048 tile :) So happy
https://drive.google.com/file/d/0Bz9_OO8kXRkfY0RWdzZ6cDA4RDQ...
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?
now... for a who can make the optimal AI competition... :P
i KNEW the AI would have been coming sooner or later [no this fast though], GREAT JOB!
