問題 by nitish712

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

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

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

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

最佳回答 by ovolve

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

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

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

單調(diào)性(Monotonicity)

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

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

平滑性(Smoothness)

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

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

下圖是個(gè)有完美單平滑性的截屏。