2048 Hard

Modification for the game 2048, where instead of a random generator the computer will chose the worst possible place to put the 2s and 4s.

See it in action here. (Hit the auto-run button to let the AI attempt to play against himself and fail miserably)

The algorithm used is the same as in the 2048-AI, but when determining where to put the 2s and 4s, the computer will also run the algorithm to find the worst place to put it for you.

The difficulty settings just determines the frequency of an AI step, instead of a random step. Easy is 0% (essentially the same as the original game), Medium is 25%, Hard is 50%, and Impossible is 100%.

The following is the readme from the 2048-AI. Don't believe it, it cannot usually earn more then the 128 tile in impossible mode.

2048 AI

The algorithm is iterative deepening depth first alpha-beta search. The evaluation function tries to keep the rows and columns monotonic (either all decreasing or increasing) while aligning same-valued tiles and minimizing the number of tiles on the grid. For more detail on how it works, check out my answer on stackoverflow.

You can tweak the thinking time via global var animationDelay. Higher = more time/deeper search.

The better heuristics now give it a success rate of about 90% in my testing (on a reasonably fast computer).

Suggested Improvements

1. Caching. It's not really taking advantage of the iterative deepening yet, as it doesn't remember the move orderings from previous iterations. Consequently, there aren't very many alpha-beta cutoffs. With caching, I think the tree could get pruned much more. This would also allow a higher branching factor for computer moves, which would help a lot because I think the few losses are due to unexpected random computer moves that had been pruned.

2. Put the search in a webworker. Parallelizing minimax is really hard, but just running it like normal in another thread would let the animations run more smoothly.

3. Comments and cleanup. It's pretty hacky right now but I've spent too much time already. There are probably lots of low-hanging fruit optimizations.