Columbia AI Project 2 - 2048 solver

2048怎麼玩？

我還真沒玩過，這是第一次玩：
http://gabrielecirulli.github.io/2048/

Adversarial Search

這也是一個要來練習minimax + alphabeta-pruning的作業。不過這邊比較奇怪的是2048是單人遊戲，哪來的opponent?

作業是要把computer AI扮演丟出新的數字的角色（惡意的，有競爭性的，implement minimax的），所以跟玩家的action是不對稱的。

這是不是一個零和遊戲呢？由於沒有敵人，應該不能算是零和遊戲（沒有你死我活），但是如果對手是丟數字出來的人，那也還不能算是零和遊戲，因為它可以置我於死，我卻不行致他於死。

每次我們的AI只能有0.1秒思考時間，能撐最多ply越高分，就這樣。

演算法 & Heuristics

這作業強調一定要用minimax / alphabeta-pruning，不知道他要怎麼檢查這個項目？
不過因為有0.1秒的思考限制，一定是要有一個heuristics來evaluate目前搜尋深度的state score。

2048的heuristics如果人腦大量玩的話，應該可以看出一些端倪：
1. 大數要在border/corner
2. row/col中數字最好按照順序排列
3. 鼓勵成對排列

其餘輔助的包括：
1. 盡量合成大數字
2. 獎勵空格出現
.
.

另外要注意的是，如果超過時間限制(0.1秒要下子）會搞到棄局，所以在alphabeta pruning的程式碼中需要時時刻刻檢查時間超過了沒，反正使用iterative deepening，至少也能回傳一個move，若真不行，隨便選一個legal move回傳也總比棄局好。

Python runtime does matter!

implementation optimization是很重要，但是在作業中就不是很重要。因為所有的game encoding都是採用一樣的。不過發現在python3執行agent搜尋深度平均約5~6，但是python2大概只有3~4，難怪在python3不錯的效果，在python2卻常掛點，還好這功課可以選擇python runtime版本，不過不知道其他同學有沒有發現這問題？因為作業分數是以能抵達2048幾次的比例做為評分標準，那當然搜尋越深越有利。

最後結果

最後大概花了三天製作出一個agent，成績如下：

Trials with max tile of 2: 0.0 %
Trials with max tile of 4: 0.0 %
Trials with max tile of 8: 0.0 %
Trials with max tile of 16: 0.0 %
Trials with max tile of 32: 0.0 %
Trials with max tile of 64: 0.0 %
Trials with max tile of 128: 4.0 %
Trials with max tile of 256: 0.0 %
Trials with max tile of 512: 12.0 %
Trials with max tile of 1024: 56.0 %
Trials with max tile of 2048: 28.0 %
Trials with max tile of 4096: 0.0 %
Trials with max tile of 8192: 0.0 %
Trials with max tile of 16384: 0.0 %
Trials with max tile of 32768: 0.0 %

根據課程人員表示，過往最高紀錄是能抵達max tile value = 8192！而且理論值（不知道怎麼證明，沒時間去看）也是落在8192 ，這想必有非常好的implementation + better heuristics，我想主要還是implementation，讓搜尋深度比這個普通版本深入不少。

可以看到大概只有1/3時間能達到2048，甚至有少數case會死在128!
很可惜沒時間再鑽研下去，畢竟我付錢的是Udacity！！！（不過也可能付錢買這門課，覺得還不錯，因為edX這門課也是可以組成一個AI micromaster)。

有興趣的人可以來這邊下載玩一下：
https://wang_sonny@bitbucket.org/wang_sonny/2048_solver.git