淺談2048游戲的簡(jiǎn)單AI算法

舒煒 劉孝芳

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

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

一、算法要求

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

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

二、算法概要

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

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

第二部分是完成對(duì)多步結(jié)果的評(píng)估，然后根據(jù)多步之后的情況選擇當(dāng)前最優(yōu)選項(xiàng)作為行動(dòng)方向。

三、評(píng)估函數(shù)

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

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

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

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

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

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

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

四、多步評(píng)估

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

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

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

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

五、分析與總結(jié)

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

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

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

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

（三）多步評(píng)估

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