一種2048游戲自動“玩游戲”算法的實現(xiàn)

許子明

摘 要：人工智能是近年來計算機研究的一個熱門領(lǐng)域，2048游戲是風(fēng)靡一時的數(shù)字益智游戲。本文提出一種2048游戲“自動游戲”功能實現(xiàn)。通過設(shè)定局面的評價指標(biāo)得到當(dāng)前局面分?jǐn)?shù)，再通過格局樹搜索和alphabeta剪枝，確定最佳移動方向，通過不斷移動，最終得到數(shù)字2048。

關(guān)鍵詞：人工智能；2048游戲；自動游戲

1 2048游戲簡介

2048游戲是一款數(shù)字益智游戲。游戲背景是在4*4的方格內(nèi)，玩家通過不斷上下左右移動，在16個方格內(nèi)，拼出“2048”數(shù)字方格。游戲的規(guī)則為：游戲開始時隨機出現(xiàn)兩個數(shù)字2的格子，玩家向上下左右一個方向移動，所有數(shù)字格子向該方向靠攏，剩余的空白格子隨機出現(xiàn)一個2或4，相同數(shù)字相撞會合并，然后經(jīng)過不斷的上下左右移動，不斷的合并最終合成2048這個數(shù)字就算成功。

2 自動游戲功能的原理

2.1 數(shù)據(jù)結(jié)構(gòu)

建立二維數(shù)組map[4][4]用來記錄每一個格子的數(shù)字，二維數(shù)組map[i][J]表示第i行第j列格子中的數(shù)字，初始化數(shù)組中所有的格子數(shù)字為0。

2.2 游戲局面評價指標(biāo)與實現(xiàn)

（1）單調(diào)性。單調(diào)性指方塊從左到右、從上到下均遵從遞增或遞減。一般來說，越單調(diào)的格局越好。首先將數(shù)組map中的每一項取以2為底的對數(shù)。先計算橫向的單調(diào)性，即每一行的單調(diào)性。首先從每一行的第一列的數(shù)字開始（map[i][J]），向后尋找最近第一個非零數(shù)字map[i][jj]，然后判斷兩個數(shù)的大小，用小的數(shù)字減去大的數(shù)字，并記錄結(jié)果，然后將jj的值賦給j（跳過其中的空白格子），向后尋找非零數(shù)字格子，用小的減去大的，將結(jié)果相加保存。依次計算第一到第四行的所有結(jié)果。縱向計算單調(diào)性與橫向類似，即計算每一列的單調(diào)性。

（2）平滑性。平滑性是指每個方塊與其直接相鄰方塊數(shù)值的差，其中差越小越平滑，一般認為越平滑的格局越好。同樣將數(shù)組map中的每一項取以2為底的對數(shù)。然后遍歷數(shù)組map中每一個格子，如果map[i][J]為零，則跳過循環(huán)繼續(xù)下一次。如果map[i][J]不為零，則向下、右尋找最近的非空格子map[i][jj]和map[ii][J]，計算map[i][J]和向下和向右非空格子數(shù)字相減的絕對值，并記錄。

（3）最大值。最大值即所有數(shù)字格子中數(shù)值最大的數(shù)值，通過遍歷數(shù)組map，比較大小即可得到。

（4）空格子數(shù)目。即為16個方格中沒有數(shù)字的方格的數(shù)目，通過遍歷二維數(shù)組map，并記錄其中數(shù)字為0的格子的數(shù)目。

（5）局面得分。將上述四個指標(biāo)分別計算后，再乘以各指標(biāo)對應(yīng)的不同權(quán)值，作為當(dāng)前局面的得分。

2.3 游戲最佳移動方向的實現(xiàn)

確定最佳移動方向的算法采取格局樹，max節(jié)點表示游戲玩家，min節(jié)點表示電腦，在隨機空白位置出現(xiàn)2或4。在樹中采用ab（alphabeta）剪枝，a表示搜索到當(dāng)前節(jié)點時已知最好選擇的下界，即max節(jié)點可以做出的最好選擇，b表示從這個節(jié)點往下搜索最壞結(jié)局的上界，即min節(jié)點可做出的最好選擇（max節(jié)點為最壞選擇）。當(dāng)b小于a時會進行剪枝，表示從此處開始不論最終結(jié)局是哪一個，其上限價值也要低于已知的最優(yōu)解，也就是說已經(jīng)不可能此處向下找到更好的解，則回溯到父節(jié)點繼續(xù)搜索。

在max節(jié)點搜索中，分為葉結(jié)點和非葉結(jié)點的處理方法。

對于葉結(jié)點，即當(dāng)前搜索深度大于等于最深搜索深度時，遍歷上下左右，然后計算移動后各局面分?jǐn)?shù)。如果計算出的分?jǐn)?shù)大于a，即當(dāng)前最好選擇大于傳入的最好選擇的值，則把分?jǐn)?shù)的值賦給a，并修改最佳移動方向。再選擇下一個方向進行移動后計算分?jǐn)?shù)，四個方向遍歷完畢后，記錄最佳方向，并將最好的a、b的值返回。

對于非葉結(jié)點，上下左右遍歷后，再向下對min節(jié)點搜索，將搜索得到的a、b的值記錄。如果min節(jié)點b大于父節(jié)點a，則將min節(jié)點b賦給父節(jié)點的a，說明電腦做出最好選擇的分?jǐn)?shù)大于當(dāng)前可做出的最好選擇，則更新最好選擇的值，并修改最佳移動方向。最后再判斷a>=b，若成立，則如果向這個方向移動，則min節(jié)點做出最壞選擇，由此向下移動的局面分?jǐn)?shù)不會超過b，即不會超過已有最好選擇，則進行剪枝，不再向下計算，跳出循環(huán)，將最佳方向和a、b的值返回。若不成立，再選擇下一個方向移動計算分?jǐn)?shù)，四個方向遍歷后，記錄最佳方向，將最好的a、b的值返回。

在min節(jié)點搜索中，在每一個空格子中賦值2，即考慮電腦隨機在空白格子出2的情況（本算法中只考慮最差位置出2的情況）。賦值之后，再向下搜索max節(jié)點，搜索最佳移動方向。如果向下搜素的a小于b，則說明min節(jié)點可以做出更差的選擇，將a賦給b，更新b的值。更新b的值后，再判斷a>=b，若成立，則剪枝并返回當(dāng)前a、b，否則的話，將賦值2的格子恢復(fù)為零，再將數(shù)字2賦給下一個空白格子，尋找使當(dāng)前局面變得最差時的局面（即電腦完美出現(xiàn)2）。最后經(jīng)過深度搜索、計算、遞歸后，決定最佳移動方向。

3 自動游戲算法結(jié)果統(tǒng)計

分析：該算法基本上能使得2048及以上數(shù)字的概率在65%以上，當(dāng)單調(diào)性所分配的權(quán)值為1.5時，合成2048及以上數(shù)字的概率達到70%。通過不斷的調(diào)整各評價指標(biāo)所占的權(quán)值，可以提高合成2048及以上數(shù)字的概率。