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

2048 Solver

github.com

Post reply on HN
Print view View original

11–20 of 41 posts

Re: 2048 Solver

#11

Post by felixN »

jfasi wrote: post #7

I could be wrong here, but from my reading of the source this doesn't look like an A* search algorithm. For starters, the search space is nondeterministic, and since you can only explore in one direction, you're not really performing a search space exploration as much as choosing a direction and going with it. Secondly, the implementation doesn't perform the combination of current state score and proposed state score…

Yes, true. I had the A* Algorithm in mind when I have implemented it, but the outcome really differs from that.

Re: 2048 Solver

#12

Post by edanm »

wingerlang wrote: post #10
edanm wrote: post #5

Earlier quoted context omitted.

From the op: "But level=2 is enough to win 100% of all games!" So I think it can win all games?

That does not answer how many moves it takes to get to 2048 though.

Oh. Was that what was meant by "rounds"? I assumed how many times does the game have to be played.

Re: 2048 Solver

#13

Post by baking »

jlaswell wrote: post #9

Thanks for sharing this. I may have missed this answer between all of the threads related to 2048, but has anyone found if there is a limit for the 4x4 tile size?

If he got 32768, that would seem to be the highest unless you could get the following 16 squares which would collapse to 65536:

2, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768

You could theoretically beat that if you happened to get a 4 just when you needed it (starting with 4, 4, 8, 16, etc.)

Re: 2048 Solver

#15

Post by svalorzen »

toppy wrote: post #4

Any remarks on average number of rounds to get to 2048?

That does not depend much on the solution, mostly it depends at the speed at which numbers are generated (which you can approximate constant to 20.8 + 40.2).

Re: 2048 Solver

#16

Post by toppy »

felixN wrote: post #14
toppy wrote: post #4

Any remarks on average number of rounds to get to 2048?

I run 100 games - the algorithm needs 949 rounds in average to reach the 2048 tile

Thanks. Good to know The Game is beatable in 10-15 minutes ;)

Re: 2048 Solver

#17

Post by Stephen_R »

Hello everyone, I am currently taking a course in Artificial Intelligence and have been planning to implement the A* algorithm towards 2048. But seeing here that people believe that this isnt a "true" A* implementation, would the hackerNews community be interested in an actual working Javascript implementation of multiple AI methods? (i.e. having a dropdown selector for the method to use and implementation via a button)

Re: 2048 Solver

#18

Post by zwegner »

jlaswell wrote: post #9

Thanks for sharing this. I may have missed this answer between all of the threads related to 2048, but has anyone found if there is a limit for the 4x4 tile size?

The highest tile you can get is 2^17, 131072. Each doubling of the tile size requires another extra space, as you have to construct two of the previous tile, and once you construct one, it has to go somewhere. In the end, the final board will have a string of every power of two from 2^16 to 4, and then another 4 in the last empty space. The 4s then combine, then the 8s, and so on, rippling up like binary addition until you get 2^17. Hope that makes sense, I thought about this for a while but it's not the easiest concept to put to words.

Re: 2048 Solver

#19

Post by cottonseed »

jfasi wrote: post #7

I could be wrong here, but from my reading of the source this doesn't look like an A* search algorithm. For starters, the search space is nondeterministic, and since you can only explore in one direction, you're not really performing a search space exploration as much as choosing a direction and going with it. Secondly, the implementation doesn't perform the combination of current state score and proposed state score…

My first reaction was that Monte Carlo would be the way to go.
Post reply on HN