News for hackers. Stuff that matters.
Re:2048 Solver by jfasi on Wednesday March 26, 2014 @11:07AM (#7473880)
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 that lies at the heart of the A* algorithm. Instead it takes the current state for granted (which, again, it must given the inability to backtrack) and chooses the available move with the largest score.

Thirdly, and I'm reaching a little here, I can't find any place where any heuristic is used to optimize search performance by pruning the search tree. The search space is brute forced on each iteration, and the entire tree is scored.

At the expense of seeming pedantic I suggest this is a greedy play algorithm rather than A*. You can be even more precise and call it a single-ply minimax.

Now that that's out of the way, I should temper my criticism with the fact that this implementation works. It's not algorithmically complicated because it doesn't have to be. It doesn't use any of the typical performance tricks because it doesn't need to. What it lacks in sophistication it makes up in "good enough."

Re:2048 Solver by felixN on Wednesday March 26, 2014 @11:20AM (#7473956)
Yes, true. I had the A* Algorithm in mind when I have implemented it, but the outcome really differs from that.
Re:2048 Solver by cottonseed on Wednesday March 26, 2014 @11:55AM (#7474239)
My first reaction was that Monte Carlo would be the way to go.
Re:2048 Solver by sltkr on Wednesday March 26, 2014 @12:23PM (#7474474)
Seems like a great application for Monte Carlo tree search.
Re:2048 Solver by naruil on Wednesday March 26, 2014 @02:02PM (#7475128)
Check my AI for 2048 https://news.ycombinator.com/item?id=7474909

Only reach 8192, but with the game implemented in the right way :)

Re:2048 Solver by segmondy on Wednesday March 26, 2014 @01:34PM (#7474936)
Show us your better solution! Thanks!
Re:2048 Solver by elwell on Wednesday March 26, 2014 @01:49PM (#7475033)