Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

2048 AI

ov3y.github.io

Post reply on HN
Print view View original

111–120 of 197 posts

Re: 2048 AI

#111

Post by ronaldx »

feral wrote: post #38

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 som…

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.

Re: 2048 AI

#113

Post by [deleted] »

Xcelerate wrote: post #105
buro9 wrote: post #104

I'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 got up to 9,000 with: left, down, right, down, (repeat)

[deleted]

Re: 2048 AI

#114

Post by seventytwo »

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 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.

Re: 2048 AI

#115

Post by gradstudent »

feral wrote: post #48
ovolve wrote: post #43

Earlier quoted context omitted.

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…

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…

> 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 is simply not true. Stochastic strategies like MC search have an advantage over game-tree search when the game's branching factor limits you to considering just a few ply ahead (e.g. as in Go).

Re: 2048 AI

#116

Post by ltray »

I wrote a script last night that does a simple: up, right, down, left. Ran it for a few thousand games last night -- highest it got was over 10k, and consistently got around 2.5-3k.

Re: 2048 AI

#117

Post by tlarkworthy »

saurik wrote: post #106
feral wrote: post #82

Earlier quoted context omitted.

My impression is that you don't understand how these things work, so I'll start from the basics; apologies if wrong. First off, the chess counter-example was in response to something general ovolve said about 'all minimax algos'. More broadly, in practice the issue is that you only have computational resources to search a fraction of possible game states. So where do you direct your limited resources? Some candidate…

I am having a difficult time figuring out how to respond to this comment given that the assumption going into this conversation is that you are wrong and we are only interested in figuring out why you are wrong. For avoidance of doubt, we are assuming you are wrong because ovolve claimed to have implemented an algorithm matching your description, that implementation was available for your perusal (it is only commente…

I am with saurik.

The utility function is an approximation. So MCMC is aggregating information over an erroneous space, and min/max is also optimizing over an erroneous space too.

Which is the correct thing to do is conditioned on how the utility function behaves. In this scenario I think min/max plays maximumly conservative, which empirically seems to be the best thing to do.

If the utility is minimize free space on the board, the min/max will try to get to a free board but doesn't take risks so gets there in a suboptimal route. The MCMC will take the odd risky move as long as a large proportion of the futures lead to a even emptier board.

Clearly you don't want risky moves, because do enough of them and it ends in disaster (and its a long game). So the utility function should be exponentially weighted against going near risky situations. However, developing such a utility function which combines well in MCMC really requires understanding too much about the future game dynamics.

For MCM to work, the utility function really needs to capture how potentially bad a situation is, and I don;t think that is easy. Min/max is naturally pessimistic in stratergy, which is probably the correct thing to do.

Re: 2048 AI

#118

Post by msluyter »

buro9 wrote: post #104

I'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/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.

Re: 2048 AI

#119

Post by ljf »

seventytwo wrote: post #91
pzs wrote: post #73

Earlier quoted context omitted.

If you have only a single 2048 tile in the end, and arrived to that by only combining the minimum number of required tiles, then your score will be 10*2048. If you think backwards, you'll get 2048 for the last tile, before that you need to get twice 1024 for the previous two, and so on until the level of 4's, which is the first one at which you get scores. This assumes only twos appear on the board.

Initially, I had arrived at this conclusion as well, but I've seen solutions (both from other people posting and from running this script) that have gotten to 2048 with 14000 or less. I'm not entirely sure where the discrepancy is coming from, though... Obviously with a certain number of "4"s being generated each turn, the 10x2048 value will be reduced, but not to the degree we see. For example, I have logged a win w…

It seems there is a bug where only the higher or two cascades trigger at once, will be scored. So some of the points seem to being lost.

Re: 2048 AI

#120

Post by gohrt »

mistercow wrote: post #47
ovolve wrote: post #43

Earlier quoted context omitted.

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…

> 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?

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

Post reply on HN