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

許子明

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

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

1 2048游戲簡(jiǎn)介

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

2 自動(dòng)游戲功能的原理

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

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

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

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

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

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

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

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

2.3 游戲最佳移動(dòng)方向的實(shí)現(xiàn)

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

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

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

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

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

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

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