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

141–150 of 197 posts

Re: 2048 AI

#141

Post by stevesearer »

buro9 wrote: post #135
Xcelerate wrote: post #105

Earlier quoted context omitted.

I got up to 9,000 with: left, down, right, down, (repeat)

Not bad. My new simple algo is: 1. Down until you cannot go down 2. Left 3. Down until you cannot go down 4. Right 5. Go to 1.

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 numbers goes up dramatically.

Re: 2048 AI

#142

Post by mturmon »

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.

Does anyone know of a quantitative way to measure the influence of random draws vs. skill on the final score? I would have guessed that strategy would be effective on this game, but that could be wrong.

Re: 2048 AI

#143

Post by gradstudent »

feral wrote: post #128
gradstudent wrote: post #115

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

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.

Re: 2048 AI

#144

Post by bhrgunatha »

sillysaurus3 wrote: post #123
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…

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

Someone else posted that it uses the minimax algorithm with alpha beta pruning and iterative deepening.

Minimax[1] looks "several" moves ahead to see what may happen. It assumes you always play your best possible move (to MAXimise your score) and your opponent always plays their best possible move (to maximise their score and MINimises yours). Because this creates a huge amount of possibilities, their is a method to reduce the number of moves considered called alpha beta pruning[2]. Some future moves can never lead to a better score for you and so are discarded or ignored.

Both approaches need you to look as many moves ahead as you can - each extra move you consider multiplies the number of possibilities exponentially, so there is another method called iterative deepening[3] which uses the algorithm to look 1 move ahead to find the best move and records that move. Then it repeats looking at 2 moves ahead and if it finds a better score than with 1 move it keeps that instead. Then 3 moves, then 4. The program will continue looking at more and more moves ahead until it reaches a time limit (or a size limit.)

[1] https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with...

[2] https://en.wikipedia.org/wiki/Alpha-beta_pruning

[3] https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs...

Re: 2048 AI

#145

Post by tlarkworthy »

feral wrote: post #121
tlarkworthy wrote: post #117

Earlier quoted context omitted.

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…

Actually I thought about it more. There are a few approaches

so you only need to decide 1 of 4 moves at the beginning

1. min max to a finite horizon using a heuristic utility function (as implemented)

2. Dynamic program/MCMC to a finite horizon and use the heuristic. Good at modelling the opponent behaviour, but could lead to bad results with a bad heuristic. (commented out approach)

3. Sample till the game ends (infinite horizon), pick the first move that lead to the game that went the longest (or won). This avoids developing an ad hoc heuristic.

So now I vote for 3. :p

Re: 2048 AI

#149

Post by bermanoid »

gradstudent wrote: post #143
feral wrote: post #128

Earlier quoted context omitted.

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…

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...
Post reply on HN