問題 by nitish712

我最近偶然發(fā)現(xiàn)一款叫2048的游戲。你需要通過上下左右方向鍵來移動合并值相同的方塊(Title)。每一次移動之后，一個值為2或者4的新方塊會隨機出現(xiàn)在某個空位置。如果所有位置都塞滿方塊，并且沒有值相同的方塊可以合并的時候，游戲結(jié)束。游戲的目標是合并出一個值為2048的方塊。

我需要遵循一套定義良好的策略來實現(xiàn)這個目標。所以我想到寫個程序來實現(xiàn)。我當前的算法如下：

我所做的是，在任何時刻，我都嘗試合并值為2或者4的方塊，也就是我會嘗試讓值為2和4的方塊越少越好。如果我嘗試那么做，其它的方塊會自動的合并，看起來像是個好策略。

但是當我真正使用這套算法的時候，我大概只能得到4000分，游戲就結(jié)束了。游戲的最高分應(yīng)該是20000多點，遠超我當前的分數(shù)。有比上面策略更好的算法嗎?

最佳回答 by ovolve

我是AI程序的作者，前面也有人提到AI程序。你可以看AI版游戲，或者直接閱讀源代碼。

當前，這套運行在我筆記本瀏覽器的javascript程序能夠達到90%左右的勝率，每次移動的思考時間是100毫秒。盡管不是最完美，但做得還不賴。

既然這個游戲是一個離散狀態(tài)空間，信息完備的回合制游戲，類似于象棋和國際跳棋，那么我就使用了針對這些游戲的證明過的行之有效的方法。一套叫minimax search的算法，結(jié)合了alpha-beta pruning。既然已經(jīng)有很多信息解釋了這套算法，那么我就僅談?wù)勎以趕tatic evaluation function中使用到的兩個重要概念。這將會把一些人在這里表達的直覺形式化。

單調(diào)性(Monotonicity)

這個概念保證方塊的值沿著上下左右方向的，要么增加，要么減少。這個概念單獨地解釋了一個大家提到的直覺，值較大的方塊應(yīng)該聚集到某一個角落。這將有助于阻止值小的方塊被孤立起來，也將讓面板保持良好的組織結(jié)構(gòu)，使得值小的方塊漸進層疊式的并逐步合并為值大的方塊。

下圖是一個有完美單調(diào)性格子的截屏。我通過運行eval函數(shù)被設(shè)置為忽略其它概念的算法獲得，僅僅考慮單調(diào)性。

平滑性(Smoothness)

上面的概念傾向于構(gòu)造值遞減的結(jié)構(gòu)，但如要合并，相鄰的方格值必須相同。因此，平滑性衡量相鄰方格值的差，并嘗試減少差。

Hacker News上的一個評論者用圖論給出了一個平滑性的有趣解釋。來源于2048的一個優(yōu)秀分支。

下圖是個有完美單平滑性的截屏。