nneonneo/2048-ai — pull request #27 by xificurk (2014-06-07 07:15:36+00:00)
Title: Improved algorithm reaching 32k tile

This PR improves the algorithm, so that it consistently reaches 32k tile. Here (https://www.dropbox.com/s/9463l6ztznj3zy0/2048.png) is a "Game over" screenshot of one of the best games I've seen it play.

First there are couple of minor code tweaks. I have also moved caching and search termination code to `score_tilechoose_node` method. Imho, it makes more sense to use it after player's deterministic move, instead of after random computer move, although the benchmarking I tried did not show significant improvements. The two most important commits are **new heuristic scoring** and **adaptive search depth limit**.

**New heuristic scoring**

It uses a combination of three factors - number of empty tiles, number of available merge moves and monotonicity of the row/column.
An empty tile is in fact as important as the ability to create it by merging tiles of the same value.
The monotonicity of the row/column enforces generally good position for building up higher and higher tiles. Look at the code for more details, it's pretty self-explanatory. The calculation uses third powers of tile values, so that higher tiles get more severe penalty if they are moved in the middle of the board.

**Adaptive search depth limit**

This gives a huge speed boost, especially early in the game. The idea is that you need to search the game tree really deep only if the board gets complicated. A good measure of the board complexity is the number of distinct tiles. With this patch AI alternates between extremely fast segments (right after it builds the a highest tile) and slow segments (right before it builds a new highest tile).
I've measured a time it took to get to a certain tile for the original algorithm and the new one, here is how much time this patch saves:
2k: 50%
4k: 45%
8k: 30%
16k: 5%
As you can see, the time to reach winning 2k tile was cut in half and it stays faster roughly up to a point when it builds 16k tile.

**Benchmark results**

I've run a benchmark to measure the improvements. With 229 runs, it always got to 4k tile with lowest score 76,376 and highest 720,668 averaging at 336,030. And here is an overview of the maximum rank reached:
4k: 100%
8k: 99%
16k: 78%
32k: 10%

There is ceratinly a room for tweaking the code, but I doubt it will be possible to get another significant improvement while keeping the computational cost at a sane level.