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

41–50 of 197 posts

Re: 2048 AI

#41

Post by cscheid »

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…

Yup, the way to do it is via a small variant of 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').

Re: 2048 AI

#42

Post by stuaxo »

cordite wrote: post #33

It gets so close! http://puu.sh/7rrD6.png I find it frustrating to watch it hit (where I have not managed to get to) where you have one block 128, 256, 512, and a 1024. Moving around only makes it harder to join things together. I am rather convinced this game is more by luck than actual good-play.

I found you can get to 256 by just being twiddle-fingers, sometimes even 512 ..

Re: 2048 AI

#43

Post by ovolve »

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…

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

Re: 2048 AI

#44

Post by saraid216 »

izzydata wrote: post #23

I've been playing this for awhile now and I think I have found that the best method is to only use 3 directions. This forces your highest number into a corner and only spawns 2's and 4's in the opposite corner. You build up numbers that cascade down to the corner. It almost never gets stuck, but if you do I guess you'd have to push the 4th direction you haven't been using.

I've been doing that, too, but my impression is that it's a human cognitive convenience, rather than something algorithmically stronger.

Re: 2048 AI

#46

Post by lettergram »

I ran it twice and it failed to achieve 2048, are other people having similar issues? Either way, nice attempt it works pretty darn well for 1 night of work.

Re: 2048 AI

#47

Post by mistercow »

ovolve wrote: post #43
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…

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?

Re: 2048 AI

#48

Post by feral »

ovolve wrote: post #43
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…

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

Re: 2048 AI

#50

Post by notme_ »

lettergram wrote: post #46

I ran it twice and it failed to achieve 2048, are other people having similar issues? Either way, nice attempt it works pretty darn well for 1 night of work.

same here
Post reply on HN