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

121–130 of 197 posts

Re: 2048 AI

#121

Post by feral »

tlarkworthy wrote: post #117
saurik wrote: post #106

Earlier quoted context omitted.

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…

I agree that all approaches are approximations, and which would actually perform best in this game is an empirical question. It'd take some work to really explore and tune either minimax or MC approach, so I wouldn't throw either out due to one failed attempt.

I accept the argument that "minimax is conservative, and conservative is good" might be correct. But I don't think its likely, and, without the time to code my own solution, all I can do is give arguments to that end.

I gave one intuitive argument here: https://news.ycombinator.com/item?id=7381382

Another argument is to remember that minimax, and AB-pruning, is a really strong way of reducing your search space - because of how unfavourable adversary moves are propagated up the tree - which could result in drastic pruning if the minimax assumption is wrong.

One 'bad' state, 6 or 8 ply deep through your branching factor ~10 tree, can result in you pruning entire lines of enquiry using minimax AB; surely that can't be right if the chance of the bad state happening is tiny, and especially if an alternative is chosen which isn't much better.

So I still think that if you want to tune the search algorithm to be risk adverse, then, yes, do so; but minimax is a drastic way to achieve that. But yes, how big of an effect that decision has in practice depends on complicated things, such as correlations in the search tree. (i.e. If you find a bad state in a section of the game tree, maybe there are likely to be other bad states nearby, so its not such a big deal to prune that whole section using minimax).

Re: 2048 AI

#123

Post by sillysaurus3 »

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…

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

Re: 2048 AI

#124

Post by jsmeaton »

Crito wrote: post #78
terabytest wrote: post #10

Hahah, I knew this was coming sooner or later. Thanks! Great job! EDIT: This AI is a better player than me.

I don't know if you've experienced it yourself or have heard other reports of it, but after playing your game for a few hours last night I've been experiencing a 2048-flavored "tetris effect" all day today. My brain keeps on trying to identify "like things" to collapse together; pretty wild.

I played for about 2 hours right before bed and couldn't get to sleep for hours. I was wired. Don't know if this is related to what you're suggesting or not, but I won't be playing this game again at night time.

Re: 2048 AI

#125

Post by terabytest »

Crito wrote: post #78
terabytest wrote: post #10

Hahah, I knew this was coming sooner or later. Thanks! Great job! EDIT: This AI is a better player than me.

I don't know if you've experienced it yourself or have heard other reports of it, but after playing your game for a few hours last night I've been experiencing a 2048-flavored "tetris effect" all day today. My brain keeps on trying to identify "like things" to collapse together; pretty wild.

I had this a lot while developing 2048. At some point, I'd feel like I could collapse letters while typing, and that's when I decided I should probably stop playing so often.

Re: 2048 AI

#127

Post by shibby »

vlad00 wrote: post #90
kaybe wrote: post #85

Earlier quoted context omitted.

Me too, I have this weird overlay of the game in my vision. It took a lot more of tetris to reach that effect.

All the fonts seem smaller, not sure if only one.

I'm getting that as well.

I've won once.

The 'technique' I used was to keep the numbers on the left hand edge.

Then using left, down and up built up the rest of the tiles with the movement to left hand edge being the preferred move when it is possible.

I've not managed to repeat the victory yet though.

Re: 2048 AI

#128

Post by feral »

gradstudent wrote: post #115
feral wrote: post #48

Earlier quoted context omitted.

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 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 say, if you instead get $20, you will be pleasantly surprised. "extra advantage for you", as you put it.

But it should be crystal clear that minimax is nonetheless the wrong decision policy here. If you use a minimax policy when the outcomes are random, you will generally be doing it wrong.

There are exceptions (e.g. you are starving and need $10 or else you'll die; or you are in my casino, and you think I'm using loaded dice, in which case the outcomes aren't random and you have an adversary; etc.) but in general, minimax is just wrong there.

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

No - my argument is that if an opponent is random a minimax strategy is generally not best.

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

Yes, that's also true.

Re: 2048 AI

#129

Post by spyckie2 »

You can add a simple heuristic to the scoring to increase the win rate by a lot - weighted corners.

Add the logged value of the numbers on the corners to the score and the higher numbers will tend to 'stick' to them. This also serves as a mechanism to guarantee that the new numbers appear away from the large numbers, which tend to block them from combining.

I also turned down the compute time to 20ms and it still runs well.

Re: 2048 AI

#130

Post by [deleted] »

seventytwo wrote: post #114

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…

[deleted]
Post reply on HN