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.
Seems like a great application for Monte Carlo tree search.
Check my AI for 2048
https://news.ycombinator.com/item?id=7474909
Only reach 8192, but with the game implemented in the right way :)
Show us your better solution! Thanks!
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."