ovolve

Ahh good catch. That got messed up during refactoring the original code. Thanks to the person who submitted the fix on github too.

I've been messing around trying to find a balance between both of those heuristics. They're both implemented, but there doesn't seem to be any magic bullet.

=)

Check out the eval function, and specifically the function smoothness() in grid.js. It implements the edge weighting you describe!

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 in the fact that sometimes an unpredicted random computer move can mess things up. Unfortunately exhaustively enumerating all possible computer moves was way too slow (for single-threaded javascript in the browser).

Trying every possibility was way too slow (branching factor of ~15 to 20), so it only searches the most "annoying" moves, where annoying is defined by lining up with the highest value tiles and not being adjacent to other 2's (or 4's). The game is random though, so it can and does make moves that haven't been searched.

Random location (uniform). 90% chance of a 2, 10% chance of a 4. This actually made it hard to model the computer move in the search.

Sorry, the code is a little unkempt.

The basic idea is minimax search. Googling that will get you started, but basically the algorithm plays out the game and keeps a score of the position after every move. Then it just makes the move that leads to the best score.

The "score" here is basically a count of how many free squares there are (with a little extra to keep things aligned if possible).

One major thing with these search algorithms is that the game tree grows exponentially as you move forward. To combat that, implemented alpha-beta pruning and a heuristic to only search the nastier computer moves rather than all of the possibilities.