8 ms·

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 oppo

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.
  - khafra 13y ago
    It sounds like you're thinking he suggested just greedily taking the best possible move. But that's not what he suggested; he suggested evaluating the actual distribution of the opponent's moves and making the move with the highest expected value.
    - saurik 13y ago
      No, I entirely understood that. I am quite happily willing to believe that I misunderstand the ramifications of that algorithm (I spent a lot of time talking about game theory in college, but it was not my field, and that was a long time ago), but that is the algorithm I inferred. (I would respond more, but you didn't leave me with any specific complaints to respond to, so all I can really say is "no".)
moultano 13y ago
I suspect that the best objective function would be "maximize the time until I lose" which is closer to avoiding the worst case scenario than it is to performing best in the average case scenario.
sillysaurus3 13y ago
A friend has a question for you: "How many moves does it think ahead? Or does it just think in the 'here-and-now' (only 1 move ahead)?"
- bhrgunatha 13y ago
  Someone else posted that it uses the minimax algorithm with alpha beta pruning and iterative deepening. Minimax[1] looks "several" moves ahead to see what may happen. It assumes you always play your best possible move (to MAXimise your score) and your opponent always plays their best possible move (to maximise their score and MINimises yours). Because this creates a huge amount of possibilities, their is a method to reduce the number of moves considered called alpha beta pruning[2]. Some future moves can never lead to a better score for you and so are discarded or ignored. Both approaches need you to look as many moves ahead as you can - each extra move you consider multiplies the number of possibilities exponentially, so there is another method called iterative deepening[3] which uses the algorithm to look 1 move ahead to find the best move and records that move. Then it repeats looking at 2 moves ahead and if it finds a better score than with 1 move it keeps that instead. Then 3 moves, then 4. The program will continue looking at more and more moves ahead until it reaches a time limit (or a size limit.) [1] https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with... [2] https://en.wikipedia.org/wiki/Alpha-beta_pruning https://en.wikipedia.org/wiki/Alpha-beta_pruning [3] https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs...
kaoD 13y ago
I was also working on a 2048 AI, but you beat me to it! Nice job. 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.

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.
- khafra 13y ago
  It sounds like you're thinking he suggested just greedily taking the best possible move. But that's not what he suggested; he suggested evaluating the actual distribution of the opponent's moves and making the move with the highest expected value.
  - saurik 13y ago
    No, I entirely understood that. I am quite happily willing to believe that I misunderstand the ramifications of that algorithm (I spent a lot of time talking about game theory in college, but it was not my field, and that was a long time ago), but that is the algorithm I inferred. (I would respond more, but you didn't leave me with any specific complaints to respond to, so all I can really say is "no".)

moultano 13y ago

I suspect that the best objective function would be "maximize the time until I lose" which is closer to avoiding the worst case scenario than it is to performing best in the average case scenario.

sillysaurus3 13y ago

A friend has a question for you: "How many moves does it think ahead? Or does it just think in the 'here-and-now' (only 1 move ahead)?"

bhrgunatha 13y ago
Someone else posted that it uses the minimax algorithm with alpha beta pruning and iterative deepening. Minimax[1] looks "several" moves ahead to see what may happen. It assumes you always play your best possible move (to MAXimise your score) and your opponent always plays their best possible move (to maximise their score and MINimises yours). Because this creates a huge amount of possibilities, their is a method to reduce the number of moves considered called alpha beta pruning[2]. Some future moves can never lead to a better score for you and so are discarded or ignored. Both approaches need you to look as many moves ahead as you can - each extra move you consider multiplies the number of possibilities exponentially, so there is another method called iterative deepening[3] which uses the algorithm to look 1 move ahead to find the best move and records that move. Then it repeats looking at 2 moves ahead and if it finds a better score than with 1 move it keeps that instead. Then 3 moves, then 4. The program will continue looking at more and more moves ahead until it reaches a time limit (or a size limit.) [1] https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with... [2] https://en.wikipedia.org/wiki/Alpha-beta_pruning https://en.wikipedia.org/wiki/Alpha-beta_pruning [3] https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs...

kaoD 13y ago

I was also working on a 2048 AI, but you beat me to it! Nice job. 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.