淺談2048游戲的簡單AI算法

舒煒 劉孝芳

摘 要：2048游戲曾經風靡一時，游戲簡單但富有挑戰性。這篇文章主要講述了2048游戲的AI實現，在不進行人為干預的情況下取得游戲勝利。文章詳細討論了該游戲的評估函數和多步分析，并在最終對該算法進行了一些深入性的分析。

關鍵詞：2048游戲；AI；算法；局部最優

一、算法要求

2048游戲規則極其簡單，給定一個44的矩陣，玩家控制矩陣中數字的整體移動方向，電腦則會隨機在一個空格中生成2或者4，在移動過程中，相同的數字相撞會合并成兩數之和，如果有數字超過2048則為游戲勝利，而如果矩陣被填滿，并且矩陣中的最大值沒有達到2048時，則游戲失敗。

我們此次需要完成的是2048游戲的AI，即只通過算法進行方向移動，在不經過任何人為干預的情況下獲取游戲勝利。算法優劣的評判標準有三個：一是游戲勝率評估，即超過2048的概率要盡可能大；二是最高分評估，即游戲中所獲取的最大值要盡可能大；三是等待時間，即每步之間等待時間不能過長。

二、算法概要

此次主要研究的是2048的AI實現，該AI算法主要分為兩個部分。

第一部分是評估函數，確定局部最優情況，最終確定的評估函數算法有兩種：一是局部進行評分的算法，在此稱為局部最優得分算法；一是盡量貼近最優情況陣型的算法，稱為局部最優矩陣算法。

第二部分是完成對多步結果的評估，然后根據多步之后的情況選擇當前最優選項作為行動方向。

三、評估函數

（一）局部最優得分算法

對上下左右四個方向產生的結果進行評估，評估方式為建立多個子算法加權得分，而得分最高的方向即為當前行動的最佳方向，下一步向該方向移動，為局部最優策略。由于不同子算法之間評判標準的不同，可能出現相互干擾，甚至相互對立的情況，同時不同時期受到的影響也可能不同，所以我們需要通過調整數字權重以及子算法權重完成優化，找到較好的評判標準，提高勝率。

可參考的評估子算法：可以檢測邊角值，進行加權求和，數值越大說明大數在邊角，更易合并取得更高的分數；檢測所有數值的周圍數值的情況，差距越小時兩者更易進行合并；檢測矩陣中最大值，最大值直接反映游戲情況；檢測空格數，空格數越多，就有更大機會成功。

（二）局部最優矩陣算法

與局部最優得分算法不同，局部最優矩陣算法是將地圖矩陣看著一個整體，尋找到適合的陣型，而不是按具體評分標準進行判斷。目前找到的已知的幾種最佳合并陣型，將其作為地圖的初始權重矩陣，對數字也設置權重，將兩者在對應位置的乘積之和作為評判標準，如果在此方向合并后結果評判最優，下一步則向該方向移動。

我們找到來三種比較優秀的陣型進行測試：一是較為常見的蛇形S陣型，這是人類的常見高分策略，也是最易得到的矩陣情況，矩陣優先級為[1，2，3，4，8，7，6，5，9，10，11，12，16，15，14，13]；二是SPD陣型，這種陣型是根據高分算法總結得到的電腦合并矩陣，使矩陣偏向于向某一角進行合并，矩陣優先級為[16，15，12，4，14，13，11，3，10，9，8，2，7，6，5，1]；三是ZSL陣型，與SPD矩陣略有不同，但仍保留向單一角落合并的傾向，矩陣的優先級為[16，15，14，4，13，12，11，3，10，9，8，2，7，6，5，1]。

當前算法在三種優先級權重陣型對應加權作用下，會自然表現出選擇最適合當前局面的陣型進行游戲的行為。當然由于在游戲中沒有固定方向，所以必須考慮權重矩陣對稱和旋轉的情況。

四、多步評估

事實上，僅僅靠著優秀的評估函數，游戲AI就可以初步完成，最終獲取一定的游戲勝率。但由于游戲過程中會隨機生成2和4，局部最優往往不是全局最優，所以我們無法保證隨機生成的數字會不會使當前情況變糟。

如果將2048游戲看成兩個人的博弈，玩家會選擇向某一方向移動來使游戲獲取更高的分數，而作為玩家對手的電腦則會選擇隨機生成一個數字來影響我的選擇。我們無法判斷對手的好壞，所以玩家在當前情況下冒著極大風險選擇的獲取最高分數的方向，可能沒有影響，但也可能因為對手的妙手而萬劫不復，所以游戲獲勝的最佳策略是將對手看的極其聰明，即假設電腦每一步生成的數字都是最壞的情況來保證目前選擇不會變得更糟糕，而玩家選擇的策略不應利益最大，而是以不會出現意外為主。

通過以上分析，我們得到以下思路：利用四叉樹來分析多步之后的情況，四叉樹的每一枝代表當前游戲的一個方向，每一層代表一步操作，同時需要修剪風險高于利益，使得當前情況變得糟糕的枝干，簡化計算的同時保持較高的勝率，而當前最佳移動方向即是在完成枝干修剪后分數最大的枝干代表的方向。

算法的具體實現可參考的有Minimax算法和Alpha-beta剪枝。Minimax算法是一種悲觀算法，即每步都假設對方選擇最優的情況下，己方進行選擇；而Alpha-beta剪枝則可以簡化計算量，大體思路為我們不需要構建完整的樹，其中當前格局無法找到最好情況下，我們應該返回父節點，而舍棄當前節點。兩者的結合可以完成2048游戲的多步分析，使勝率達到較高水平。

五、分析與總結

（一）局部最優得分算法

在此次游戲的局部評分算法的研究中，簡單的評分子算法比較容易實現，如查找最大值之類算法花費時間并不算太多，各個獨立算法實現較為簡單。問題主要出在權重配比的方面，多個子算法之間相互干擾，并且不同時期的比重也會有所不同，所以調節較為困難。

（二）局部最優矩陣算法

與局部最優得分算法相比，只看整體的局部最優矩陣算法在權重調整方面更顯優勢，但卻更缺乏靈活性，只向特定的陣型傾斜代表著必然忽略不少優秀的情況，導致在中途的適應性比不上局部最優得分算法，較為死板，但勝在調試簡單，計算相對偏少，評估表現較為優秀，配合上多步評估可以取得十分不錯的結果。

（三）多步評估

如果只需要實現簡單的AI，那么使用局部最優的策略就可以完成，但要進一步提升勝率，就必須考慮通過四叉樹來預判多步之后的情況。不過因為游戲中是隨機在空格中生成數字，所以簡單的四叉樹的遍歷效果會大打折扣，故需要考慮風險與收益的情況，從而剪去高風險的枝葉。整個過程是依次遞進，總體思路較為清晰，實現不算困難。