3 ms·

> at least 938.8 moves on average > at least ... on average wat > The main simplification that enabled that calculation was to ignore the structure of the bo

> at least 938.8 moves on average > at least ... on average wat > The main simplification that enabled that calculation was to ignore the structure of the board Oh OK so he doesn't mean "minimum", he means "assuming perfect play under his simplified model". Which is neither the minimum, nor the average assuming perfect play under an exact model. So it's unclear that his previous figure of 938.8 is particularly meaningful since it assumes an inexact model. Actually, assuming a perfect AI exists (i.e. the constraints imposed by the structure of the board is not a hindrance to a sufficiently-advanced AI) then the average number of moves needed is simply 2048 / mean( (2,0.9), (4,0.1) ) = 2048 / 2.2 ~= 930.91 which is very close to the previously-quoted figure and has the advantage that it - is independent of any potentially inaccurate model of the game dynamics - takes like 1s to calculate, and you could do it in your head

deleted 9y ago
[deleted]
jdleesmiller 9y ago
That's also a good approach, and indeed much simpler! What I think it doesn't take into account is that you need to have more than just the 2048 tile on the board in order to reach the 2048 tile, because it takes a few moves to merge the tiles, and during those moves the game continues to add new 2 and 4 tiles. That explains why it's a few moves lower than the estimate from the Markov chain analysis. I take your point that the 'at least 938.8 moves on average' phrasing could be clearer, but it's the best way I've found to express the result in a small number of words. More precisely, I'm claiming in the first post that: 1. The number of moves that it takes to win is a random variable, because it depends on the sequence of 2s and 4s, so we can talk about the 'expected number of moves to win' (i.e. an average). 2. The 'bag' game without the structural constraints imposed by the board always takes fewer moves to win than the game with those constraints. 3. The expected number of moves to win for the bag game is 938.8, so using (1) and (2) this yields a lower bound for the expected number of moves to win the full game. (There are no decisions for the player to make in the bag game, so there isn't really a notion of 'perfect play' for the bag game. It's more like a 'bag process'.) 4. By playing lots of games of 2048, I found that I could get pretty close to this lower bound on average, at least when I played well (no major blunders). I hope that's clearer!
- infinity0 9y ago
  My point actually was that your (2) is not correct. The game gives you +2.2 (av) every single turn regardless of what move you make, so improving the AI can't possibly increase the speed at which you get these points. Improving the AI only reduces your chance of dying. However, good point with "it takes a few moves to merge the tiles". Coupled with the fact that the game starts you off with 2 tiles (4 points), my "quick" method gets closer to your value: 2048 (target) - 4 (starting) = 2044 2044 / 2.2 = 929.090909090909 + 10 moves to merge ~= 939.1 on average to get a 2048 tile on the board.

deleted 9y ago

[deleted]

jdleesmiller 9y ago

That's also a good approach, and indeed much simpler! What I think it doesn't take into account is that you need to have more than just the 2048 tile on the board in order to reach the 2048 tile, because it takes a few moves to merge the tiles, and during those moves the game continues to add new 2 and 4 tiles. That explains why it's a few moves lower than the estimate from the Markov chain analysis. I take your point that the 'at least 938.8 moves on average' phrasing could be clearer, but it's the best way I've found to express the result in a small number of words. More precisely, I'm claiming in the first post that: 1. The number of moves that it takes to win is a random variable, because it depends on the sequence of 2s and 4s, so we can talk about the 'expected number of moves to win' (i.e. an average). 2. The 'bag' game without the structural constraints imposed by the board always takes fewer moves to win than the game with those constraints. 3. The expected number of moves to win for the bag game is 938.8, so using (1) and (2) this yields a lower bound for the expected number of moves to win the full game. (There are no decisions for the player to make in the bag game, so there isn't really a notion of 'perfect play' for the bag game. It's more like a 'bag process'.) 4. By playing lots of games of 2048, I found that I could get pretty close to this lower bound on average, at least when I played well (no major blunders). I hope that's clearer!

infinity0 9y ago
My point actually was that your (2) is not correct. The game gives you +2.2 (av) every single turn regardless of what move you make, so improving the AI can't possibly increase the speed at which you get these points. Improving the AI only reduces your chance of dying. However, good point with "it takes a few moves to merge the tiles". Coupled with the fact that the game starts you off with 2 tiles (4 points), my "quick" method gets closer to your value: 2048 (target) - 4 (starting) = 2044 2044 / 2.2 = 929.090909090909 + 10 moves to merge ~= 939.1 on average to get a 2048 tile on the board.