問題 by nitish712

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

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

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

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

最佳回答 by ovolve

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

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

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

單調性(Monotonicity)

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

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

平滑性(Smoothness)

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

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

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

空閑方塊(Free Tiles)

最后，有一個針對空閑格子過少的懲罰。畢竟面板過于擁擠的時候，選擇受限且很快會被用完。

就是這樣。掃描游戲格子，同時優(yōu)化以上標準，這會產生相當好的表現(xiàn)。與明確硬編碼的移動策略相比，這種使用通用性的方法有一個優(yōu)點，這種算法可以找到有趣且難以預料的解決方案。如果你觀察它運行，它經常會做出一些驚奇但有效的移動，比如突然轉向一個相反的墻或者角落。

修改

這是該方法強大能力的一個展示。我拿掉了方格值大小的限制(到2048之后還可以繼續(xù)運行，下圖是8次嘗試中最好一次的截屏，是的，那可是一個4096外加一個2048)，那意味著在同一個面板上它完成了3次困難的2048方塊。