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

181–190 of 197 posts

Re: 2048 AI

#181

Post by khafra »

Anderkent wrote: post #133
feral wrote: post #88

Earlier quoted context omitted.

It doesn't have a 100% win rate as it stands. Mini-max isn't even 'playing safe'. Consider the following choice of moves, each leading to one of 5 random tile inserts: Move A, which leads to 5 possible moves with the following game state goodnesses: ['Loss','Win','Win','Win','Win'] Move B, resulting in: ['99%CertainLoss','99%CertainLoss','99%CertainLoss','99%CertainLoss','99%CertainLoss'] Minimax is never going to ch…

Fair enough; I only ran it a couple times and it got to 2048 so I assumed it's a guaranteed win.

Min-max optimizes your chance of winning under the assumption of a rational adversary. That chance will be lower than "certain victory," especially in un-solved, symmetric games, because a rational adversary will also be playing min-max. The guarantee min-max provides is that it will do even better against a non-rational adversary than it does against a rational adversary; not that it will do better than any other algorithm against non-rational adversaries--which is the way I think it often gets parsed.

Also, we should note that the "value" in "expected value" doesn't have to mean "score." It could be the logarithm of your score, or your chance of winning against a rational adversary, or even the enjoyability of the game to spectators (if you have a precise metric for that).

Re: 2048 AI

#182

Post by helgefmi »

I was coincidentally working on the same thing when I saw this yesterday. Pushed the code to https://github.com/helgefmi/c2048 if it's of anyones interest.

It's just a wicked fast board implementation with a simple depth first search, as of now. But the idea of "making up" an opponent to make it possible to do alpha beta pruning is a cool idea. I might try to implementet it myself.

I regularly get scores above 50k with AI_DEPTH=5-6 and NUM_TRIES=20-30. My record so far is a score of 220k :-).

Re: 2048 AI

#183

Post by janezhu »

izzydata wrote: post #32
janezhu wrote: post #31

Earlier quoted context omitted.

I got up to 16220 that way-- the thing you have to look out for though is as you build the cascading layers, when you get the row three, not to block yourself in (having all 3 rows full so that the only direction you can go, is the one you are avoiding). Try to keep your cascading layers down to 2, and keep about 2 steps ahead when you get to the 3rd layer. Many people have suggested keeping your highest number in th…

Thanks for the suggestion. I can't stop until I beat this eventually.

Finally made it-- cascade gif: https://vine.co/v/Mbb07Wh0UPM/

Re: 2048 AI

#185

Post by stevesearer »

buro9 wrote: post #173
stevesearer wrote: post #141

Earlier quoted context omitted.

Right/Down/right/Down with an Up/Right/Down thrown in when stuck has worked well for me. My first 1024 block came that way. When I began playing I was moving around the board in an unorganized fashion, but am now finding that moving the larger numbers to one corner (bottom-right for me) is the best method. By having your block consolidation take place in one particular area, the odds that you'll have matching large n…

15,456 Yup, this one works very well.

I've tried a few games where I do those exact moves with no human judgement and the score ends up quite a bit lower than when I 'generally' follow those moves and consolidate using my best judgement.

Another interesting test was to always play a clockwise or counter-clockwise pattern. The consolidation happens in the middle of the board. This method seemed to result in higher scores than the right/down/right/down pattern.

Re: 2048 AI

#186

Post by gabriel34 »

theandrewbailey wrote: post #75
ovolve wrote: post #30

Earlier quoted context omitted.

Random location (uniform). 90% chance of a 2, 10% chance of a 4. This actually made it hard to model the computer move in the search.

When playing, it seemed like a 50% chance the new tile would be placed in exactly the spot or two that I didn't want it, even if there were 8+ open spaces.

That is a sampling bias caused by confirmation bias. Extreme cases such as the one pointed out tend to reinforce the hypothesis because they are more traumatic and, therefore, better remembered then the avalanche of cases where the higher probability positive outcome happens.

Re: 2048 AI

#188

Post by feral »

gradstudent wrote: post #165
bermanoid wrote: post #149

Earlier quoted context omitted.

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

You're right. Still, there is something missing here: the game has no win condition. It is true that the best play seems to be to go for dice but suppose that rolling a 1 means I lose the game and forefit all my winnings. Why would I ever play that?

Why would you ever play dice, if rolling 1 meant losing everything?

Lots of situations. If you had $0, obviously.

Probably if you had less than $833.33 (the expected value of the dice in my game), slightly more subtly.

Maybe even other scenarios, depending on how long you wanted to play for, if there was a time cost to playing, if you could play for as long as you wanted, what your utility/risk preferences were, etc.

The point is that there are appropriate tools for reasoning about such games correctly - utility, decision theory, etc. - and they beat minimax.

Re: 2048 AI

#189

Post by gradstudent »

feral wrote: post #188
gradstudent wrote: post #165

Earlier quoted context omitted.

You're right. Still, there is something missing here: the game has no win condition. It is true that the best play seems to be to go for dice but suppose that rolling a 1 means I lose the game and forefit all my winnings. Why would I ever play that?

Why would you ever play dice, if rolling 1 meant losing everything? Lots of situations. If you had $0, obviously. Probably if you had less than $833.33 (the expected value of the dice in my game), slightly more subtly. Maybe even other scenarios, depending on how long you wanted to play for, if there was a time cost to playing, if you could play for as long as you wanted, what your utility/risk preferences were, etc.…

You're changing the rules and shifting the goalposts. Look, it's simple: if the objective is to win then you want to avoid giving your opponent any chance to beat you. That means you never choose dice.

> The point is that there are appropriate tools for reasoning about such games correctly - utility, decision theory, etc. - and they beat minimax.

Perhaps this is true but you have not convinced me that this is the case here. Moreover, the OP claims to have empirical results showing that AB-pruning does better than MC-search for the game of 2048.

Post reply on HN