BUG: 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 w…
Ahh good catch. That got messed up during refactoring the original code. Thanks to the person who submitted the fix on github too.
2048 AI
161–170 of 197 posts
Re: 2048 AI
#162Does the AI guarantee winning?
Re: 2048 AI
#163Tada! I got my 2048 tile :) So happy
https://drive.google.com/file/d/0Bz9_OO8kXRkfY0RWdzZ6cDA4RDQ...
Re: 2048 AI
#164i KNEW the AI would have been coming sooner or later [no this fast though], GREAT JOB!
Re: 2048 AI
#165Earlier quoted context omitted.
You describe a one-player game with stochastic outcomes. I'm talking about a deterministic two-player game with one player making random moves. They're not the same thing.
Actually they're exactly the same. As in, completely identical games under a very trivial mapping. Think about how you'd formulate each one in terms of payoff matrices...
Re: 2048 AI
#166I'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.
Re: 2048 AI
#167Earlier quoted context omitted.
Assuming 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 d…
Actually, to make a 2048 you need to make two 1024s. It's unlikely that you'll make two 1024s at the same time. Similarly for the lower tiles. As a sort of upper bound you expect the game to be over in about 1024 moves and it's likely to not be much less than that. I think a more realistic number is somewhere in the 500s
It's been too long since I've taken any hardcore discrete math for me to reliably reason about the bounds on the number of moves required to win. All I can do is make estimates based on simplifications.
How I arrived at my estimates for the order of magnitude of the minimum number of moves required to win:
At most, you can merge 4 tiles in one move. Assuming you were doing 4 tiles every move, and the game just didn't produce twos, it'd take just 128 moves. Order of magnitude: 10^2.
Assuming exactly one merge per move, and that the game only produces twos, it'd take 1024 moves. Order of magnitude: 10^3.
Re: 2048 AI
#168Re: 2048 AI
#169I'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.
I had some luck (winning the game, that is) by following this general heuristic: - 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/a…
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.
Re: 2048 AI
#170Earlier quoted context omitted.
> That doesn't make sense when talking about a random opponent, though. Sure it does. AB search means you play to maximise your own value and minimise the value for your opponent. If your opponent is using a random strategy they will likely make a poor move and that's extra advantage for you. Your argument here (and elsewhere in this thread) seems to be: if the opponent is random a stochastic strategy is best. This i…
Consider this game: You choose either Die or Coin. If you chose Die, I will roll a die. If the die is 1, I give you $0; otherwise, $1000. If you choose the coin, I'll give you $10 for heads, and $20 for tails. If you use a minimax policy, you will choose the coin, because the worst outcome of that choice is a $10 payoff. The 'best' 'worst' outcome is what you get with minimax, and that's $10. It is true that, as you…
There are almost no opportunities to make a 'great' move - since a great move with a significantly better effect on chance of winning than a move which doesn't change anything at all - is possible only if the move fixes a huge earlier mistake that you wouldn't have made in the first place.
For this particular game, advantages are temporary and disadvantages are near-permanent - so it makes sense to play very defensively, which minmax does. Imagine a game of Die or Coin, where if you choose coin, then you get $10 for heads, and $20 for tails; and for dice you throw a hundred-side die and get $25 for values 2-100 but if you roll 1, then you get shot and die.
[edit] what I'm saying is that assuming that [a] all payoffs are either effectively 0 or -infinity; and [b] most moves will (in the near expected future) be either 0 chance of the bad event or >0 chance of the bad event; then minmax would generate equal results to MC search - however, MC search would fail badly if you put overly optimistic payoffs, i.e., give too large rewards for 'good moves' and too little penalties for bad moves; and this is hard to estimate.
Minmax works if your payoff scale is completely wrong by orders of magnitude as long as the preference ordering is correct, MC search doesn't. If you know that position A is better than B but don't know if it is 1.1 times better or a million times better - then you can't implement a good MC search but can implemnt minmax.