13 ms·

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

by feral 13y ago

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.

cscheid 13y ago
Yup, 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 ago
Heh. 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?
  - dimfox 13y ago
    The new tiles only appears on the opposite of your move direction. Your code does not seem to care about that. Maybe it will perform better if this is considered?
  - gohrt 13y ago
    No. No Free Lunch Theorem means that there is no algorithm (that is programmed with no awareness of any specific search space) can be successful in ALL search spaces (problems). But 2048 is a highly-structured search space. Even with random opponent, the opponent's choices are constrained by the game's rule structure. http://en.wikipedia.org/wiki/No_free_lunch_theorem http://en.wikipedia.org/wiki/No_free_lunch_theorem
- feral 13y ago
  Its interesting that your approach performed worse; I wonder if it could be modified to do better? Interesting. >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.
  - saurik 13y ago
    When playing against a random opponent, sometimes it will "accidentally" make the best possible move. In chess, this might be extremely unlikely, as there are so many possible moves: the probability that, of all the pieces on the board, with all of the positions it could have made, that it would stumble upon a move that devastates your position--especially considering that often multiple correct moves must be performed in specific sequence to take advantage of what "should be" a winning position--is vanishingly small. Further: the potential for gain (trivial mate against a stupid opponent in a handful of moves) is great. If you are thereby playing for "fastest win over time", taking advantage of random's suboptimality seems sane. In 2048, the bottleneck on your score seems best approximated by how long you survive: pulling stunts won't get you to 2048 all that faster as you need to have worked through enough tiles to arrive at that point: I'd imagine the difference would be at best a tiny fraction of the "required" moves. Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal. As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess. In summary: I just don't think comparing this game to chess is leading to useful intuitions.
thedufer 13y ago
Its not always winning, but it does sometimes win. Is this game even winnable with every possible prng seed? I wouldn't be surprised if there were guaranteed-loss states.
tyilo 13y ago
It did win for me on the first try: http://i.imgur.com/uMB2J7f.png http://i.imgur.com/uMB2J7f.png
- tambourine_man 13y ago
  It won for me too, kind of mesmerizing to watch it play it all by itself. Congratulations to the author.
- jonah 13y ago
  Won for me on the second run: http://i.imgur.com/zc0uNLz.png http://i.imgur.com/zc0uNLz.png
ronaldx 13y ago
If new tiles are inserted randomly, you have to defend adequately against the worst case. Avoid-death always has a very good expected value, relatively. So minimax is probably right in many cases and close enough to being right in most cases.
sztupy 13y ago
To check how the game would play out if the opponent (the computer who in the original game places the tiles randomly) would acutally play instead of randomly dropping the tiles I made a fork of the original game: http://sztupy.github.io/2048-Hard/ http://sztupy.github.io/2048-Hard/ 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.

by feral 13y ago

cscheid 13y ago

Yup, 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 ago

Heh. 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?
- dimfox 13y ago
  The new tiles only appears on the opposite of your move direction. Your code does not seem to care about that. Maybe it will perform better if this is considered?
- gohrt 13y ago
  No. No Free Lunch Theorem means that there is no algorithm (that is programmed with no awareness of any specific search space) can be successful in ALL search spaces (problems). But 2048 is a highly-structured search space. Even with random opponent, the opponent's choices are constrained by the game's rule structure. http://en.wikipedia.org/wiki/No_free_lunch_theorem http://en.wikipedia.org/wiki/No_free_lunch_theorem
feral 13y ago
Its interesting that your approach performed worse; I wonder if it could be modified to do better? Interesting. >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.
- saurik 13y ago
  When playing against a random opponent, sometimes it will "accidentally" make the best possible move. In chess, this might be extremely unlikely, as there are so many possible moves: the probability that, of all the pieces on the board, with all of the positions it could have made, that it would stumble upon a move that devastates your position--especially considering that often multiple correct moves must be performed in specific sequence to take advantage of what "should be" a winning position--is vanishingly small. Further: the potential for gain (trivial mate against a stupid opponent in a handful of moves) is great. If you are thereby playing for "fastest win over time", taking advantage of random's suboptimality seems sane. In 2048, the bottleneck on your score seems best approximated by how long you survive: pulling stunts won't get you to 2048 all that faster as you need to have worked through enough tiles to arrive at that point: I'd imagine the difference would be at best a tiny fraction of the "required" moves. Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal. As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess. In summary: I just don't think comparing this game to chess is leading to useful intuitions.

thedufer 13y ago

Its not always winning, but it does sometimes win. Is this game even winnable with every possible prng seed? I wouldn't be surprised if there were guaranteed-loss states.

tyilo 13y ago

It did win for me on the first try: http://i.imgur.com/uMB2J7f.png http://i.imgur.com/uMB2J7f.png

tambourine_man 13y ago
It won for me too, kind of mesmerizing to watch it play it all by itself. Congratulations to the author.
jonah 13y ago
Won for me on the second run: http://i.imgur.com/zc0uNLz.png http://i.imgur.com/zc0uNLz.png

ronaldx 13y ago

If new tiles are inserted randomly, you have to defend adequately against the worst case. Avoid-death always has a very good expected value, relatively. So minimax is probably right in many cases and close enough to being right in most cases.

sztupy 13y ago

To check how the game would play out if the opponent (the computer who in the original game places the tiles randomly) would acutally play instead of randomly dropping the tiles I made a fork of the original game: http://sztupy.github.io/2048-Hard/ http://sztupy.github.io/2048-Hard/ 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.