舒煒 劉孝芳

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

關鍵詞：2048游戲；AI；算法；局部最優(yōu)

一、算法要求

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

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

二、算法概要

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

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

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

三、評估函數(shù)

（一）局部最優(yōu)得分算法

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

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

（二）局部最優(yōu)矩陣算法

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

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

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

四、多步評估

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

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

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

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

五、分析與總結

（一）局部最優(yōu)得分算法

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

（二）局部最優(yōu)矩陣算法

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

（三）多步評估

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